оптимизированная функция itoa

Я думаю о том, как реализовать преобразование целого (4 байта, без знака) в строку с инструкциями SSE. Обычная процедура состоит в том, чтобы разделить число и сохранить его в локальной переменной, а затем инвертировать строку (в этом примере отсутствует процедура инверсии):

char *convert(unsigned int num, int base) { static char buff[33]; char *ptr; ptr = &buff[sizeof(buff) - 1]; *ptr = '\0'; do { *--ptr="0123456789abcdef"[num%base]; num /= base; } while(num != 0); return ptr; } 

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

Первым шагом к оптимизации вашего кода является избавление от произвольной поддержки базы. Это связано с тем, что деление на константу – это почти наверняка умножение, но деление на base – это деление, а потому, что '0'+n быстрее, чем "0123456789abcdef"[n] (в первом случае памяти не было).

Если вам нужно выйти за frameworks этого, вы можете сделать таблицы поиска для каждого байта в базе, о которой вы заботитесь (например, 10), затем вектор-добавьте результаты (например, десятичные) для каждого байта. Как в:

 00 02 00 80 (input) 0000000000 (place3[0x00]) +0000131072 (place2[0x02]) +0000000000 (place1[0x00]) +0000000128 (place0[0x80]) ========== 0000131200 (result) 

Терье Матисен изобрел очень быстрый itoa (), который не требует таблиц поиска. Если вас не интересует объяснение того, как это работает, перейдите к производительности или реализации.

Более 15 лет назад Terje Mathisen придумал распараллеливание itoa () для базы 10. Идея состоит в том, чтобы взять 32-битное значение и разбить его на два куска по 5 цифр. (Быстрый поиск в Google для «Terje Mathisen itoa» дал следующее сообщение: http://computer-programming-forum.com/46-asm/7aa4b50bce8dd985.htm )

Мы начинаем так:

 void itoa(char *buf, uint32_t val) { lo = val % 100000; hi = val / 100000; itoa_half(&buf[0], hi); itoa_half(&buf[5], lo); } 

Теперь нам может понадобиться алгоритм, который может преобразовать любое целое число в домене [0, 99999] в строку. Наивный способ сделать это может быть:

 // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { // Move all but the first digit to the right of the decimal point. float tmp = val / 10000.0; for(size_t i = 0; i < 5; i++) { // Extract the next digit. int digit = (int) tmp; // Convert to a character. buf[i] = '0' + (char) digit; // Remove the lead digit and shift left 1 decimal place. tmp = (tmp - digit) * 10.0; } } 

Вместо использования плавающей запятой мы будем использовать математику с фиксированной запятой 4.28, потому что в нашем случае она значительно быстрее. То есть, мы фиксируем двоичную точку в позиции 28-го бита, так что 1.0 представляется как 2 ^ 28. Для преобразования в фиксированную точку мы просто умножаем на 2 ^ 28. Мы можем легко округлить до ближайшего целого числа, маскируя с помощью 0xf0000000, и мы можем извлечь дробную часть, маскируя с помощью 0x0fffffff.

(Примечание: алгоритм Terje немного отличается при выборе формата с фиксированной запятой).

Итак, теперь у нас есть:

 typedef uint32_t fix4_28; // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { // Convert `val` to fixed-point and divide by 10000 in a single step. // NB we would overflow a uint32_t if not for the parentheses. fix4_28 tmp = val * ((1 << 28) / 10000); for(size_t i = 0; i < 5; i++) { int digit = (int)(tmp >> 28); buf[i] = '0' + (char) digit; tmp = (tmp & 0x0fffffff) * 10; } } 

Единственная проблема с этим кодом состоит в том, что 2 ^ 28/10000 = 26843.5456, который усечен до 26843. Это вызывает неточности для определенных значений. Например, itoa_half (buf, 83492) создает строку «83490». Если мы применяем небольшую коррекцию в нашем преобразовании к 4.28 фиксированной точке, то алгоритм работает для всех чисел в домене [0, 99999]:

 // 0 <= val <= 99999 void itoa_half(char *buf, uint32_t val) { fix4_28 const f1_10000 = (1 << 28) / 10000; // 2^28 / 10000 is 26843.5456, but 26843.75 is sufficiently close. fix4_28 tmp = val * ((f1_10000 + 1) - (val / 4); for(size_t i = 0; i < 5; i++) { int digit = (int)(tmp >> 28); buf[i] = '0' + (char) digit; tmp = (tmp & 0x0fffffff) * 10; } } 

Terje чередует часть itoa_half для низких и высоких половин:

 void itoa(char *buf, uint32_t val) { fix4_28 const f1_10000 = (1 << 28) / 10000; fix4_28 tmplo, tmphi; lo = val % 100000; hi = val / 100000; tmplo = lo * (f1_10000 + 1) - (lo / 4); tmphi = hi * (f1_10000 + 1) - (hi / 4); for(size_t i = 0; i < 5; i++) { buf[i + 0] = '0' + (char)(tmphi >> 28); buf[i + 5] = '0' + (char)(tmplo >> 28); tmphi = (tmphi & 0x0fffffff) * 10; tmplo = (tmplo & 0x0fffffff) * 10; } } 

Существует дополнительный трюк, который делает код немного быстрее, если цикл полностью развернут. Умножение на 10 выполняется как последовательность LEA + SHL или LEA + ADD. Мы можем сохранить 1 инструкцию, умножая вместо этого на 5, что требует только одного LEA. Это имеет тот же эффект, что и сдвиг tmphi и tmplo вправо на 1 позицию, каждый из которых проходит через петлю, но мы можем компенсировать, корректируя наши значения сдвига и маски следующим образом:

 uint32_t mask = 0x0fffffff; uint32_t shift = 28; for(size_t i = 0; i < 5; i++) { buf[i + 0] = '0' + (char)(tmphi >> shift); buf[i + 5] = '0' + (char)(tmplo >> shift); tmphi = (tmphi & mask) * 5; tmplo = (tmplo & mask) * 5; mask >>= 1; shift--; } 

Это помогает только в том случае, если цикл полностью развернут, потому что вы можете предварительно вычислить значение сдвига и маски для каждой итерации.

Наконец, эта подпрограмма производит результаты с нулевым запасом. Вы можете избавиться от заполнения, вернув указатель на первый символ, который не равен 0 или последнему символу, если val == 0:

 char *itoa_unpadded(char *buf, uint32_t val) { char *p; itoa(buf, val); p = buf; // Note: will break on GCC, but you can work around it by using memcpy() to dereference p. if (*((uint64_t *) p) == 0x3030303030303030) p += 8; if (*((uint32_t *) p) == 0x30303030) p += 4; if (*((uint16_t *) p) == 0x3030) p += 2; if (*((uint8_t *) p) == 0x30) p += 1; return min(p, &buf[15]); } 

Существует еще один трюк, применимый к 64-битовому (т.е. AMD64) коду. Дополнительные, более широкие регистры позволяют аккумулировать каждую 5-значную группу в регистре; после вычисления последней цифры вы можете разбить их вместе с SHRD, OR с 0x3030303030303030 и сохранить в памяти. Это улучшает производительность для меня примерно на 12,3%.

Векторизация

Мы могли бы выполнить вышеупомянутый алгоритм как есть на устройствах SSE, но почти нет выигрыша в производительности. Однако, если мы разделим значение на более мелкие куски, мы можем воспользоваться 32-разрядными инструкциями умножения SSE4.1. Я попробовал три разных раскола:

  1. 2 группы из 5 цифр
  2. 3 группы из 4 цифр
  3. 4 группы из 3 цифр

Самый быстрый вариант - 4 группы из 3 цифр. Ниже приведены результаты.

Спектакль

Я тестировал множество вариантов алгоритма Терье в дополнение к алгоритмам, предложенным Витаутом и Инге Хенриксеном. Я проверил исчерпывающее тестирование входов, что каждый выход алгоритма соответствует itoa ().

Мои номера взяты у Westmere E5640 с 64-разрядной версией Windows 7. Я ориентируюсь на приоритет в реальном времени и блокируется на kernel ​​0. Я выполняю каждый алгоритм 4 раза, чтобы все вставить в кеш. I раз 2 ^ 24 вызова с использованием RDTSCP для удаления эффекта любых изменений динамической тактовой частоты.

Я приурочил 5 различных моделей входов:

  1. itoa (0 .. 9) - почти лучшая производительность
  2. itoa (1000 .. 1999) - более длинный вывод, отсутствие ответвлений неверно
  3. itoa (100000000 .. 999999999) - самый длинный результат, отсутствие ответвлений неверно
  4. itoa (256 случайных значений) - изменяемая длина вывода
  5. itoa (65536 случайных значений) - изменяемая длина вывода и трещины L1 / L2 caches

Данные:

  ALG TINY MEDIUM LARGE RND256 RND64K ПРИМЕЧАНИЯ
 NULL 7 clk 7 clk 7 clk 7 clk 7 clk Контрольная базовая базовая линия
 TERJE_C 63 clk 62 clk 63 clk 57 clk 56 clk Лучшая реализация C алгоритма Терье
 TERJE_ASM 48 clk 48 clk 50 clk 45 clk 44 clk Наивная, рукописная версия алгоритма Терье AMD64
 TERJE_SSE 41 clk 42 clk 41 clk 34 clk 35 clk SSE встроенная версия алгоритма Терье с группировкой цифр 1/3/3/3
 INGE_0 12 clk 31 clk 71 clk 72 clk 72 clk Первый алгоритм Inge
 INGE_1 20 clk 23 clk 45 clk 69 clk 96 clk Второй алгоритм Inge
 INGE_2 18 clk 19 clk 32 clk 29 clk 36 clk Улучшенная версия второго алгоритма Inge
 VITAUT_0 9 clk 16 clk 32 clk 35 clk 35 алгоритм clk vitaut
 VITAUT_1 11 clk 15 clk 33 clk 31 clk 30 clk Улучшенная версия алгоритма Vitaut
 LIBC 46 clk 128 clk 329 clk 339 clk 340 clk Реализация MSVCRT12

Мой компилятор (VS 2013 Update 4) выпустил удивительно плохой код; assembly версии алгоритма Терье - всего лишь наивный перевод, и он на 21% быстрее. Я также был удивлен успехом реализации SSE, который, как я ожидал, будет медленнее. Большой сюрприз заключался в том, насколько быстрыми были INGE_2, VITAUT_0 и VITAUT_1. Bravo to vitaut для создания портативного решения, которое приносит максимум усилий на уровне сборки.

Примечание: INGE_1 является модифицированной версией второго алгоритма Инге Хенриксена, поскольку оригинал имеет ошибку.

INGE_2 основан на втором алгоритме, который дал Инге Хенриксен. Вместо того, чтобы хранить указатели на предварительно просчитанные строки в массиве char * [], он хранит сами строки в массиве char [] [5]. Другое большое улучшение заключается в том, как он хранит символы в выходном буфере. Он хранит больше символов, чем необходимо, и использует арифметику указателя, чтобы вернуть указатель на первый ненулевой символ. Результат значительно быстрее - конкуренция даже с оптимизированной SSE версией алгоритма Терье. Следует отметить, что микробенчмарк немного поддерживает этот алгоритм, потому что в реальных приложениях dataset 600K будет постоянно удалять кеши.

VITAUT_1 основан на алгоритме Витаута с двумя небольшими изменениями. Первое изменение заключается в том, что он копирует пары символов в основной цикл, уменьшая количество инструкций магазина. Подобно INGE_2, VITAUT_1 копирует оба конечных символа и использует арифметику указателя, чтобы вернуть указатель на строку.

Реализация

Здесь я даю код для 3 самых интересных алгоритмов.

TERJE_ASM:

 ; char *itoa_terje_asm(char *buf, uint32_t val) ; ; *** NOTE *** ; buf *must* be 8-byte aligned or this code will break! itoa_terje_asm: MOV EAX, 0xA7C5AC47 ADD RDX, 1 IMUL RAX, RDX SHR RAX, 48 ; EAX = val / 100000 IMUL R11D, EAX, 100000 ADD EAX, 1 SUB EDX, R11D ; EDX = (val % 100000) + 1 IMUL RAX, 214748 ; RAX = (val / 100000) * 2^31 / 10000 IMUL RDX, 214748 ; RDX = (val % 100000) * 2^31 / 10000 ; Extract buf[0] & buf[5] MOV R8, RAX MOV R9, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R8, 31 ; R8 = buf[0] SHR R9, 31 ; R9 = buf[5] ; Extract buf[1] & buf[6] MOV R10, RAX MOV R11, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R10, 31 - 8 SHR R11, 31 - 8 AND R10D, 0x0000FF00 ; R10 = buf[1] << 8 AND R11D, 0x0000FF00 ; R11 = buf[6] << 8 OR R10D, R8D ; R10 = buf[0] | (buf[1] << 8) OR R11D, R9D ; R11 = buf[5] | (buf[6] << 8) ; Extract buf[2] & buf[7] MOV R8, RAX MOV R9, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R8, 31 - 16 SHR R9, 31 - 16 AND R8D, 0x00FF0000 ; R8 = buf[2] << 16 AND R9D, 0x00FF0000 ; R9 = buf[7] << 16 OR R8D, R10D ; R8 = buf[0] | (buf[1] << 8) | (buf[2] << 16) OR R9D, R11D ; R9 = buf[5] | (buf[6] << 8) | (buf[7] << 16) ; Extract buf[3], buf[4], buf[8], & buf[9] MOV R10, RAX MOV R11, RDX LEA EAX, [RAX+RAX] ; RAX = (RAX * 2) & 0xFFFFFFFF LEA EDX, [RDX+RDX] ; RDX = (RDX * 2) & 0xFFFFFFFF LEA RAX, [RAX+RAX*4] ; RAX *= 5 LEA RDX, [RDX+RDX*4] ; RDX *= 5 SHR R10, 31 - 24 SHR R11, 31 - 24 AND R10D, 0xFF000000 ; R10 = buf[3] << 24 AND R11D, 0xFF000000 ; R11 = buf[7] << 24 AND RAX, 0x80000000 ; RAX = buf[4] << 31 AND RDX, 0x80000000 ; RDX = buf[9] << 31 OR R10D, R8D ; R10 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) OR R11D, R9D ; R11 = buf[5] | (buf[6] << 8) | (buf[7] << 16) | (buf[8] << 24) LEA RAX, [R10+RAX*2] ; RAX = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) | (buf[4] << 32) LEA RDX, [R11+RDX*2] ; RDX = buf[5] | (buf[6] << 8) | (buf[7] << 16) | (buf[8] << 24) | (buf[9] << 32) ; Compact the character strings SHL RAX, 24 ; RAX = (buf[0] << 24) | (buf[1] << 32) | (buf[2] << 40) | (buf[3] << 48) | (buf[4] << 56) MOV R8, 0x3030303030303030 SHRD RAX, RDX, 24 ; RAX = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24) | (buf[4] << 32) | (buf[5] << 40) | (buf[6] << 48) | (buf[7] << 56) SHR RDX, 24 ; RDX = buf[8] | (buf[9] << 8) ; Store 12 characters. The last 2 will be null bytes. OR R8, RAX LEA R9, [RDX+0x3030] MOV [RCX], R8 MOV [RCX+8], R9D ; Convert RCX into a bit pointer. SHL RCX, 3 ; Scan the first 8 bytes for a non-zero character. OR EDX, 0x00000100 TEST RAX, RAX LEA R10, [RCX+64] CMOVZ RAX, RDX CMOVZ RCX, R10 ; Scan the next 4 bytes for a non-zero character. TEST EAX, EAX LEA R10, [RCX+32] CMOVZ RCX, R10 SHR RAX, CL ; NB RAX >>= (RCX % 64); this works because buf is 8-byte aligned. ; Scan the next 2 bytes for a non-zero character. TEST AX, AX LEA R10, [RCX+16] CMOVZ RCX, R10 SHR EAX, CL ; NB RAX >>= (RCX % 32) ; Convert back to byte pointer. NB this works because the AMD64 virtual address space is 48-bit. SAR RCX, 3 ; Scan the last byte for a non-zero character. TEST AL, AL MOV RAX, RCX LEA R10, [RCX+1] CMOVZ RAX, R10 RETN 

INGE_2:

 uint8_t len100K[100000]; char str100K[100000][5]; void itoa_inge_2_init() { memset(str100K, '0', sizeof(str100K)); for(uint32_t i = 0; i < 100000; i++) { char buf[6]; itoa(i, buf, 10); len100K[i] = strlen(buf); memcpy(&str100K[i][5 - len100K[i]], buf, len100K[i]); } } char *itoa_inge_2(char *buf, uint32_t val) { char *p = &buf[10]; uint32_t prevlen; *p = '\0'; do { uint32_t const old = val; uint32_t mod; val /= 100000; mod = old - (val * 100000); prevlen = len100K[mod]; p -= 5; memcpy(p, str100K[mod], 5); } while(val != 0); return &p[5 - prevlen]; } 

VITAUT_1:

 static uint16_t const str100p[100] = { 0x3030, 0x3130, 0x3230, 0x3330, 0x3430, 0x3530, 0x3630, 0x3730, 0x3830, 0x3930, 0x3031, 0x3131, 0x3231, 0x3331, 0x3431, 0x3531, 0x3631, 0x3731, 0x3831, 0x3931, 0x3032, 0x3132, 0x3232, 0x3332, 0x3432, 0x3532, 0x3632, 0x3732, 0x3832, 0x3932, 0x3033, 0x3133, 0x3233, 0x3333, 0x3433, 0x3533, 0x3633, 0x3733, 0x3833, 0x3933, 0x3034, 0x3134, 0x3234, 0x3334, 0x3434, 0x3534, 0x3634, 0x3734, 0x3834, 0x3934, 0x3035, 0x3135, 0x3235, 0x3335, 0x3435, 0x3535, 0x3635, 0x3735, 0x3835, 0x3935, 0x3036, 0x3136, 0x3236, 0x3336, 0x3436, 0x3536, 0x3636, 0x3736, 0x3836, 0x3936, 0x3037, 0x3137, 0x3237, 0x3337, 0x3437, 0x3537, 0x3637, 0x3737, 0x3837, 0x3937, 0x3038, 0x3138, 0x3238, 0x3338, 0x3438, 0x3538, 0x3638, 0x3738, 0x3838, 0x3938, 0x3039, 0x3139, 0x3239, 0x3339, 0x3439, 0x3539, 0x3639, 0x3739, 0x3839, 0x3939, }; char *itoa_vitaut_1(char *buf, uint32_t val) { char *p = &buf[10]; *p = '\0'; while(val >= 100) { uint32_t const old = val; p -= 2; val /= 100; memcpy(p, &str100p[old - (val * 100)], sizeof(uint16_t)); } p -= 2; memcpy(p, &str100p[val], sizeof(uint16_t)); return &p[val < 10]; } 

http://sourceforge.net/projects/itoa/

Он использует большой массив static const всех 4-значных целых чисел и использует его для преобразования 32-битных или 64-битных данных в строку.

Портативный, не требуется определенный набор инструкций.

Единственная более быстрая версия, которую я мог найти, была в коде сборки и ограничена 32 битами.

В этом столбце сравнивается несколько методов integer с преобразованием строк aka itoa. Самый быстрый способ: fmt::FormatInt из библиотеки fmt, которая примерно в 8 раз быстрее, чем sprintf / std::stringstream и в 5 раз быстрее, чем наивная реализация ltoa / itoa (фактические числа могут, конечно, варьироваться в зависимости от платформы) ,

В отличие от большинства других методов fmt::FormatInt пропускает цифры. Он также сводит к минимуму число целых делений, используя идею из беседы Александреску. Три подсказки оптимизации для C ++ . Реализация доступна здесь .

Это, конечно, если C ++ является опцией, и вы не ограничены API itoa .

Отказ от ответственности: я являюсь автором этого метода и библиотеки fmt .

Интересная проблема. Если вас интересует только 10 radix только itoa() то я сделал пример в 10 раз быстрее и в 3 раза быстрее, чем типичная реализация itoa() .

Первый пример (3-кратная производительность)

Первый, который в 3 раза быстрее, чем itoa() , использует однопроходный шаблон для разворачивания программного обеспечения и основан на реализации itoa() с открытым исходным кодом, найденной в groff .

 // itoaSpeedTest.cpp : Defines the entry point for the console application. // #pragma comment(lib, "Winmm.lib") #include "stdafx.h" #include "Windows.h" #include  #include  using namespace std; #ifdef _WIN32 /** a signed 32-bit integer value type */ #define _INT32 __int32 #else /** a signed 32-bit integer value type */ #define _INT32 long int // Guess what a 32-bit integer is #endif /** minimum allowed value in a signed 32-bit integer value type */ #define _INT32_MIN -2147483647 /** maximum allowed value in a signed 32-bit integer value type */ #define _INT32_MAX 2147483647 /** maximum allowed number of characters in a signed 32-bit integer value type including a '-' */ #define _INT32_MAX_LENGTH 11 #ifdef _WIN32 /** Use to init the clock */ #define TIMER_INIT LARGE_INTEGER frequency;LARGE_INTEGER t1, t2;double elapsedTime;QueryPerformanceFrequency(&frequency); /** Use to start the performance timer */ #define TIMER_START QueryPerformanceCounter(&t1); /** Use to stop the performance timer and output the result to the standard stream */ #define TIMER_STOP QueryPerformanceCounter(&t2);elapsedTime=(t2.QuadPart-t1.QuadPart)*1000.0/frequency.QuadPart;wcout<, 1989-1992 \author Inge Eivind Henriksen, 2013 \note Function was originally a part of \a groff, and was refactored & optimized in 2013. \relates itoa() */ const char *Int32ToStr(_INT32 i) { // Make room for a 32-bit signed integers digits and the '\0' char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; *--p = '\0'; if (i >= 0) { do { *--p = numbersIn10Radix[i % 10]; i /= 10; } while (i); } else { // Negative integer do { *--p = reverseArrayEndPtr[i % 10]; i /= 10; } while (i); *--p = '-'; } return p; } int _tmain(int argc, _TCHAR* argv[]) { TIMER_INIT // Make sure we are playing fair here if (sizeof(int) != sizeof(_INT32)) { cerr << "Error: integer size mismatch; test would be invalid." << endl; return -1; } const int steps = 100; { char intBuffer[20]; cout << "itoa() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) itoa(i, intBuffer, 10); TIMER_STOP; } { cout << "Int32ToStr() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) Int32ToStr(i); TIMER_STOP; } cout << "Done" << endl; int wait; cin >> wait; return 0; } 

В 64-битной Windows результатом запуска этого примера является:

 itoa() took: 2909.84 ms. Int32ToStr() took: 991.726 ms. Done 

В 32-битной Windows результатом запуска этого примера является:

 itoa() took: 3119.6 ms. Int32ToStr() took: 1031.61 ms. Done 

Второй пример (10-кратная производительность)

Если вы не возражаете потратить некоторое время на инициализацию некоторых буферов, тогда можно оптимизировать описанную выше функцию в 10 раз быстрее, чем обычная реализация itoa() . Вам нужно создать строковые буферы, а не буферы символов, например:

 // itoaSpeedTest.cpp : Defines the entry point for the console application. // #pragma comment(lib, "Winmm.lib") #include "stdafx.h" #include "Windows.h" #include  #include  using namespace std; #ifdef _WIN32 /** a signed 32-bit integer value type */ #define _INT32 __int32 /** a signed 8-bit integer value type */ #define _INT8 __int8 /** an unsigned 8-bit integer value type */ #define _UINT8 unsigned _INT8 #else /** a signed 32-bit integer value type */ #define _INT32 long int // Guess what a 32-bit integer is /** a signed 8-bit integer value type */ #define _INT8 char /** an unsigned 8-bit integer value type */ #define _UINT8 unsigned _INT8 #endif /** minimum allowed value in a signed 32-bit integer value type */ #define _INT32_MIN -2147483647 /** maximum allowed value in a signed 32-bit integer value type */ #define _INT32_MAX 2147483647 /** maximum allowed number of characters in a signed 32-bit integer value type including a '-' */ #define _INT32_MAX_LENGTH 11 #ifdef _WIN32 /** Use to init the clock */ #define TIMER_INIT LARGE_INTEGER frequency;LARGE_INTEGER t1, t2;double elapsedTime;QueryPerformanceFrequency(&frequency); /** Use to start the performance timer */ #define TIMER_START QueryPerformanceCounter(&t1); /** Use to stop the performance timer and output the result to the standard stream. Less verbose than \c TIMER_STOP_VERBOSE */ #define TIMER_STOP QueryPerformanceCounter(&t2);elapsedTime=(t2.QuadPart-t1.QuadPart)*1000.0/frequency.QuadPart;wcout<= 1, setting it smaller will make the buffers smaller but the performance slower. If you want to set it larger than 100000 then you must add some more cases to the switch blocks. Try to make it smaller to see the difference in performance. It does however seem to become slower if larger than 100000 */ static const _INT32 numElem10Radix = 100000; /** Array used for fast lookup number character lookup */ const char *numbersIn10Radix[numElem10Radix] = {}; _UINT8 numbersIn10RadixLen[numElem10Radix] = {}; /** Array used for fast lookup number character lookup */ const char *reverseNumbersIn10Radix[numElem10Radix] = {}; _UINT8 reverseNumbersIn10RadixLen[numElem10Radix] = {}; void InitBuffers() { char intBuffer[20]; for (int i = 0; i < numElem10Radix; i++) { itoa(i, intBuffer, 10); size_t numLen = strlen(intBuffer); char *intStr = new char[numLen + 1]; strcpy(intStr, intBuffer); numbersIn10Radix[i] = intStr; numbersIn10RadixLen[i] = numLen; reverseNumbersIn10Radix[numElem10Radix - 1 - i] = intStr; reverseNumbersIn10RadixLen[numElem10Radix - 1 - i] = numLen; } } /*! \brief Converts a 32-bit signed integer to a string \param i [in] Integer \par Software design pattern Uses a single pass non-reversing algorithm with string buffers and is 10x as fast as \c itoa(). \returns Integer as a string \copyright GNU General Public License \copyright 1989-1992 Free Software Foundation, Inc. \date 1989-1992, 2013 \author James Clark, 1989-1992 \author Inge Eivind Henriksen, 2013 \note This file was originally a part of \a groff, and was refactored & optimized in 2013. \relates itoa() */ const char *Int32ToStr(_INT32 i) { /* Room for INT_DIGITS digits, - and '\0' */ char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; _INT32 modVal; *--p = '\0'; if (i >= 0) { do { modVal = i % numElem10Radix; switch(numbersIn10RadixLen[modVal]) { case 5: *--p = numbersIn10Radix[modVal][4]; case 4: *--p = numbersIn10Radix[modVal][3]; case 3: *--p = numbersIn10Radix[modVal][2]; case 2: *--p = numbersIn10Radix[modVal][1]; default: *--p = numbersIn10Radix[modVal][0]; } i /= numElem10Radix; } while (i); } else { // Negative integer const char **reverseArray = &reverseNumbersIn10Radix[numElem10Radix - 1]; const _UINT8 *reverseArrayLen = &reverseNumbersIn10RadixLen[numElem10Radix - 1]; do { modVal = i % numElem10Radix; switch(reverseArrayLen[modVal]) { case 5: *--p = reverseArray[modVal][4]; case 4: *--p = reverseArray[modVal][3]; case 3: *--p = reverseArray[modVal][2]; case 2: *--p = reverseArray[modVal][1]; default: *--p = reverseArray[modVal][0]; } i /= numElem10Radix; } while (i); *--p = '-'; } return p; } int _tmain(int argc, _TCHAR* argv[]) { InitBuffers(); TIMER_INIT // Make sure we are playing fair here if (sizeof(int) != sizeof(_INT32)) { cerr << "Error: integer size mismatch; test would be invalid." << endl; return -1; } const int steps = 100; { char intBuffer[20]; cout << "itoa() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) itoa(i, intBuffer, 10); TIMER_STOP; } { cout << "Int32ToStr() took:" << endl; TIMER_START; for (int i = _INT32_MIN; i < i + steps ; i += steps) Int32ToStr(i); TIMER_STOP; } cout << "Done" << endl; int wait; cin >> wait; return 0; } 

В 64-битной Windows результатом запуска этого примера является:

 itoa() took: 2914.12 ms. Int32ToStr() took: 306.637 ms. Done 

В 32-битной Windows результатом запуска этого примера является:

 itoa() took: 3126.12 ms. Int32ToStr() took: 299.387 ms. Done 

Почему вы используете буферы обратного преобразования строк?

Это можно сделать без обратных буферов поиска строки (таким образом, сохраняя 1/2 внутренней памяти), но это делает его значительно медленнее (время ожидания составляет около 850 мс в 64-битных и 380 мс в 32-разрядных системах). Мне непонятно, почему это происходит гораздо медленнее – особенно в 64-битных системах, чтобы проверить это дальше, вы можете просто изменить следующий код:

 #define _UINT32 unsigned _INT32 ... static const _UINT32 numElem10Radix = 100000; ... void InitBuffers() { char intBuffer[20]; for (int i = 0; i < numElem10Radix; i++) { _itoa(i, intBuffer, 10); size_t numLen = strlen(intBuffer); char *intStr = new char[numLen + 1]; strcpy(intStr, intBuffer); numbersIn10Radix[i] = intStr; numbersIn10RadixLen[i] = numLen; } } ... const char *Int32ToStr(_INT32 i) { char buf[_INT32_MAX_LENGTH + 2]; char *p = buf + _INT32_MAX_LENGTH + 1; _UINT32 modVal; *--p = '\0'; _UINT32 j = i; do { modVal = j % numElem10Radix; switch(numbersIn10RadixLen[modVal]) { case 5: *--p = numbersIn10Radix[modVal][4]; case 4: *--p = numbersIn10Radix[modVal][3]; case 3: *--p = numbersIn10Radix[modVal][2]; case 2: *--p = numbersIn10Radix[modVal][1]; default: *--p = numbersIn10Radix[modVal][0]; } j /= numElem10Radix; } while (j); if (i < 0) *--p = '-'; return p; } 

Это часть моего кода в asm. Он работает только для диапазона 255-0. Он может быть быстрее, но здесь вы можете найти направление и основную идею.

4 imuls 1 память 1 запись в память

Вы можете попытаться уменьшить 2 imule и использовать lea со смещением. Однако вы не можете найти что-нибудь более быстрое в C / C ++ / Python;)

 void itoa_asm(unsigned char inVal, char *str) { __asm { // eax=100's -> (some_integer/100) = (some_integer*41) >> 12 movzx esi,inVal mov eax,esi mov ecx,41 imul eax,ecx shr eax,12 mov edx,eax imul edx,100 mov edi,edx // ebx=10's -> (some_integer/10) = (some_integer*205) >> 11 mov ebx,esi sub ebx,edx mov ecx,205 imul ebx,ecx shr ebx,11 mov edx,ebx imul edx,10 // ecx = 1 mov ecx,esi sub ecx,edx // -> sub 10's sub ecx,edi // -> sub 100's add al,'0' add bl,'0' add cl,'0' //shl eax, shl ebx,8 shl ecx,16 or eax,ebx or eax,ecx mov edi,str mov [edi],eax } } 

@Inge Henriksen

Я считаю, что ваш код имеет ошибку:

 IntToStr(2701987) == "2701987" //Correct IntToStr(27001987) == "2701987" //Incorrect 

Вот почему ваш код неправильный:

 modVal = i % numElem10Radix; switch (reverseArrayLen[modVal]) { case 5: *--p = reverseArray[modVal][4]; case 4: *--p = reverseArray[modVal][3]; case 3: *--p = reverseArray[modVal][2]; case 2: *--p = reverseArray[modVal][1]; default: *--p = reverseArray[modVal][0]; } i /= numElem10Radix; 

Должен быть ведущий 0 до «1987», который «01987». Но после первой итерации вы получаете 4 цифры вместо 5.

Так,

IntToStr (27000000) = “2700” // Неверно