☰

Como usar "paralelo" para acelerar a "classificação" de arquivos grandes que cabem na RAM?

tag-icon • tag-icon bash performance sort multithreading
Como usar "paralelo" para acelerar a "classificação" de arquivos grandes que cabem na RAM?

Eu tenho um arquivo de linha de 100 M que cabe na RAM de um sistema GNU/Linux.

Isso é bastante lento:

sort bigfile > bigfile.sorted

e não usa todos os 48 núcleos da minha máquina.

Como classifico esse arquivo rapidamente?

Responder1

Suponhamos que você tenha 48 núcleos, 500 GB de RAM livre e o arquivo tenha 100 M de linhas e caiba na memória.

Se você usar a classificação normal, será bastante lento:

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

Você pode tornar isso um pouco mais rápido ignorando sua localidade:

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

Você pode tornar isso mais rápido dizendo ao sort para usar mais núcleos:

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

Você também pode tentar fornecer mais memória de trabalho ao sort (isso não ajuda se o sort já tiver memória suficiente):

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

Mas parece que o tipo realmente gosta de fazer muitos threads únicos. Você pode forçá-lo a paralelizar mais com:

$ 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

Ele divide o arquivo em 48 blocos dinamicamente (um bloco por núcleo) e classifica esses blocos em paralelo. Então fazemos uma espécie de fusão de um par desses. Então fazemos uma espécie de fusão de um par desses. Então fazemos uma espécie de fusão de um par desses. Então fazemos uma espécie de fusão de um par desses. Então fazemos uma espécie de fusão de um par desses. E assim por diante, até termos apenas uma entrada. Tudo isso é feito em paralelo quando possível.

Para um arquivo de 100 GB com linhas 4G os tempos são:

$ 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

Portanto, usar a paralelização acelera em torno de um fator de 4.

Para facilitar o uso, transformei-o em uma pequena ferramenta: parsortque agora faz parte do GNU Parallel.

Ele também suporta sortopções e leitura de stdin ( parsort -k2rn < bigfile).

informação relacionada