[Перевод] Сортировка целых чисел при нехватке памяти
Автор оригинала на английском языке — хабраюзер dzeban
Введение
В прошлый раз мы обсудили, как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе libmemrestrict — библиотеку с обёртками функций вроде malloc для отслеживания использования памяти, и ptrace-restrict — инструмент на базе ptrace, перехватывающий вызовы brk, sbrk и mmap с той же целью.
Так зачем нам пытаться организовывать ограничение памяти — так ли это часто встречается? Когда в последний раз ООМ прибил ваше приложение? Вы всегда думаете о потреблении памяти во время программирования? Память — штука дешёвая, и если вам не хватает памяти, добавьте ещё пару гигабайт.
И, тем не менее, невозможно бесконечно добавлять память — и не из-за того, что у вас нет бесконечного её источника. При обработке Больших данных просто невозможно вместить весь ввод в массив — необходимо распределять данные между оперативкой, носителями и сетью. Необходимы алгоритмы и техники для такой обработки данных.
И вот я занялся подобными задачами, начав с простой — как отсортировать миллион целых чисел (4 MiB данных) при наличии 2 MiB памяти? Эту задачу можно обобщить на тот случай, когда у вас недостаточно памяти, чтобы вместить все данные.
Дано
Необходимо написать программу сортировки набора целых чисел, хранящихся в файле. Для его создания я написал простейшие утилиты randints и rangeints
Программа должна выдавать отсортированный массив на stdout в виде текста
Она должна измерить время работы и вывести его на stderr. Нельзя просто запустить программу через утилиту time, потому что она посчитает время на чтение файла и время на его вывод.
Она должна работать, имея памяти как минимум в два раза меньше объёма файла. Для этого мы применим libmemrestrict или ptrace-restrict.
Для некоторых методов эти утилиты не пригодятся. Например, для mmap они не сработают — придётся физически ограничить использование памяти.
Они будут проверяться для решения оригинальной задачи (сортировки 4 MiB в 2 MiB). Также я запущу их на виртуалке со 128 MiB памяти для сортировки 500 Mb (125 миллионов четырёхбайтных целых).
Наивный подход
Попробуем отсортировать числа напрямую и подсчитаем использование памяти (и время). Просто считаем файл в массив целых, и вызовем qsort.
Попробуем файл с 4 Мб данных. Без ограничений всё работает:
$ ./naive 4M.bin > /dev/null
4000000 bytes sorted in 0.323146 seconds
но это неинтересно. Ограничим память 2 MiB:
$ LD_PRELOAD=./libmemrestrict.so ./naive ints > ints.sorted
Segmentation fault
Поднимем ограничение до 4 MiB — и вновь неудача. (libmemrestrict читает настройки из окружения).
$ MR_THRESHOLD=5000000 LD_PRELOAD=./libmemrestrict.so ./naive ints > ints.sorted
Segmentation fault
Очевидно, для qsort требуется больше памяти. Посмотрим, сколько он хочет, при помощи massif от valgrind:
$ valgrind --tool=massif ./naive ints
$ ms_print massif.out.10676
Вот вам красивый график:
MB
8.819^ :::::::::::::::::::::::::::#
| : #
| : #
| : #
| : #
| : #
| : #
| : #
| : #
| :::::::@ #::::::::::::::::::::::::
| : @ #
| : @ #
| : @ #
| : @ #
| : @ #
| @@@@@@: @ #
| @ : @ #
| @ : @ #
| :::@ : @ #
| ::: @ : @ #
0 +----------------------------------------------------------------------->Gi
0 1.721
Видно несколько размещений данных, удваивающих запросы в памяти до 4 MiB — это мой массив, и затем ещё четыре MiB для qsort. Статистика:
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
21 173,222,581 5,247,504 4,000,568 1,246,936 0
22 173,223,802 5,246,920 4,000,000 1,246,920 0
23 173,226,655 5,247,504 4,000,568 1,246,936 0
24 173,229,202 5,246,920 4,000,000 1,246,920 0
25 173,229,311 9,246,928 8,000,000 1,246,928 0
26 869,058,772 9,246,928 8,000,000 1,246,928 0
86.52% (8,000,000B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->43.26% (4,000,000B) 0x400A26: readfile (in /home/avd/dev/cs/sorting/external/naive)
| ->43.26% (4,000,000B) 0x400ACD: main (in /home/avd/dev/cs/sorting/external/naive)
|
->43.26% (4,000,000B) 0x35D40383F7: qsort_r (in /usr/lib64/libc-2.18.so)
| ->43.26% (4,000,000B) 0x400B3D: main (in /home/avd/dev/cs/sorting/external/naive)
|
->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
4 миллиона байт использую я, и ещё 4 миллиона — qsort_r. И ещё 1,2 MB дополнительно в куче использует massif.
Судя по всему, в этом случае qsort ведёт себя как O (n) по отношению к сложности по объёму. Что странно, поскольку qsort работает «на месте» и использует различные техники оптимизации, гарантирующие сложность по объёму в O (log n). Дополнительное чтение по реализации glibc qsort.
Ладно –, а сможет ли он отсортировать 500 MB в 128 MiB RAM?
$ ./naive 500M.bin > /dev/null
Segmentation fault
Конечно, нет. Быстродействие:
$ ./naive 4M.bin > /dev/null
4000000 bytes sorted in 0.322712 seconds
Значит, наивная сортировка неплохо работает без ограничений, вообще не работает с ограничениями, а qsort требует себе памяти O (n). Это странно. К примеру, если ограничить память 5,3 Мб, она заработает и не затребует памяти объёмом O (n). Я пока ещё разбираюсь с этим.
Файл и mmap
mmap — хакерский способ сортировки большого количества данных в условиях ограничения памяти. Он перекладывает груз распределения данных между памятью и свопом на плечи операционки.
Работает это так:
- Через mmap мы отправляем весь файл в память
- Получаем от него указатель на данные
- Вызываем алгоритм сортировки данных по этому указателю
И всё! Теперь вы не получите переполнение памяти, даже сортируя файл по объёму больший, чем доступная память. Для понимания работы механизма нужно немного разобраться с управлением памятью в ОС.
Каждая программа представлена процессом, у которого есть своё личное, изолированное от других, виртуальное адресное пространство. Длина его ограничена шириной шины CPU, то есть для 32-битного CPU она равна 232, то есть 4 GiB.
Всё размещение памяти, которым занимается процесс, происходит в виртуальной памяти. Эта виртуальная память отображается на физическую подсистемой ядра для работы с памятью — MMU. И обычно происходит в «ленивом» режиме — то есть, когда процесс просит памяти, ядро ему сразу её даёт, но при этом физически не размещает её мгновенно — то есть, страница виртуальной памяти не отображается сразу на физическую. Когда к такой странице происходит доступ (например, на запись), MMU создает исключение «page fault», которое ядро обрабатывает, отображая виртуальную страницу на физическую. Теперь она отображена, и запись в эту страницу будет транслироваться MMU как запись по определённому адресу в физической памяти.
С другой стороны, если помнить, что виртуальное адресное пространство ограничено лишь размером шины CPU, можно попасть в ситуацию, в которой программа захочет занять больше памяти, чем есть в наличии. К примеру, в 32-битной системе, имеющей 256 MiB RAM, процесс может разместить и использовать 1 GiB памяти. В таком случае страницы памяти попадут в своп — они вместо RAM попадут на накопитель, такой, как жёсткий диск. При доступе к такой странице ядро считает её с накопителя и отправит в память (заменяя другую страницу в памяти).
Ядро неплохо справляется с распределением данных между памятью и накопителем, поэтому естественно попытаться использовать это его свойство в нашей задаче. Когда мы вызовем mmap для нашего файла, ядро зарезервирует диапазон виртуальных адресов, который не будет сразу размещён. Когда мы попытаемся получить доступ к ним, ядро подгрузит его из входного файла в память. Когда у нас закончится физическая память, ядро уберёт страницы в своп. Таким образом мы будем балансировать данными между файлом на диске, памятью и свопом.
Ограничением является только виртуальное адресное пространство (4 GiB для 32bit системы и 256 TiB для 64bit), и своп –, но накопители сегодня стоят недорого.
В связи с тем, что mmap грузит весь файл в виртуальную память, мы не сможем использовать libmemrestrict или ptrace-restrict, поскольку они ограничивают саму виртуальную память. Попытавшись ограничить сортировку данных объёмом в 100M в виртуальную память объёмом 10M, мы получим ошибку от mmap:
$ qemu-x86_64 -R 10M ./mmaped 100M.bin
mmap stack: Cannot allocate memory
Ничего удивительного — файл грузится в виртуальную память, и ядро распределяет её между физической памятью и свопом. Так что нам нужно не менее 100М виртуальной памяти, плюс ещё немного места для qemu.
Поэтому для данного метода я использую виртуальную машину с 128 MiB памяти. Вот моя программа сортировки, использующая mmap. И всё работает!
$ free -m
total used free shared buffers cached
Mem: 119 42 76 0 4 16
-/+ buffers/cache: 21 97
Swap: 382 0 382
$ ll -h 500M.bin
-rw-r--r-- 1 root root 477M Feb 3 05:39 500M.bin
$ ./mmaped 500M.bin > /dev/null
500000000 bytes sorted in 32.250000 seconds
Информация от top:
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
3167 root 20 0 480m 90m 90m R 84.6 76.4 1:18.65 mmaped
Мы используем 500 Мб виртуальной памяти, а реальная доступная память при этом составляет 90 MiB. Отметим, что MiB это 220, а MB это 106 = 1 миллион. И 500 MB = 500 000 000 байт, а 500 000 000 >> 20 = 476 MiB.
Глянув на детали от vmstat во время сортировки 500 MB, мы увидим, как ядро балансирует между свопом, дисковым кэшем, буферами и свободной памятью:
procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu----
r b swpd free buff cache si so bi bo in cs us sy id wa
0 0 0 77776 2120 15104 1 27 710 971 24 34 3 1 95 1
1 1 0 2060 488 90068 1 27 785 1057 25 37 3 1 95 1
1 0 928 3400 60 89744 1 27 799 1092 25 38 3 1 94 1
0 2 1908 1928 212 92040 1 27 852 1174 26 40 4 1 94 1
0 2 3436 2360 280 93056 1 27 911 1282 28 42 4 1 94 2
0 0 5272 3688 196 94688 1 27 1066 1471 31 48 4 1 93 2
0 0 5272 3720 204 94700 1 27 1064 1469 31 48 4 1 93 2
Сначала у нас было ~70 MiB свободной памяти, пустой своп и немножко памяти было отдано под буферы I/O и кэш. Затем после mmap вся эта память ушла на кэш. Когда свободная память кончилась, ядро стало использовать своп, который увеличивается вместе с увеличением загрузки I/O. И мы приходим к тому, что почти вся память отдана под кэш диска — что нормально, поскольку страницы с дисковым кэшем, в случае, когда нам требуется память под приложение, уходят первыми.
Итак, сортировка через mmap — прикольный хак, требующий базовых представлений о работе с памятью, и дающий простое решение для обработки большого количества данных при маленьком количестве памяти.
Внешняя сортировка со слиянием
Допустим, mmap использовать нельзя — вы хотите отсортировать файл в 5 GiB на 32-битной системе.
Существует известный популярный способ под названием «внешняя сортировка со слиянием». Если у вас не хватает памяти, нужно использовать внешний накопитель — например, жёсткий диск. Придётся только работать с данными по кусочку, поскольку в память они все не влезут.
Внешняя сортировка со слиянием работает так:
- разбиваете данные на куски по объёму доступной памяти
- каждый кусок сортируется в памяти и пишется на внешний носитель
- теперь у вас есть куски размером filesize/buffersize
- читаете части кусков размером buffersize/#chunks, чтобы объединить их в буфере и вывести результат в файл
Я сделал простую неоптимизированную реализацию:
$ LD_PRELOAD=./libmemrestrict.so ./external-merge 4M.bin 1048576 > /dev/null
4194304 bytes sorted in 0.383171 seconds
Отсортировали, имея 2 MiB памяти и используя буфер в 1 MiB.
Теперь отсортируем 500 Мб. Сначала отключим своп, поскольку мы управляем обменом кусков данных вручную.
$ swapoff /dev/vda5
Обнулим кэши:
$ echo 3 > /proc/sys/vm/drop_caches
Проверим доступную память:
$ free -m
total used free shared buffers cached
Mem: 119 28 90 0 0 6
-/+ buffers/cache: 21 97
Swap: 0 0 0
Будем использовать буфер в 50 Мб — в 10 раз меньше размера файла.
$ ./external-merge 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 120.115180 seconds
Ничосий, две минуты! С чего бы это? Конечно, из-за операций I/O. Три вещи тормозят процесс. На фазе разделения данных мы последовательно читаем файл, используя маленький буфер. На фазе слияния мы открываем и закрываем файлы с кусками информации. А ещё есть и вывод — на фазе слияния мы выводим 50 Мб данных на stdout, что, несмотря на перенаправление в /dev/null, даёт нагрузочку. Если это отключить, мы получаем прирост быстродействия на 25%.
$ ./external-merge-no-output 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 87.140000 seconds
Использование памяти меня устраивает. Если запустить программу через massif, можно увидеть, что пик потребления — это размер буфера и небольшая куча.
--------------------------------------------------------------------------------
Command: ./external-merge 500M.bin 50000000
Massif arguments: (none)
ms_print arguments: massif.out.17423
--------------------------------------------------------------------------------
MB
47.75^ :::::
|#::::::@:::::::::::@:::::::::@:::@::::@::::@::::::::@::::@::::@:::@
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
|# : : @ : : : : @ : : @ @ @ @ : @ @ @ @
0 +----------------------------------------------------------------------->Gi
0 332.5
Number of snapshots: 98
Detailed snapshots: [4 (peak), 10, 20, 29, 32, 35, 38, 45, 48, 54, 64, 74, 84, 94]
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
0 0 0 0 0 0
1 119,690 584 568 16 0
2 123,141 50,004,496 50,000,568 3,928 0
3 4,814,014 50,005,080 50,001,136 3,944 0
4 4,817,234 50,005,080 50,001,136 3,944 0
99.99% (50,001,136B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->99.99% (50,000,000B) 0x400FA2: external_merge_sort (in /root/external-merge)
| ->99.99% (50,000,000B) 0x40128E: main (in /root/external-merge)
|
->00.00% (1,136B) in 1+ places, all below ms_print's threshold (01.00%)
Можно ограничить память и 50 Мб, плюс ещё 500 KB на временные строки, содержащие пути к файлам:
$ LD_PRELOAD=./libmemrestrict.so MR_THRESHOLD=51000000 ./external-merge 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 87.900000 seconds
В общем, с памятью — ок, с быстродействием — не ок. mmap позволяла сделать эту операцию за 32 секунды. Давайте улучшать наш способ.
Проведём профилирование программы при помощи gprof. Создадим бинарник
$ gcc -pg -g -Wall -Wextra external-merge.c -o external-merge-gprof
И вызовем программу многократно для накопления статистики при помощи моего удобственного скрипта из статьи по gprof. Вот результат:
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
81.98 432.87 432.87 compar
18.17 528.82 95.95 print_arr
0.00 528.82 0.00 1100 0.00 0.00 form_filename
0.00 528.82 0.00 100 0.00 0.00 merge
0.00 528.82 0.00 100 0.00 0.00 save_buf
0.00 528.82 0.00 10 0.00 0.00 external_merge_sort
0.00 528.82 0.00 10 0.00 0.00 split
Большая часть времени ушла на сортировку и вывод. Но не забудьте, что gprof не показывает время, ушедшее на системные вызовы и I/O.
Что тут можно улучшить?
- добавить во внешнюю сортировку многопоточность и трюки с I/O
- взять другой алгоритм сортировки
Универсальная внешняя сортировка со слиянием — это простая идея для сортировки больших данных при малом количестве памяти, но без каких-либо улучшений она работает медленно.
Настраиваем сортировку
Можно, конечно, использовать многопоточность для разделения и слияния –, но это плохая идея. Использование его на фазе разделения смысла не имеет, потому что данные содержатся в одном буфере. Можно попытаться повлиять на то, как ядро читает данные. Для этого есть две функции:
- readahead (только в Linux).
- posix_fadvise с POSIX_FADV_SEQUENTIAL.
Они сообщают подсистеме управления памятью о том, как мы будем читать данные. В нашем случае чтение последовательно, поэтому было бы неплохо увидеть содержимое файла в кэше страниц.
На фазе слияния мы можем не делать постоянные открытия и закрытия файлов, а создать выделенные потоки для каждого из файлов. Каждый поток будет держать открытым свой файлик, а мы будем заполнять для него буфер. Когда он заполняется, он сортируется и выводится. И ещё для каждого потока будет работать readahead.
Вот усовершенствованная многопоточная версия внешней сортировки со слиянием. Ну, как я и сказал, многопоточность — не очень хорошая идея. На одноядерном проце разницы никакой нет.
$ ./mt-ext-merge 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 117.380000 seconds
Это с выводом данных. А без вывода:
$ ./mt-ext-merge-no-output 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 91.040000 seconds
Ну ладно, давайте попробуем на четырёхъядерной машине (Intel Core i7–3612QM CPU @ 2.10GHz):
$ ./naive 500M.bin > /dev/null
500000000 bytes sorted in 23.040499 seconds
$ ./mmaped 500M.bin > /dev/null
500000000 bytes sorted in 23.542076 seconds
$ ./external-merge 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 39.228695 seconds
$ ./mt-external-merge 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 41.062793 seconds
$ ./external-merge-no-output 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 28.893745 seconds
$ ./mt-external-merge-no-output 500M.bin 50000000 > /dev/null
500000000 bytes sorted in 28.368976 seconds
Теперь для ста кусочков и ста потоков:
$ ./external-merge-no-output 500M.bin 5000000 > /dev/null
500000000 bytes sorted in 27.107728 seconds
$ ./mt-external-merge-no-output 500M.bin 5000000 > /dev/null
500000000 bytes sorted in 28.558468 seconds
Разницы между external-merge и mt-external-merge нет. С чего это? Да потому, что многопоточность не решает проблемы ограничений ввода и вывода. Она хорошо подойдёт для тех случаев, когда:
- исполнение потоков независимо
- ресурсы ввода и вывода могут работать параллельно — например, как RAID
У нас потоки взаимозависимы — главному потоку приходится ждать сортировки буфера, а уже потом начинать следующее чтение из файла. И чтение для разделения идёт быстрее, чем сортировка буфера, поэтому большую часть времени потоки ждут, пока основной поток закончит работу.
Нужны другие способы улучшения алгоритма.
Особые алгоритмы сортировки
Попробуем использовать что-то отличное от QuickSort. Раз уж мы знаем, что сортируем целые числа, надо это использовать. Есть особые алгоритмы, которые используются для конкретных типов данных, и их можно разделить на две группы:
- не используют сравнения
- не требуют загрузки всего массива в память
Они работают лучше, чем O (n log (n)) — нижняя граница для сравнивающих алгоритмов вроде QuickSort. Но не все они подойдут в случае ограничения памяти. Поэтому я остановился на использовании сортировки подсчётом
Сортировка подсчётом
Если у нас много данных с малым разбросом, можно использовать сортировку подсчётом. Идея проста — мы будем хранить в памяти не данные, а массив счётчиков. Мы последовательно читаем данные и увеличиваем соответствующие счётчики. Сложность алгоритма по времени линейна, а по объёму — пропорциональна диапазону данных.
Простая реализация работает с массивом от 0 до N. Целые числа соответствуют индексам массива. Вот мой вариант, который неплохо работает и без всякого тюнинга. Второй аргумент — размер буфера в элементах. Буферизация сильно ускоряет работу, поскольку программа читает из файла не по 4 байта.
$ ./counting-array 500M-range.bin 1000000 > /dev/null
Range is 1000000
500000000 bytes sorted in 3.240000 seconds
Угумс. Полгига данных отсортировано за 3 с половиной секунды на 128 MiB памяти и одном CPU. Сравним с qsort или mmap:
$ ./mmaped 500M-range.bin > /dev/null
500000000 bytes sorted in 76.150000 seconds
В 23 раза быстрее!
Но не забывайте об ограничениях — только целые числа (или их эквивалент), и небольшой их последовательный промежуток. Я пытался делать вариант с непоследовательными промежутками через хэши и бинарный поиск –, но быстродействие у него очень плохое.
А если мы предположим уникальность наших чисел, то счётчики могут быть только в двух состояниях — есть или нет, поэтому они могут быть однобитными. Тогда наш массив ужмётся. Да и массив нам не нужен — мы можем хранить числа в виде битов, то есть вместо массива у нас будет вектор. Читаем файл и устанавливаем N-ный бит, если там встретилось число N. После этого просто проходимся по вектору и выводим в файл те числа, для которых взведены биты.
Такие решения требуют внимательного подхода, поскольку всё равно можно выйти за пределы ограничений. К примеру, для сортировки всех чисел из промежутка целых (232), вам понадобится 1 бит на каждое число, а это 4294967296 бит = 536870912 байт = 512 MiB. А у нас есть только 128 MiB, чего вам не хватит. Но в некоторых случаях выигрыш будет колоссальным — вот история на эту тему из «Programming Pearls» by Jon Bentley.
Знание ваших данных очень полезно.
Итог
За 5 месяцев, потраченных на статью, я сделал много чего — десяток программ, несколько хороших идей, много плохих. И много чего ещё можно сделать и поправить.
Простая проблема сортировки данных при недостатке памяти выявила целый набор странностей, о которых мы обычно не думаем:
- распространённые алгоритмы не подходят для всех проблем
- отладка и профилирование — очень полезные и наглядные вещи
- I/O — проблемная область, если не перекладывать всю работу на ядро
- многопоточность не является панацеей для достижения скорости
- знайте ваши данные и ваше окружение
Табличка для сортировки:
| Тест | Наивный QuickSort | mmap и QuickSort | Внешняя сортировка со слиянием | Многопоточная внешняя сортировка со слиянием | Сортировка подсчётом |
| 4 MiB in 2 MiB | Segfault | N/A | 0.38s | 0.41s | 0.01 |
| 500 MB in 128 MiB | Segfault | 32.25s | 87.14s | 91.04 | 3.24 |
Познайте ваши данные и разработайте простой алгоритм для работы с ними!
Ссылки
