Как я сравнение строк переизобретал
Мне в парсере нужно понимать, когда мы спарсили какой-нибудь служебный заголовок: например, чтобы сразу указать, что запрос будет иметь chunked transfer encoding. Но из-за того, что в http ключи заголовков регистро-независимые, мне пришлось изобрести свой EqualFold (стандартный был сильно медленнее, потому что поддерживает utf8). Долгое время это было ОК, пока я не дошел до экстремальных оптимизаций. И тут начинается самое интересное.
Я сначала посмотрел, как это сделано в nginx (спойлер:у них далеко не самый эффективный парсер ). До заголовков, правда, дойти не успел: меня в целом и методы запросов устроили. Как это устроено: мы берем 1-2-4 символов, и приводим к uint8-16-32, после чего сравниваем уже полученные числа.
У меня это нужно, потому что по каждому символу мне нужно применить побитовое ИЛИ по 0x20 (старый добрый трюк для ловеркейса аски). Таким образом, я не просто заинлайнил EqualFold, но еще и развернул цикл - сплошные победы. Соответственно, теперь имеем код следующего вида:
Мне в парсере нужно понимать, когда мы спарсили какой-нибудь служебный заголовок: например, чтобы сразу указать, что запрос будет иметь chunked transfer encoding. Но из-за того, что в http ключи заголовков регистро-независимые, мне пришлось изобрести свой EqualFold (стандартный был сильно медленнее, потому что поддерживает utf8). Долгое время это было ОК, пока я не дошел до экстремальных оптимизаций. И тут начинается самое интересное.
Я сначала посмотрел, как это сделано в nginx (спойлер:
У меня это нужно, потому что по каждому символу мне нужно применить побитовое ИЛИ по 0x20 (старый добрый трюк для ловеркейса аски). Таким образом, я не просто заинлайнил EqualFold, но еще и развернул цикл - сплошные победы. Соответственно, теперь имеем код следующего вида:
Так вот, почему ж парсер неэффективный-то
Начать стоит с того, что они по одному и тому же запросу проходятся дважды. Это такая особенность их парсера: сначала разбиваем на токены, потом уже производим основные манипуляции. Зачем это нужно? Я не знаю. А поэтому, и не берусь судить.Но да, это неэффективно, и можно было лучше
Продолжим тем, что у них примерно та же штука, что и у меня когда-то в парсере было. А именно - диспатчинг. Другими словами - у парсера есть состояние, и цикл, который проходит по сырому запросу. И на каждой итерации этого цикла, мы заново через свитч проверяем состояние парсера. Это неэффективно, потому что мы внутри всегда знаем, куда нам надо дальше (да, безусловные переходы с гото), а с их подходом - мы делаем кучу ненужных свитч-кейсов. Которые, хоть и по инту, но все же в сумме стоят весьма дорого - проверил на личной шкуре.
Замечание: на безусловных переходах полностью от диспатча и состояния не уйти, он все равно будет нужен при вызове функции, чтобы прыгнуть туда, где парсер в прошлый раз остановился. Но это стоит практически ничего
Замечание 2: раньше в парсере, при каждом безусловном переходе я заодно записывал новое состояние в поле структуры. Избавился, тем самым сэкономив пару лишних mov, посредством записи состояния только при выходе (при этом, успешного) из функции
Замечание 3: можно сильно удешевить диспатчинг, не прибегая к гото (если такая задача стоит). Достаточно просто взять ту же схему, что и с гото, когда каждый блок полностью автономно парсит свою часть запроса, и дальше уже передает управление туда, куда следует. Тобишь, в таком случае - у нас сильно уменьшается как количество состояний (что позитивно влияет на размер свитч-кейса, количество сравнений, работу бранч-предиктора, функция лучше в кэш помещаться будет, и т.д.), так и упрощается сам код. Получится такая штука, что в каждом состоянии мы парсим отдельную единицу запроса (например - метод, путь запроса, ключ заголовка, и т.п.), и только после этого выполняем повторный диспатчинг, чтобы перейти к следующему участку кода. Таким образом, у нас все еще остаются некоторые затраты на свитч, но они сильно минимизируются на фоне остального
Начать стоит с того, что они по одному и тому же запросу проходятся дважды. Это такая особенность их парсера: сначала разбиваем на токены, потом уже производим основные манипуляции. Зачем это нужно? Я не знаю. А поэтому, и не берусь судить.
Продолжим тем, что у них примерно та же штука, что и у меня когда-то в парсере было. А именно - диспатчинг. Другими словами - у парсера есть состояние, и цикл, который проходит по сырому запросу. И на каждой итерации этого цикла, мы заново через свитч проверяем состояние парсера. Это неэффективно, потому что мы внутри всегда знаем, куда нам надо дальше (да, безусловные переходы с гото), а с их подходом - мы делаем кучу ненужных свитч-кейсов. Которые, хоть и по инту, но все же в сумме стоят весьма дорого - проверил на личной шкуре.
Замечание: на безусловных переходах полностью от диспатча и состояния не уйти, он все равно будет нужен при вызове функции, чтобы прыгнуть туда, где парсер в прошлый раз остановился. Но это стоит практически ничего
Замечание 2: раньше в парсере, при каждом безусловном переходе я заодно записывал новое состояние в поле структуры. Избавился, тем самым сэкономив пару лишних mov, посредством записи состояния только при выходе (при этом, успешного) из функции
Замечание 3: можно сильно удешевить диспатчинг, не прибегая к гото (если такая задача стоит). Достаточно просто взять ту же схему, что и с гото, когда каждый блок полностью автономно парсит свою часть запроса, и дальше уже передает управление туда, куда следует. Тобишь, в таком случае - у нас сильно уменьшается как количество состояний (что позитивно влияет на размер свитч-кейса, количество сравнений, работу бранч-предиктора, функция лучше в кэш помещаться будет, и т.д.), так и упрощается сам код. Получится такая штука, что в каждом состоянии мы парсим отдельную единицу запроса (например - метод, путь запроса, ключ заголовка, и т.п.), и только после этого выполняем повторный диспатчинг, чтобы перейти к следующему участку кода. Таким образом, у нас все еще остаются некоторые затраты на свитч, но они сильно минимизируются на фоне остального
Что делать
собственно, а вот так оно выглядит в нжинкс. Интересное наблюдение: тут не используются 64-битные числа, максимум 32-битные. Вероятно, это связано с тем, что этот код работает на все еще очень большом количестве 32-битных машин
Кстати, интересный способ я подсмотрел во все том же файлике у них. А именно - парсить константные подстроки.
Под константными подстроками подразумеваются такие подстроки, которые вообще всегда одинаковые. Таким, например, является префикс HTTP/ в версии протокола (напоминаю: в плейнтексте маска протокола выглядит, как HTTP/1.1). Собственно, на этом примере я и узнал об этом
В этом, на самом деле, ничего особого нет. Но я, например, сначала так не сделал, поэтому может кому и полезно будет
Собственно, у нас же вот есть парсилка запросов хттп, так? И в ней есть состояния? Так почему бы не сделать посимвольное сравнение на состояниях? Ну, то есть, буквально захардкоженное префиксное дерево, но с сохранением состояния. Да, мы буквально посимвольно сравниваем каждый байт. Покажу на картинке ниже.В индиге, кстати, так сложилось, что выгоднее было это не реализовывать
Собственно, а какие еще у этого применения есть? Ну, например, можно использовать в жсон парсерах.
Под константными подстроками подразумеваются такие подстроки, которые вообще всегда одинаковые. Таким, например, является префикс HTTP/ в версии протокола (напоминаю: в плейнтексте маска протокола выглядит, как HTTP/1.1). Собственно, на этом примере я и узнал об этом
В этом, на самом деле, ничего особого нет. Но я, например, сначала так не сделал, поэтому может кому и полезно будет
Собственно, у нас же вот есть парсилка запросов хттп, так? И в ней есть состояния? Так почему бы не сделать посимвольное сравнение на состояниях? Ну, то есть, буквально захардкоженное префиксное дерево, но с сохранением состояния. Да, мы буквально посимвольно сравниваем каждый байт. Покажу на картинке ниже.
Собственно, а какие еще у этого применения есть? Ну, например, можно использовать в жсон парсерах.
true, false, null - это все тоже константные подстроки, так-то.Оказывается, чтобы включить режим HTTPS only, можно не просто редиректить на идентичный url, только со scheme https (как это пока что работает у меня; см. пикрил)
https://https.cio.gov/hsts
https://https.cio.gov/hsts
Что делать
Оказывается, чтобы включить режим HTTPS only, можно не просто редиректить на идентичный url, только со scheme https (как это пока что работает у меня; см. пикрил) https://https.cio.gov/hsts
Но есть нюанс: использование HSTS угробит мне самоподписанные сертификаты для локалхоста
Фанфакт: в среднем, чтобы загрузить веб-страницу, браузеру приходится сделать 70 дополнительных запросов для подгрузки ресурсов
https://httparchive.org/reports/page-weight#reqTotal
https://httparchive.org/reports/page-weight#reqTotal
httparchive.org
HTTP Archive: Page Weight
This report tracks the size and quantity of many popular web page resources. Sizes represent the number of bytes sent over the network, which may be compressed.
Forwarded from Illia
Да, Паша занимается экстримальным программированием. Я бы даже назвал его экстримистом
👍1
SSL vs. TLS
SSL изначально разработали в Netscape (если помните такой браузер). Аббревиатура расшифровывается, как Secure Sockets Layer. Его первая версия, SSLv1, была чисто внутренним продуктом, зато на продакшн выкатили уже SSLv2 и SSLv3. Но это была конкретно разработка компании, нежели стандарт, хоть де-факто таковым оно и являлось. Потом Netscape разорился, и на рфс выкатили бумаги по SSLv3 в качестве historic document. На его основе появился TLSv1, похожий, но не совместимый. Потом TLSv1.1, 1.2, и, наконец, в 2018 - TLSv1.3. Несмотря на то, что тлс был лучше и безопаснее, SSLv3 все равно считали достаточно надежным и продолжительное время использовали все же его, даже если клиент поддерживал TLS. Но вот, в какой-то момент пришли умники в очках, и указали на критические уязвимости. Вот SSL больше и не используют.
P.S. в TLSv1.0 тоже понаходили. По итогу тоже начали форсировать повсеместную поддержку 1.1
SSL изначально разработали в Netscape (если помните такой браузер). Аббревиатура расшифровывается, как Secure Sockets Layer. Его первая версия, SSLv1, была чисто внутренним продуктом, зато на продакшн выкатили уже SSLv2 и SSLv3. Но это была конкретно разработка компании, нежели стандарт, хоть де-факто таковым оно и являлось. Потом Netscape разорился, и на рфс выкатили бумаги по SSLv3 в качестве historic document. На его основе появился TLSv1, похожий, но не совместимый. Потом TLSv1.1, 1.2, и, наконец, в 2018 - TLSv1.3. Несмотря на то, что тлс был лучше и безопаснее, SSLv3 все равно считали достаточно надежным и продолжительное время использовали все же его, даже если клиент поддерживал TLS. Но вот, в какой-то момент пришли умники в очках, и указали на критические уязвимости. Вот SSL больше и не используют.
P.S. в TLSv1.0 тоже понаходили. По итогу тоже начали форсировать повсеместную поддержку 1.1
Красивый хак с логарифмом по основанию 2
https://github.com/allegro/bigcache/blob/main/utils.go#L14-L16
https://github.com/allegro/bigcache/blob/main/utils.go#L14-L16
👍1
Да я буду щитпостить в перерывах между техническими постами
На 14 февраля расскажу, что такое ALPN, и с чем его едят
ALPN - Application Layer Protocol Negotiation. Представляет из себя расширение TLS (в мейнстрим имплементациях появился с 14-16 года в среднем). Фактически - позволяет еще на этапе TLS хэндшейка выбрать используемый далее протокол. Тобишь, буквально: указываешь, какие протоколы поддерживаешь (все токены зарегистрированы в IANA) - клиент выбирает - и вы дальше уже это говно используете.
По этому механизму, например, преимущественное большинство браузеров и поддерживают хттп2 - вместо того, чтобы начинать общение с хттп1.1 и дальше уже через заголовок Upgrade обновляться. Хоть и этот способ рудиментарным не объявлен, таковым фактически он и является. Минусы - его поддерживать тоже придется. Но в целом, не критично.
Фанфакт: это расширение в 2014 ввел наш славноизвестный гугл.
Вообще, по моим наблюдениям, с 97 года веб очень сильно тянет гугл. Что хттп2 - стандартизированная спустя 3 года версия гугловского SPDY, что ALPN как основной способ налаживания хттп2 транспорта, что хттп3 (который просто http2-over-quic). В принципе, имея убийственную связку из одного из самых популярных браузеров (который еще и evergreen, но об этом в следующем посте), не менее популярного сайта, а также четвертого по популярности веб-сервера - гораздо проще вводить новые, экспериментальные технологии, и тестировать их в жестоком и кровавом бою
ALPN - Application Layer Protocol Negotiation. Представляет из себя расширение TLS (в мейнстрим имплементациях появился с 14-16 года в среднем). Фактически - позволяет еще на этапе TLS хэндшейка выбрать используемый далее протокол. Тобишь, буквально: указываешь, какие протоколы поддерживаешь (все токены зарегистрированы в IANA) - клиент выбирает - и вы дальше уже это говно используете.
По этому механизму, например, преимущественное большинство браузеров и поддерживают хттп2 - вместо того, чтобы начинать общение с хттп1.1 и дальше уже через заголовок Upgrade обновляться. Хоть и этот способ рудиментарным не объявлен, таковым фактически он и является. Минусы - его поддерживать тоже придется. Но в целом, не критично.
Фанфакт: это расширение в 2014 ввел наш славноизвестный гугл.
Вообще, по моим наблюдениям, с 97 года веб очень сильно тянет гугл. Что хттп2 - стандартизированная спустя 3 года версия гугловского SPDY, что ALPN как основной способ налаживания хттп2 транспорта, что хттп3 (который просто http2-over-quic). В принципе, имея убийственную связку из одного из самых популярных браузеров (который еще и evergreen, но об этом в следующем посте), не менее популярного сайта, а также четвертого по популярности веб-сервера - гораздо проще вводить новые, экспериментальные технологии, и тестировать их в жестоком и кровавом бою
Что делать
который еще и evergreen
evergreen браузерами называют те, которые обновляются самостоятельно в фоне. То есть - без явных просьб пользователя. Звучит хоть и не очень хорошо, но все же считается больше хорошим тоном, нежели наоборот. Например, из-за того, что обновления IE были привязаны к обновлению операционной системы, чисто вечнозелеными их назвать было сложно. Отсюда и пошла головная боль фронтэндеров, когда сайт нужно еще и под IE оптимизировать