如何使用「並行」來加快RAM中大檔案的「排序」速度？

Question

假設您有 48 個核心、500 GB 可用 RAM，檔案有 100 M 行並且適合記憶體。

如果你使用普通排序，它會相當慢：

$ 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

但看起來確實很喜歡做很多單線程。您可以透過以下方式強制它更多地並行化：

$ 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 個區塊（每個核心一個區塊），並對這些區塊進行並行排序。然後我們將其中的一對進行合併排序。然後我們將其中的一對進行合併排序。然後我們將其中的一對進行合併排序。然後我們將其中的一對進行合併排序。然後我們將其中的一對進行合併排序。依此類推，直到我們只有一個輸入。如果可能的話，所有這些都是並行完成的。

對於具有 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）。

Answer 1