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

Автор оригинала на английском языке — хабраюзер 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 она равна 2³², то есть 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 это 2²⁰, а MB это 10⁶ = 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. После этого просто проходимся по вектору и выводим в файл те числа, для которых взведены биты.

Такие решения требуют внимательного подхода, поскольку всё равно можно выйти за пределы ограничений. К примеру, для сортировки всех чисел из промежутка целых (2³²), вам понадобится 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
• Алгоритмы параллельной сортировки

ссылка на оригинал статьи http://habrahabr.ru/post/266557/