Вопросы Теги

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

Решение

Это работает:

find. -execdir sh \;

Демо 

# Create some sample directories
$ for i in {1..4}; do mkdir -p "/tmp/example/$i/foo" ; done

# spawn
$ find -s /tmp/example -name foo -execdir sh \;
sh-3.2$ pwd
/private/tmp/example/1
sh-3.2$ exit
sh-3.2$ pwd
/private/tmp/example/2
sh-3.2$ exit
sh-3.2$ pwd
/private/tmp/example/3
sh-3.2$ exit
sh-3.2$ pwd
/private/tmp/example/4
sh-3.2$ exit
$

Как это работает

найти

Соответствующая информация на справочной странице и/или другая информация:

-s:Заставить find перемещаться по файловым иерархиям в лексикографическом порядке, т. е. в алфавитном порядке внутри каждого каталога. Это не критично для решения, но делает порядок оболочек предсказуемым.

/tmp/example:Аргумент пути. Утилита find рекурсивно спускается по дереву каталогов для каждого указанного пути.

-name pattern:Соответствует файлам, если последний компонент проверяемого пути соответствует шаблону. Специальные символы соответствия шаблону оболочки(['',]'', *'', and?'' )могут использоваться как часть шаблона.

-execdir utility \;:Первичный каталог -execdir идентичен первичному каталогу -exec, за исключением того, что утилита будет выполняться из каталога, содержащего текущий файл.

ш

sh:Запуск shв этом контексте запускает интерактивную оболочку из каталога, содержащего текущий файл.

23
12.04.2020, 22:46
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

Вы можете сделать это быстрее, указав сортировке использовать больше ядер:

$ 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параметры и чтение со стандартного ввода(parsort -k2rn < bigfile).

44
19.03.2021, 02:30

Теги

Похожие вопросы