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

[tzlom]

Просадка при записи в /dev/null это не дисковая подсистема а printf в цикле, что вообщем то медленно и не удивительно, плюс блок буфера там маленький.
Для интереса можете попробовать покидать нули в /dev/null и посмотреть с какой скоростью это может быть и как размер блока влияет на скорость:

time dd if=/dev/zero of=/dev/null bs=4k count=4m
4194304+0 records in
4194304+0 records out
17179869184 bytes transferred in 5.086937 secs (3377252235 bytes/sec)

real	0m5.093s
user	0m0.955s
sys	0m4.125s

time dd if=/dev/zero of=/dev/null bs=4m count=4k
4096+0 records in
4096+0 records out
17179869184 bytes transferred in 2.210588 secs (7771628794 bytes/sec)

real	0m2.221s
user	0m0.009s
sys	0m2.201s

[youROCK]

Кстати в mmap вы получаете такое же время скорее всего из-за того, что весь файл умещается в кеш файловой системы. Причем, при запуске через qemu с ограничением по памяти, вы используете кеш файловой системы на хосте. В общем, вариант с mmap без кеша на HDD должен показывать очень плохие результаты по сравнению с внешней сортировкой слиянием из-за рандомного I/O против последовательного I/O у внешней сортировки слиянием

[dzeban]

По поводу использования 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]

Внезапненько!
Впрочем, в std::sort тоже используются две разные сортировки: для масеньких массивов и для всех остальных.

[ivan2kh]

<>

[ivan2kh]

Думаю здесь подойдет сортировка со сжатием данных. При работе с 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 элементов.

[ivan2kh]

вот пример
github.com/ivan2kh/dummy/blob/master/sort.go

[niamster]

Про mmap — все неверно.
Во первых когда мапится файл — ядро к swap не прикасается — чистые страницы отбрасываются, грязные — пишутся на накопитель, потом отбрасываются.
Во вторых при анонимном mmap — это тоже самое, что и sbrk — при нехватке ядро вымещает страницы в swap. Разница между mmap и sbrk в том, что можно сделать munmap в то время как unsbrk не существует.

Также имеет смысл упомянуть что подавляющее большинство аллокаторов использует mmap, а sbrk — только в системах которые не поддерживает mmap, что в данный момент большая редкость.

[niamster]

Отдельно хотелось бы раскритиковать заголовок — в данном случае не представлен алгоритм позволяющий отсортировать массив в условиях жесткого ограничения, а рассмотрены сомнительные приемы зависимые от операционной системы.
В моей практике довольно часто встречаются случаи, когда система имеет 32MB памяти, 0MB swap и накопитель — NOR FLASH — в данном случае действительно приходится выкручиваться, и никакие mmap не помогут.