Думаю, с переводом чисел в ASCII строки в своей жизни сталкивался каждый программист. В свое время для меня было удивительно узнать, что перевод десятичной цифры в равнозначный ASCII символ – операция сложения. С этим знанием я ложился спать, и с этим же знанием я бодро просыпался утром. Но однажды я задал себе вопрос – а как переводятся числа с плавающей запятой: Float или Double!? С этого момента, сна в моей жизни, а тем более крепкого и спокойного – стало меньше. Уверен, не я один задавался этим вопросом, и более того, не я один нашел ответ на оный. Но я думаю, есть те, кто заблудился, те, кто до сих пор неровно дышит от полного непонимания, что же происходит под капотом этих ваших трансляторов, компиляторов и прочего-прочего. Более того, не только полное отсутствие знаний в трансляции чисел нарушало мое психическое равновесие: люди, услышавшие мои душевные страдания, кидали сомнения в нужности и полезности этого знания. Мне говорили так: “Ну раскроешь ты завесу тайны, а дальше то что?! Напишешь свой велосипед, который будет работать в сто раз медленнее?! Иди ка ты, Ваня, асфальт укладывай, а мы тут великим займемся – вон, JSON пришел, надо еще подумать, как его переложить...”. Я же, парировал: “Нет, я напишу мотоцикл! Он будет быстр как Ямаха, а его рев будет устрашать даже матерых программистов!”.
Заметка: все тесты и весь код писались / запускались исключительно под x86_x64 архитектуру, little-endian формат. Эту зависимость, следует держать в уме при чтении материала.
Сразу начать писать о переводе плавающих чисел в ASCII строки – будет не верно, ведь моя задача не только рассказать о методах и алгоритмах лежащих внутри этих переводов, но и рассказать о том, как мне удалось их улучшить – сделать быстрее, агрессивнее! Как-никак, я автор вот этого канала про нуууууу очень хардкорные Оптимизации Asm[x86, ARM] и C / C++. Делать решения быстрее, искать обходные пути – мое хобби, мой life-style. Именно поэтому, эту статью я хотел бы посвятить переводу беззнаковых 32-ух-битных чисел в ASCII строки. Поверьте мне, рассказ будет полезным и, надеюсь, интересным: то, что я расскажу вам – придумал я и на просторах сети не встречал нигде! Я не берусь утверждать, что в чем-то превзошел кого-либо, мне просто хочется поделиться своим результатом, трюком – который, может, поможет и вам. Более того, вещи описанные здесь, упростят жизнь и читателю, в понимании дальнейшего развития цикла статей, и мне — в описании того, как это работает(смогу делать отсылки на эту статью).
Начнем с малого: разберем примитивный алгоритм перевода 32-ух битного беззнакового целого числа в ASCII строку и опишем его недостатки.
В самом общем случае, мы получаем последнюю цифру числа, записываем ее ASCII представление в область памяти строки(в начало строки, и увеличиваем индекс начала на 1), и то же самое проделываем для оставшихся цифр числа. Затем, строку переворачиваем и получаем ответ. Конечно, мы можем ничего не переворачивать, а идти в обратную сторону – с конца итоговой числовой строки, уменьшая текущую позицию. Для этого, нам все же нужно будет эту конечную позицию вычислить, то есть придется вычислить длину получающейся строки. В этом алгоритме есть моменты, на которые стоит обратить внимание если вы хотите, чтобы это работало быстрее:
- Мы должны делать операции взятия остатка на 10, а само число на каждой итерации делить нацело на 10. Здесь, конечно, деления не будет – компилятор заменит его умножением.
- Операции из пункта один могут запросто создавать Dependency Chain в конвейере процессора.
- Мы постоянно обращаемся к памяти, чтобы что-то туда записать, что-то достать – дело тут не столько в КешМиссах, сколько в том, что даже наличие значения в кеше L1 – чего-то да стоит, и опять же, грузит блоки конвейера Процессора, по линиям RW. Более того, команда MOV ассемблера при работе с голой памятью, если верить Агнеру Фогу, имеет больший latency, нежели ее регистровый собрат.
- Мы как минимум должны вычислить либо длину строки, либо произвести операцию переворота строки, что опять же – излишества…
Оптимизации этого алгоритма существуют, и как правило лежат в основе различных библиотек: например, плюсовый to_chars(C++17), а еще abseil, google-овый.
Вот какие улучшения я встречал:
- Использование LUT, для того, чтобы записывать в строку не по одной цифре, а по две за раз(деление нацело на 100, остаток из той же серии – в конце перевода, делаем проверку на то, что у нас осталась либо одна цифра, либо деление завершено).
- Разворот цикла бегущего по цифрам числа, точнее – избавление от оного вовсе.
По крайней мере, первый пункт из списка оптимизаций выше, неминуемо ведет к работе с памятью и дальнейшей амортизации скорости доступа кешем процессора: старые данные вытесняем, новые записываем. Здесь, как повезет, но будет круто, если данные 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 1000000000
BM_FastIntToBuffer_1<int32_t>/0 0.455 ns 0.455 ns 1000000000
BM_FastIntToBuffer_1<int32_t>/1 3.40 ns 3.40 ns 228868292
BM_FastIntToBuffer_1<int32_t>/8 3.79 ns 3.79 ns 194594644
BM_FastIntToBuffer_1<int32_t>/64 3.99 ns 3.99 ns 176719588
BM_FastIntToBuffer_1<int32_t>/512 4.01 ns 4.01 ns 174835143
BM_FastIntToBuffer_1<int32_t>/4096 4.01 ns 4.01 ns 174360728
BM_FastIntToBuffer_1<int32_t>/32768 4.01 ns 4.01 ns 174990974
BM_FastIntToBuffer_1<int64_t>/0 0.456 ns 0.456 ns 1000000000
BM_FastIntToBuffer_1<int64_t>/0 0.455 ns 0.455 ns 1000000000
BM_FastIntToBuffer_1<int64_t>/1 3.38 ns 3.38 ns 230695679
BM_FastIntToBuffer_1<int64_t>/8 3.78 ns 3.78 ns 195911364
BM_FastIntToBuffer_1<int64_t>/64 4.00 ns 4.00 ns 176595354
BM_FastIntToBuffer_1<int64_t>/512 4.02 ns 4.01 ns 174571183
BM_FastIntToBuffer_1<int64_t>/4096 4.02 ns 4.02 ns 173962202
BM_FastIntToBuffer_1<int64_t>/32768 4.01 ns 4.01 ns 174352211
BM_FastIntToBuffer_1<int64_t>/262144 4.01 ns 4.01 ns 174021355
BM_FastIntToBuffer_1<int64_t>/2097152 4.02 ns 4.02 ns 174066641
BM_FastIntToBuffer_1<int64_t>/16777216 4.04 ns 4.04 ns 172736260
BM_FastIntToBuffer_1<int64_t>/134217728 3.91 ns 3.91 ns 178819304
BM_FastIntToBuffer_1<int64_t>/1073741824 3.26 ns 3.26 ns 214479196
BM_FastIntToBuffer_2<int32_t>/0 4.78 ns 4.78 ns 146524823
BM_FastIntToBuffer_2<int32_t>/0 4.78 ns 4.78 ns 146525099
BM_FastIntToBuffer_2<int32_t>/1 7.02 ns 7.02 ns 102428060
BM_FastIntToBuffer_2<int32_t>/8 6.66 ns 6.66 ns 99453560
BM_FastIntToBuffer_2<int32_t>/64 6.45 ns 6.45 ns 104754274
BM_FastIntToBuffer_2<int32_t>/512 6.44 ns 6.44 ns 107937513
BM_FastIntToBuffer_2<int32_t>/4096 6.44 ns 6.44 ns 108483775
BM_FastIntToBuffer_2<int32_t>/32768 6.44 ns 6.44 ns 108500271
BM_FastIntToBuffer_2<int64_t>/0 4.78 ns 4.78 ns 146476646
BM_FastIntToBuffer_2<int64_t>/0 4.78 ns 4.78 ns 146442788
BM_FastIntToBuffer_2<int64_t>/1 7.05 ns 7.05 ns 99472455
BM_FastIntToBuffer_2<int64_t>/8 6.67 ns 6.67 ns 99141872
BM_FastIntToBuffer_2<int64_t>/64 6.45 ns 6.45 ns 104705700
BM_FastIntToBuffer_2<int64_t>/512 6.44 ns 6.44 ns 107980669
BM_FastIntToBuffer_2<int64_t>/4096 6.44 ns 6.44 ns 108475908
BM_FastIntToBuffer_2<int64_t>/32768 6.44 ns 6.44 ns 108548677
BM_FastIntToBuffer_2<int64_t>/262144 6.44 ns 6.44 ns 108581914
BM_FastIntToBuffer_2<int64_t>/2097152 6.44 ns 6.43 ns 108572736
BM_FastIntToBuffer_2<int64_t>/16777216 6.43 ns 6.43 ns 108629837
BM_FastIntToBuffer_2<int64_t>/134217728 6.37 ns 6.37 ns 109567105
BM_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>/0
benchmark: 8 ns BM_FastIntToBuffer_1<int32_t>/0
benchmark: 28 ns BM_FastIntToBuffer_1<int32_t>/1
benchmark: 30 ns BM_FastIntToBuffer_1<int32_t>/8
benchmark: 34 ns BM_FastIntToBuffer_1<int32_t>/64
benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/512
benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/4096
benchmark: 36 ns BM_FastIntToBuffer_1<int32_t>/32768
benchmark: 9 ns BM_FastIntToBuffer_1<int64_t>/0
benchmark: 9 ns BM_FastIntToBuffer_1<int64_t>/0
benchmark: 28 ns BM_FastIntToBuffer_1<int64_t>/1
benchmark: 31 ns BM_FastIntToBuffer_1<int64_t>/8
benchmark: 34 ns BM_FastIntToBuffer_1<int64_t>/64
benchmark: 36 ns BM_FastIntToBuffer_1<int64_t>/512
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/4096
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/32768
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/262144
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/2097152
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/16777216
benchmark: 37 ns BM_FastIntToBuffer_1<int64_t>/134217728
benchmark: 32 ns BM_FastIntToBuffer_1<int64_t>/1073741824
benchmark: 15 ns BM_FastIntToBuffer_2<int32_t>/0
benchmark: 15 ns BM_FastIntToBuffer_2<int32_t>/0
benchmark: 51 ns BM_FastIntToBuffer_2<int32_t>/1
benchmark: 55 ns BM_FastIntToBuffer_2<int32_t>/8
benchmark: 59 ns BM_FastIntToBuffer_2<int32_t>/64
benchmark: 57 ns BM_FastIntToBuffer_2<int32_t>/512
benchmark: 56 ns BM_FastIntToBuffer_2<int32_t>/4096
benchmark: 56 ns BM_FastIntToBuffer_2<int32_t>/32768
benchmark: 14 ns BM_FastIntToBuffer_2<int64_t>/0
benchmark: 14 ns BM_FastIntToBuffer_2<int64_t>/0
benchmark: 51 ns BM_FastIntToBuffer_2<int64_t>/1
benchmark: 55 ns BM_FastIntToBuffer_2<int64_t>/8
benchmark: 58 ns BM_FastIntToBuffer_2<int64_t>/64
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/512
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/4096
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/32768
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/262144
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/2097152
benchmark: 56 ns BM_FastIntToBuffer_2<int64_t>/16777216
benchmark: 55 ns BM_FastIntToBuffer_2<int64_t>/134217728
benchmark: 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
Автор: Иван Камынин
