Аксёнов вещает

Давно и упорно утверждаю, что даже "сложные" структуры данных это базово запредельно просто, типа как полнотекстовый индекс в одну строку. Недавно сделал доклад "Про базу векторных баз", там утверждал это про векторные индексы, что это тоже одна строка. Неясно, насколько слушатели мне поверили. Поэтому хоп, даешь доказательства моих дерзких тезисов! Итак, вот вам работающий HNSW индекс в 1 (одну) строчку кода.

using Hnsw = vector<vector<vector<int>>>;

Конечно же, это только данные. Но! Их таки вполне достаточно. Реализация кода, те. вполне себе честной функции поиска тоже махонькая и занимает чуть меньше 60 (шестидесяти) строк. Это вместе с пустыми строками, комментариями и всякой скучной обвязкой. Ключевая часть при этом занимает меньше 20 (двадцати) строк. С небольшими изменениями вставлю прямо сюда.

auto Visit = [&](int slot) {
    if (!visited.insert(slot).second)
        return;
    float d = distance(query, vecs[slot]);
    cands.push({ d, slot });
    results.push({ d, slot });
    if (results.size() > ef)
        results.pop();
};

Visit(entry);
while (!cands.empty()) {
    Match top = cands.top();
    if (results.size() >= k && top.dist > results.top().dist)
        break;
    cands.pop();
    for (int nb : nodes[top.key][0])
        Visit(nb);
}

И ВСЁ. Это буквально весь векторный поиск на базовом слое (слово NSW). Иерархичность (букву H в слове HNSW) и некоторую скорость добавляют ещё 20 строк выше, но для поста это уже перебор. Смотрите исходники! https://github.com/shodanium/tg/blob/main/hnsw/hnsw.cpp#L35 Я не удержался и даже в эту реализацию вставил пару мини-экспериментиков под #if 0, но суммарно всё равно получилось менее 200 строчек. Из которых самое мясо SearchHnsw(), повторюсь, менее 60 строчек. Дальше сильно упрощать и уменьшать не получается, читаемость страдает. К чему я это всё? "Сложные" структуры - это просто. Нередко хватает одной строки. Да и код к ним - тоже несложно. Нередко хватает сотни. Берите код, изучайте, играйтесь, и главное - не бойтесь "сложного", оно не такое уж сложное! Код вот https://github.com/shodanium/tg/tree/main/hnsw, слайды вот https://github.com/shodanium/tg/blob/main/slides/cf2026vecdb.pptx, специально к вечеру пятницы ;)

Закрою тему рандома. Сорян, дальше поинтереснее будет пост (уже готовлю его), но чота нимагумалчать. Вот так в прошлом посте (если его расшифровать) выглядел "ну какой-то" ГСЧ покороче.

unsigned int x = 1;
unsigned int rnd32() {
  return x = (x * 9973) ^ 97;
}

Вот так делается вполне приличный ГСЧ по кличке MWC128. Говорят, с периодом 2^127, проходит примерно все разумные тесты, итп.

__uint128_t cx = (((__uint128_t)1)<<64) + 12345;
uint64_t rnd64() {
  return cx = __uint128_t(0xffebb71d94fcdaf9) * uint64_t(cx) + (cx >> 64);
}

А вот так выглядит приличная хэш-функция FNV1.

unsigned int fnv1(const char * s) {
  unsigned int x = 0x811c9dc5;
  while (*s)
    x = (x * 0x1000193) ^ *s++;
  return x;
}

Совпадение?! Разумеется, нет. "Умножить стейт на простое число и прибавить" (ну или поксорить) это отлично известная классическая техника перемешивания бит, в части генераторов случайности она называется LCG, Linear Congruential Generator. От своей древности, как и теорема Пифагора, она работать ни разу не перестала. Для хэш-функции мы ксорим очередной входящий байт; для годного генератора случайных чисел верхние биты стейта; для короткого "просто" какую-то константу. Смысл-то не меняется: перемешиваем биты изо всех сил. И да, все числа 9973, 0x1000193 и 0xffebb71d94fcdaf9 это специально подобранные простые числа. Теперь из прикольного должно стать очевидно, как нагольфить еще 3-4 байта в k1249.cpp! Правильно, верно, всего лишь заменить константы 9973 и 97 на какие-нибудь ещё покороче, типа 97 и 5 или даже просто 7 и 5. А из полезного... MWC128 в одну строчку так-то уже считаю полезно. Но остро не хватает ссылки, откуда я покрал этот MWC128 (а язык Rust покрал свой SmallRng). Там ещё много интересных генераторов, обсуждения теории, итп. Вот она: https://prng.di.unimi.it/

...а рендерит этот код вот такое вот. Мягкие тени! DOF эффект! Неизменно круто :)

А вот было/стало

Оптимизируем код под упоротое. Под площадь визитки!!! Опять набрел на мега-рейтрейсер имени Andrew Kensler, и на этот раз залип. Стало интересно, сумею ли уменьшить. Немного сумел, сделал за вечерок из 1317 исходных байт свои 1249 байт, что для code golf вроде неплохо. Особо порадовало, что из 35 строк сумел сделать 33 строки (сохранив исходную ширину 39 символов). Весь код тут, скриншоты кода было/стало пониже. Основная экономия, как полагается, макросами и дедупом кода. Но случился и один интересный моментик, кратко раскрою! В оригинале случайное число от 0 до 1 генерируется вот так.

#include <stdlib.h>
f R(){return(f)rand()/RAND_MAX;}

Получилось сэкономить тут и символы и строчки, переделав генератор вот так.

i u=1;
f R(){return((u=u*9973^97,u>>8)*6e-8+.5);}

Для практики, понятное дело, это неприменимо (но кстати, и качественные RNG делаются компактно), однако для code golf развлечений вышло забавно.

Сколько стоит мьютекc? Вопрос, на который удивительно часто рассказывают, эээ, очень странное. Про мьютекс нас всегда интересует предельный, худший случай. Это когда на нем большой contention, во много потоков. На практике мы просто запустим какие-нибудь хотя бы 8 потоков и померим, что получилось. А перед этим глянем в теорию, сколько должно быть? Взять и отпустить мьютекс это базово всего лишь пара синхронизированных операций с памятью, они сегодня стоят порядка 20-50 тактов, возьмем 50-100 на обе. Частоты ядер сегодня порядка 2-3 ггц уж всяко, а бывает и больше. Итого ожидаем порядка 20-60 млн пар lock/unlock. И больше! Что видим на практике? Тяп-ляп бенчмарк в самолете показывает почти 80 млн на макбуке M4.

shodan@shodan-air tg % cc -O2 -lstdc++ mutex01.cpp 
shodan@shodan-air tg % time ./a.out
total 78227016
./a.out  0.67s user 4.89s system 546% cpu 1.017 total

Код тут: https://github.com/shodanium/tg/blob/main/mutex01.cpp Итого мьютекс сам по себе операция, мягко говоря, нестрашная. 80 миллионов раз в секунду взять и отпустить успеваем! Да, без какой-то существенной полезной нагрузки. Но это значит, что даже и с ней про довольно высокие уровни типа 1 млн локов в секунду можно особо не думать, тк. это порядка 1% процессора. С такими бодрыми темпами понятно, что не очко обычно губит критично практически всегда другое. Ни разу не сам мьютекс, а код под ним (“критическая секция” называется). Всего 1 мсек под локом и оп, наш 1 млн операций уже потребует 1000 сек, а не 0.01 сек. Ну да, много делать под локом не надо, это и так все знают. …А что бояться локов самих по себе не надо, и что короткоживущие мьютексы это настолько быстро, не все. Самые лютые гипотезы, которые я слышал, промахивались даже не в тыщщи раз 😜 Ну, вот вы теперь точно знаете, а я протестировал формат написания тяп-ляп-микропоста за полчаса в самолете 😀

Хоп, внезапно (нет) вещаю про всё подряд в рамках АвиТолк! https://www.youtube.com/watch?v=WSq48_EY9g4

...Вот, в чем заключается суперхак. Суперхак = кусочная интерполяция + ловкая суперскалярность. Идея-раз! А давайте честно считать деления только 1 раз на 16 пикселов. Оказывается, этого хватает, чтобы текстуры не плавали. Хоп, дорогущих делений теперь кратно меньше. Идея-два! А давайте присядем на суперскалярность. Именно Pentium научился параллельно (!) запускать FPU инструкции и обычные целочисленные инструкции. Пока следующий FDIV запущен в обсчёт, мы блок из 8 точек покрасим, например. Строчки L383..L456 именно это и делают. Хоп, дорогущие деления теперь считай бесплатны. Просто. Красиво. Иии... до сих пор актуально. Разумеется, такое применение для текстурирования уже давно мертво. Однако обе идеи отлично живы, ещё нас всех переживут. Как боевой пример, моя реализация GEODIST() вместо сложной тригонометрии использует именно кусочно-линейную интерполяцию. Годами используется в проде в Сфинксе (точно) и КликХаусе (вероятно), прекрасно работает. За суперскалярность, надеюсь, в 2026 тоже агитировать не нужно. В простейшем случае это банально старый добрый _mm_prefetch() следующего кусочка данных параллельно обсчету текущих. Тоже прекрасно работает. ...а я нет, а я канал завёл, а пишу преступно редко!!! Но вот, пытаюсь исправиться 🤪

Прорывной графон, улёт башки!!!

...Спрятан хак примерно вот здесь, в дебрях отрисовки, и разобраться в этой тыще строк асма непросто. Вот какой вывод мы должны сделать из "x86 assembly-language horizontal 8-bpp span-drawing code, with 16-pixel subdivision"? Правильно! Верно! Ну совершенно ведь очевидно, что тут у нас inner loop самого главного и тормозного куска: прорывного рендера с текстурированием и перспективной коррекцией!!! 30 лет назад Quake был прорывом: можно как угодно вертеть башкой! Освещение не однотонное! Полностью 3D мир, а не одни вертикальные стены! Текстуры каким-то чудом не плывут! И при этом FPS дико бодрый! "Перспективная коррекция" это как раз "чтобы текстуры не плыли" и есть. Треугольники обычно рисуются как? Берем 3 вершины, проецируем их на экран, бежим построчно "по Y", считаем начало/конец каждой строчки (спана) пикселов "по X", закрашиваем строчку, готово. При закраске текстурой нам нужно текстурные координаты (U,V) для каждого экранного пикселя посчитать. Математически честно они считаются так.

// compute next (u,v)
s += ds;
t += dt;
z += dz;
u = s / z;
v = t / z;

// paint
*pixels++ = texture[v][u];

Сегодня GPU такое считают сами, аппаратно и быстро. Тогда все делалось на CPU, и деления это было очень, ОЧЕНЬ дорого. На Pentium они подешевели, FDIV стал всего 19 тактов, ещё на 80486 был 73 такта. Можно схалявить, убрать деления совсем и тупо лерпить (U,V) по всему треуглу, но тогда характерно "поплывут" текстуры. И да, во многих играх того времени они и плыли! Но не в Quake, несмотря на умопомрачительные 30 fps на Pentium-133. Умножаем 19 тактов на 320x200 пикселей (экраны тоже были не очень) на 30 fps... ой, это ж 37 млн тактов/сек на одни лишь деления. А у нас всего 133 млн тактов/сек, а кроме "просто" рендера пикселов в игре ещё гора всякого есть. И несмотря на эту кажущуюся техническую невозможность, Quake бегает и бодро. И текстуры не плывут, вот прям идеально всё выглядит. WHAT SORCERY IS THIS?! 🧙‍♂️

Внезапно, ретро-оптимизаций пост! Про один незаслуженно малоизвестный суперхак из Quake. Все, разумеется, знают известный 1/sqrt(x) хак из Quake 3. Красивый, лаконичный, очень прикольный. Но честно говоря, устаревший почти сразу. Сегодня про другой суперхак, имхо более важный. Который а) сделал Quake 1 вообще возможным; б) вдруг актуален до сих пор; в) применим не только в играх. Этот видать антисексуален; вот никто и не пишет. Но я совершу ошибку начинающего, ловите лонгрид!

Хоп, внезапно (нет) вещаю голосом про хэш-таблицы!! https://t.me/podlodkanews/1699

Пару месяцев назад Зверович (автор fmtlib) придумал Zmij, более быстрый метод печатать float в строчку. По бенчмаркам выходит 3.5x быстрее std::to_chars() и 1.7x по сравнению с предыдущим лидером Dragonbox. Код пока не затащен в fmtlib, но уже доступен. Кому и зачем важно? Только для массового экспорта float в текст, но там прям критично. Например, выгрузка в виде текста всего лишь 1M всего лишь 256D векторов упирается именно в эту float2string конверсию.

Привет, меня зовут Андрей. Я строю движки и команды. Тут хочу писать про технохардкор, разработку, немного менеджмент. Плюс шитпостить, конечно! Для незнакомых чуть подробнее. Андрей Аксёнов, сделал движок/базу Sphinx, 100+ докладов на конференциях, и ещё много чего. Сегодня работаю в бигтехе на букву А (тут std::disclaimer), руковожу Инфраструктурой Поиска.