Автор оригинала на английском языке — хабраюзер 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 Мб данных. Без ограничений всё работает:
но это неинтересно. Ограничим память 2 MiB:
Поднимем ограничение до 4 MiB – и вновь неудача. (libmemrestrict читает настройки из окружения).
Очевидно, для qsort требуется больше памяти. Посмотрим, сколько он хочет, при помощи massif от valgrind:
Вот вам красивый график:
Видно несколько размещений данных, удваивающих запросы в памяти до 4 MiB – это мой массив, и затем ещё четыре MiB для qsort. Статистика:
4 миллиона байт использую я, и ещё 4 миллиона — qsort_r. И ещё 1,2 MB дополнительно в куче использует massif.
Судя по всему, в этом случае qsort ведёт себя как O(n) по отношению к сложности по объёму. Что странно, поскольку qsort работает «на месте» и использует различные техники оптимизации, гарантирующие сложность по объёму в O(log n). Дополнительное чтение по реализации glibc qsort.
Ладно – а сможет ли он отсортировать 500 MB в 128 MiB RAM?
Конечно, нет. Быстродействие:
Значит, наивная сортировка неплохо работает без ограничений, вообще не работает с ограничениями, а qsort требует себе памяти O(n). Это странно. К примеру, если ограничить память 5,3 Мб, она заработает и не затребует памяти объёмом O(n). Я пока ещё разбираюсь с этим.
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:
Ничего удивительного – файл грузится в виртуальную память, и ядро распределяет её между физической памятью и свопом. Так что нам нужно не менее 100М виртуальной памяти, плюс ещё немного места для qemu.
Поэтому для данного метода я использую виртуальную машину с 128 MiB памяти. Вот моя программа сортировки, использующая mmap. И всё работает!
Информация от top:
Мы используем 500 Мб виртуальной памяти, а реальная доступная память при этом составляет 90 MiB. Отметим, что MiB это 220, а MB это 106 = 1 миллион. И 500 MB = 500 000 000 байт, а 500 000 000 >> 20 = 476 MiB.
Глянув на детали от vmstat во время сортировки 500 MB, мы увидим, как ядро балансирует между свопом, дисковым кэшем, буферами и свободной памятью:
Сначала у нас было ~70 MiB свободной памяти, пустой своп и немножко памяти было отдано под буферы I/O и кэш. Затем после mmap вся эта память ушла на кэш. Когда свободная память кончилась, ядро стало использовать своп, который увеличивается вместе с увеличением загрузки I/O. И мы приходим к тому, что почти вся память отдана под кэш диска – что нормально, поскольку страницы с дисковым кэшем, в случае, когда нам требуется память под приложение, уходят первыми.
Итак, сортировка через mmap – прикольный хак, требующий базовых представлений о работе с памятью, и дающий простое решение для обработки большого количества данных при маленьком количестве памяти.
Допустим, mmap использовать нельзя — вы хотите отсортировать файл в 5 GiB на 32-битной системе.
Существует известный популярный способ под названием «внешняя сортировка со слиянием». Если у вас не хватает памяти, нужно использовать внешний накопитель — например, жёсткий диск. Придётся только работать с данными по кусочку, поскольку в память они все не влезут.
Внешняя сортировка со слиянием работает так:
Я сделал простую неоптимизированную реализацию:
Отсортировали, имея 2 MiB памяти и используя буфер в 1 MiB.
Теперь отсортируем 500 Мб. Сначала отключим своп, поскольку мы управляем обменом кусков данных вручную.
Обнулим кэши:
Проверим доступную память:
Будем использовать буфер в 50 Мб – в 10 раз меньше размера файла.
Ничосий, две минуты! С чего бы это? Конечно, из-за операций I/O. Три вещи тормозят процесс. На фазе разделения данных мы последовательно читаем файл, используя маленький буфер. На фазе слияния мы открываем и закрываем файлы с кусками информации. А ещё есть и вывод – на фазе слияния мы выводим 50 Мб данных на stdout, что, несмотря на перенаправление в /dev/null, даёт нагрузочку. Если это отключить, мы получаем прирост быстродействия на 25%.
Использование памяти меня устраивает. Если запустить программу через massif, можно увидеть, что пик потребления – это размер буфера и небольшая куча.
Можно ограничить память и 50 Мб, плюс ещё 500 KB на временные строки, содержащие пути к файлам:
В общем, с памятью – ок, с быстродействием – не ок. mmap позволяла сделать эту операцию за 32 секунды. Давайте улучшать наш способ.
Проведём профилирование программы при помощи gprof. Создадим бинарник
И вызовем программу многократно для накопления статистики при помощи моего удобственного скрипта из статьи по gprof. Вот результат:
Большая часть времени ушла на сортировку и вывод. Но не забудьте, что gprof не показывает время, ушедшее на системные вызовы и I/O.
Что тут можно улучшить?
Универсальная внешняя сортировка со слиянием – это простая идея для сортировки больших данных при малом количестве памяти, но без каких-либо улучшений она работает медленно.
Можно, конечно, использовать многопоточность для разделения и слияния – но это плохая идея. Использование его на фазе разделения смысла не имеет, потому что данные содержатся в одном буфере. Можно попытаться повлиять на то, как ядро читает данные. Для этого есть две функции:
Они сообщают подсистеме управления памятью о том, как мы будем читать данные. В нашем случае чтение последовательно, поэтому было бы неплохо увидеть содержимое файла в кэше страниц.
На фазе слияния мы можем не делать постоянные открытия и закрытия файлов, а создать выделенные потоки для каждого из файлов. Каждый поток будет держать открытым свой файлик, а мы будем заполнять для него буфер. Когда он заполняется, он сортируется и выводится. И ещё для каждого потока будет работать readahead.
Вот усовершенствованная многопоточная версия внешней сортировки со слиянием. Ну, как я и сказал, многопоточность – не очень хорошая идея. На одноядерном проце разницы никакой нет.
Это с выводом данных. А без вывода:
Ну ладно, давайте попробуем на четырёхъядерной машине (Intel Core i7-3612QM CPU @ 2.10GHz):
Разницы между external-merge и mt-external-merge нет. С чего это? Да потому, что многопоточность не решает проблемы ограничений ввода и вывода. Она хорошо подойдёт для тех случаев, когда:
У нас потоки взаимозависимы – главному потоку приходится ждать сортировки буфера, а уже потом начинать следующее чтение из файла. И чтение для разделения идёт быстрее, чем сортировка буфера, поэтому большую часть времени потоки ждут, пока основной поток закончит работу.
Нужны другие способы улучшения алгоритма.
Попробуем использовать что-то отличное от QuickSort. Раз уж мы знаем, что сортируем целые числа, надо это использовать. Есть особые алгоритмы, которые используются для конкретных типов данных, и их можно разделить на две группы:
Они работают лучше, чем O(n log(n)) – нижняя граница для сравнивающих алгоритмов вроде QuickSort. Но не все они подойдут в случае ограничения памяти. Поэтому я остановился на использовании сортировки подсчётом
Если у нас много данных с малым разбросом, можно использовать сортировку подсчётом. Идея проста – мы будем хранить в памяти не данные, а массив счётчиков. Мы последовательно читаем данные и увеличиваем соответствующие счётчики. Сложность алгоритма по времени линейна, а по объёму – пропорциональна диапазону данных.
Простая реализация работает с массивом от 0 до N. Целые числа соответствуют индексам массива. Вот мой вариант, который неплохо работает и без всякого тюнинга. Второй аргумент – размер буфера в элементах. Буферизация сильно ускоряет работу, поскольку программа читает из файла не по 4 байта.
Угумс. Полгига данных отсортировано за 3 с половиной секунды на 128 MiB памяти и одном CPU. Сравним с qsort или mmap:
В 23 раза быстрее!
Но не забывайте об ограничениях – только целые числа (или их эквивалент), и небольшой их последовательный промежуток. Я пытался делать вариант с непоследовательными промежутками через хэши и бинарный поиск – но быстродействие у него очень плохое.
А если мы предположим уникальность наших чисел, то счётчики могут быть только в двух состояниях – есть или нет, поэтому они могут быть однобитными. Тогда наш массив ужмётся. Да и массив нам не нужен – мы можем хранить числа в виде битов, то есть вместо массива у нас будет вектор. Читаем файл и устанавливаем N-ный бит, если там встретилось число N. После этого просто проходимся по вектору и выводим в файл те числа, для которых взведены биты.
Такие решения требуют внимательного подхода, поскольку всё равно можно выйти за пределы ограничений. К примеру, для сортировки всех чисел из промежутка целых (232), вам понадобится 1 бит на каждое число, а это 4294967296 бит = 536870912 байт = 512 MiB. А у нас есть только 128 MiB, чего вам не хватит. Но в некоторых случаях выигрыш будет колоссальным – вот история на эту тему из «Programming Pearls» by Jon Bentley.
Знание ваших данных очень полезно.
За 5 месяцев, потраченных на статью, я сделал много чего – десяток программ, несколько хороших идей, много плохих. И много чего ещё можно сделать и поправить.
Простая проблема сортировки данных при недостатке памяти выявила целый набор странностей, о которых мы обычно не думаем:
Табличка для сортировки:
Познайте ваши данные и разработайте простой алгоритм для работы с ними!
Введение
В прошлый раз мы обсудили, как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе 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 |
Познайте ваши данные и разработайте простой алгоритм для работы с ними!
Ссылки
- Сортировка миллиона 32-битных чисел в 2 Мб памяти на Python
- Внешняя сортировка больших наборов данных
- Эффективная сортировка данных, по объёму превышающих объём памяти
- Раскрываем устрицу (1-я статьи из «Жемчужин программирования»)
- Многопоточный ввод и вывод файлов
- Улучшение алгоритмов при помощи измерения быстродействия, часть 2
- Алгоритмы параллельной сортировки
Комментарии (9)
youROCK
10.09.2015 01:16+1Кстати в mmap вы получаете такое же время скорее всего из-за того, что весь файл умещается в кеш файловой системы. Причем, при запуске через qemu с ограничением по памяти, вы используете кеш файловой системы на хосте. В общем, вариант с mmap без кеша на HDD должен показывать очень плохие результаты по сравнению с внешней сортировкой слиянием из-за рандомного I/O против последовательного I/O у внешней сортировки слиянием
dzeban
10.09.2015 09:44+3По поводу использования O(n) памяти в QuickSort я таки докопался в чём там было дело.
Оказывается, в glibc есть 2 реализации быстрой сортировки — in-place вариант, который называется_quicksort, который можно найти в qsort.c, который я и рассматривал в оригинальной статье и не in-place вариантqsort_r, что в файле msort.c.
Так вот на самом деле по умолчанию используется именноqsort_r, т.е. вариант с O(n) по памяти. И только если памяти не хватает, в бой вступает in-place вариант:
0164 void 0165 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) 0166 { ... 0175 if (size < 1024) 0176 /* The temporary array is small, so put it on the stack. */ 0177 p.t = __alloca (size); 0178 else 0179 { ... 0213 /* If the memory requirements are too high don't allocate memory. */ 0214 if (size / pagesize > (size_t) phys_pages) 0215 { 0216 _quicksort (b, n, s, cmp, arg); 0217 return; 0218 } 0219 0220 /* It's somewhat large, so malloc it. */ 0221 int save = errno; 0222 tmp = malloc (size); 0223 __set_errno (save); 0224 if (tmp == NULL) 0225 { 0226 /* Couldn't get space, so use the slower algorithm 0227 that doesn't need a temporary array. */ 0228 _quicksort (b, n, s, cmp, arg); 0229 return; 0230 } ... 0254 msort_with_tmp (&p, p.t + n * sizeof (void *), n);
Забавно ещё то, что вызываемая функцияmsort_with_tmp— это Merge Sort, т.е. в абсолютном большинстве случаев, когда вы вызываете qsort в C, вы на самом деле делаете не QuickSort, а MergeSort.
maaGames
10.09.2015 16:11Внезапненько!
Впрочем, в std::sort тоже используются две разные сортировки: для масеньких массивов и для всех остальных.
ivan2kh
11.09.2015 00:27<>
ivan2kh
11.09.2015 00:34Думаю здесь подойдет сортировка со сжатием данных. При работе с 32 битными числами, считываем 64MB данных (2^24) I, сортируем, дифференцируем. Полученный массив D возможно хорошо сожмется.
Какой будет размер алфавита массива D в худшем случае?
Например, каждый последующий элемент массива D будет создавать новый элемент алфавита с помошью инкремента 1:
1, 2, 3, 4, 5, 6…
Тогда входной массив I будет иметь вид
1, 2, 4, 7, 11…
Функция входного массива I(n) = (n^2 — n + 2) / 2
Но так как мы работаем с 32 битными числами, то
(n^2 — n + 2) / 2 <= 2^32
n<92683
То есть в алфавите D будет не больше 92683 элементов.
niamster
17.09.2015 23:45Про mmap — все неверно.
Во первых когда мапится файл — ядро к swap не прикасается — чистые страницы отбрасываются, грязные — пишутся на накопитель, потом отбрасываются.
Во вторых при анонимном mmap — это тоже самое, что и sbrk — при нехватке ядро вымещает страницы в swap. Разница между mmap и sbrk в том, что можно сделать munmap в то время как unsbrk не существует.
Также имеет смысл упомянуть что подавляющее большинство аллокаторов использует mmap, а sbrk — только в системах которые не поддерживает mmap, что в данный момент большая редкость.
niamster
17.09.2015 23:51Отдельно хотелось бы раскритиковать заголовок — в данном случае не представлен алгоритм позволяющий отсортировать массив в условиях жесткого ограничения, а рассмотрены сомнительные приемы зависимые от операционной системы.
В моей практике довольно часто встречаются случаи, когда система имеет 32MB памяти, 0MB swap и накопитель — NOR FLASH — в данном случае действительно приходится выкручиваться, и никакие mmap не помогут.
tzlom
Просадка при записи в /dev/null это не дисковая подсистема а printf в цикле, что вообщем то медленно и не удивительно, плюс блок буфера там маленький.
Для интереса можете попробовать покидать нули в /dev/null и посмотреть с какой скоростью это может быть и как размер блока влияет на скорость: