ARSV/articles/for-alt/plan.md

Работа над set.c: краткий план статьи

1. Зачем ALT RPM нужны set-строки

Обычная зависимость от версии библиотеки не гарантирует, что в ней остались все нужные программе символы: символ можно удалить, не сменив SONAME, а одинаковые SONAME могут скрывать разные наборы экспортов. Поэтому ALT RPM использует версии зависимостей вида set:<encoded-set>. В Provides такая строка описывает символы, предоставляемые библиотекой, а в Requires - символы, которые конкретный потребитель требует именно от неё. Сравниваются не номера версий, а включение множеств: все хэши из Requires должны присутствовать в Provides. Гарантия вероятностная, поскольку вместо имён хранятся усечённые хэши, но ответ "символ отсутствует", когда он есть мы не получим (ложноположительное срабатывание)

2. Как строится set-строка

Список символов формируется автодепами rpm-build. Для Provides из ELF извлекаются отфильтрованные экспортируемые базовые имена символов. Для Requires ldd --bindings связывает каждый сильный неопределённый символ с конкретной библиотекой, после чего для каждого провайдера строится отдельное множество.

Далее mkset использует API set_new() → set_add() → set_fini():

1. для каждого имени вычисляется Jenkins OAAT и оставляются младшие bpp бит;
2. хэши сортируются, повторы удаляются, о коллизиях выдаётся предупреждение;
3. абсолютные значения заменяются дельтами;
4. дельты сжимаются кодом Голомба-Райса с параметром Mshift;
5. битовый поток переводится в RPM-безопасную Base62-строку.

При сравнении rpmsetcmp() выполняет обратное декодирование, приводит строки с разным bpp к общей точности и проверяет включение отсортированных наборов. В рабочем вызове первым операндом выгодно передавать Provides: исходный код кэширует прежде всего его декодирование. (переформулировать в сторону кэш есть только для) (сказать про подсёт bpp и Mshift на стороне)

3. Разбор исходного кода

Работа началась с изучения примерно десятилетнего lib/set.c. Код оказался большим по объёму и очень плотным: объединённый Base62/Golomb-декодер, таблица всех пар входных байтов, макросы состояний, прыжки по массиву через defined инструкции и подобие LRU-кэш. Отдельно были прослежены реальные точки вызова в rpm и rpm-build: во время сборки бинарник mkset создаёт строки, а rpmsetcmp() через rpmRangesOverlap() участвует в проверке зависимостей RPM и APT.

Результатом этого этапа стала документация: описание главных пяти функций API, формата строки, кодирования и декодирования, нормализации bpp, кэша, макросов сравнения и встроенного SELF_TEST. Таким образом, прежде чем менять алгоритм, для него была построена читаемая модель и зафиксированы его неочевидные инварианты.

4. Переписывание и последовательные оптимизации

Сначала алгоритм был перенесён в Python как понятная проверочная реализация. Затем появился читаемый C-вариант, а после него - оптимизированный set9.c, сохраняющий старый wire-format и публичный API. В нём были опробованы: (добавить про все промежуточные тоже)

• строковая арена вместо отдельного выделения памяти под каждое имя;
• qsort() для малых наборов и radix sort для больших;
• потоковое кодирование и декодирование без промежуточных массивов битов и дельт; (было и в оригинале, но не было в читаемом)
• два раздельных bucketed LRU-кэша для Provides и Requires; (теперь даже LRU, нет постоянных realloc)
• кэширование результата понижения bpp; (надо лучше вспомнить разницу)
• более простой адаптивный поиск включения в отсортированных массивах;
• явная проверка метаданных, размеров и кодов внутренних ошибок. (в оригинале по несколько раз)

Не все «читаемые» замены оказались быстрыми. Удаление специальных оптимизаций исходного файла замедляло обычные APT-сценарии примерно в 2–3 раза. set9.c вернулся к уровню оригинала и в проведённых симуляциях оказался быстрее/медленне него примерно на 1–10%, однако отдельный анализ показал, что старый слитый декодер и прыгающий проход по массивам всё ещё сильны. Поэтому был собран гибридный set_frank.c: новые структуры, encoder и кэш соединены с декодером и сравнением из исходного set.c. (сказать, что прироста не сильно, читаемость хуже, проверить реальные числа)

5. Как проверялись изменения

Тесты строились вокруг инвариантов формата: (логично, его и надо сохранить)

• исходный SELF_TEST и расширенные проверки публичного API;
• побайтовое совпадение результата set_fini() старой и новой реализации для bpp=10…32; (уточнить, что на ранд данных)
• дифференциальные случайные тесты равенства, включения, несравнимости и обоих направлений сравнения;
• повреждённые строки, граничные bpp/Mshift, разные точности, заполнение и вытеснение кэша;
• проверки освобождения памяти; (надо добавить про алгоритм, что этого не было, хе)
• проверка реальных Provides/Requires из Sisyphus;
• холодные и прогретые микробенчмарки, затем симуляции и настоящие вызовы ALT APT с проверкой одинакового результата.

(более того, потом всё равно предполагается запуск в сборочнице. вроде.)

(куда-то эти мысли про хэш надо впихнуть) Отдельно сравнивались Jenkins OAAT, CityHash и xxHash по скорости и коллизиям на случайных данных и ASCII-строках. Этот эксперимент помог отделить свойства хэш-функции от стоимости остального формата, но простая замена хэша не стала готовым решением: она меняет совместимость строк и не устраняет основную цену декодирования и поиска.

6. Альтернативные форматы и результаты

Параллельно были проверены варианты, не совместимые со старым форматом.

Roaring Bitmap. Создание bitmap могло быть быстрым, но равномерно распределённые хэши плохо подходят для такого представления. Для 1000 символов при bpp=32 строка выросла с 3994 до 19924 символов; холодное сравнение было примерно в 4,5 раза, прогретое - в 76 раз медленнее set9. Zstd уменьшал строку до 14126 символов, но добавлял ещё больше работы при сравнении. Вариант оставлен как отрицательный эксперимент.

Прямой массив хэшей в Base64. Отказ от delta/Golomb ускорял отдельные микротесты: в одном прогоне холодное сравнение занимало 0,87×, а прогретое 0,35× времени set9, при росте строки с 3994 до 5340 символов. Но полный поток реальных пар Sisyphus показал обратное (эту стороны надо добить) - текущая реализация была примерно в 1,4 раза медленнее. На отдельном синтетическом APT-графе resolver, напротив, ускорялся на 7–18%, зато gencaches замедлялся примерно на 12%. Кроме того, стандартный Base64 использует padding = (да, я забыл это пофиксить), который RPM запрещает внутри версии зависимости. Поэтому прямой формат интересен как компромисс между размером и стоимостью декодирования, но в текущем виде не готов заменить set-строки.

Другие направления. Рассматривались отрицательный Bloom-подобный prefilter с обязательной точной проверкой, адаптивный индекс для больших Provides, Elias–Fano и глобальные идентификаторы символов. Общий вывод: (в это возможно стоит углубиться и сделать его)

7. Итого

Суть работы была в понимании "магии" кода. Сначала были восстановлены назначение, формат и реальные пути использования; создана документация и читаемая реализация; после этого каждая оптимизация проверялась на совместимость, безопасность и скорость. Эксперименты показали, что код содержит оправданные низкоуровневые решения, а локально более простой или быстрый формат не обязательно выигрывает на полном потоке RPM/APT (still check). Наиболее практичное продолжение - (что-то)