Не зря делал, наверное

Как напоминание всплывает

Может, я чего-то не вдупляю, но эти 32 октета - ни в пизду ни в сраку. Нахуя их учитывать? Они фактически таблицу на 80 байт превращают в 16, при том максимум вмещая всего 2 вхождения, третье-то уже не влезет. Таблица на 4096 байт вместит максимум 128 вхождений. ПОЛНОСТЬЮ ПУСТЫХ. 64 вхождения, если каждое занимает 32 байта (реальных) - а это не так уж и много, вообще-то. Какой-нибудь куки? Аха, хорошо, это дропнет примерно половину всей таблицы. И похуй, что моя имплементация вообще может вообще всего 24 байта оверхеда на вхождение накидывать.

Ну вот нахуя? Количество вхождений падает обратно пропорционально квадрату средней длины вхождений. Чем тех вхождений больше, тем больше аллоцированного пространства в таблице тупо простаивает.

Я крайне надеюсь, что в QPACK это позорище вырезали. Тем лучше, чем брутальнее.

А, да, HPACK. В HTTP/2 решили, что хорошей идеей будет сжимать заголовки. Что, в общем-то, и правда хорошая идея. Правильная, я бы даже сказал. Чем полагаться на обычные компрессоры, решили сделать лучше - и сварганили свою схему кодирования, гордо именуемую HPACK, и вынесенную аж в отдельный RFC7541 (сам HTTP/2 живёт в RFC7540). Не просто так, кстати: таким образом, они хотели обезопасить шпак от изменений в будущих HTTP/2 RFC. Да и в целом они его максимально негибким сделали, чтобы никто его никак не вертел без того, чтобы новый RFC публиковать. Так и вышло: для HTTP/3 схему всё-таки подкрутили, и опубликовали, как QPACK.

Ну и вот, в HTTP/2 HEADERS фреймах (ну или же CONTINUATION, если же в соответствующем стейте) передаются как раз заголовки в формате HPACK. "Поле", как они называются (решили абстрагироваться от "заголовок"), может быть одно из 5 типов:
1. Полная пара из таблицы
2. Ключ возможно в таблице, значение вот
3. Как 2, только в таблицу не добавляется
4. Как 2, только в таблицу НИ В КОЕМ СЛУЧАЕ не добавляется.

4 - это всякие сенситив заголовки а-ля токены аутентификации. Отличие от 3 в том, что intermediaries (они же всеразличные прокси и их друзья) обязаны также передать этот заголовок дальше, как never indexed.

5. Изменение размера таблицы - не так интересно, опустим.

Углубляться в то, как оно выглядит, я не буду. Для этого я оставил номер RFC🫶

Собственно, таблица, сердце всей схемы. Она делится на две части: статическая и динамическая. Они делят общее индексное пространство, но новые значения добавляются, понятно, только в динамическую. Таблица эта хранит целые пары заголовков - и ключ, и значение. В статической, правда, добрые 2/3 с пустыми значениями, но оно и понятно - они там только ради ключей. Ну, то есть, а хули в качестве значения для cookie давать?

Статическая таблица вмещает 60 пар, индексируется с единицы (потому что индекс 0 зарезервирован для литеральных ключей). То есть, динамическая таблица начинается с индекса 62. Вообще, она сама по себе интересна: при добавлении новой пары, она встаёт в самое начало, т.е. на индекс 62. Все предыдущие, соответственно, сдвигаются на +1. Когда максимальный размер таблицы превышается, самые старые вхождения дропаются до тех пор, пока новая пара не поместится. Попытаться засунуть 10-мегабайтный заголовок в таблицу на 4096 байт это не ошибка, кстати, просто таблица окажется пустой - все старые значения дропнутся, а новое один хуй не влезет. Правда, есть и более гуманные способы её очистить.

Ещё есть забавный момент, потому что ключ новой добавляемой пары может ссылаться на уже лежащий в таблице. И тогда может возникнуть нюанс, что ключ, на который как раз и ссылается новое вхождение, находится в конце и должен быть дропнут. Тогда у нас магическим образом возникает dangling pointer, только dangling index. Тоже об этом в стандарте предупреждают. Слава богу, что мене це не бентежить, я монофаллически держу всё в закольцованном буфере.

TL;DR вышесказанного:
- Статическая таблица по индексу 1-61;
- Динамическая таблица, начиная от индекса 62 включительно;
- Когда в динамическую таблицу попадает новая пара, она занимает индекс 62, остальные смещаются;
- Если добавление новой пары превышает максимальный размер таблицы, самые старые вхождения дропаются;
- Опасно дропать сразу, иначе может произойти жопа;
- Гигантская пара размером больше максимального размера просто очистит таблицу;
- Размер таблицы - сумма длин всех вхождений;
- Длина вхождения - длина ключа, значения и 32. На 32 всё ещё злюсь, из-за них тесты ебливей писать;


А вот что забыл упомянуть, так это опциональное кодирование Хаффманом для литералов. Что ключи, что значения могут быть им закодированы. Хаффман используется со статической таблицей кодов, также представленной в RFC. Естественно, длина учитывает только декодированное ключ-значение.

https://www.securitylab.ru/news/564421.php

Компилятор иногда разбивал корректировку стэкпоинтера в эпилоге функции на две инструкции. Поскольку долгоиграющие функции с 1.14 прерывались насильно сигналом SIGURG, иногда они заставали исполнение как раз между ними двумя, таким образом ломая стэк. Иногда - сегфолт, иногда - само неконсистентность стэка замечало. В 1.25, вроде как, исправили, выполняя операции сначала на временном регистре.

Вроде слабо, а вроде и у чуваков по 30 раз на дню падало. Вот уж соболезную)

https://en.wikipedia.org/wiki/Pentium_FDIV_bug

Сначала припирались, а потом таки согласились менять на исправленные всем желающим. Большие ж бабки потеряли тогда

Случайности не случайны!

В Zen5, тобишь. У них инструкция RDRAND сильно предвзята по отношению к нулю - возвращается в более 10% вызовах, при том с флагом успеха (регистр CF=1). Подозревают, что сам регистр некорректно определяет успешность операции, вот и помечает успешным то, что таковым не является.

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

Кстати, сам рандом они генерируют из тепловых шумов. Интересно, а они тоже просто взяли ринг буфер как пул энтропии?


Актуальный багрепорт + фикс ядра: https://lore.kernel.org/lkml/20251016182107.3496116-1-gourry@gourry.net/
Как это было когда-то: https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/

Кстати, у интела оно интересно устроено. Исходя из вики, они сначала берут сырой поток данных с тепловых датчиков, формируют из них пары по 256 бит и прогоняют через AES. В итоге имеем один монолитный кирпичик 256 бит отменной энтропии, что используется в качестве сида для ГПСЧ (NIST-certified, вся хуйня; правда, называют они его DRNG - digital random number generator). Каждые ~64 килобайта генератор ресидится.

Рядом ещё есть RDSEED, оно использует всё те же тепловые флуктуации, только работает асинхронно (отдельно от основного чипа) с собственной фиксированной тактовой частотой 3ГГц. Медленнее, чем RDRAND, предназначен так же, как и назван - чтобы софтварные ГПСЧ сидить случайными числами произвольной ширины. Что, по всей видимости, и есть ключевая разница от RDRAND, который годится приложениям, которым нужен просто качественный рандом фиксированной ширины.

Правда, состояние генератора они держут общим между всеми ядрами. Ну, то есть, лежит общий некий стейджинг буфер, из которого любой может спокойно читать. И в 2020 году мужики из амстердамского университета показали, что с первой попытки можно целый ECDSA ключ сразу после подписи извлечь, если с соседнего ядра вовремя тот самый буфер почитать. А это - классическая проблема с исполнением недоверенного кода, когда он может что-то пиздить у доверенного соседа. Выпустили заплатку микрокодом, теперь RDRAND, RDSEED, EGETKEY (кто?) выполняются исключительно одним ядром за раз, остальные ждут. Просто по завершению тот стейджинг буфер перезаписывается. Задели целый ряд процов с 2012 по 2019 годы, а фикс, по классике, вкурвил и без того низкий перф (софтварные ГПСЧ кратно быстрее, что удивительно; Mersenne-Twister так и вовсе во все 20 раз).

А ещё Теодор Тсо (тот, который умнее тебя и всей твоей семьи вместе взятой) высказывал сомнения по поводу этой штуки. Мол, интеловцы хотели в ядре продавить свой RDRAND как единственный источник для /dev/random. Что, естественно, а) небезопасно (в том числе благодаря прецедентам с AMD выше) и б) просто стрёмно. Ну, то есть, мы сейчас возьмём и пересадим почти весь серверный сегмент на рандом из впаянного чипа, который никто не знает, как работает, никто не может провести аудит, так он сам ещё и от около-государственной корпорации? Звучит надёжно, наливайте!

Ну, то есть, он используется, как один из источников. Но в 2013 оказалось, что всё сыпется, если туда оказывается посажен бэкдор, нацеленный на конкретный код (маловероятная ситуация, не так ли?). Проблему смягчили (вероятно, снизили общую долю в пуле или подкрутили ϵ, чтобы оттуда более униформные значения лезли; позже и об этом пост будет). Во FreeBSD инструкцию вообще от греха подальше вырезали.


В общем, очередное напоминание, что рандом - это сложно и ответственно, а блэкбоксы - плохо. AMD не хватает побольше тестирования.

Чем дольше всматриваешься в бездну, тем больше Тьюринг-полноты вокруг замечаешь. JustWiFi7 - в свой большой компьютер ты втыкаешь маленький компьютер под линуксом, который крутится на кастомной фирмвари. Теперь линукс запускается ещё и на формфакторе ноутбучной оперативки. Зато блютуз-адаптер на моём линуксе — нет. Этот маленький пидорский кусочек пластика рандомно отъебнул и теперь заводится где угодно, кроме моей машины. Я его матушку.

Калькуляторы - это сложно.

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

Но всё всегда начинается с азов. Ещё 7 лет назад я начинал писать калькулятор, и всё ещё не кончил. Первый раз всегда плох.

Сперва идут три инпута - левый операнд, оператор, правый операнд. Если появится мысль считать многочлены в одной строке - ты попался.
Сначала ты как-то умудряешься доставать одночлены из входной строки с наибольшим приоритетом - и подставлять вместо них результат. Скорее всего - прям в строку.
Происходит эпоха Просвящения - ты узнал про обратную польскую нотацию. Но парсишь всё так же плохо.
Если умный, то быстро узнаешь про алгоритм сортировочной станции, чтобы твои выражения парсить. Вкратце - алгоритм с вхардкоженной грамматикой, зато и вызовы функций умеет, и приоритеты правильно распределяет, да и выхлоп сразу в ОПН. Блажь.
Добавляешь переменные и объявления функций. Простенькая стэковая машинка начинает разлагаться на плесень и на липовый мёд.
Открываешь для себя полноценные парсеры с настоящим AST, как у взрослых дядь. Теперь считать чуть сложнее, но ты справляешься - достаточно тот AST рекурсивно сколлапсировать до единственного узла - результата. Появляются неймспейсы.
На этом моменте, твой калькулятор уже практически полный по Тьюрингу, остаётся только добавить ветвления и векторы. Появление нового типа заставляет тебя задуматься, как складывать векторы с функциями. Это чеховское ружьё.
Рано или поздно, ты всё-таки внимаешь драгонбуку, основе основ всея разработки компиляторов. Узнаёшь про лексический анализ, грамматики, виды парсеров и прочие приятные штуки. Но всё равно ещё долго будешь держаться за привычный recursive top-down, потому что он словно подол материнской юбки посреди толкущейся толпы.

Дальнейшая история здесь расходится на два возможных пути (отступничество не рассматривается):

1. Твой интерпретатор постепенно становится всё более серьёзной штукой с более внятной системой типов (тут-то ружьё и стреляет), со своим байткодом и потенциально IR, и вероятно - со временем даже превратится в компилятор. Тогда у тебя не остаётся вариантов, как вводить строгую типизацию, потому что так банально проще. Ты теперь разрабатываешь полномасштабный императивный язык.

2. Случайно решаешь посмотреть, кто такие лямбда исчисления и кого они считают. Оказалось, твои извилины. Потом будет логика, теория типов и неизбежный пиздинг из Хаскелла, как наиболее продвинутого прикладного типизированного лямбда-калькулюса. Ты теперь разрабатываешь функциональный язык, соболезную.

То есть, из абсолютно тривиальной задачи можно прийти к поистине монструозным результатам. Я себе как-то раз хотел научный калькулятор заделать, чтобы вместо питона его использовать, так столкнулся с контекстно-зависимой грамматикой - в зависимости от типа переменной, одно и то же выражение могло бы означать как применение функции, так и обычное неявное умножение (у которого, фанфакт, приоритет выше обычного умножения и даже деления). Забросил:(

А ведь это всё ещё (практически буквально) детские игрушки. Google в 2014 нанял Hans-J. Boehm, тот, который свой эффективный сборщик мусора написал. И поручили они ему калькулятор для Андроида сделать. И это оказалось настолько сложным, что он попросил помощи у своих коллег. Если вкратце, то от представления рациональных парой числителя и знаменателя он дошёл до представления полиномами, а для трансцедентных (как вот e и pi) использовал Real Recursive Arithmetic; но только там, где нельзя применить обычные символьные вычисления, потому что RRA - на то и рекурсивная, что никогда не остановится даже для абсолютного нуля. А это не очень прикольно для той же тригонометрии с её sin(pi).

Крайне рекомендую почитать полную статью, она довольно короткая, но исключительно занимательная: https://chadnauseam.com/coding/random/calculator-app

Считаем такты, или почему иногда стоит задумываться при переносе выражений в код.

Конкретнее, интересна строчка с объявлением combinedInvMass. В ней мы складываем два обёрнутых значения. 1 операция сложения и 2 операции деления. Если немного переписать выражение, то получим a+b / ab (где a, b - массы). 1 сложение, 1 умножение и 1 деление - в сумме операций остаётся всё так же три, но теперь на одно деление меньше. И в горячем пути (а он прям раскалённый) это даст нихуя себе выигрыш!

Стоимость деления в процессорах традиционно кратно выше стоимости умножения, в масштабах примерно 20-40 против 1-7 тактов соответственно (ну примерно). Просто потому, что умножать и само по себе проще, так ещё и легче по АЛУ раскидать, чтобы за такт несколько штук параллельно молотить - это, кстати, и есть то самое спекулятивное выполнение, о котором все говорят. Однопоточный код всё ещё прекрасно параллелится в транзисторах:)

Меньше делите — меньше энтропия расти будет. Ощасливьте котят!

Деление можно делать по Евклиду. Итеративно вычитаем, пока есть что (или не надоест). Но получается дороговато для больших чисел, да и за такт всего один бит считается. Неприятно.

В 1957-58 сразу трое додумались, как делить лучше. SRT алгоритм, который де-факто стандарт в процессорах, устроен интереснее: берём два самых значимых бита делителя и делимого и используем, как ключи для лукап-таблицы, в которой лежат коэффициенты (5 чисел {-2, -1, 0, 1, 2}). На полученный "угаданный"* коэффициент умножается делитель, результат произведения вычитается из делимого. Это наш остаток. Коэффициент сохраняем в регистр, сдвигаем его на 2, как и остаток на 2 влево. Повторяем цикл, только теперь используя в качестве индекса для таблицы два наиболее значимых бита у нашего остатка. Графически - берём по 2 бита с числителя и знаменателя, делим с остатком, результат переносим вниз и к нему дописываем следующие два бита числителя, остаток сохраняем.

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

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

С SRT теперь можно делить не по одному, а по двум битам за такт, что дало очень ощутимый буст в производительности. Но как раз из-за этого и случился фокус жопы у интела с делением. Тогда проблема была в этой самой лукап-таблице - из 1066 вхождений, 5 забыли заполнить, имея в итоге 0 там, где должен был бы быть +2 — а всё потому, что паттерн для принтера херово скомпилировали.

Статистически, ошибка должна была бы всплывать лишь раз в 27000 лет. Но обнаружили её спустя всего 5 лет после релиза. День новый, а статистика брешет, словно в первый.

https://www.bitflux.ai/blog/memory-is-slow-part2/

TL;DR и IO тоже делать надо грамотно. А ещё mmap() ощущается неправильным, и файлы им читать не очень круто - даже если уже в кэше лежит, всё равно на каждую страницу придётся прерываться.

По традиции приебусь к мелочам.

Там в бенчмарке десятки считают, и считалку эту заоптимизировали в вот это. В скрин не влезло, но там выше ещё убедили компилятор, что данные в памяти выровнены по 4096 байтам, так что обращения за границы не вылезут. Это важно, потому что теперь компилятор может со спокойной совестью векторизировать это всё.

Выглядит страшно. Но идея здесь в том, чтобы показать компилятору, что все 16 путей в теле цикла - независимы, включая персональные счётчики (чтобы всё в один регистр не нести). Теперь, если не векторизирует, то хоть камушек по всем доступным АЛУ раскидает, больше операций за такт перемолет.

Сложения ниже отыгрывают ту же роль. Хоть в gcc это практически ничего и не даст (с -O2 вырезаны подчистую), другим компиляторам это может очень даже помочь. Clang вот выдал лесенку сложений, которые уже процессор сам дальше переварит.

В общем, оптимизации - дело тонкое. Не менее тонкое, чем бенчмарки:)

xor eax, eax?

Мэтту Годболту яйца зачесались выпустить свой Advent of, но только про компиляторные ну немного анальные, да эквилибристики.

Ровно эта штука, о которой он в первом дне у себя рассказывает, мне попадалась вот здесь. Как оказалось, фокус xor'ить регистр с самим собой - имеет как практичный, так и побочный эффекты:
а) инструкция xor на х86 занимает 2 байта, когда как обычный mov eax, 0 пирует на все 5. Потому что надо ж ещё саму константу операндом хранить. Это практичная часть.
б) во всё том же х86, процессор прекрасно знает, зачем оно такое. И сама инструкция фактически даже не выполняется - просто подкапотное причёсывание с переименованием регистров. Это камню удобнее. А нам - приятнее.

Фанфакт - GCC применяет сию гимнастику, начиная лишь с -О2. А вот Clang не стесняется и тулит безусловно даже на -О0. Технически, шланг это даже за оптимизацию не воспринимает. Высокомерно!