如何使用“并行”来加速适合 RAM 的大文件的“排序”？

Question

我有一个 100 M 行的文件，它适合 GNU/Linux 系统上的 RAM。

这是相当慢的：

sort bigfile > bigfile.sorted

并且没有在我的机器上使用所有 48 个内核。

如何快速对该文件进行排序？

Answer 1

让我们假设您有 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

但似乎 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 个块（每个内核一个块），并行对这些块进行排序。然后我们对其中的一对进行合并。然后我们对其中的一对进行合并。然后我们对其中的一对进行合并。然后我们对其中的一对进行合并。然后我们对其中的一对进行合并。依此类推，直到我们只有一个输入。在可能的情况下，所有这些都是并行完成的。

对于具有 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)。