На рождественских каникулах я ехал на автобусах из одного штата в другой, и мне нужно было как-то убить 24 часа. Я читал об UTF-8 и узнал об этой кодировке нечто интересное: все традиционные символы ASCII сохранены в ней в их исходном однобайтовом представлении, поэтому их можно сканировать крайне быстро. Я решил поэкспериментировать с кодом, максимально быстро подсчитывающим такие символы, в результате получив готовый парсер CSV, который вполне сравним с предыдущими парсерами, а то и быстрее них.

В статье я расскажу о своём процессе работы, экспериментах и оптимизациях, которые привели меня к этому итогу.

Кошмар с автозавершением

Наше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ.

Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации.

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

Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными:

Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти, в то время как хэш-таблица — всего 24 МБ.

Где мы ошиблись?

Загадка базы данных

Вся наша база данных находилась в памяти, однако операции поиска по ней занимали 12 тысяч тактов. При миллионе показаний датчика IoT-устройства с 64 КБ кэша реализация красно-чёрного дерева оказалась слишком медленной для запросов в реальном времени.

«Давайте попробуем B-дерево», — предложил я.

«Разве они нужны не только для баз данных на дисках? — спросил лид, — У нас всё находится в памяти. Чем нам будет полезно B-дерево?»

Вопрос был вполне разумным. B-деревья были придуманы для доступа к диску; каждый узел в них — это блок диска. Однако паттерны промахов кэша выглядели подозрительно похожими на паттерны дискового ввода-вывода — всего в 100 раз, а не в 100000 раз быстрее.

В итоге мы реализовали B-дерево. Результаты удивили всех...

У компании Tesla есть программа баг-баунти, приглашающая исследователей находить уязвимости безопасности в её автомобилях. Для участия мне нужно было настоящее «железо», поэтому я начал искать на eBay детали Tesla Model 3. Моя цель заключалась в том, чтобы компьютер и сенсорный экран Tesla заработали на моём столе, после чего я мог бы запустить операционную систему машины.

Компьютер машины состоит из двух частей: MCU (Media Control Unit, блока управления медиа) и autopilot computer (AP, компьютера автопилота), расположенных один поверх другого. В машине компьютер размещён перед пассажирским сиденьем, примерно за бардачком. Сама эта деталь размером с iPad и толщиной с 500-страничную книгу. Она заключена в металлический корпус с водяным охлаждением.

Поискав на Ebay «Tesla Model 3 MCU», я нашёл довольно много результатов в ценовом диапазоне $200 - $300. Изучая страницы товаров, я заметил, что многие из продавцов — компании-«утилизаторы», которые скупают разбитые машины, разбирают их и по отдельности продают детали. Иногда они даже выкладывают фотографии самих разбитых машин и позволяют фильтровать страницы товаров по деталям, извлечённым из одного автомобиля.

Все знают, что такое AWS S3, но немногие осознают масштабы, в которых он работает, и те усилия, которые понадобились, чтобы этого добиться.

По сути, это масштабируемый сервис многопользовательского хранилища с API для сохранения и извлечения объектов, обеспечивающий крайне высокую доступность¹ и надёжность² по относительно низкой цене³.

Масштабы

• 400+ триллионов⁴ объектов

• 150 миллионов запросов в секунду

• > 1 ПБ/с пикового трафика

• Десятки миллионов дисков

А что лежит в основе всего этого?

Жёсткие диски.

Способы достижения S3 таких масштабов — это настоящее инженерное чудо. Чтобы понять и оценить систему, нужно сначала оценить её базовый строительный блок — жёсткий диск.

Жёсткие диски (HDD) — это старая, уже выходящая из моды технология, во многом вытесненная SSDs. Жёсткие диски хрупки физически, ограничены по IOPS и имеют высокие задержки.

Однако благодаря им возможно то, на что пока неспособны флэш-диски: крайне дешёвая экономика хранения.

Катастрофа с красно-чёрным деревом

Компилятор тратил 60% времени на поиск символов. Не на парсинг, не на генерацию кода, просто на поиск в таблице символов.

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

«У него O(log n); судя по учебникам, оно идеально подходит для этой цели», — сказал мой коллега.

Но профилировщик показывал иное...

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

Затем мы перешли к теории множеств, позволившей закодировать внутреннюю структуру этих символов. В результате получилась иерархия натуральных чисел теории множеств, называемых ординалами. Также это привело к интересному выводу: если мы допускаем существование бесконечных множеств, то и само множество всех натуральных чисел (ℕ) имеет структуру ординала. В статье мы обозначили это бесконечное число, как ω и продемонстрировали, что им можно манипулировать при помощи те же арифметических правил, что и конечными числами, но иногда оно ведёт себя неожиданным образом. Например, мы выяснили, что ω + 1 ≠ 1 + ω.

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

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

Excel не единственный, кто любит превращать любые данные в даты.

Если вы работаете с датами в JavaScript, то, вероятно, рано или поздно пользовались new Date(someString). Это удобно: передаём строку, получаем объект Date. Но привыкнув к Python, я был удивлён тем, насколько свободно JavaScript обращается с форматами дат. Позвольте мне проиллюстрировать это примерами.

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

Мне кажется это ироничным: тысячелетиями математика оставалась более-менее естественной наукой. У нас не было философского объяснения тому, почему 2 + 2 должно быть равно 4. Мы просто наблюдали происходящее вокруг нас и пытались вывести правила. Абстракции были важны, но они обязательно должны были обосновываться объективной реальностью. Согласованности аксиом было недостаточно: углы нашего гипотетического треугольника должны были соответствовать углам в реальном мире.

Всё началось с тупой идеи. 

У меня есть мышь Logitech MX Vertical, которая постоянно перемещается между моей домашней машиной, рабочим ноутбуком и другими устройствами. Однажды я задумался: у этой штуки есть флэш-память. Она обязана быть, иначе как мышь запоминает настройку DPI между подключениями? А можно ли в этой памяти хранить что-то ещё?

Ага, мне было скучно.

Я решил использовать мышь в качестве крошечного USB-накопителя. Так как она физически перемещается между компьютерами, то, строго говоря, способна и переносить между ними данные.

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

В процессе такой работы одной из самых часто поднимаемых тем становится «раздувание зависимостей»: деревья зависимостей npm со временем становятся больше, и зачастую это вызвано давно уже избыточным кодом, возможности которого платформа уже предоставляет нативно.

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

«Преждевременная оптимизация — корень всех зол, но преждевременная пессимизация является им не в меньшей степени». — Андрей Александреску

Проблема перераспределения

Динамические массивы (векторы C++, ArrayList в Java) — одна из самых полезных структур данных. Они сочетают в себе удобство для кэша, присущее массивам, с гибкостью динамического изменения размера.

Однако у них есть скрытые затраты, связанные с перераспределением.

Однажды я работал над агрегатором логов встраиваемой системы. Система накапливала сообщения логов в динамическом массиве и периодически скидывала их на флэш-накопитель. Кажется, всё просто, не так ли?

Но производительность была ужасной. Система тратила 60% времени на realloc().

Миф про O(1)

Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.

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

Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.

Но профилировщик рассказал иную историю...

В AWS здорово то, что этой платформе уже почти двадцать лет. Печально в AWS то… что ей уже почти двадцать лет. Если вы уже долгое время пользуетесь ею, то вам может быть сложно заметить тем изменений её «фундаментальных» сервисов. Хуже того: даже если вы относительный новичок в AWS, вам всё равно довольно легко найти устаревшие посты, объясняющие всё так, как было раньше, но не сейчас. В своей статье я перечислю часть примеров такой эволюции, которые помогут вам, если вы запутаетесь.

Алгоритм Slug, используемый для рендеринга на GPU шрифтов непосредственно из кривых Безье, был разработан осенью 2016 года, а значит, в этом году мы отмечаем десятилетие его рождения. В середине 2017 года я опубликовал в JCGT статью об этой методике, а вскоре после этого моя компания продала первую лицензию на версию 1.0 Slug Library. С тех пор Slug многократно лицензировался разработчиками видеоигр, а также компаниями, специализирующихся в научной визуализации, CAD, редактировании видео, медицинском оборудовании и даже создании планетариев. Среди наших клиентов Activision, Blizzard, id Software, 2K Games, Ubisoft, Warner Brothers, Insomniac, Zenimax и Adobe. Slug оказался моим самым успешным программным продуктом.

Изначально я создавал Slug с целью улучшения рендеринга текста в C4 Engine, шрифты которого должны выглядеть идеально не только в GUI, но и внутри игровых уровней, где они могут быть очень крупными и отображаться под разными углами. Недавно я использовал Slug в создании редактора формул Radical Pie, в котором, разумеется, необходим крайне качественный рендеринг шрифтов, а также векторной графики для таких обозначений, как скобки, знаки корня и чисто графических элементов наподобие стрелок и выделения математических выражений. Кроме того, Slug используется для рендеринга всего интерфейса пользователя внутри основного окна редактирования и всех диалоговых окон.

В этом посте я расскажу об изменениях в методике рендеринга с 2017 года, когда была опубликована научная статья и выпущена первая версия Slug Library. Завершается статья важным объявлением для тех, кто захочет реализовать алгоритм Slug в собственных проектах.

Все мы слышали об этих законах сетевых эффектов: ценность сети растёт как квадрат от количества участников. Или что затраты на коммуникацию растут как квадрат от количества участников; это может быть n log n или что-то подобное, в зависимости от того, как упорядочить участников. Иными словами, удвоение размера команды не удваивает её скорость, возникает ещё оверхед координирования. Величина оверхеда зависит от того, насколько плохо вы спроектировали организацию.

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

Итак, вот оно:

Каждый слой согласований замедляет процесс в десять раз

Знаю, что вы подумали. «Да ладно, в десять раз? Это слишком много, не похоже на правду. Ты, наверно, преувеличиваешь».

Не-а.

Уточню, что здесь учитывается общее время, а не трудозатраты. Почти всё дополнительное время тратится на ожидание.

Вы получили уведомление о непрочитанном сообщении

Это может быть сообщение в Slack (или Teams), мессенджере или электронной почте. Может быть, вас тэгнули в Notion или в документе Office.

Вы открываете его и видите множество абзацев текста или, может быть, список со всеми признаками сгенерированного ИИ послания: заголовки, много форматирования, фразы вида «это не X, это Y», обильно присыпанные длинными тире.

Отправивший вам это сообщение человек, вероятно, потратил на него с десяток секунд. Он попросил чат-бота создать текст и просто переслал его ответ вам в полном виде, не проверив и не проанализировав его.

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

Когда я пишу эту статью, то чувствую себя довольно глупо. На самом деле, это история с моралью «Прежде, чем действовать, изучи вопрос и понимай, в чём заключается твоя цель, потому что иначе потеряешь много времени».

Я продолжаю работать над проектом PSRayTracing. Как ни стараюсь я положить его на полку, время от времени слышу о чём-то «новом» и задаюсь вопросом: «а можно ли засунуть это в мой трассировщик лучей, чтобы выжать из него ещё немного скорости?». На этот раз такой темой стали аппроксимации Паде. Моя цель заключалась в обеспечении более быстрых (и точных) тригонометрических аппроксимаций.

Увы, это не помогло... однако я обнаружил нечто иное, позволившее существенно ускорить мой трассировщик!

Словом 2025 года в Японии стало слово медведь. Количество столкновений с чёрным уссурийским медведем по сравнению с предыдущем годом удвоилось. 200 человек было ранено, 13 погибло. Окума («большой медведь») — это городок на восточном побережье Японии. Но больше всего население Окумы боится не медведей, а радиации.

Окума — город, расположенный ближе всех к трём реакторам АЭС Фукусима-1, расплавившимся 11 марта 2011 года. В тот день землетрясение магнитудой 9,0 баллов и цунами уничтожили резервные генераторы и насосы системы охлаждения трёх реакторов, загруженных ядерным топливом. В четвёртом реакторе топлива не было, но его здание, заполненное водородом из соседнего блока, взорвалось вместе с тремя остальными.

Волна, обрушившаяся на восточное побережье Японии, привела к гибели 20 тысяч человек, тела многих из них вынесло в море и они не были обнаружены. В окрестностях уничтоженных реакторов резко возросли уровни радиации, и 160 тысяч людей было эвакуировано из Окумы и ещё 11 городов. 20-километровое кольцо вокруг электростанции было объявлено зоной отчуждения. Из-за ужасной снежной бури, накрывшей город цезием-137 и другими радионуклидами, эвакуировали даже Иитате, деревню в 60 километрах к северо-западу.

Пятнадцать лет спустя четыре тысячи работников с трудом пытаются контролировать продолжающуюся катастрофу. Три расплавившихся реактора остаются настолько радиоактивными, что выводят из строя роботов, отправляемых для оценки разрушений. Никто точно не знает, где находится расплавившееся топливо и насколько ниже бетонных постаментов реакторов оно опустилось, вероятно, достигнув почвы. Вода, использовавшаяся для охлаждения реакторов, хранится в тысяче с лишним резервуаров, исчерпавших предел своей ёмкости в 2023 году. Эта охлаждающая вода, которая, по первоначальным утверждениям Tepco, была чистой и сбрасывалась в Тихий океан с 2023 года, оказалась загрязнённой 62 радионуклидами, в том числе цезием, стронцием и плутонием. Два бассейна выдержки, заполненных отработанным ядерным горючим, всё ещё не освобождены. Они шатко держатся поверх первого и второго блоков, представляющих собой взорвавшиеся переплетения металла, готовые упасть и быть смытыми в океан.

Я был одержим процедурными картами с ещё детства, когда кидал кубики на таблицы случайных подземелий из AD&D Dungeon Master's Guide. В этом есть что-то волшебное — ты не проектируешь подземелье, а исследуешь его, помещение за помещением, а кубики решают, попадёшь ли ты в сокровищницу или в тупик с кучей крыс.

Спустя годы я решил создать собственный генератор карт. Он создаёт маленькие средневековые островные миры с дорогами, реками, побережьями, горами, лесами и деревьями. И всё это полностью процедурным образом. Генератор написан на Three.js WebGPU с TSL-шейдерами, примерно 4100 шестиугольников в 19 сетках генерируются за ~20 секунд.