☰

Как использовать «параллельную» обработку для ускорения «сортировки» больших файлов, помещающихся в ОЗУ?

tag-icon • tag-icon bash performance sort multithreading
Как использовать «параллельную» обработку для ускорения «сортировки» больших файлов, помещающихся в ОЗУ?

У меня есть файл размером 100 Мб, который помещается в ОЗУ на системе GNU/Linux.

Это довольно медленно:

sort bigfile > bigfile.sorted

и не использует все 48 ядер на моем компьютере.

Как быстро отсортировать этот файл?

решение1

Предположим, у вас 48 ядер, 500 ГБ свободной оперативной памяти, а файл имеет размер 100 млн строк и помещается в память.

Если использовать обычную сортировку, то она довольно медленная:

$ 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 блоков на лету (по одному блоку на ядро), сортирует эти блоки параллельно. Затем мы делаем сортировку слиянием пары из них. Затем мы делаем сортировку слиянием пары из них. Затем мы делаем сортировку слиянием пары из них. Затем мы делаем сортировку слиянием пары из них. Затем мы делаем сортировку слиянием пары из них. И так далее, пока у нас не останется только один вход. Все это выполняется параллельно, когда это возможно.

Для файла размером 100 ГБ с 4 G строками тайминги следующие:

$ 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параметры и чтение из stdin ( parsort -k2rn < bigfile).

Связанный контент