Comments 9
Просадка при записи в /dev/null это не дисковая подсистема а printf в цикле, что вообщем то медленно и не удивительно, плюс блок буфера там маленький.
Для интереса можете попробовать покидать нули в /dev/null и посмотреть с какой скоростью это может быть и как размер блока влияет на скорость:
Для интереса можете попробовать покидать нули в /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
0
Кстати в mmap вы получаете такое же время скорее всего из-за того, что весь файл умещается в кеш файловой системы. Причем, при запуске через qemu с ограничением по памяти, вы используете кеш файловой системы на хосте. В общем, вариант с mmap без кеша на HDD должен показывать очень плохие результаты по сравнению с внешней сортировкой слиянием из-за рандомного I/O против последовательного I/O у внешней сортировки слиянием
+1
По поводу использования O(n) памяти в QuickSort я таки докопался в чём там было дело.
Оказывается, в glibc есть 2 реализации быстрой сортировки — in-place вариант, который называется
Так вот на самом деле по умолчанию используется именно
Забавно ещё то, что вызываемая функция
Оказывается, в 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. +3
<>
0
Думаю здесь подойдет сортировка со сжатием данных. При работе с 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 элементов.
Какой будет размер алфавита массива 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 элементов.
0
Про mmap — все неверно.
Во первых когда мапится файл — ядро к swap не прикасается — чистые страницы отбрасываются, грязные — пишутся на накопитель, потом отбрасываются.
Во вторых при анонимном mmap — это тоже самое, что и sbrk — при нехватке ядро вымещает страницы в swap. Разница между mmap и sbrk в том, что можно сделать munmap в то время как unsbrk не существует.
Также имеет смысл упомянуть что подавляющее большинство аллокаторов использует mmap, а sbrk — только в системах которые не поддерживает mmap, что в данный момент большая редкость.
Во первых когда мапится файл — ядро к swap не прикасается — чистые страницы отбрасываются, грязные — пишутся на накопитель, потом отбрасываются.
Во вторых при анонимном mmap — это тоже самое, что и sbrk — при нехватке ядро вымещает страницы в swap. Разница между mmap и sbrk в том, что можно сделать munmap в то время как unsbrk не существует.
Также имеет смысл упомянуть что подавляющее большинство аллокаторов использует mmap, а sbrk — только в системах которые не поддерживает mmap, что в данный момент большая редкость.
0
Отдельно хотелось бы раскритиковать заголовок — в данном случае не представлен алгоритм позволяющий отсортировать массив в условиях жесткого ограничения, а рассмотрены сомнительные приемы зависимые от операционной системы.
В моей практике довольно часто встречаются случаи, когда система имеет 32MB памяти, 0MB swap и накопитель — NOR FLASH — в данном случае действительно приходится выкручиваться, и никакие mmap не помогут.
В моей практике довольно часто встречаются случаи, когда система имеет 32MB памяти, 0MB swap и накопитель — NOR FLASH — в данном случае действительно приходится выкручиваться, и никакие mmap не помогут.
0
Sign up to leave a comment.
Сортировка целых чисел при нехватке памяти