Чайник из Юты

я хрюкнул

гемини

Тот факт, что между нейронками и компрессорами больше общего, чем может показаться - забавляет меня больше всего. Мой дед бы охуел. Задумайтесь!

Конечно, они сравнивали со средненькими классифицирующими моделями. Там есть пространство для тюнинга и получения доминирующей точности, но тогда не было бы кликбейта.

И это всё ещё классификация без обучения. Для вообще любого языка.

GZIP наносит ответный удар

Вот мы хотим классифицировать текст. Классическая задача для ML. Поэтому в основном здесь рулят deep neural networks (отныне DNN).

Да, но:
- посчитай миллионы параметров
- поднеси тонну текста
- поднеси железо
- ой иди нахуй меня на таком не учили

А теперь помните кросс-энтропию? 3b1b видос выпускал. Это когда мы оцениваем, насколько хорошо одно распределение ложится на другое. А-ля в HPACK у HTTP2 вхардкоженная в стандарт таблица Хаффмана, строили по типичным для протокола сэмплам. А теперь представьте таким какой-нибудь бинарный код или кириллицу сжимать. Не-алфавитные символы в той таблице по 30 бит занимают, если что.

Ну так вот, какой-то чувак построил флоу-чарт, какие языки из каких происходят, и он даже был достаточно точным. Но вы щас будете ржать

Он просто брал тексты на одном языке, прилеплял к ним тексты на другом, и смотрел, как хорошо gzip это сожмёт.

Идея такая: чем ближе языки, тем ближе будут их распределения - похожие слова, похожие слоги, и прочие филологические говны.

В 2023 выходит интересная бумага. Даже не потому, что в ней буквально 5.5 авторов, из которых трое с очень китайскими фамилиями, и не менее американскими именами. А потому, что они gzip'ом тексты классифицируют.

И классифируют охуенно, при том. Делают буквально так же, как и с языками - склеивают два текста и смотрят, насколько хорошо оно пожалось.

Правда, интуиция тут немного другая. Энтропия по Шеннону - классическая теория информации - это скаляр от распределения. А есть её обобщение - сложность Колмогорова, она же алгоритмическая энтропия, она же да дохуя имён там. Она определена, как минимальная длина программы, способной воспроизвести данные целиком. В оригинале - программа для машины Тьюринга.

В таком обобщённом определении, сложность Колмогорова невычислима. Но ведь никто не мешает взять что-нибудь попроще, чем МТ?

Есть класс grammar-based компрессоров, например. Они пытаются построить грамматику текста, которая и выступает программой. Тогда всё становится возможным.

Вот и мы возьмём C(x) как аппроксимацию. Пусть она возвращает длину сжатой строки x.

Собственно, теперь нам остаётся взять информационное расстояние между двумя текстами. Китаймериканцы представили Normalized Compression Distance, определённую как

NCD(x,y) = (C(xy) - min(C(x), C(y))) / max(C(x), C(y))

(простите, у меня пока нет према, чтобы в латех писать)

Интуитивно - мы просто считаем, насколько хорошо тексты пожались вместе относительно того, как они пожались по-отдельности. Чем лучше компрессор, тем лучше аппроксимация, и тем точнее классификация. Из промышленных - точнее всех gzip, оптимальней всех zstd.

Собственно, вот и всё. Берём референсы (классы), и смотрим, к какому из них текст ближе всего.

Важное замечание - идея не новая, просто раньше брали датасет, и все сэмплы из него конкатенировали в один большой документ. И дальше уже считали, насколько конкретный текст близок к этому документу. Это, конечно, быстрее на маленьких выборках, но с большими - как вот YahooAnswers - работает весьма хуёво. Во-первых медленно, во-вторых компрессор тогда не в состоянии выудить из этого все преимущества выборки. Окно компрессора маловато.

Зато способ с попарным сравнением текста с каждым сэмплом датасета охуенно профитирует.

Для тестов взяли выпуски новостей. 7 in-distribution и 5 out-of-distribution датасетов - разница в том, что DNN в сравнениях обучали на первых семи, а остальные пять в выборки не входили. Это всякие филиппинские и хуй-выговоришь новости. И в результате...

...NCD был на уровне нейронок в in-distribution новостях. А out-of-distribution рвал, потому что компрессор в целом data-type-agnostic. Даже когда нейронки слегка пре-тренили. Ему поебать, если вы ещё не поняли. Он хоть самобытный диалект с 40 носителями пожмёт и сделает это с гордостью.

Так ещё и экологичнее, потому что видюхи ненужны. Нет, они реально об этом в бумаге написали.

Я на матфак вступил

В мире меча и компляторов!

https://github.com/xoreaxeaxeax/schrodingers-toctou



TL;DR Когда мы скомпилируем что-то эдакое:

unsigned int g(unsigned short *p) {
  short t = *p; //copy *p into a local for safekeeping
  return (unsigned short)t - t;
}

мы в ассемблере (arm gcc 14.2.0, -O2) можем вполне себе увидеть:

g:
        ldrh    r2, [r0]     # load *p, once
        ldrsh   r0, [r0]     # load *p, twice
        subs    r0, r2, r0
        bx      lr

одно чтение стало два!

Собственно, размножение почкованием доступно потому, что абстрактная машина С считает, что память между двумя чтениями не изменится. Invented load называется.

Да вот незадача.

if (sh->len <= 20)  // CHECK reads shared->len
    // ** attacker modifies shared->len **
    memcpy(out, sh->data, sh->len);  // USE reads it again: buffer overflow

Неатомарненько выходит. Там аж PoC в репозитории есть.

При том подвержена куча компиляторов на куче таргетов. Как на -О2, так и на -О3.

Сложно винить сами компиляторы - в них длиннющий пайплайн с кучей стадий, вот и неудивительно, что такое на выходе. Но в то же время они и виноваты, потому что написали-то нормально.

Можно изъёбываться с барьерами и volatile, но это всё не убивает проблему на корню. Volatile, например, относится к lvalue, тот же memcpy квалификатор не сохраняет. Тогда оверфлова просто закапывается чуть ниже. А барьеры нередко стоят не там, где надо.

Даже деды хуесосят комитет С, по этому и не только по этому поводу. В половине случаев, правда, дед вполне себе конкретный - начинается на Л, кончается на инус Торвальдс.

Ёжик плакал и кололся, но на С писать не переставал.

https://pubs.acs.org/ancac3/article-abstract/14/1/21/602927/Will-Any-Crap-We-Put-into-Graphene-Increase-Its

„We added shit to graphene“

И немного про bump-аллокаторы

А теперь к непосредственной теме. Проще всего, естественно, сделать отдельную аллокацию под фрейм и оставить его в "копилочке" соответствующему обработчику (будь то поток либо горутина). Но я слишком аутист, чтобы столь осквернять дух машины.

Спустя добрых пол года размышлений, я пришёл к старому-доброму bump-аллокатору. Это я просто аллоцирую одним махом буфер на добрый мегабайт и больше его не дрочу. Сим я эксплуатирую demand-pages - виртуальные страницы маппятся в физическую память только тогда, когда мы туда что-то пишем. Вот поэтому какой-нибудь хром и может выжирать сотни гигабайт виртуальной памяти, умещаясь при этом в 6-8 физических.

Когда я получаю DATA-фрейм, я сначала проверяю, а не готов ли обработчик прям щас его забрать. Если да - я ему передаю владение над подключением. А если нет - то я прибавляю счётчик сохранённых фреймов, кладу обработчику в копилочку вычитанные данные (сырыми, как есть - он потом сам разберётся). И ухожу вправо, чтобы продолжить читать.

То есть у меня один гигантский буфер для чтения, и если надо что-то сохранить - я просто смещаюсь от начала, чтобы не затирать предыдущие чтения. Бесконечно так делать я не могу (память кончится). Особенность bump-аллокатора - он не умеет разрешать фрагментацию. Вообще. Если даже в самом начале есть свободный участок, который подходит идеально - нам придётся потом снова бампить и идти вперёд. А впереди самая старая аллокация, субоптимально. Исправляется скрещиванием с какими-нибудь свободными слотами, но в моём амортизированном случае - на самом деле, это просто моё предположение, автоматически верное по праву единственного пользователя - фреймы должны быстро вычитываться.

Поэтому - аллокатор возвращается писать в самое начало, только когда количество непрочитанных записей становится равным нулю. Нужно гарантировать, что впереди от аллокации вот вообще ничё нет. Пусто как в голове с похмелья.

Выходит такой интересный мемори футпринт. Активно-используемая память буфера прыгает к какой-то отметке, и остаётся там. Через некоторое время вернётся в самое начало. Примерно как этот ползунок в ВинАмпе, в котором частоты прыгали, и оставляли след на некоторое время на максимальной отметке.


Если интересно, то пролистайте ещё вот эту статью, где буквально тот же аллокатор делают для игрушечной ОСи. Надеюсь, ни Раст, ни запах в комнате вас не вспугнёт.

Немного про HTTP/2

Я самое интересное забыл! Но сначала всё-таки введение в окна.
TL;DR - если разгерметизировались, то лучше поменять, теплопроводимости пизда.


В HTTP/2 есть connection/stream windows. Connection window я буду называть глобальным, не с вашего позволения.

Семантически это то же самое, что и окна в TCP подключениях - ты перестаёшь слать данные, когда этосамое окно переполняется. Удалённый пир сам тебе говорит, сколько байт он обработал. Это для того, чтобы избежать заторов - congestion - когда ты продолжаешь насыпать, пока пир ахуевает и не может ничего принять.

Фанфакт: этот механизм появился ещё пол века назад, в стенах внутренней сети Форда. Там из-за того, что пиры не успевали обрабатывать объёмы принимаемых данных, начинали жутко дропать все входящие пакеты, и по итогу сеть выхуевала ретрансмитами. Порой вообще падала.

В HTTP/2, из-за мультиплексирования внутри одного подключения, пришлось переизобретать окна по второму кругу. Теперь у каждого стрима есть своё собственное окно, и одно глобальное на целое подключение. Нахуя глобальное нужно - вообще без понятия, но скорее всего, чтобы им можно было отключать per-stream окна. Последние были изобретены ради DATA фреймов (ими тело перекидывают).

Потому что! HTTP/1 болело Head-of-Line блокировкой. Это значит, что пока текущий запрос не завершится, другой ты хуй начнёшь обрабатывать. Ради этого браузеры даже по нескольку подключений открывали (по-умолчанию до 6 на домен, domain sharding звётся, писал тут). Хром сходу два открывает.

Ровно для этого и породили стримы. Потому что несколько подключений нахуй не надо (а ещё их количество часто и щедро режет файрволл). Ну и в дополнение можно сильно лучше сжатие заголовков HPACK производить. Но вот представим: мы шлём сразу два POST-запроса одновременно. Обработчик может начать втыкать перед тем, как непосредственно начать обрабатывать это тело. Это значит, что всё подключение блокируется, пока этот далбаеб не начнёт работать. Connection stalling - очень такая себе штука, особенно если в этот момент прилетает PING (им обычно RTT замеряют или в подключение палкой тыкают, а-ля кипалайв).

Решение - DATA-фреймы нужно куда-то откладывать, чтобы пайплайн не вставал. Собственно, для этого и есть окна. Per-stream окна, видимо, добавили с расчётом на то, что кто-то додумается каждому обработчику индивидуальную складскую коробочку выделять.

Естественно, per-stream окна можно вполне спокойно отключать. Нужно просто сделать его равным глобальному окну. А для глобального окна можно просто гигабайт въебать. Так, например, делает фейсбук (только у них почему-то гигабайт без одного байта. Мелочные люди.)

https://github.com/xoreaxeaxeax/skitter-creek-bath-salts

На фуфыксах времён PS4 и Xbox One можно было ебануть swizzle-mode доступа к памяти, благодаря чему вся безопасность успешно наёбывалась. Можно даже микрокод проца и fTPM вычитать

А, про mark-sweep. Я удивился, когда оказалось, что это просто обойти весь граф и повыставлять флаги, а потом освободить всё то, где флаги не выставились. Теперь стало интересно, что Боем такого на этом изобрёл, что его аж в Гугл калькулятор разрабатывать взяли

В мире аллокаторов: glibc, схемы и стратегии

glibc's malloc интересен. В основном тем, что концептуально это практически тот же dlmalloc, но в гораздо больших масштабах. Во-первых, у них есть thread-local tcache, чтобы не соваться в глобальные арены с их нагруженными локами. Тут аллокации происходят по segregated free list схеме - о ней см. ниже. Если тут ничего нет, мы идём тогда в fastbins - single linked lists чанков по их size-классам. Интересная штука, что когда они освобождаются, то они не объединяются сразу в большие сегменты. Ну, когда-нибудь, когда аллокатор решит консолидироваться - но не сразу, как в dlmalloc.

Если и там ничего не нашлось, тогда уже идут smallbins (полностью соответствущие таковым в dlmalloc) и largebins. Largebins заменили treebins в угоду перфоманса, вместо дерева они заделаны на двойном связном списке. Тут, помимо указателей на предыдущий и следующий узлы, ещё лежат их размеры. Ещё одно отличие от dlmalloc, кстати, что здесь никто не будет разбивать больший блок - идут просто по минимизации остатка.

То есть, glibc идёт всё дальше и дальше, пока где-то не найдётся местечко. Но первым делом он всё-таки не в tcache идёт, а в unsorted bin, куда скидываются все недавно освобождённые джанги. Правда, оттуда берётся сегмент, только если он идеально по размеру подходит.

Вот такой вот зверь.


О, фанфакт. У best-fit даже есть антонимическая пара - worst-fit, который пытается всегда в наибольший блок засунуть. Справляется, к слову, соответственно названию.

Коль уж речь зашла, фитов вообще до пизды. Но конкретно все эти - best-fit, first-fit (в первый попавшийся), last-fit (в последний попавшийся), next-fit (начало поиска там, где в прошлый раз кончили) - относятся к схеме sequental fits. Потому что друг от друга отличаются, как пригожин в париках. Есть, конечно, и другие схемы:
- segregated free list - список из очередей для разных size-классов, в каждой очереди свободные слоты, почти как treebins;
- buddy systems - как предыдущий, только хип размечается экспоненциально - делим пополам, вторую половину снова делим пополам, и так пока не усрёмся; фрагментация ебейшая, без героических оптимизаций и/или гибридизации сосёт;
- indexed fits - в сущности обычный sequental fit с индексирующей структурой данных - фактически этим treebin и является;
- bitmapped fits - битмапа, где каждый бит соответствует статусу сегмента фиксированной длины;

Последнее - прикольная, но ненужная вещь, GP аллокаторы его не имплементируют, потому им он, видите ли, медленный. Я пытался себе для HTTP2 его переизобрести, но в результате нашлась опция получше. Зато прекрасно применяют в mark-sweep сборщиках мусора.

Но сразу говорю, делить по схемам - дело гиблое. Как минимум, даже dlmalloc сел минимум на два стула, а glibc-шный это вообще ядерный микс из четырёх аллокаторов, где один из них вообще сразу две стратегии объединяет.

Так что, как обычно, практики наложили себе в руки, как только увидели, что наизобретали теоретики. Всё-таки скорее инженерное нежели математическое это дело, программирование.



Между делом: когда ресёрчил, то внезапно оказалось, что заголовки динмассива по-умному называются dope vector. Почему не метадатой назвать? А хуй его, гуси еблись, а информатик слово придумывал. Но это ещё ладно. Знаете, как указательная арифметика для адрессации массива называется, которая offset + index*sizeof(T)? Dead reckoning. Википедия ведёт вообще на линейную интерполяцию ИЗ НАВИГАЦИИ. БЛЯТЬ.

В мире аллокаторов: dlmalloc

У меня хобби такое, аллокаторы переизобретать.


Аллокаторов вагон, маленькой тележкой занимаюсь пока я. Практически у каждой программы свой уникальный паттерн мемори-менеджмента. Некоторым нужно аллоцировать очень много маленьких объектов (как вот питон), некоторые жрут килобайтами (как вот компиляторы). Ясен хуй, каждый из кейсов накладывает свои ограничения, вокруг которых можно чуть эффективнее играться. Пускай это будет некий оптимум. Даже general-purpose аллокаторы блуждают вокруг чутка разных усреднённых оптимумов - скорость, фрагментация, thread-safety. По хорошему, конечно, и их тоже под задачу выбирать надо. Как жаль что поебать.

Есть сегмент памяти, у нас там 4 объекта живёт. Скажем, два посередине освобождаются, и у нас остаётся два свободных блока - и два занятых по краям. Нам бы эту память посередине переиспользовать, но аллокатор-то не может знать, какого размера будут новые объекты. Это называется coalescing (объеденить два маленьких сегмента для одного большого объекта) и splitting (разбиение большего сегмента для объекта поменьше).

Вот сначала и был dlmalloc, отец ptmalloc и дед glibc's malloc. О нём и поговорим.

Его инвариант - не может быть двух соседствующих свободных блоков. То есть, занято-свободно-занято-... идёт в строго шахматном порядке:

chunk A | FREE | FREE | chunk B
               ↓
chunk A | LARGE  FREE | chunk B

Но устроен он интереснее. У него есть отдельные корзины (bins) для маленьких <256 байт объектов, и отдельное бинарное дерево для >256 байт (но меньше 256 килобайт). Логика такая: оверхед 8 байт для аллокации на 40 байт это дохуя. Оверхед 10 килобайт для аллокации на 400 килобайт - это норм. Сами smallbins - это просто double linked-list, при том зацикленные. Их 28 штук, на каждый (разумный) size-class. В неаллоцированных и лежат как раз указатели на предыдущий и следующий узлы, пока они не будут выделены и их не перезапишет программа своей хуйнёй. На них есть своя лукап-таблица на 32 вхождения, поэтому выделение маленьких объектов пиздец быстрое и константное.

Бинарное дерево у них называется treebin (видимо чтобы не путать). Это, ну... Просто бинарное дерево, самое обыкновенное. Правда, они тоже делятся на size classes, только тут они уже очень широкие и идут по степеням двойки (каждый следующий size class range экспоненциально больше). Подходящий блок внутри них ищется по стратегии best-fit, то есть куда аллокация лучше всего влазит. Правда, с небольшой девиацией - обычно best-fit выбирает свободный блок, который максимально близок по размеру к запрашиваемому. Но тут, если для 380кб аллокации будут претенденты 400кб и 900кб, то выбор падёт на последнего - потому что после него останется 520кб дура. Аллокатору такая идея нравится больше, так как можно будет ещё один здоровый кусок нормально туда уместить. Его стратегия вообще agressively coalesce:

We don't know the future, so use a generally robust policy: coalesce aggressively, preserve large holes by best-fit for larger allocations, and use fast size classes/locality heuristics for small allocations.

Этим-то он и отходит от теоретического best-fit.

'I NOTATION POLISH REVERSE ❤️'

rsync in a nutshell

3 месяца назад, 30 лет тому, австралийский национальный университет дропает эту имбу. Алгоритм для модифицирования файла на удалённой машине для соответствия оригинальному. Если по-простому, то переносить диффы. Это если кто до этого про rsync не слышал.

У меня, если что, просто интернета нет. Со скуки нашёл откуда-то бумагу по нему. Вот и пишу теперь с хотспота. А вам читать.


Собственно, диффы. Можно, конечно, и их перекидывать, но есть проблема. Взяли ядро GNU/линукса версий 1.99.10 и 2.0.0, там 32к строк разницы. GNUшный diff выдал выхлопа на 2.1мб. Когда тестили rsync, в среднем там по сети перелетало 1.5мб (рекорд - 1.2мб). Так ещё и пока diff 4 минуты ебался, rsync за 2 минуты отфинишировал. Конкретно здесь - чем быстрее кончил, тем наоборот лучше.

Diff mogged. Особенно учитывая решаемую проблему - синхронизация файлов в условиях сети с высокой задержкой и низкой пропускной способностью.


Задачи выплёвывать человекочитаемые диффы не стояло, поэтому алгоритм прост как три пизды: есть компьютер А, есть компьютер Б. Компьютер А держит оригинал, Б хочет синхронизироваться. Недофайл, который лежит на Б, делится на блоки по S байт, для каждого считаем rolling checksum и MD5 хэш*. Они парами отправляются компьютеру А. Дальше А умным образом смотрит у себя, что из этого всего у него есть, и отправляет обратно Б инструкцию, что и куда записать, чтобы получить копию.

*в оригинальной бумаге используется MD4. MD5 вышел в 1991, а бумага по rsync - в 1996. Скорее всего, выбор был сделан на основе перфа - MD4 быстрее, а MD5 сильнее криптографически. Может, последний и правда уменьшает риск коллизий, ака ПОВЫШАЕТ ЭНТРОПИЮ. Тогда переход имел смысл, как только компьютеры стали шустрее калькуляторов из Техаса.

Ну так вот, умный образ. Он классный. Компьютер А проходится по всему файлу, и для каждого оффсета считает rolling checksum. Да, дороговато, мы пересчитываем чексумму для практически каждого байта в файле. Но это простенькая 32-битная чексумма, похожая на adler-32, и она определена, как взвешенная сумма байт. Поэтому, чтобы посчитать чексумму для следующего оффсета, из неё достаточно просто вычесть первый сумманд и прибавить новый. Таким образом и выходит быстро и дёшево пробежать по всему файлу и найти все блоки S байт, которые соответствуют оным в наличии у Б.

Естественно, это слабая чексумма. Я где-то оставлю документ, 3 раздел о ней. Но сила ей и не нужна, для силы есть MD5.

А дальше начинается самое интересное. Дальше начинается хэшмапа на открытой адрессации!

rsync использует трёхуровневую схему поиска совпадающих блоков. Когда А получает все пары чексумм-MD5, он считает 16-битный хэш от 32-битной чексуммы и сортирует пары, полученные от Б, по этому хешу. Получается хэшмапа на 2^16 слотов.

Вот и выходит: когда А считает чексумму, он сразу берёт от неё хэш и идёт в мапу. First-level check - проверка на то, что с таким хэшем вообще не-нулевой слот. Потом линейно ищется слот со совпадающей чексуммой - это second-level check (до тех пор, пока хэш чексуммы не перестанет совпадать с посчитанным). О мапах на открытой адрессации я подробнее здесь писал.

Когда находится совпадающая чексумма, наступает очередь считать и сравнивать MD5 хэши. Если ещё и он сходится, то тогда уже А выдает инструкцию Б записать данные от предыдущего мэтча до текущей позиции в файле - это данные, которых у Б нет. За ними следует индекс блока, который у Б есть. Чем-то на LZ77 похоже.

А главное - это работает хорошо для практически-идентичных файлов.

Под постом оставлю сниппет с псевдокодом на расте, как примерно устроена вся эта эпопея со скользящей чексуммой.