GNU sort を並列で置き換える CLI ツール「xort」を Rust で作った

TL;DR

• xort は Unix の sort コマンドのドロップイン置き換えを目指した CLI ツールです。Rust 製。
• ripgrep が grep に、fd が find に対してやったことを、sort に対してやろうとしています。
• デフォルトで並列・バイト比較デフォルト（LC_ALL=C 相当）で、GNU sort よりだいたい 1.7〜2.4 倍速い。整数の -n は radix の高速パスで 約 2.5 倍。
• -n -k -t -u -r -s -c -m -h -V -M -g などおなじみのフラグはそのまま使えて、出力は LC_ALL=C sort とバイト一致（GNU と 155 ケースで差分テスト済み）。
• そのうえで GNU にはない --top / --count / --header / CSV・JSON 対応 / gzip・zstd 透過展開を足しています。

cargo install xort

リポジトリ: OTL/xort - GitHub

なぜ作ったのか

sort は地味だけど、ログ解析やデータ前処理でめちゃくちゃ使うコマンドです。それなのに GNU sort は性能面でけっこう取りこぼしがあります。

• 歴史的にシングルスレッド（--parallel はあるが限定的）。
• C 以外のロケールだと Unicode 照合のコストが重い。気づかないうちに UTF-8 ロケールで遅いソートを回している人は多いはず。

一方で、いまどきのマシンはコアが余っています。「全コア使って、予測可能な順序で、速くソートする」ツールがあっていいはずだ、というのが出発点でした。

xort のデフォルトの順序はバイト比較（LC_ALL=C sort と同じ意味）です。これは速いだけでなく「環境のロケールで結果が変わらない」という意味でも嬉しい。ロケール依存の照合が必要な場面では従来の sort を使ってください。

インストールと基本的な使い方

cargo install xort       # crates.io から
cargo install --path .   # チェックアウトしたディレクトリから

使い方は基本 sort と同じです。引数なしなら stdin を読みます。

xort -n data.txt              # 数値ソート
xort -u names.txt             # ソートして重複除去
xort -t: -k3,3n /etc/passwd   # 3 番目の : 区切りフィールドを数値でソート
xort -n -S 256M huge.txt      # RAM に乗らない入力は外部マージソートで

既存のシェルスクリプトの sort を xort に置き換えても、（LC_ALL=C 相当の挙動でよければ）そのまま動くことを目標にしています。

ベンチマーク

hyperfine で GNU coreutils sort 9.4 と比較しました。フェアにするため、両者とも LC_ALL=C・全コア使用で測定しています。GNU が UTF-8 ロケールでさらに遅くなる分は、あえて利用していません。出力は GNU とバイト一致を確認済みです。

インメモリのソート（10M 整数 / 小数、8M 行テキスト、4 コア）:

ワークロード（入力）	GNU sort	xort	倍率
数値, 10M 整数 (-n)	4.81 s	2.03 s	2.37×
浮動小数, 10M 小数 (-n)	4.92 s	2.32 s	2.12×
テキスト, 8M 行	2.15 s	1.23 s	1.74×
ユニークなテキスト, 8M 行 (-u)	2.54 s	1.54 s	1.65×
Top-100, 10M 整数 (--top 100)	2.12 s	0.64 s	3.33×

この傾向は 入力サイズ（1M〜100M） や データ分布（一様 / ソート済み / 逆順 / ほぼソート済み / 低カーディナリティ）を変えても崩れません。xort は 1→4 コアで約 2.4× スケールします。

ベンチは環境差が大きいので、数字は「自分の環境で」確認するのがおすすめです。scripts/benchmark.sh（QUICK=1 で短時間版）で再現できるようにしてあります。

GNU sort にできないこと

ここが xort を作っていて一番楽しい部分です。互換性を保ちつつ、「あったら便利」を足しました。

--top N — sort | head より圧倒的に安い

上位 N 件だけ欲しいとき、sort | head は全件をソートしてから捨てます。--top は**有界の選択（bounded selection）**で済むので、フルソートが要りません。

xort -n --top 10 metrics.txt    # 小さい順に 10 件
du -b * | xort -n --top 5       # でかいファイル上位 5 件

上の表のとおり、10M 整数の Top-100 で 3.33× 差がつきます。

--count — sort | uniq -c 内蔵

xort --count access.log

定番イディオムの sort | uniq -c を 1 コマンドで。

--header — ヘッダ行を固定してソート

xort --csv --header -k age -n people.csv

CSV の 1 行目をヘッダとして先頭に固定したまま、残りをソートします。

構造化データ（CSV / TSV / JSON / JSONL）

クォート対応の CSV/TSV を列名 or 列番号でソートできます。JSON 配列 / JSONL は .path.to.field でフィールド指定。

cat events.jsonl | xort --jsonl -k .ts    # .ts フィールドでソート

JSONL のフィールドソートは jq -s 'sort_by(…)' より速く出ます。

gzip / zstd の透過展開

入力の圧縮はマジックバイトで自動判定（ファイル名が合っていなくても、stdin でも OK）、出力は -o の拡張子で圧縮します。gzip / zstd へのパイプは不要。

xort -n big.txt.gz -o sorted.zst    # gzip で入って zstd で出る

日付ソート

xort --date-sort access.log         # ISO-8601 / Unix epoch / Apache・syslog ログ
xort -k1,1D --progress events.tsv   # フィールド 1 を日付キーに、プログレスバー付き

そのほか --color（ソートキーのハイライト）、--progress、--stats、--completions、--man といった UX 周りも入れています。

実装メモ

効いている工夫を 3 つだけ。

1. 整数 -n の radix 高速パス

グローバルな数値ソート（-n）で、全行の値がぴったり i64 に収まるときは、比較ソートの代わりに stable LSD radix sort に切り替えます。

10M 整数（4 コア, LC_ALL=C）で -n が 3.41 s → 2.46 s（広レンジ）、2.39 s → 1.77 s（低カーディナリティ）。xort 自身の比較パスより 約 1.4×、GNU sort -n より 約 2.5× 速い。

出力は GNU とバイト一致を維持しています（値の順序、同値時の行全体タイブレーク、+ を GNU 同様「非数値」として扱う、など）。小数が混じったり i64 の範囲を超える値が出たら、透過的に任意精度の比較パスへフォールバックします。「速いけど壊れる」では意味がないので。

2. フィールドキーは decorate-sort-undecorate

-k / -t のフィールドキーソートは、比較のたびにキーを切り出すのではなく、最初に全行のキーを一度だけ抽出してからソートします（いわゆる Schwartzian transform）。

単一キーは GNU sort -k より 約 1.8×。複数キー（例 -k2,2 -k3,3n）は GNU とほぼ同等まで来ました（以前は 1.3× 遅かった）。レコードごとに複数の事前計算キーを辿る分、パースコストとキャッシュミスのトレードオフになります。このへんは正直に書いておきます。

3. RAM を超える入力（-S）も並列マージ

-S の外部マージソートは、各チャンクを並列にソートしてからマージします。同じバジェットの sort -S に対して 10M 整数で約 1.3× 速い。

互換性とテスト

「速い」より先に「正しい」が大事なので、そこは差分テストで担保しています。

• デフォルト順序はバイト比較なので、出力は LC_ALL=C sort に一致。
• scripts/difftest.sh が、ランダムな単語・数値入力とフラグの組み合わせで xort を GNU sort と突き合わせます（155 ケース）。

cargo test --all
cargo clippy --all-targets -- -D warnings
bash scripts/difftest.sh    # GNU sort との差分テスト（要 `sort`）

まとめ

• xort は GNU sort のドロップイン置き換え＋並列デフォルト＋便利フラグ追加を狙った Rust 製 CLI です。
• 既存スクリプトに混ぜても壊れないよう、GNU との差分テストで互換性を担保しています。
• --top / --count / 構造化データ / 圧縮透過あたりは、日々のログ解析でそこそこ効くはず。
• ちなみにこの記事含めて全部Claudeで作りました。

ライセンスは MIT です。Issue・PR・ベンチ報告、歓迎します。

OTL/xort - GitHub