Чайник из Юты

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

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

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

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

В стд го шестнадцатиричку пишут через AppendUint(dst, val, base) - и работает это примерно как и обычный append. Корнеркейсом вынесли десятиричные числа меньше ста. Для всего остального - formatBits. Там уже три корнеркейса:
- Основа десятиричная;
- Основа - степень двойки;
- Всё остальное (1 < base <= 36)

Для десятиричной основы там творится какой-то ужас (и довольно медленный, к слову - взятие остатка в цикле, пока не спустимся до ста).

Вот кейс с основанием степенью двойки интересный. shift с bits.TrailingZeroes - это сколько бит представляет символ алфавита. 2 = 0b10 => 1 бит на символ, 16 = 0b10000 => 4 бита на символ. m - маска для индексирования алфавита, чтобы получить наш излюбленный overlapping overflow. Идентичный трюк где-то в старой мапе использовался, насколько я помню.

В цикле остаётся лишь взять нижние shift бит (как раз по нашей маске m), записать символ и битшифтом передвинуть следующие shift битиков в b. И так пока в b не останется числа на один разряд.

У меня есть дефолтные заголовки, которые добавляются в ответ, если ты их не перегрузил (добавил в ответ вручную). Для этого, я сначала пишу заголовки, которые мне сунули, и ставлю флаг excluded на дефолтный, если я его там встретил. Мапу по традиции решил избегать, хотя надо будет ещё раз побенчить, заместо там обычный линейный поиск. O(nm), выходит. И это неприятно немного, но пока у меня там всё равно их всего один по-умолчанию (штуки по типу Date и Server всё равно лучше, удобнее и потенциально шустрее через миддлвари докидывать), то всё в общем-то довольно шустро.

К превеликому удивлению, золотая середина - бинпоиск - ситуацию только усугубил. Выигрыш в 30нс дал только кейс с 10 дефолтными заголовками (а это - дохуя). Грустно:(

А, ну теперь понятно, почему между 0.16.3 и 0.17.3 (ещё в разработке) полтора года прошло. Я фактически с нуля всё переписал. Учитывая, что суммарно там всего 10к строк

Отнюдь, абсолютным рекордсменом пока остаётся вот этот некрасавец

...сим простым мановением руки, мы сокращаем объём строк втрое

Ифэррнилы здесь были бы просто охуенны, согласитесь

Ладно, чаще лучше не поддерживать. А то косвенно виноватым в проёбе кукисов окажешься.

TL;DR суть TRACE в том, чтобы вернуть в теле ответа запрос таким, каким сервер его получил (вот прям совсем-совсем таким, без каких-либо преобразований, вот практически эхо). И если злоумышленник каким-то образом заставит браузер отправить TRACE запрос, там, внезапно, окажутся наши кукисы, которые от джаваскрипта так-то охранять надо

Ещё оказалось, что OPTIONS * (он же server-wide OPTIONS), который должен возвращать список всех поддерживаемых сервером методов, имеет свою причуду. Ему нужно вернуть не просто список всех поддерживаемых методов со всех эндпоинтов, а только их юнион! Только те методы, которые унивеврсально поддерживаются каждым эндпоинтом. При том OPTIONS и TRACE идут безусловно (ты так-то обязан поддерживать TRACE, есличо).

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

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

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

Таким лёгким манёвром мы сделали так, чтобы можно было определять неконфликтующие роуты /user/:id и /user/me. Правда, не совсем понимаю, почему кто-то умудряется это в фичи приписывать - штука так-то дефолтная.

Ещё я потом между делом добавил greedy wildcards, в стандартном mux подглядел, и заменил ими костыльные path catcher'ы - аж от души отлегло.

Но вот незадача: тут-то уж точно хэшмапы не вкорячишь. Ну, то есть, можно было бы, но это было бы крайне неудобно из-за того, что при инсерте я довольно часто "ломаю" строки напополам и подменяю ноды. Приходится держать наследников всё так же в массиве. А это проблема - вполне себе может быть кейс, когда сервис насчитывает в себе 500-700 роутов. А с деревом штука такая, что чем меньше ключи похожи, тем ширше его пидорасит. Очень неприятно линейно перебирать пару сотен строк, знаете ли. Даже учитывая, что строки сами по себе не сильно-то на сравнение приятные:)

Поленившись ещё месяца 2, наконец допёр до нормальных бенчмарков (не в слепую же проблему решать?). Ситуацию спасает всеми излюбленный бинарный поиск. Удивительно просто оказалось сделать вставку упорядоченной - один цикл while key < predecessor.value и slices.Insert (кстати, невероятно полезный пакет). Немного сильнее попотеть пришлось над поиском - slices.BinarySearchFunc сгладил worst-case, но на более лайтовых кейсах всё-таки оверхеда прибавил. Нагло спиздил Вырезал с мясом Заинлайнил себе slices.BinarySearch, и получил очень приятные числа практически по всем бенчам. В сумме, где-то в 2-4 раза шустрее стало - особенно прирост был, очевидно, с "широкими" деревьями - где у одного узла очень много наследников (и, соответственно, каждого перебрать надо). Со 128 штуками, вместо 128 линейных сравнений, мы теперь делаем только 7 - чистая вин-вин ситуация. На удивление, "глубокие" деревья со 128 узлами вглубь тоже прирост показали.

Кстати, в slices.BinarySearch переполнения избежали более прикольным способом, чем в джабе - int(uint(a+b) >> 1). Что значит, если переполнение и случится - старший бит один хуй падёт пред побитовым сдвигом вправо:)

Забавная ситуация произошла как-то, кстати. Когда я релизнул 0.17.0, решил сразу обновить pavlo.ooo, сократить параметр name до просто n (с телефона чтобы удобнее набирать было; добавить скрытый текстовый бокс мне религия не позволяет), и добавить вариант вообще без параметра это сделать - через динамический роутинг. Это оказалась проблема - внезапно я начал ловить ошибку синтаксиса темплейта. Ошибку, которой быть не должно - я даже в тестах так и не смог репродуцировать (правда, я и не сильно-то старался, в общем).

Вернулся в окно с индигой. Посмотрел я на тот парсер темплейтов. Если не ошибаюсь, это говно было написано году в 22-23, и парсило примерно следующее: /user/{id}/post/{postId}. На тот момент я почему-то решил сделать для этого парсер на машине состояний (через годика два я начну лениться и хуярить на strings.IndexByte), чтобы лучше валидировать, ошибочки покрасивше показывать, по красоте, в общем. Тестами вроде как даже покрыл, работать должно было норм.

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

Сел и переписал всё с нуля. Теперь вайлдкарды, которые раньше в {...} заключены были, поменял, и сделал /user/:id/post/:postId. Это очень правильное решение, на самом деле, потому что теперь, вместо отдельного выделения вайлдкарда собственной парой открывающего и закрывающего символов, у нас остаётся только один - это двоеточие. Неявной закрывающей "кавычкой" представляется слэш, отделяющий текущий сегмент от следующего - а это важно, потому что он служит опорной точкой при матчинге. Иначе приходилось бы изъёбываться с поиском подстроки какими-то более умными алгоритмами, чем мой излюбленный strings.IndexByte. Ну, а ещё, мне теперь нужно меньше валидировать - потому что между окончанием вайлдкарда и закрывающим слэшем больше не может ничего стоять:)

Я, конечно, не помню, поддерживалось ли раньше что-то вроде /user{id}, или вайлдкард был обязан растягиваться на целый сегмент (скорее всего), но в новом дереве я и это добавил. Стало красиво и круто.

Но, собственно, а что же в новом дереве поменялось-то?

2 месяца спустя, я наконец выкатил новый релиз. Пощипал баги, заделал кодеки (теперь и сжимать, и разжимать!), кучу всяких внутренних штук переделал, чтобы было красиво. Ну и тестами немного докрыл. Работы осталась куча, 0.17.3 ещё месяц-второй ждать, но пока выглядит работоспособно и вполне себе ебабельно.

Буду рад какому-либо фидбеку. Если по внутрянке - то ещё лучше.

А вот по доке не надо. Я и сам вижу, какая она ущербная:( Лучше правда не получается. Простите.

И лого. Я и сам знаю, что это какая-то ЛЛМка скорее, нежели вебфреймворк. Мне и самому на первый взгляд чатгпт. Но вы не подумайте, на самом деле это очень близко к символу семени жизни, просто без круга в центре. Конченное лого.

https://github.com/indigo-web/indigo

Кстати, хочу напомнить об этой годноте.

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

В HTTP/1.1 есть два вида передачи тела:
- Целый
- Раздробленный*
* перевёл как мог, я ебу как их локализировать. В оригинале - chunked. Да и целым я тоже хуй его, корректно ли кликать.

С целой передачей, у нас есть Content-Length, и там конкретное количество октетов*, содержащихся в теле запроса**.
* в сетевой разработке предпочитают применять понятие "октет битов" вместо "байт", поскольку, в отличии от "байт", слово "октет" чётко говорит о том, что битов там 8. А байт - он и из 6, и из 9, и из 16 битов состоять может (CDC6600, PDP-10, PDP-11).
** В rfc2616 просят игнорировать CRLF перед методом запроса, поскольку некоторые старые и хуёвые клиенты после тела добавляли неучтённые в длине CRLF. Сия помарка осталась там и до сих пор.

С chunked всё интереснее. Он сделан для ситуаций, когда длина тела заранее неизвестна, посему мы его льём "потоком". А именно - кусками - откуда и происходит его название. Каждый кусок - это <hex len>\r\n<data>\r\n. Шестнадцатиричная длина, перенос строки*, данные, перенос строки. Тело считается завершённым тогда, когда мы получаем чанк с нулевой длиной.
* CRLF остался стандартным разделителем и до сих пор в HTTP/1.1, и пошло это ещё со времён HTTP/0.9. Unix (точнее, все unix-like уже на тот момент - линукс, бсд, OSX) издревна понимал просто LF (\n), а вот винда, как обычно, отличилась, и хотела именно CRLF (\r\n). Поскольку упор был на гипертекстовую природу протокола, дабы быть человекочитаемым, так оно и закрепилось вплоть до самых последних rfc. Пускай некоторые имплементации и поддерживают LF-only (как, например, моя - минутка саморекламы), но такое поведение конформным не считается. В ABNF-нотации в стандарте синтаксис определяет конкретно и только CRLF.

Им удобно отдавать, например, потоковый JSON ответ с сервера. Ещё очень удобно таким образом файлы лить, но их лучше совать целиком. Потому что тогда за цену 1.5 сисколлов* мы можем задействовать sendfile(2), находясь под линуксом. А я нахожусь под линуксом, мне поебать. Zero-copy передача файла - это вот очень хорошо, на самом деле. Линусу это, кстати, не нравится.
* 1 - чтобы размер файла получить, 0.5 - заголовки придётся записать отдельно от тела, но для файлов больше пары килобайт таких записей всё равно будет несколько - в результате всё равно остаёмся в выигрыше.

А ещё, благодаря такому стримингу тела, можно удобно воротить нотификации и лонгполлинг без прибегания к вебсокетам, да. Единственное - IDLE подключения всё ещё мрут по таймауту.

В более новых стандартах, у чанков ещё и появились экстеншены. Пары ключ-значение, идущие сразу после длины блока, разделённые через ;. С ними можно получить практически HTTP внутри HTTP. Жаль только мало кто их поддерживает - с точки зрения дизайна вебфреймворка/клиента ебливо. Правда, AWS S3 их использует как раз - и это проблема. Не для меня, конечно, а для тех, кто попытается распопробовать мою индигу с AWS.

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

Забавный эффект. Чем дальше, тем сложнее писать хороший код.

Какая-то NP задача получается, блядь.

В какой-то момент вот этот цикл и условие (пикрил 1) я вынес в отдельную функцию (пикрил 2). Подумал: круто! Абстрагирую! Меньше самоповторений!

А потом присмотрелся. Мой го стал с привкусом плюсов. Что ещё хуже - с привкусом плюсовых итераторов.

Откатил.