☰

RAM内の大容量ファイルの「並べ替え」を高速化するために「並列性」を使用する方法は？

tag-icon • tag-icon bash performance sort multithreading
RAM内の大容量ファイルの「並べ替え」を高速化するために「並列性」を使用する方法は？

GNU / LinuxシステムのRAMに適した100Mラインファイルがあります。

これは非常に遅いです。

sort bigfile > bigfile.sorted

そして、私のコンピュータでは48コアすべてが使用されていません。

このファイルをすばやく並べ替えるにはどうすればよいですか？

答え1

48コア、500GBの使用可能な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

より多くのコアを使用するように指定することで、ソート速度を速くすることができます。

$ 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

しかし、単一のスレッドをたくさん実行するのが好きなようです。以下を使用すると、強制的にさらに並列化することができます。

$ 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つをマージソートします。次に、ペアの1つをマージソートします。次に、ペアの1つをマージソートします。次に、ペアの1つをマージソートします。次に、ペアの1つをマージソートします。入力が 1 つしかないまで続きます。可能であれば、これはすべて並列に行われます。

4G行の100GBファイルの場合、時間は次のとおりです。

$ 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。

関連情報