По поводу использования 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.
Круто, я пытался сделать что-то подобное, но не смог, поэтому заюзал lxc-контейнер. По cgroups очень сложно найти какую-то внятную документацию, чтобы человек извне мог понять что вообще происходит — к чему там все эти иерархии, контроллеры и пр. и как оно, собственно, работает. Может вы напишите кратенькую статейку-ликбез на эту тему?
Так а разве systemd-run не запустит программу под теми же cgroups? В чём тогда отличие от lxc в данном случае кроме управления через systemd и удобства?
Valgrind — это динамический отладчик для пользовательских приложений, про него информации уйма, в том числе на хабре. Про остальное я впервые слышу и не могу ничего нагуглить. Можно поподробнее, что такое NOP и SWAP?
Хочу на домашнем сервере развернуть гипервизор с несколькими виртуалками. Хочется что-то вроде одна виртуалка для разработки (LAMP, Postgres, git), другая с NAS, третья со всякой фигней типа mpd, vpn, торренты? Под NAS хочется полностью отдать 2 диска в md RAID1, другой диск отдать полностью под хранение разработки, и на четвертом нарезать LVM тома под ОСи для виртуалок.
1. Что удобнее с учетом вышеперечисленного?
2. Какие есть способы бэкапа виртуалок и сколько весят эти бэкапы?
Если у вас 1 КБ текста, то да — разницы нет. Но когда надо пошифровать гигабайты, то тут уж разница между 1 часом и 0.5 часа существенней будет.
Но вообще я не об этом — очень интересно было бы послушать о применении Haskell для решения задачи криптоанализа. Поэтому, когда вы начнете проходить более продвинутый курс в котором будет данная тема — вы знаете, что от вас будут ждать ;-)
Крипта на функциональном языке — это, конечно, очень интересно. Но всё-таки мне кажется, что haskell бы больше подошел для решения задач криптоанализа, чем для реализации криптопримитивов.
Вы не пробовали замерять производительность вашего варианта на Haskell и C?
Оказывается, в glibc есть 2 реализации быстрой сортировки — in-place вариант, который называется
_quicksort
, который можно найти в qsort.c, который я и рассматривал в оригинальной статье и не in-place вариантqsort_r
, что в файле msort.c.Так вот на самом деле по умолчанию используется именно
qsort_r
, т.е. вариант с O(n) по памяти. И только если памяти не хватает, в бой вступает in-place вариант:Забавно ещё то, что вызываемая функция
msort_with_tmp
— это Merge Sort, т.е. в абсолютном большинстве случаев, когда вы вызываете qsort в C, вы на самом деле делаете не QuickSort, а MergeSort.malloc возвращает указатель на void. void — это не NULL
1. Что удобнее с учетом вышеперечисленного?
2. Какие есть способы бэкапа виртуалок и сколько весят эти бэкапы?
В избранное.
Но вообще я не об этом — очень интересно было бы послушать о применении Haskell для решения задачи криптоанализа. Поэтому, когда вы начнете проходить более продвинутый курс в котором будет данная тема — вы знаете, что от вас будут ждать ;-)
А как же блочные и поточные шифры?
Вы не пробовали замерять производительность вашего варианта на Haskell и C?