По словам друга и бывшего коллеги:
Два года моей жизни в одном хранилище…. Поздравляю @pkhuong @arexus и всех! Https://t.co/jPFnYrc5V4
После попыток упаковать некоторые внутренние компоненты в течение более двух лет мы недавно получили согласие на открытие исходного кода AppNexus Common Framework под лицензией Apache License 2.0, несмотря на его неполное состояние.
ACF содержит базовую структуру данных и код библиотеки времени выполнения, который мы используем для создания производственных сервисов, на языке C. Некоторые из них правильно упакованы, большая часть содержит только необработанные файлы из нашего внутреннего репозитория. По иронии судьбы, остановившись на названии проекта, мы решили не публиковать самые «фреймворковые» фрагменты кода: неясно, что кому-то еще будет выгодно. Структуры данных написаны на языке C и, как правило, оптимизированы для чтения, возможно, с некоторой поддержкой неблокирующего параллелизма с одной записью и несколькими читателями. Существуют также некоторые неблокирующие алгоритмы для поддержки структур данных и некоторый базовый код HTTP-сервера, который, как мы сочли, полезен для запуска служб с интенсивным использованием ЦП или смешанных служб с интенсивным использованием ЦП и сети.
Публикация нашего внутреннего кода заняла много времени, потому что мы пытались открыть проект, которого еще не было, несмотря на то, что он состоял из кода, который мы используем каждый день. AppNexus не продает код или двоичные файлы. Как и многие другие компании, AppNexus продает услуги, поддерживаемые внутренним кодом. Наша внутренняя кодовая база заполнена неформальными библиотеками (я не смог бы разобраться в кодовой базе, если бы она не была организована таким образом), но обеспечение четкого разделения между псевдобиблиотеками - это большая дополнительная работа, имеющая сомнительную ценность.
Эти нечеткие разграничения усугубляются тем, что мы импортировали некоторые идеи непосредственно из литературы по операционным системам, чтобы поддерживать эффективные параллельные операции. Это произвело эффект снежного кома: все, даже базовые структуры данных, в конечном итоге косвенно зависит от кода фреймворка, который специализируется на нашем варианте использования. Обычными первыми нарушителями являются модуль безопасного восстановления памяти и отслеживающий распределитель памяти (с режимом ударного указателя); Оба они глубоко разбираются во внутреннем устройстве, что, вероятно, не имеет смысла вне AppNexus.
Еще в 2015 году мы изучили наш внутренний код поддержки (то есть код, который напрямую не управляет бизнесом) и решили, что должны поделиться им. Мы были и до сих пор уверены, что другие люди сталкиваются с аналогичными проблемами, и обмен идеями, если не прямая торговля кодом, может быть полезен только нам и кодерам в целом. Мы попытались распутать внутреннюю «Общую» вспомогательную библиотеку от остальной части кода и отделить ее от более самоуверенных частей нашего кода, сохраняя при этом интеграцию (она нам нужна), но исключительно по желанию.
Это было тяжело. Стремление к отдельному общему объекту и пакету Debian сделало это еще сложнее, чем должно было быть. Сильное разделение упакованного кода ACF и остальной части репо добавило много трений, и большая часть кода поддержки осталась в дереве.
Может быть, мы сделали ошибку, когда пытались «распечатать» наши внутренние компоненты. Нам нужна библиотека многоразового кода; это не означает, что нам нужен буквальный общий объект. Мне вспоминаются два определения переносимого кода: код, усыпанный условными обозначениями платформы, или код, который можно заставить работать на другой платформе с минимальными усилиями. В большинстве случаев я предпочитаю последнее. В частности, когда код в основном выполняется на одной платформе или интегрирован в несколько программ, я бы предпочел уменьшить накладные расходы для общего случая, сделав повторное использование возможным и достаточно простым, чтобы другие могли извлечь выгоду.
Вот как мы реализовали ACF: мы согласились с тем, что результат не будет таким безупречным, как наши любимые библиотеки с открытым исходным кодом, и что большая часть кода даже не будет упакована или полностью отделена от внутренних компонентов. Это далеко не идеальное состояние, но оно ближе к нашим целям, чем держать проект в секрете и отодвигать на второй план. Мы получили это, «упаковав» объем работы - сократив ее до выяснения того, что никогда не будет полезно другим, и отслеживая лицензии и происхождение - перед тем, как отправить частичный результат в общедоступный репозиторий. Неудивительно, что как только это было сделано, мы выполнили больше работы над ACF за несколько дней, чем в прошлом году.
Теперь, когда ACF вышел, нам все еще нужно найти лучший способ помочь другим использовать наш код, синхронизировать публичный репозиторий с нашим внутренним репозиторием и, в моих мечтах, принять патчи для публичного репо и иметь они работают и на внутренний. В конце концов, важно, чтобы код был доступен с четкой лицензией, и чтобы кто-то с похожими проблемами мог легко позаимствовать наши идеи, если не наш код.
Если кто-то еще находится в такой же ситуации, пожалуйста, дайте себе разрешение открыть исходный код чего-то, что еще не полностью упаковано. Какими бы неприятными ни были такие проекты, это должно быть лучше, чем держать их закрытыми.
Как печатать целые числа быстрее
В файле преобразования целых чисел в строковые (an_itoa) реализовано несколько забавных идей для решения удручающе распространенной проблемы. Мне он настолько нравится, что это первый файл, который я очистил и упаковал после того, как сделал репозиторий общедоступным.
Мы написали этот код в июле 2014 года. В то время у нас было приложение с умеренным развертыванием (пара стоек на трех континентах), которое приближалось к полной загрузке ... в то время как больше машин находилось в разработке, быстрый perf прогон показал, что оно тратит много времени на преобразование строк в целые числа и обратно. У нас уже была быстрая строка для целочисленной функции. Однако преобразование машинных целых чисел обратно в строку требует немного больше усилий и занимает около 20% от общего времени процессора.
Конечно, реальное решение здесь - не иметь этой проблемы. Нам вообще не следовало использовать удобочитаемый формат, такой как JSON. Мы давно поняли, что формат будет проблемой, и фактически находились в середине перехода, после первого временного исправления (замены части теоретически реконфигурируемого Javascript, который почти никогда не перенастраивался, на жестко запрограммированный C, который выполнял тот же JSON манипуляции). Но вот мы были посреди этого медленного перехода, включающего терабайты ценных постоянных данных, и нам нужно было еще раз увеличить скорость, пока protobuf не был готов к работе.
Когда вы застряли с кодом C, который был вручную преобразован, строка за строкой, из Javascript, вы не хотите пытаться вносить в код высокоуровневые изменения. Единственная разумная быстрая победа заключалась в более быстром преобразовании целых чисел в строковые.
Удобочитаемые форматы, приводящие к потере циклов ЦП на печать целых чисел, - обычная проблема, и мы быстро нашли несколько многообещающих подходов или библиотек. Нашей базовой линией был код системы счисления 10 в строковых кодировщиках. В этом сообщении о Lwan предлагалось использовать radix-10, но генерировать строки в обратном направлении, а не наоборот, как в библиотеке stringencoders. Facebook явно столкнулся с аналогичной проблемой в 2013 году, что привело к этому решению Андрея Александреску. Код Facebook представляет собой комбинацию двух ключевых идей: кодирования radix-100 и определения размера строки заранее с поиском скачкообразным образом, чтобы сгенерировать результат в обратном направлении, прямо туда, куда он должен идти.
Radix-100 имеет смысл, хотя я не был поклонником 200-байтовой таблицы поиска. Я также сомневался в стремительных поисках; это много ответвлений, и их не всегда легко предсказать. Тип memmove, который нам нужно исправить после преобразования, невелик и легко специализируется на x86, поэтому нам может вообще не понадобиться знать количество цифр.
Затем я посмотрел на микробенчмарки в сообщении Андрея, и они сделали вид, что код был либо протестирован на целых числах с фиксированным числом цифр (например, только 4-значные целые числа), либо выбран случайным образом с равномерной вероятностью в большом диапазоне.
Если количество цифр фиксировано, разветвленность быстрого поиска не является проблемой. При равномерной выборке ... это тоже не проблема: большинство целых чисел большие! Если я выберу наугад целое число в [0, 1e6), 90% целых чисел будут иметь 6 цифр, 99% 5 или 6 и т. Д.
Иногда единообразный выбор отражает реальную рабочую нагрузку (например, случайные идентификаторы uid или последовательные идентификаторы объектов). Часто не так уж и много. Как правило, более распространены небольшие количества; например, можно ожидать, что небольшие числа будут примерно следовать экспоненте.
Я также был обеспокоен объемом кэша данных с большей таблицей поиска для кодировки radix-100, но затем понял, что мы конвертируем целые числа в жестких циклах, поэтому таблица поиска обычно должна быть горячей. Это также означало, что мы могли позволить себе много байтов команд; функция с несколькими atoi КБ недопустима, но пара сотен байтов вполне подойдет.
Учитывая эти известные решения, мы с Джоном начали немного рисовать. Ясно, что кодировка radix-100 была хорошей идеей. Теперь мы должны знать, можем ли мы добиться большего.
Наша первая попытка заключалась в том, чтобы найти количество десятичных цифр быстрее, чем при поиске скачком. Оказалось, что приблизить log_10 сложно, и мы сдались;)
Затем мы поняли, что нам не нужно знать количество десятичных цифр. Если бы мы сгенерировали строку в регистрах, мы могли бы узнать длину постфактум, сдвинуть символы с помощью побитового сдвига и напрямую записать в память.
Меня все еще беспокоила таблица поиска: случайные обращения к 200-байтовой таблице для кодировки radix-100 могли повредить при преобразовании коротких массивов небольших целых чисел. Мне было удобнее использовать некоторую форму арифметики, которая меняла бы скорость в лучшем случае на стабильную, хотя и немного неоптимальную производительность. Как оказалось, легко преобразовать значения от 0 до 100 в распакованный двоично-десятичный код с обратным умножением на 1/10 и некоторым перемещением битов в регистре. Когда у нас есть строка байтов BCD, мы можем добавить '0' по вертикали для преобразования в символы ASCII.
Подход radix-100 хорош тем, что он разделяет ввод на две цифры за раз; время выполнения для данного целого числа примерно вдвое меньше, поскольку современные процессоры имеют множество исполнительных блоков для тела.
График зависимости для кодировки radix-10 12345678 выглядит следующим образом с 7 последовательными шагами.
При переходе на radix-100 количество шагов уменьшается вдвое, до 4; шаги по-прежнему последовательны, за исключением преобразования целых чисел в [0, 100) в строки.
Можем ли мы выставить еще больше ILP, чем цикл radix-100?
Уловка состоит в том, чтобы разделить и победить: разделите на 10000 (1e4) перед разделением каждой группы из четырех цифр с преобразованием radix-100.
Истинное рекурсивное кодирование дает нам меньше шагов, и 2 из 3 шагов могут выполняться параллельно. Однако это не всегда может стоить хлопот для небольших целых чисел, и мы знаем, что маленькие числа - обычное дело. Таким образом, даже если у нас есть хороший подход «разделяй и властвуй» для больших целых чисел, мы также должны реализовать быстрый путь для небольших целых чисел.
Быстрый путь для малых целых чисел (или наиболее значимая часть больших целых чисел) преобразует 2- или 4-значное целое число в распакованный BCD, находит количество ведущих нулей, преобразует BCD в ASCII, добавляя '0' (0x30) к каждому байту, и сдвигает любой ведущий ноль; мы предполагаем, что замыкающий шум допустим, и в любом случае это все NUL байтов.
Для 32-битных целых чисел an_itoa (на самом деле an_uitoa) выглядит так:
if number < 100:
execute specialised 2-digit function
if number < 10000:
execute specialised 4-digit function
partition number with first 4 digits, next 4 digits, and remainder.
convert first 2 groups of 4 digits to string.
if the number is < 1e8: # remainder is 0!
shift out leading zeros, print string.
else:
print remainder # at most 100, since 2^32 < 1e10
print strings for the first 2 groups of 4 digits.
64-битная версия, an_ltoa (на самом деле an_ultoa) более похожа, с отличиями, когда входное число превышает 1e8.
Это на самом деле быстрее?
Я уже пришел к выводу, что объем кеш-памяти в основном не является проблемой, но все же важно убедиться, что мы не получаем ничего слишком большого.
an_itoa: 400 байт.an_ltoa: 880 байтfb_itoa: 426 байт + 200 байт LUTfb_constant_itoa(без скачкообразного поиска): 172 байта + 200 байтов LUTlwan_itoa(radix-10, обратная генерация): 60 байт.modp_uitoa10: 91 байт.
Быстрый поиск в конвертере Facebook занимает много места (существует масса условных переходов, и большие числа нужно где-то закодировать). Даже без таблицы поиска an_itoa меньше, чем fb_itoa, а an_ltoa (который добавляет код для ›32-битных целых чисел) всего на 254 байта больше, чем fb_itoa. Быстрый поиск Facebook пытается ускорить выполнение небольших целых чисел, сначала проверяя их; если мы конвертируем маленькие числа, мы не ожидаем использовать все ~ 250 байтов в поиске скачкообразным образом. Это также верно для an_itoa и an_ltoa: код настроен так, что большие числа переходят вперед по специализированным подпрограммам для небольших целых чисел. Маленькие целые числа, таким образом, пропускаются только для выполнения кода в начале функций. 400 или 800 байтов являются значительными следами по сравнению с 60 или 90 байтами функций radix-10, но приемлемы при вызове в тесных циклах.
Теперь, когда мы чувствуем, что размер кода и данных разумны (что редко подчеркивается микробенчерами), мы можем посмотреть на скорость.
Сначала я выполнил преобразование со случайными целыми числами в каждом классе подсчета цифр от 1 цифры (т.е. числа в [0, 10)) до 19 (числа в [1e8, 1e9)). I $ был горячим, но подпрограммы не были подогреты на множестве чисел одного класса (в этом случае было бы более реалистично).
У нас есть данные для:
an_itoa, наша 32-битная процедура преобразования;an_ltoa, наша 64-битная процедура преобразования;fb_constant_itoa, код Facebook, с отключенным поисковым запросом "скачущий";fb_itoa, Radix-100 код Facebook;itoa, преобразование GNU libc (через sprintf);lw_itoa, обратный преобразователь Radix-10 Lwan;modp, преобразователь строкового кодировщика radix-10 /strreverse.
Я включил fb_constant_itoa, чтобы служить нижней границей подхода radix-100: цикл преобразования останавливается, как только он достигает 0 (так же, как fb_itoa), но данные записываются с фиксированным смещением, как это делает lw_itoa. В обоих случаях нам понадобится еще одна копия, чтобы сдвинуть часть буфера вывода, заполненную символами, поверх неиспользуемого заполнения (код Facebook решает проблему, определяя, где должен заканчиваться вывод перед преобразованием).
Некоторые функции идут только до UINT32_MAX, и в этом случае у нас нет данных после 9 цифр.
Сплошная линия - это среднее время на конверсию (в циклах) для более 10 тыс. Точек данных, а заштрихованная область охватывает от 10-го до 90-го процентиля.
(GNU) Преобразование libc далеко не всегда. Простой код modp (строковые кодеры) перекрывается с itoa Facebook; он немного медленнее, но намного меньше.
Затем у нас есть два неполных кодировщика строк: ни fb_constant_itoa, ни lw_itoa не генерируют свой вывод там, где он должен идти. Они заполняют буфер с конца, а что-то еще (не прошедшее тестирование) отвечает за копирование действительных байтов туда, где они принадлежат. Если неполной реализации достаточно, то подход Lwan по системе radix-10 уже конкурирует (возможно, быстрее) с кодом Facebook. Тот же обратный цикл, но в radix-100, определенно быстрее, чем конвертер полного скачкообразного поиска Facebook / radix-100.
И, наконец, у нас есть an_itoa и an_ltoa, которые находятся в стыке друг с другом, быстрее, чем modp и fb_itoa для малых и больших целых чисел, и даже сравнимы или быстрее, чем неполные преобразователи. Их время выполнения также более надежно (меньше дисперсии), чем у modp и fb_itoa: modp платит за второй цикл переменной длины в strreverse, а fb_itoa - за поиск скачком. В an_itoa и an_ltoa больше кодовых путей, но нет цикла, поэтому количество (непредсказуемых) условных переходов меньше.
Что мы узнали из этого эксперимента?
- Улучшить
sprintf(g) libc несложно. В этом есть смысл, поскольку этот код очень общий. Однако на практике мы преобразуем только в десятичный, какой-то шестнадцатеричный, еще менее восьмеричный, а все остальное - это шум. Может быть, мы можем себе позволить особый случай этих баз. - Двойной траверс в
modp_uitoa10болит. Есть смысл избежать этого, создавая обратную генерацию, в идеале в нужном месте с самого начала. - Кодировка Radix-100 превосходит radix-10 (
fb_constant_itoaбыстрее, чемlwan_itoa). - Использование регистров в качестве буферов при генерации цифр является преимуществом (
an_itoaиan_ltoaработают быстрее для небольших значений). - Разделяй и властвуй - это тоже победа (
an_ltoaболее плоский вариант для больших целых чисел).
Получив результаты, которые имели смысл для легко понятного микробенчмарка, я решил попробовать несколько дистрибутивов. Опять же, код был горячим, предикторы теплые, и мы собрали 10 тысяч циклов для каждого распределения / функции.
Очевидно, что мы можем игнорировать sprintf (itoa) glibc.
Первый фасет генерировал целые числа путем равномерного выбора между 100, 1000, ¹⁰⁴,…, ¹⁰⁸. Это полуреалистичная настройка более раннего набора данных, который генерировал кучу чисел в каждом классе размера и служит легко понимаемым наихудшим случаем для прогнозирования ветвлений. И an_itoa, и an_ltoa быстрее, чем другие реализации, и более ответвленные реализации (fb_itoa и modp) демонстрируют их различия. fb_itoa Facebook даже не быстрее, чем кодировщик modp radix-10 / strreverse. Поиск с ускорением действительно мешает (fb_constant_itoa, без этого компонента, немного быстрее, чем сопоставимый radix-10 lw_itoa).
Второй аспект - еще более сложный случай для предикторов ветвления: случайные экспоненты (pow(2, 64.0 * random() / RAND_MAX)) для имитации реальных подсчетов. И an_itoa, и an_ltoa быстрее, чем другие реализации, хотя an_ltoa меньше: an_itoa обрабатывает только 32-битные целые числа, поэтому имеет меньшую энтропию. Между 32-битными реализациями an_itoa заметно быстрее и согласованнее, чем lw_itoa (который также является неполным) и modp. Полные 64-битные преобразователи обычно демонстрируют большую вариативность во время выполнения (их ввод более рандомизирован), но an_ltoa по-прежнему заметно быстрее, чем fb_itoa, и даже чем неполный fb_constant_itoa. Мы также замечаем, что время выполнения fb_itoa более разбросано, чем fb_constant_itoa: быстрый поиск добавляет накладные расходы во времени, но также и большую дисперсию. Это заставляет меня думать, что код Facebook более чувствителен, чем другие, к разнице в распределении данных между микробенчмарками и производственной продукцией.
Третий аспект должен представлять печать внутренних последовательных идентификаторов объектов: равномерные целые числа в [0, 256K). Как и ожидалось, каждый подход более жесткий, чем при экспоненциальном распределении (большинство целых чисел большие). Параметры _93 _ / _ 94_ работают быстрее остальных, и далеко не ясно, что fb_itoa предпочтительнее даже modp. Диапазон был также выбран потому, что это в некотором роде наихудший случай для an_itoa: код выполняет дополнительную работу для значений от 10⁴ до 10⁸, чтобы сделать больше перед условным переходом для x < 1e8. Это никогда не окупается в тестируемом здесь диапазоне. Однако даже с этой слабостью an_itoa все еще кажется предпочтительнее fb_itoa и даже более простому modp_uitoa10.
Четвертый аспект (первый из второй строки) показывает, что происходит, когда мы выбираем случайные целые числа в [0, 20). Этот тестовый пример интересен тем, что он небольшой и поэтому частично репрезентативен для подсчета редких событий, а также потому, что для него требуется 1 или 2 цифры с равной вероятностью. Все работает очень хорошо, и дистрибутивы среды выполнения в целом жесткие; Предикторы ветвления могут неплохо справиться с задачей, когда есть только два варианта. Я не уверен, почему существует такая разница между распределением an_itoa и an_ltoa. Код для любого значения меньше 100 идентичен на уровне C, но есть небольшая разница в генерации кода… но я не могу точно определить, откуда эта разница.
Пятый аспект для случайных целых чисел в [100, 200) аналогичен, с немного большей дисперсией.
Шестой аспект генерирует временные метки unix около даты в 2014 году с равномерным выбором плюс-минус один миллион секунд. Он предназначен для отображения отметок времени печати. Опять же, an_itoa и an_ltoa быстрее остальных, а an_itoa немного быстрее и стабильнее. Radix-100 (fb_constant_itoa) быстрее и согласованнее, чем radix-10 (lw_itoa), но неясно, предпочтительнее ли fb_itoa перед modp. Разница для modp больше, чем для других реализаций, даже fb_itoa: это стоимость цикла radix-10 и дополнительных strreverse.
Этот набор результатов показывает, что условные переходы являются проблемой при преобразовании целых чисел в строки и что важная из ветвей сильно зависит от распределения. Подход Facebook с быстрым поиском числа цифр кажется особенно чувствительным к распределению. Запуск fb_itoa в производственной среде, потому что он хорошо себя показал в микробенчмарке, является хорошей идеей только в том случае, если мы знаем, что микробенчмарк является репрезентативным для производственной среды.
Для преобразования больших чисел требуется больше времени, но подход «разделяй и властвуй» an_itoa и an_ltoa постоянно быстрее на верхнем уровне, в то время как развернутая SIMD в подходе регистров хорошо подходит для небольших чисел.
Итак, если вы когда-нибудь окажетесь в узком месте на s[n]printf
Правильное решение проблемы
itoaработает слишком медленно простое: не делайте этого. В конце концов, если нет особых требований, мы обнаруживаем, что Protobuf очень хорошо работает как лучший JSON.
Однако, как только вы окажетесь в этом плохом месте, нет ничего лучше обычного кода преобразования libc. Это в каком-то смысле делает эту проблему опасно забавной… особенно с учетом того, что распределение данных может иметь такое большое значение. Ни один тест не является идеальным, но на различные реализации по-разному влияют недостатки микробенчмарков. Таким образом, важно не переусердствовать с данными тестов, что, вероятно, даже более важно, чем повышение производительности еще в 10–20% случаев (в 4–5 раз лучше, чем в коде libc, это уже само собой разумеющееся). Вот почему я предпочитаю код преобразования целых чисел с более последовательным подсчетом циклов: меньше места для различий из-за распределения данных.
Наконец, если, как в случае с 2014-AppNexus, вы обнаружите, что конвертируете множество целых чисел в строки в жестких циклах, попробуйте an_itoa или an_ltoa! Весь репозиторий - это Apache 2.0, и должно быть легко скопировать и вставить все зависимости, чтобы сократить его до двух файлов. Также обратите внимание, что функции используют свой целевой массив (до 10 байтов для an_itoa и 20 для an_ltoa) в качестве временного пространства, даже для целых чисел, которым требуется меньше цифр.
Автор Dr. Пол Кхыонг
