Чайник из Юты

Теперь и с каналов ливать. Ну что ж ты будешь делать

А в чем прикол бустить каналы премиум-подписками?

Начал замечать, что с тех пор, как добавили женерики - начали добавлять и интересные пакеты. Вроде все того же slice, арены (отнюдь не уверен во взаимосвязи), итераторы планируют. Может, пустые интерфейсы - и правда не настолько хорошее решение by design?

https://github.com/golang/go/issues/61897

Говорят, стоит ожидать. Штош, было бы замечательно увидеть итераторы, наконец, и в стандартной библиотеке

С юбилеем меня

Интерпретатор, совместимый с go1.19 и go1.20. Интересный проект, чтобы быстро проверить идею - отнюдь никаких оптимизаций не предусмотрено, и даже никакой виртуальной машины для исполнения нет

в семье все должно быть поровну

И снова сказ о том, как я парсер свой оптимизировал.

Решил я из интереса написать http-forwarder, для этого мне нужно из запроса достать заголовки Host, Content-Length и Transfer-Encoding (Host чтобы знать, кому перенаправлять; Content-Length и Transfer-Encoding - чтобы знать, что делать с телом запроса). Решил я для этого использовать bytes.IndexByte(). Результат (после пары часов пост-оптимизирования, конечно же) - 11.7gb/s throughput.

Неплохо. Посмотрел на свой парсер в индиге - 1.7гб/с. Уныленько. Переломал все к чертям, позаменял на bytes.IndexByte(). Стало 4.5гб/с. Уже лучше, хоть и все еще уныленько - но эту проблему я пока решаю.

Так а в чем же прикол, собственно? Да суть вся в том, что bytes.IndexByte() для х86 архитектур использует SIMD, позволяя, тем самым, обходить строки гооораздо быстрее. Собственно, весь выигрыш и сводится к тому, насколько грамотно получится вкрутить эту штуку себе в код. В парсере для http-forwarder'а, например, большую часть данных просто пропускают мимо ушей, потому что основных (и самых важных заголовков) - очень маленькое подмножество, благодаря чему и получается достичь относительно высокой производительности. В индиге отставание в практически 3 раза, но уже потому, что приходится гораздо больше данных копировать - все же тут парсеру приходится быть немного более general-purpose, и извлекать больше деталей из запроса. А, ну и путь запроса много сжирает, да.

Хороший трелло, и таски интересные

Раз уж зашла тема, то стоит еще обсудить мапу.

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

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

Но почему так? Потому что при интенсивной записи, не очень интенсивном чтении и небольшом количестве ключей (лимит - 50 заголовков, в среднем 10-20), обычный перебор будет быстрее. Но тенденция сохраняется до 20-30 элементов, далее скорость начинает линейно отставать от в среднем константной у хэшмапы (но и с 50 элементами перебор не намного медленнее хэшмапы). Также заметную часть расходов удалось убрать за счет отсутствия операции очищения мапы.

Но в целом, обычный одномерный слайс строк просто-напросто более удачная структура данных по части абсолютной производительности для конкретного кейса¯\_(ツ)_/¯

Еще про оптимизации.

Иногда, чем проверять символ на вхождение в множество других символов посредством свитча,

switch char {
case 'a', 'b', 'c': ...
}

дешевле сделать лукап по массиву.

То есть, эксплуатируя особенность ascii-кодировки, в которой каждый символ закодирован строго одним байтом, мы можем просто завести [256]bool. Константа 256 - максимальное значение uint8 (алиасом на который byte, собственно, и является). В таком случае, заполняя массив следующим образом, мы можем получить значение, лежащее по индексу, равному значению символа. То есть, if table['a'] { ... }

Преимущество перед свитчом это, правда, начинает иметь только начиная с определенного момента. Авторы json-iter, например, решили, что свитч с числами на 16 кейсов уже будет дороже, чем лукап по массиву.

А, и да. Это вполне себе можно считать идеальной хэш-мапой:)

Оказывается, на маке нельзя ничего ручками (кроме чтения) сделать с /usr/bin - даже с судо. Видите ли, политики безопасности (ну да, если у малвари судо, то он без /usr/bin все равно ничего сделать не сможет, правда ведь?). Собственно, задача: куда без переустановки компилятора, добавить исполняемый файл go, чтобы он был доступен по всей системе, а не только в интерактивном шелле zsh?

каждый айтишник такой

Ладно, надо украсть gperf

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

С первым способом особо проблем нет, это имплементируется довольно банальным способом. Больше нас интересует второй пункт. Его идея состоит в том, чтобы если заранее известны необходимые обработчику заголовки, то их можно было сложить в одну структуру, и их запись/извлечение имели константную асимптотику. Иными словами - хэшмапа, но работающая на заранее известном множестве ключей. Более того, такая штука также может использоваться для хранения динамических сегментов путей (во встроенном роутере), что также повышает производительность.

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

Эх, сколько же проблем решает сильный компайл-тайм

А, и кстати. Можете меня поздравить, индига отныне официально zero-allocations :)