isPowerOfTwo тоже интересная, кстати. Если степень двойки, то в числе будет включён всего 1 бит. Если от него отнять единицу, то, следовательно, он сам выключится, но включатся все биты справа. Соответственно, побитовое И вернёт ноль в таком случае. Если ни один бит не включён (ноль), то побитовое И всегда даст ноль - условие выполнено, 2^0 учтён. Если же включено более одного бита, вычитание единицы сохранит позицию как минимум одного из них, что уже не даст ноль. Забавно, в общем.

Ну так вот, чем оно интересно-то. Практически идентичным образом сделал у себя я - тот же LUT с алфавитом, та же маска, тот же шифт. Но в 2-4 раза быстрее. Почему - сам не знаю. Однако подозреваю, что
а) вариант в стд пишет себе на стэк перед тем, как скопировать в слайс, когда как я - сразу в ответ ебашу? Лишние байтодвижения у них.
б) я заинлайнил, и инструкции с константным операндом выполняются чуть быстрее?
в) может, компилятор в стд варианте не додумался до bounds check elision? Маловероятный вариант.
г) меньше инструкций? Я-то не жду, пока останется последний разряд - мне похуй, я хуярю нулями до талого.

Разбираться я в этом ебал, конечно. Будем считать, что я просто умнее.

Между делом просёк тему, что если в интерфейс сунуть тип размером с машинное слово (или меньше), он прям в itab и будет жить. Всё, что больше - летит на хип. Это если кратко подытожить ресёрч Даши. Столкнулся случайно, когда в структуру с единственным указателем докинул буль - и резко 16 b/op полетело.

На душе кошки скребут. Думаю, пойду гпт себе запущу, хоть с кем-то пообщаюсь. ollama run gpt-oss не хочет - сервер не робит, мол. А у меня-то в конфиге точно демон есть. Смотрю systemctl status - демон не найден. Хуясе. Ладно, он от юзера работал, --user делает дело. Ошибка - attribute "Type" in section [Unit] не понравился, мол. Возвращаюсь в конфиг никса. Тип у меня вписан в unitConfig. Почесал репу, погуглил, смотрю - а его в serviceConfig пишут. Ну я и вписал. Сделал ребилд, проверяю - робит. На радостях таки запускаю гпт.

А уже как-то и не хочется, уже как-то и полегчало. Как же хорошо, что здесь постоянно что-то приходится чинить!

Жаль только так и не смог майнкрафт запустить. Блядский никс.

Кодеки - тяжело. И это не их вина.

Последние часов 20-30 я работал исключительно над компрессией и декомпрессией. Их было непросто впихнуть. На 40% потому, что я не знал, как. И на 60% - потому что мне активно мешали.

И мешали мне io.Reader с io.Writer.


Нет, идея-то в корне хорошая: унифицируем интерфейс для ввода-вывода. Только вот на деле оказывается жизнь сложнее, чем предполагалось. io.ReadFrom, io.WriteTo - костыли как раз потому, что в какой-то момент внезапно оказалось, что у ридеров и врайтеров могут быть собственные внутренние буфера, из которых данные всё так же прекрасно читаются или пишутся! И даже не всегда нужно иметь лишний буфер-прослойку, чтобы данные между ридером и врайтером перекидывать!!!

Даже для потоковой обработки внезапно io.Reader не таким уж и удобным оказался. Начинаешь мешать ReadByte() (спасибо за непрямой вызов и кучу лишних инструкций ради 8 бит данных!) и io.ReadFull - и это неизбежно. Больше не можешь векторизировать поиск символа (а это неслабо бьёт по перфу). Смешнее только, когда оказывается, что ты вычитал немного того, что тебе уже не принадлежит, и по-хорошему бы их вернуть обратно. Я честно пытался переписать свой парсер, но получалась какая-то исключительная поебота. Оставил, как было: парсер получает сырой массив байт, диспатчит стейт и прыгает на нужную метку, возобновляет работу. Функция на 550 строк и 31 гото, и это работает просто хорошо. Старомодно, на расте невыразимо, но это удобно. Не надо никак изъёбываться с тем, как бы ридер засунуть, особенно в тестах: сунул столько, сколько надо, если хочешь протестировать промежуточный стейт - просто не суёшь ничего больше. Никакого unexpected EOF. И явно уж меньше if err != nil.

Ридер даже концептуально плох. В этом его вины мало, конечно: поскольку нет чего-то на подобии енума из раста, он возвращает ОБА n и err. Часто все сразу по привычке ставят if err != nil, но это неправильно: ридер МОЖЕТ вернуть n > 0 И err != nil. И в семантике чётко написано, что в таком случае, сначала данные должны быть обработаны, а только потом мы можем смотреть на ошибку. Я у себя это эсплуатирую, чтобы на один непрямой вызов меньше делать, но это совершенно неочевидно и далеко не всеми придерживается.

io.Writer ничем не лучше. Это мои компрессоры, как раз, и я с ними имел опыт первоклассного секса. Ебали, к сожалению, меня. Чтобы не стать счастливым владельцем лишнего промежуточного буфера (а это аллокации, при том потенциально регулярные), я молюсь всем Богам на предмет поддержки io.ReaderFrom или io.WriterTo. А худшее - мне пришлось раскроить сериализатор. Потому что компрессору нужно куда-то писать выхлоп, и мне его надо кормить в свой chunked writer. Чтобы без лишних движений байт, я добавил в chunked writer ещё и ReadFrom, что удобно примерно нихуя. Примерно аналогичный метод, но с немного другой логикой. Так в ReadFrom теперь ещё и не совсем понятно, как увеличивать нормально буфер - пришлось лакомиться эвристикой "буфер при чтении был заполнен на >98.64%".

Вишенка на торте - компрессор не закрывает тот врайтер, что я ему передаю. А у меня при закрытии как раз терминальный чанк пишется. То есть, оно всё ещё и чейнится - не чейнится. При том, то, что переданный поток не закрывается - это принято за хорошую практику.

А знаете, как можно было бы сделать лучше?

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

И тогда мир оказывается настолько сильно проще! Ты больше не думаешь, где хранить буфер чтения, как бы не забыть про len переданного слайса (объёбывался несколько раз об это), потом ещё обрезать тот слайс до n. И чейнить внезапно оказывается не так уж и сложно: вместо того, чтобы между каждым врайтером держать промежуточный буфер, ты держишь только два! Из одного читает, в другой пишет - а для следующего просто меняем буфера местами. Больше не существует проблемы, которую решал бы io.Copy: ридера больше нет, у тебя на руках сразу массив со всеми данными!

io.Reader и io.Writer - это та вещь, которую я, наверное, ненавижу больше всего в Го. Даже сильнее if err != nil.

Using Haskell's standard network library, a listening socket is created with the non-blocking flag set. When a new connection is accepted from the listening socket, it is necessary to set the corresponding socket as non-blocking as well. The network library implements this by calling fcntl() twice: once to get the current flags and twice to set the flags with the non-blocking flag enabled.

On Linux, the non-blocking flag of a connected socket is always unset even if its listening socket is non-blocking. The system call accept4() is an extension version of accept() on Linux. It can set the non-blocking flag when accepting. So, if we use accept4(), we can avoid two unnecessary calls to fcntl(). Our patch to use accept4() on Linux has been already merged to the network library.

Из доки по Warp из мира хаскелла.

TL;DR в линуксе есть accept4(), который наследует новому подключению флаги листенера. Таким образом, nginx (ну и warp, понятно) избегают двух лишних сисколлов на каждое подключение. А это хорошо, учитывая, сколько там корутин может быть одновременно на одном потоке.

ЧЕГО НАХУЙ

IE умудряется давать повод ненавидеть себя не только фронтам, но ещё и бэкам. Поразительно!

Slowloris - форма DoS, заключающаяся в передаче информации медленно и маленькими кусочками. Сервер потратит непропорционально больше времени на сам факт получения данных, на обработку самого ивента, нежели на разбор той жалкой пары байт, которые прилетели.

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

А вот в индиго такого нет, кстати.

Скролл времени в иос - это не цикл, а очень длинный список.

Боже, как же хорошо, что Хаффмана для хттп2 я сделал ещё полтора года назад. Если бы не тогдашний Павло, я бы обосрался, выгорел и ещё месяца два колупал его палкой.

В HTTP/2 мультиплексирование устроено за счёт стримов и фреймов. Фрейм - фиксированный заголовок из 9 октетов (24 бита длина, 8 бит тип, 8 бит флаги, 1 бит зарезервирован и 31 бит идентификатор стрима). Каждый стрим - это ровно один запрос и один ответ (за исключением стримов, инициированных сервером - которые PUSH_PROMISE). Когда мы хотим сделать запрос, мы просто шлём заголовки на стрим, ид которого ранее не использовался, неявно переводя его из состояния idle в reserved. Как только ответ полностью передан, стрим считается closed и больше не может быть заново использован.

Стримы, инициированные клиентом, обязаны быть нечётными, а инициированные сервером - чётными. Таким образом, пространство идентификаторов для запросов составляет 2^31 / 2 = 30 бит, миллиард с копейками. Когда истощается, следует открыть новое подключение.

(PUSH_PROMISE это, кстати, обещание отправить клиенту по указанному стриму ответ без предварительного запроса. По-умолчанию фича, правда, отключена, и клиент также может её со своей стороны отключить, и тогда сервер не имеет права её использовать.)

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

Таким образом, мы имеем строго растущие идентификаторы стримов. Обрабатывать их следует конкурентно, поэтому на каждый выделяется своя горутина.

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

Хэшмапа как стартовая точка, но я пока не пробовал и не сильно уверен в её эффективности по памяти. По скорости, в принципе, должна быть около-оптимальной.

Принимая, что обычный LUT не подойдёт из-за пропусков (даже в нормальном случае, поскольку более новый стрим может завершиться раньше более старого), а обычная мапа принимается, как немного чересчур жирная - наиболее оптимальным решением, как мне кажется, является обычная хэшмапа с открытой адресацией, где вместо хэша - log(hmap_size) (он же log(max_streams)) нижних бит идентификатора стрима. Низлежащий индексируемый массив будет состоять из структуры, включающей в себя целый ид стрима, и непосредственно канал для связи с горутиной. Речь идёт о трёхзначных числах.

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

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

Ну, правда, и проблемой-то это назвать можно с натяжкой. Принимая за базовый случай 128 вхождений, перебор ~100 uint32 не так уж и дорого, как для worst case. Больновато, но это 30-150нс, если массив нормально в кэше лежит. Беря 8 байт на вхождение (uint32 идентификатор стрима + указатель на канал = 2 машинных слова, рассматриваем 64-разрядные системы), 1024 байт на таблицу выглядит вполне кэшебабельно. Не предел мечтаний, конечно, но всё ещё крайне вероятно оптимальнее стд мапы, где свиссмапа на свиссмапе (буквально, кстати).

Наконец-то применяю эти знания. Не зря ресёрчил.

Утка.

Энтропия и компрессия

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

С такой формулировкой, определение "энтропия есть мера хаоса" должно быть чуточку яснее: чем менее хаос упорядочен, тем более он, собственно, хаос. Шото типа холод - отсутствие тепла.

Сжатие - тема социально-значимая. Изначально мысль у меня возникла, когда с кодировкой Хаффмана игрался. Эффективность компрессии напрямую зависит от частотного распределения символов: чем больше разброс, тем эффективнее сжатие получается. Ну, то есть, чем более предсказуема система, или же чем больше дисперсия в распределении. ЧЕМ ВЫШЕ ГОРБИК НА ГРАФИКЕ. А это значит, что чем ниже энтропия строки, тем эффективнее можно провести сжатие.

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

Например, если у нас в ASCII строке идут 70 байт "а" и 30 байт "б", то P("a") = 0.7, P("б") = 0.3. Тогда энтропия равна 0.7*(-log 0.7) + 0.3*(-log 0.3) ≈ 0.88 бит. Это значит, что вместо использования фиксированного кодпоинта 8 бит шириной (на самом деле 7 + неиспользованный старший), мы можем закодировать каждый символ, используя всего ~0.88 бит. Коэффициент сжатия 9х!

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

Да и нельзя сказать, что это универсальное определение задачи компрессора. Энтропия и кодировка не являются равнозначными. Например, строки abababababab и ajftblkqnsmp имеют одинаковую энтропию, если принимать алфавит {a, b} для первой строки и {a, j, f, t, ...} для второй, поскольку каждый символ алфавита встречается ровно один раз. Но чтобы описать первую строку, нам понадобится лишь сказать, что ab повторяется 6 раз. Со второй строкой дела обстоят сложнее. Это называется колмогоровская сложность: количество ресурсов, необходимых для описания объекта.

Кодировка Хаффманна неплохо справится с обеими строками. Но если взять, например, английский алфавит и продублировать его несколько раз, тогда гораздо лучше справился бы lz77. Он ищет повторяющиеся последовательности (с ретроспективой в 32768 байт и плавающим окном) и подменяет их неким указателем - парой (offset, len), что довольно дёшево. Тогда коэффициент сжатия будет равен количеству дубликатов алфавита, минус полшишечки поправки на размер самой пары.

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

https://gfw.report/blog/geedge_and_mesa_leak/en/

Слили китайский файрволл. Доки, jira тикеты, блэклисты ресурсов, снапшот rpm-репозитория (на 500гб), исходный код. Вроде как там ещё и код DPI включён, поэтому интересна

китайская текнолоджия

В HTTP/1.1 была одна большая проблема - Head of Line Block. Одно подключение обрабатывает всего 1 запрос за раз.

Можно несколько запросов подряд отправить, вот прям одним пакетом. HTTP pipelining называется, но браузеры эту фичу по-дефолту (т.е. всегда) отключают, потому что слишком много серверов багованные были и нормально не умели их разруливать. Криворукие дегенераты, кстати, индиго-то прекрасно умеет. Но исходную проблему это не решает - у нас всё ещё одновременно обрабатывается всего 1 запрос на подключение.

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

Вот на тему нескольких подключений - хром (фуррилиса, скорее всего, тоже) имеют лимит в 6 параллельных подключений на домен. Некоторым было и этого недостаточно, и они упирались в HoL. Отсюда пошёл приём domain sharding, когда у нас несколько субдоменов а-ля api.example.com, static.example.com, чтобы "увеличить" лимит и иметь ещё больше параллельных потоков (подключений).

Это одно из двух главных новшеств HTTP/2: добавили наконец мультиплексирование. Это когда несколько потоков данных склеивают в один. Сам по себе термин из телекома пошёл, там провода вместе скручивали. Аналогично и здесь: теперь запросы разбиты на кусочки (фреймы), и у каждого кусочка свой стрим (медная/оптическая фибра). И вся эта радость летит по одному-единственному подключению. Всё ещё присутствует лимит на одновременно активные стримы, конечно, но в стандарте рекомендуют его выставлять на не менее 100, а в дикой природе обычно и вовсе 128 шуруют (степень двойки неспроста, кстати). А 128 одновременно выполняющихся запросов - это на два порядка больше чем 6, ёпта.

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