10.10.2020 12:03
IvanKamynin 17 4100 Источник


Думаю, с переводом чисел в 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 * 10 ) * 2^{24} + ( b - c * 10 ) * 2^{16} + ( c - d * 10) * 2^8 + d$


Здесь, 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