[Перевод] Сортировка целых чисел при нехватке памяти

Автор оригинала на английском языке — хабраюзер 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

Познайте ваши данные и разработайте простой алгоритм для работы с ними!

Ссылки


© Habrahabr.ru