detpax на Си

В 7687e77d7a77d0a14e4dd38c79886b942199ac9d упоминал написанный мною на
Go детерминированный архиватор. Где-то с использованием или сборкой Go
могут быть сложности. Да и вообще это как-бы единственная зависимость
написанная на нём из оставшихся в BASS для минимальной работы.

По быстрому написал на Си. Но не смог остановиться и уже из спортивного
интереса решил сделать его эффективным. Результаты оказались (для меня)
впечатляющими.

Алгоритм изначально был примерно как в Go, что было ужасно. Сначала
собираем всю информацию о файлах/директориях. Изначально это был realloc
массив, что, очевидно, не хорошо. Во время этой сборки, мы сразу же
заполняем и ищем в hsearch() хэше информацию о существующих инодах (для
определения жёстких ссылок). При этом надо сортировать список файлов в
пределах директории, чтобы не было того, что ссылка в архиве пойдёт
после файла на который ссылается. На каждую строку был malloc(). В
общем, медленнее и прожорливее сложно придумать.

Во-первых, от realloc массива где хранятся все элементы избавился просто
скопировав без изменений (0d5461a43eac20210e3ae033c9366233aeb0ae1f) KEKS
memory pool allocator. После чего делается только массив указателей
который и сортируется.

Во-вторых, нам нет никакого смысла пытаться сразу заполнять информацию о
жёстких ссылках по время walk-а по директориям. Это можно делать на лету
прямо в процессе формирования tar архива. Когда собрали информацию обо
всех файлах, то вместе с формированием массива для сортировки, сразу же
делаем и массив (dev, ino)->path. Один раз сортируем его и можно через
бинарный поиск (bsearch()) быстро по нему искать. Если path был NULL, то
значит файл встретился первый раз. Если не пустой, то вот сразу же на
руках и путь который надо в link вставить.

Чтобы уменьшить кол-во malloc-ов для хранения строчек, изначально я
просто сделал поля с path-ами фиксированной длины буферами. Да, жрёт
дофига, но нигде не realloc-ируется, нет тьмы вызовов malloc.

Затем решил делать так: выделяем большой буфер, храним offset на него.
Когда нужно выделить память под строчку, то просто линейно друг за
другом выделяем их в нём. Когда строчка не может уместиться в оставшемся
месте буфера, то создаём ещё один, обнуляем offset. Строго говоря, нам
даже не нужно помнить про старые большие выделенные буферы (если явно не
хотим освобождать их). Вместо того чтобы писать код на эту аллокацию и
прочее, снова просто использовал memory pool allocator. Да, в нём будет
один большой элемент, будет какая-то часть места съедена заголовком (в
котором freelist, ссылка на следующий chunk, align/size размеры), но да
и фиг с ним, мелочи.

А затем вспомнил про (0de9685e0fa681be50a28978292319594d97d5c1) немецкие
строки. И вместо struct{char *, size_t} я храню struct{unsigned char [16]}.
В первых двух байтах хранится длина строки (для путей этого достаточно).
А дальше либо 14 байт строка (embedded), либо 6 байт префикс (первые
байты строки) и ссылка на участок памяти для строки. Если выделяемая
строка маленького размера, то они умещаются в этих немецких строках.
Если нет, то выделяется память их вышеописанного буфера для строк, ну и
указатель сохраняется в немецкой строке. После заполнения данными, явно
вызывается метод "обнови prefix", если предполагается использование в
операциях сравнения строк (например при сортировке).

Далее я разделил хранение строчки с директорией и строчки с именем
файла. struct Path {struct Str dir, struct Str fn}. В принципе можно
же просто linked list-ами (entity просто имеет ссылка на вышестоящую
директорию) собирать полностью весь пусть воедино, вообще не храня
отдельно строки "foo", "foo/bar", "foo/bar/baz" и т.д. Не проверял, но
во время сортировки на одной моей директории вызывается 1.6M раз функция
сравнения строк, и если бы каждый раз пришлось ходить по цепочке
связанных элементов, то наверняка бы было довольно медленно, но надо бы
проверять.

Что в итоге? bsdtar, использующий libarchive, при архивировании одного
dataset-а, делал более 2M malloc-ов (судя по valgrind), выделяя суммарно
более 1G памяти. detpax делал ~13K malloc-ов, выделяя ~43M. Причём,
~100% всех этих malloc-ов делались не моим кодом, а readdir. У меня
malloc срабатывал ~70 раз всего лишь. zsh time показывал что bsdtar
потреблял 140M памяти в пике, тогда как у меня 20 с чем-то. На архивах
типа boost, он работал чуть-чуть побыстрее (10-20%) моего detpax, но на
бОльших данных у меня раза в полтора быстрее. И ведь у меня задача
ресурсоёмче: мне *всё* надо отсортировать перед началом создания архива.

Более половины строк вышли embedded. Из 1.6M сравнений (которые во время
сортировки происходят), 600k+ проверяются только сравнением длин, даже
не доходя до просмотра значений. Я сортирую не просто побайтно, а с
учётом длины (короче -- приоритетнее, как в KEKS для MAP-ов). Ну а далее
в ~50k случаев сравниваются embedded значения, в ~50k случаев сравнение
выходит на этапе проверки префиксов. Всего 10% от общего числа, но это
тоже ожидаемо, ведь преобладающая часть строк это полные пути к
директориям, где начало у них вовсю совпадает и они не embedded из-за
размера. При этом где-то 50 chunk-ов по ~64KB было выделено для хранения
строк (то есть ~3.2MB для их хранения).

Само собой поддерживаются расширенные pax заголовки: для длинных путей,
link-ов и размеров.

Никаких зависимостей кроме штатных библиотек. Никаких "-l"
дополнительных не надо. Чисто C99. Пока пускай ещё полежит в отдельной
ветке, возможно что-то ещё касательно имён придумаю (всё же иметь "name"
и ссылку на директорию притягивает, но осложняет сортировку).