10.10.2020 16:22:36 |
Автор: 
Думаю, с переводом чисел в ASCII строки в своей жизни сталкивался каждый программист. В свое время для меня было удивительно узнать, что перевод десятичной цифры в равнозначный ASCII символ операция сложения. С этим знанием я ложился спать, и с этим же знанием я бодро просыпался утром. Но однажды я задал себе вопрос а как переводятся числа с плавающей запятой: Float или Double!? С этого момента, сна в моей жизни, а тем более крепкого и спокойного стало меньше. Уверен, не я один задавался этим вопросом, и более того, не я один нашел ответ на оный. Но я думаю, есть те, кто заблудился, те, кто до сих пор неровно дышит от полного непонимания, что же происходит под капотом этих ваших трансляторов, компиляторов и прочего-прочего. Более того, не только полное отсутствие знаний в трансляции чисел нарушало мое психическое равновесие: люди, услышавшие мои душевные страдания, кидали сомнения в нужности и полезности этого знания. Мне говорили так: Ну раскроешь ты завесу тайны, а дальше то что?! Напишешь свой велосипед, который будет работать в сто раз медленнее?! Иди ка ты, Ваня, асфальт укладывай, а мы тут великим займемся вон, JSON пришел, надо еще подумать, как его переложить.... Я же, парировал: Нет, я напишу мотоцикл! Он будет быстр как Ямаха, а его рев будет устрашать даже матерых программистов!.
Заметка: все тесты и весь код писались / запускались исключительно под x86_x64 архитектуру, little-endian формат. Эту зависимость, следует держать в уме при чтении материала.
Сразу начать писать о переводе плавающих чисел в ASCII строки будет не верно, ведь моя задача не только рассказать о методах и алгоритмах лежащих внутри этих переводов, но и рассказать о том, как мне удалось их улучшить сделать быстрее, агрессивнее! Как-никак, я автор вот этого канала про нуууууу очень хардкорные Оптимизации Asm[x86, ARM] и C / C++. Делать решения быстрее, искать обходные пути мое хобби, мой life-style. Именно поэтому, эту статью я хотел бы посвятить переводу беззнаковых 32-ух-битных чисел в ASCII строки. Поверьте мне, рассказ будет полезным и, надеюсь, интересным: то, что я расскажу вам придумал я и на просторах сети не встречал нигде! Я не берусь утверждать, что в чем-то превзошел кого-либо, мне просто хочется поделиться своим результатом, трюком который, может, поможет и вам. Более того, вещи описанные здесь, упростят жизнь и читателю, в понимании дальнейшего развития цикла статей, и мне в описании того, как это работает(смогу делать отсылки на эту статью).
Начнем с малого: разберем примитивный алгоритм перевода 32-ух битного беззнакового целого числа в ASCII строку и опишем его недостатки.
В самом общем случае, мы получаем последнюю цифру числа, записываем ее ASCII представление в область памяти строки(в начало строки, и увеличиваем индекс начала на 1), и то же самое проделываем для оставшихся цифр числа. Затем, строку переворачиваем и получаем ответ. Конечно, мы можем ничего не переворачивать, а идти в обратную сторону с конца итоговой числовой строки, уменьшая текущую позицию. Для этого, нам все же нужно будет эту конечную позицию вычислить, то есть придется вычислить длину получающейся строки. В этом алгоритме есть моменты, на которые стоит обратить внимание если вы хотите, чтобы это работало быстрее:
1. Мы должны делать операции взятия остатка на 10, а само число на каждой итерации делить нацело на 10. Здесь, конечно, деления не будет компилятор заменит его умножением.
2. Операции из пункта один могут запросто создавать Dependency Chain в конвейере процессора.
3. Мы постоянно обращаемся к памяти, чтобы что-то туда записать, что-то достать дело тут не столько в КешМиссах, сколько в том, что даже наличие значения в кеше L1 чего-то да стоит, и опять же, грузит блоки конвейера Процессора, по линиям RW. Более того, команда MOV ассемблера при работе с голой памятью, если верить Агнеру Фогу, имеет больший latency, нежели ее регистровый собрат.
4. Мы как минимум должны вычислить либо длину строки, либо произвести операцию переворота строки, что опять же излишества
Оптимизации этого алгоритма существуют, и как правило лежат в основе различных библиотек: например, плюсовый to_chars(C++17), а еще abseil, google-овый.
Вот какие улучшения я встречал:
1. Использование LUT, для того, чтобы записывать в строку не по одной цифре, а по две за раз(деление нацело на 100, остаток из той же серии в конце перевода, делаем проверку на то, что у нас осталась либо одна цифра, либо деление завершено).
2. Разворот цикла бегущего по цифрам числа, точнее избавление от оного вовсе.
По-крайней мере, первый пункт из списка оптимизаций выше, неминуемо ведет к работе с памятью и дальнейшей амортизации скорости доступа кешем процессора: старые данные вытесняем, новые записываем. Здесь, как повезет, но будет круто, если данные LUT всегда лежат в кеше L1(L2, L3 кеши, конечно, лучше голой памяти, но все равно теряем много), а механизм хардварного префетчинга работает на ура: загрузка данных из оперативной памяти это около 100+ тактов процессора, даже больше. Тем не менее, полную зищиту от воздействия Кеш Памяти, нам дает отсутствие работы с памятью как таковой.
Вот, например, попытки улучшить to_chars в GCC видим, например, оптимизацию за счет LUT. А второй вариант, и вовсе пытается выполнять сжатие этой самой LUT до размера одной кеш линии, что, конечно, идет в ущерб производительности на горячий кеш.
В интернете мождно найти парочку неплохих бенчмарков, сравнивающих существующие реализации перевода беззнаковых, 32-ух битных чисел в ASCII строку по скорости выполнения перевода. Я прогнал многие из них, и выводом получил, что самая быстрая реализация перевода из libfmt. Позже, однако, мне написал danlark (разработчик из google) и предложил потестировать еще и реализацию от google, из библиотеки abseil. Собственно, оная сумела немного обойти реализацию libfmt. Ниже, я привожу код этой реализации, так как именно с ней и буду производить дальнейшие сравнения(все исходники вы сможете найти отдельной ссылкой на github в конце статьи, если читать под спойлером вам не удобно, например):
Код, конечно, на Хабре немного поехал...
const char one_ASCII_final_digits[10][2] { {'0', 0}, {'1', 0}, {'2', 0}, {'3', 0}, {'4', 0}, {'5', 0}, {'6', 0}, {'7', 0}, {'8', 0}, {'9', 0}, };const char two_ASCII_digits[100][2] = { {'0', '0'}, {'0', '1'}, {'0', '2'}, {'0', '3'}, {'0', '4'}, {'0', '5'}, {'0', '6'}, {'0', '7'}, {'0', '8'}, {'0', '9'}, {'1', '0'}, {'1', '1'}, {'1', '2'}, {'1', '3'}, {'1', '4'}, {'1', '5'}, {'1', '6'}, {'1', '7'}, {'1', '8'}, {'1', '9'}, {'2', '0'}, {'2', '1'}, {'2', '2'}, {'2', '3'}, {'2', '4'}, {'2', '5'}, {'2', '6'}, {'2', '7'}, {'2', '8'}, {'2', '9'}, {'3', '0'}, {'3', '1'}, {'3', '2'}, {'3', '3'}, {'3', '4'}, {'3', '5'}, {'3', '6'}, {'3', '7'}, {'3', '8'}, {'3', '9'}, {'4', '0'}, {'4', '1'}, {'4', '2'}, {'4', '3'}, {'4', '4'}, {'4', '5'}, {'4', '6'}, {'4', '7'}, {'4', '8'}, {'4', '9'}, {'5', '0'}, {'5', '1'}, {'5', '2'}, {'5', '3'}, {'5', '4'}, {'5', '5'}, {'5', '6'}, {'5', '7'}, {'5', '8'}, {'5', '9'}, {'6', '0'}, {'6', '1'}, {'6', '2'}, {'6', '3'}, {'6', '4'}, {'6', '5'}, {'6', '6'}, {'6', '7'}, {'6', '8'}, {'6', '9'}, {'7', '0'}, {'7', '1'}, {'7', '2'}, {'7', '3'}, {'7', '4'}, {'7', '5'}, {'7', '6'}, {'7', '7'}, {'7', '8'}, {'7', '9'}, {'8', '0'}, {'8', '1'}, {'8', '2'}, {'8', '3'}, {'8', '4'}, {'8', '5'}, {'8', '6'}, {'8', '7'}, {'8', '8'}, {'8', '9'}, {'9', '0'}, {'9', '1'}, {'9', '2'}, {'9', '3'}, {'9', '4'}, {'9', '5'}, {'9', '6'}, {'9', '7'}, {'9', '8'}, {'9', '9'} };static inline void PutTwoDigits(size_t i, char* buf){ memcpy( buf, two_ASCII_digits[i], 2 );}char* uint32_to_string_1 ( uint32_t i, char *buffer ) noexcept{ uint32_t digits; // The idea of this implementation is to trim the number of divides to as few // as possible, and also reducing memory stores and branches, by going in // steps of two digits at a time rather than one whenever possible. // The huge-number case is first, in the hopes that the compiler will output // that case in one branch-free block of code, and only output conditional // branches into it from below. if (i >= 1000000000) { // >= 1,000,000,000 digits = i / 100000000; // 100,000,000 i -= digits * 100000000; PutTwoDigits(digits, buffer); buffer += 2; lt100_000_000: digits = i / 1000000; // 1,000,000 i -= digits * 1000000; PutTwoDigits(digits, buffer); buffer += 2; lt1_000_000: digits = i / 10000; // 10,000 i -= digits * 10000; PutTwoDigits(digits, buffer); buffer += 2; lt10_000: digits = i / 100; i -= digits * 100; PutTwoDigits(digits, buffer); buffer += 2; lt100: digits = i; PutTwoDigits(digits, buffer); buffer += 2; *buffer = 0; return buffer; } if (i < 100) { digits = i; if (i >= 10) goto lt100; memcpy(buffer, one_ASCII_final_digits[i], 2); return buffer + 1; } if (i < 10000) { // 10,000 if (i >= 1000) goto lt10_000; digits = i / 100; i -= digits * 100; *buffer++ = '0' + digits; goto lt100; } if (i < 1000000) { // 1,000,000 if (i >= 100000) goto lt1_000_000; digits = i / 10000; // 10,000 i -= digits * 10000; *buffer++ = '0' + digits; goto lt10_000; } if (i < 100000000) { // 100,000,000 if (i >= 10000000) goto lt100_000_000; digits = i / 1000000; // 1,000,000 i -= digits * 1000000; *buffer++ = '0' + digits; goto lt1_000_000; } // we already know that i < 1,000,000,000 digits = i / 100000000; // 100,000,000 i -= digits * 100000000; *buffer++ = '0' + digits; goto lt100_000_000;}
В реализации abseil, мы видим обе оптимизации, из описанных мною выше(LUT + избавление от цикла). Более того, хочу отметить, что в этом коде есть немного больше интересного, чем я описываю: эти нюансы больше относятся к архитектурным особенностям процессоров intel, работе branch predictor-а and so on.
Можно ли в принципе избавиться от использования LUT, а данные записывать в память не так часто? Да, можно: используя один трюк, который вы могли упустить из виду. Про этот трюк и пойдет дальнейший рассказ.
Память в компьютере бывает разная это вам и RAM и SSD, Кеш Память процессора, или защищенные буферы оного, анклавы e.t.c. Есть еще один очень интересный тип памяти регистровая, и она, к слову, очень быстрая. Если вам доводилось программировать GPU вы прекрасно понимаете о чем я. У каждого процессора свой набор регистров: их как правило ограниченное количество, они имеют свою битность и команды процессора, которые умеют оперировать содержимым оных. Именно регистровую память я и предлагаю использовать в качестве буфера для записи итоговой ASCII строки. Скажем, регистр емкостью 8 байт, мы можем использовать как строку из 8 ASCII символов. А если нам нужно 10 байт, а именно столько нам и нужно для корректного перевода целого, беззнакового 32-ух битного числа, мы просто возьмем два регистра. Получать значения по индексу в таком мини-буффере просто: воспользуемся логическими операциями процессора, а именно AND по битовой маске вида 0x..FF В нашем случае, получать / записывать значения по индексу не требуется. Нам нужно записывать значения в буфер так, чтобы затем, при сохранении в Оперативную память, нам не пришлось переворачивать полученную строку. Получили цифру числа, записали в конец буфера и пошли дальше, к началу. Тут нам на помощь, приходят битовые(циклические) сдвиги. Записав последнюю цифру числа и выполнив такой сдвиг мы как бы переворачиваем строку, и движемся от конца к началу. Для начала я приведу код описанной реализации, а затем, отвечу на вопросы, которые у вас точно появятся, после того, как вы увидите ее:
Код, конечно, на Хабре немного поехал...
char* uint32_to_string_0 ( uint32_t n, char *out_str ) noexcept{ if ( n < 10u ) { const uint64_t in = n + 0x30ull; memcpy( out_str, &in, 8u ); return out_str + 1u; } const uint32_t b = n / 10u; if ( n < 100u ) { const uint64_t in = 256ull * n - 2559ull * b + 0x3030ull; memcpy( out_str, &in, 8u ); return out_str + 2u; } const uint32_t c = n / 100u; if ( n < 1000u ) { const uint64_t in = 65536ull * n - 2559ull * ( 256ull * b + c ) + 0x303030ull; memcpy( out_str, &in, 8u ); return out_str + 3u; } const uint32_t d = n / 1000u; if ( n < 10000u ) { const uint64_t in = 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) + 0x30303030ull; memcpy( out_str, &in, 8u ); return out_str + 4u; } const uint32_t e = n / 10000u; if ( n < 100000u ) { const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x08ull ) + e + 0x3030303030ull; memcpy( out_str, &in, 8u ); return out_str + 5u; } const uint32_t f = n / 100000u; if ( n < 1000000u ) { const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x10ull ) + ( ( 256ull * e - 2559ull * f ) + 0x303030303030ull ); memcpy( out_str, &in, 8u ); return out_str + 6u; } const uint32_t g = n / 1000000u; if ( n < 10000000u ) { const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x18ull ) + ( ( 65536ull * e - 2559ull * ( 256ull * f + g ) + 0x30303030303030ull ) ); memcpy( out_str, &in, 8u ); return out_str + 7u; } const uint32_t h = n / 10000000u; if ( n < 100000000u ) { const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x20ull ) + ( ( 16777216ull * e - 2559ull * ( 256ull * ( 256ull * f + g ) + h ) ) + 0x3030303030303030ull ); memcpy( out_str, &in, 8u ); return out_str + 8u; } const uint32_t x = n / 100000000u; const uint64_t r_0 = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x20ull ) + ( 16777216ull * e - 2559ull * ( 256ull * ( 256ull * f + g ) + h ) - 10 * x ); if ( 9u < x ) { const uint64_t in_1 = ( ( x % 10u ) << 8ull ) + x / 10u + 0x3030ull; memcpy( out_str, &in_1, 8u ); const uint64_t in_2 = ( ( r_0 + 0x3030303030303030ull ) ); memcpy( out_str + 2u, &in_2, 8u ); return out_str + 9u; } else { const uint64_t in_1 = x + 0x30u; memcpy( out_str, &in_1, 8u ); const uint64_t in_2 = r_0 + 0x3030303030303030ull; memcpy( out_str + 1u, &in_2, 8u ); return out_str + 10u; }}
Где сдивги? Где нахождение последней цифры? А эти коэффициенты, это что, магические числа, да? Обо всем по порядку. Сдвиги, это вам не только сдвиги это еще и операции умножения на степень двойки. Нахождение последнй цифры числа операция взятия остатка на 10. Компиляторы легко заменяют ее на более дешевую операцию умножения, получая тождественные результаты. Я писал про этот трюк тут(но смысл статьи в том, что можно сделать лучше, и компиляторы этого не делают). Собственно, сдвиги и коэффициенты умножения я объединил вместе. А вот эта вся сумма, а точнее формула для нахождения итоговой строки это сумма регистров, каждый из которых содержит одну ASCII цифру итоговой строки в нужной позиции. Другими словами, мы имеем дело с выражением следующего вида(переводим четырехзначное число в строку):
Здесь, a, b, c, d результаты целочисленного деления на 1, 10, 100, 1000 переводимого в строку числа.
Выражение в скобочках вычисление цифры числа. Итоговая сумма сама строка. Вру, к ней же еще нужно добавить 0x30 в каждом байтике: эту операцию мы можем сделать единожды, просто прибавив 8-ми байтовое 0x30...0x30. А что по бенчмаркам, Ваня? Вот бенчмарк(позаимствовал у abseil), а вот результаты на AMD Rayzen 7 3700x(BM_FastIntToBuffer_1 моя реализация, BM_FastIntToBuffer_2 abseil):
-----------------------------------------------------------------------------------Benchmark Time CPU Iterations-----------------------------------------------------------------------------------BM_FastIntToBuffer_1<int32_t>/0 0.456 ns 0.456 ns 1000000000BM_FastIntToBuffer_1<int32_t>/0 0.455 ns 0.455 ns 1000000000BM_FastIntToBuffer_1<int32_t>/1 3.40 ns 3.40 ns 228868292BM_FastIntToBuffer_1<int32_t>/8 3.79 ns 3.79 ns 194594644BM_FastIntToBuffer_1<int32_t>/64 3.99 ns 3.99 ns 176719588BM_FastIntToBuffer_1<int32_t>/512 4.01 ns 4.01 ns 174835143BM_FastIntToBuffer_1<int32_t>/4096 4.01 ns 4.01 ns 174360728BM_FastIntToBuffer_1<int32_t>/32768 4.01 ns 4.01 ns 174990974BM_FastIntToBuffer_1<int64_t>/0 0.456 ns 0.456 ns 1000000000BM_FastIntToBuffer_1<int64_t>/0 0.455 ns 0.455 ns 1000000000BM_FastIntToBuffer_1<int64_t>/1 3.38 ns 3.38 ns 230695679BM_FastIntToBuffer_1<int64_t>/8 3.78 ns 3.78 ns 195911364BM_FastIntToBuffer_1<int64_t>/64 4.00 ns 4.00 ns 176595354BM_FastIntToBuffer_1<int64_t>/512 4.02 ns 4.01 ns 174571183BM_FastIntToBuffer_1<int64_t>/4096 4.02 ns 4.02 ns 173962202BM_FastIntToBuffer_1<int64_t>/32768 4.01 ns 4.01 ns 174352211BM_FastIntToBuffer_1<int64_t>/262144 4.01 ns 4.01 ns 174021355BM_FastIntToBuffer_1<int64_t>/2097152 4.02 ns 4.02 ns 174066641BM_FastIntToBuffer_1<int64_t>/16777216 4.04 ns 4.04 ns 172736260BM_FastIntToBuffer_1<int64_t>/134217728 3.91 ns 3.91 ns 178819304BM_FastIntToBuffer_1<int64_t>/1073741824 3.26 ns 3.26 ns 214479196BM_FastIntToBuffer_2<int32_t>/0 4.78 ns 4.78 ns 146524823BM_FastIntToBuffer_2<int32_t>/0 4.78 ns 4.78 ns 146525099BM_FastIntToBuffer_2<int32_t>/1 7.02 ns 7.02 ns 102428060BM_FastIntToBuffer_2<int32_t>/8 6.66 ns 6.66 ns 99453560BM_FastIntToBuffer_2<int32_t>/64 6.45 ns 6.45 ns 104754274BM_FastIntToBuffer_2<int32_t>/512 6.44 ns 6.44 ns 107937513BM_FastIntToBuffer_2<int32_t>/4096 6.44 ns 6.44 ns 108483775BM_FastIntToBuffer_2<int32_t>/32768 6.44 ns 6.44 ns 108500271BM_FastIntToBuffer_2<int64_t>/0 4.78 ns 4.78 ns 146476646BM_FastIntToBuffer_2<int64_t>/0 4.78 ns 4.78 ns 146442788BM_FastIntToBuffer_2<int64_t>/1 7.05 ns 7.05 ns 99472455BM_FastIntToBuffer_2<int64_t>/8 6.67 ns 6.67 ns 99141872BM_FastIntToBuffer_2<int64_t>/64 6.45 ns 6.45 ns 104705700BM_FastIntToBuffer_2<int64_t>/512 6.44 ns 6.44 ns 107980669BM_FastIntToBuffer_2<int64_t>/4096 6.44 ns 6.44 ns 108475908BM_FastIntToBuffer_2<int64_t>/32768 6.44 ns 6.44 ns 108548677BM_FastIntToBuffer_2<int64_t>/262144 6.44 ns 6.44 ns 108581914BM_FastIntToBuffer_2<int64_t>/2097152 6.44 ns 6.43 ns 108572736BM_FastIntToBuffer_2<int64_t>/16777216 6.43 ns 6.43 ns 108629837BM_FastIntToBuffer_2<int64_t>/134217728 6.37 ns 6.37 ns 109567105BM_FastIntToBuffer_2<int64_t>/1073741824 5.97 ns 5.97 ns 116885892
Более того, я проводил тесты и на других процессорах результаты сопоставимы. В частности, тестировал и на Ryzen 9 3900x, и на ноутбуке с Intel i7 haswell 4th gen, а также запускал на мобильном девайсе(armv8):
benchmark: 12 ns BM_FastIntToBuffer_1<int32_t>/0benchmark: 8 ns BM_FastIntToBuffer_1<int32_t>/0benchmark: 28 ns BM_FastIntToBuffer_1<int32_t>/1benchmark: 30 ns BM_FastIntToBuffer_1<int32_t>/8benchmark: 34 ns BM_FastIntToBuffer_1<int32_t>/64benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/512benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/4096benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/32768benchmark: 9 ns BM_FastIntToBuffer_1<int64_t>/0benchmark: 9 ns BM_FastIntToBuffer_1<int64_t>/0benchmark: 28 ns BM_FastIntToBuffer_1<int64_t>/1benchmark: 31 ns BM_FastIntToBuffer_1<int64_t>/8benchmark: 34 ns BM_FastIntToBuffer_1<int64_t>/64benchmark: 36 ns BM_FastIntToBuffer_1<int64_t>/512benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/4096benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/32768benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/262144benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/2097152benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/16777216benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/134217728benchmark: 32 ns BM_FastIntToBuffer_1<int64_t>/1073741824benchmark: 15 ns BM_FastIntToBuffer_2<int32_t>/0benchmark: 15 ns BM_FastIntToBuffer_2<int32_t>/0benchmark: 51 ns BM_FastIntToBuffer_2<int32_t>/1benchmark: 55 ns BM_FastIntToBuffer_2<int32_t>/8benchmark: 59 ns BM_FastIntToBuffer_2<int32_t>/64benchmark: 57 ns BM_FastIntToBuffer_2<int32_t>/512benchmark: 56 ns BM_FastIntToBuffer_2<int32_t>/4096benchmark: 56 ns BM_FastIntToBuffer_2<int32_t>/32768benchmark: 14 ns BM_FastIntToBuffer_2<int64_t>/0benchmark: 14 ns BM_FastIntToBuffer_2<int64_t>/0benchmark: 51 ns BM_FastIntToBuffer_2<int64_t>/1benchmark: 55 ns BM_FastIntToBuffer_2<int64_t>/8benchmark: 58 ns BM_FastIntToBuffer_2<int64_t>/64benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/512benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/4096benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/32768benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/262144benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/2097152benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/16777216benchmark: 55 ns BM_FastIntToBuffer_2<int64_t>/134217728benchmark: 46 ns BM_FastIntToBuffer_2<int64_t>/1073741824
Важно отметить, что сам алгоритм не старается выполнить все умножения, деления, остатки за раз а чередует их пачками, дабы максимально нагрузить конвейер процессора. Сначала мы грузим вычислительные блоки, а затем, грузим блоки Записи / Чтения, Логических операций, затем, снова делаем вычислительные операции, тем самым, не давая Бэкенду и Фронтенду (да, современные процессоры обладают такими штуками) простаивать, а цепочка зависимостей получается не такая и большая. К памяти мы обращаемся максимум дважды(хотя префетчер скорее всего поместит в кеш именно две кеш линии, даже если нам нужна только одна): когда записываем результат. LUT отсутствует, а вот if-ов хватает, тут уж нам остается верить в наш branch predictor.
Упомянутый выше danlark прогонял бенчмарк на серверном железе, и результаты получилсь близкими, то есть такого разрыва в 1.5 раза как выше не наблюдалось.
Смысл этой статьи не столько в переводе чисел в строки, сколько в напоминании о том, что со строками можно работать как с числами. Да, мы получаем / можем получить зависимость порядка байт, но, возможно, полученный результат будет настолько хорош, что на эти моменты и неудобства можно будет закрыть глаза. Я использовал этот прием в разных задачах, и могу сказать, что плюсы у него точно есть: реален случай, когда подобный трюк, позволял компилятору сделать довольно сложную векторизацию кода, например.
Многое из описанного здесь, писалось еще два месяца назад, и по этой причине, результаты разных бенчмарков были утеряны, тем не менее, кое-что удалось сохранить, этим я и поделился выше. Также, отмечу, что C++17 to_chars дает неплохие результаты, но не такие хорошие как у libfmt, abseil. Ниже я оставляю ссылку на код Бенчмарка, и буду очень признателен, если вы запустите его у себя, а результатами поделитесь в комментариях. Очень хочется посмотреть на Малинку, Ардуинку, Андроид(посовременнее) или Apple, RISC и пр.
А вот и код google бенчмарка:
https://github.com/ov3rdr1v337/decima/blob/main/mybenchmark.cc
Категории: 
