☰

RAM に収まる大きなファイルの「ソート」を高速化するために「並列」を使用するにはどうすればよいでしょうか?

tag-icon • tag-icon bash performance sort multithreading
RAM に収まる大きなファイルの「ソート」を高速化するために「並列」を使用するにはどうすればよいでしょうか?

GNU/Linux システムの RAM に収まる 100 MB 行のファイルがあります。

これはかなり遅いです:

sort bigfile > bigfile.sorted

私のマシン上の 48 個のコアすべてを使用するわけではありません。

ファイルを高速に並べ替えるにはどうすればいいでしょうか?

答え1

48 個のコア、500 GB の空き RAM、ファイルが 1 億行でメモリに収まると仮定します。

通常のソートを使用すると、かなり遅くなります。

$ time sort bigfile > bigfile.sort
real    4m48.664s
user    21m15.259s
sys     0m42.184s

ロケールを無視することで、少し高速化できます。

$ export LC_ALL=C
$ time sort bigfile > bigfile.sort
real    1m51.957s
user    6m2.053s
sys     0m42.524s

sort により多くのコアを使用するように指示することで、処理を高速化できます。

$ export LC_ALL=C
$ time sort --parallel=48 bigfile > bigfile.sort
real    1m39.977s
user    15m32.202s
sys     1m1.336s

また、sort にさらに作業メモリを追加することもできます (sort にすでに十分なメモリがある場合は役に立ちません)。

$ export LC_ALL=C
$ time sort --buffer-size=80% --parallel=48 bigfile > bigfile.sort
real    1m39.779s
user    14m31.033s
sys     1m0.304s

しかし、sort はシングルスレッドを多用する傾向があるようです。次のようにして、並列化を強制することができます。

$ merge() {
    if [ $1 -le 1 ] ; then
        parallel -Xj1 -n2 --dr 'sort -m <({=uq=}) | mbuffer -m 30M;'
    else
        parallel -Xj1 -n2 --dr 'sort -m <({=uq=}) | mbuffer -m 30M;' |
          merge $(( $1/2 ));
    fi
  }
# Generate commands that will read blocks of bigfile and sort those
# This only builds the command - it does not run anything
$ parallel --pipepart -a bigfile --block -1 --dr -vv sort |
    # Merge these commands 2 by 2 until only one is left
    # This only builds the command - it does not run anything
    merge $(parallel --number-of-threads) |
    # Execute the command
    # This runs the command built in the previous step
    bash > bigfile.sort
real    0m30.906s
user    0m21.963s
sys     0m28.870s

ファイルをオンザフライで 48 個のブロックに分割し (コアごとに 1 ブロック)、それらのブロックを並列にソートします。次に、それらのペアのマージ ソートを実行します。次に、それらのペアのマージ ソートを実行します。次に、それらのペアのマージ ソートを実行します。次に、それらのペアのマージ ソートを実行します。次に、それらのペアのマージ ソートを実行します。次に、それらのペアのマージ ソートを実行します。入力が 1 つになるまで、これを繰り返します。可能な場合は、これらすべてを並列に実行します。

4 G ラインの 100 GB ファイルの場合、タイミングは次のようになります。

$ LC_ALL=C time sort --parallel=48 -S 80% --compress-program pzstd bigfile >/dev/null
real    77m22.255s
$ LC_ALL=C time parsort bigfile >/dev/null
649.49user 727.04system 18:10.37elapsed 126%CPU (0avgtext+0avgdata 32896maxresident)k

したがって、並列化を使用すると速度が約 4 倍向上します。

使いやすくするために、これを小さなツールにしました。parsortこれは現在、GNU Parallel の一部になっています。

sortオプションと標準入力からの読み取りもサポートしています( parsort -k2rn < bigfile)。

関連情報