http://ru.wikipedia.org/wiki/Itoa_(Си) смотрели уже? Там есть ссылка на http://www.strudel.org.uk/itoa/ с бенчмарками

плюсую itoa/

кстати ещё есть g_sprintf https://developer.gnome.org/glib/unstable/glib-String-Utility-Functions.html#...

Напиши индусокод с case. Быстрее будет только на fpga.

Если не важно сохранение интерфейса, я бы соптимизировал 0.4 так, что бы строка сразу записывалась задом наперед для избежания ее развертывания.

char* itoa2(int value, char* result,int size, int base) {
 if (base < 2 || base > 36) { *result = '\0'; return result; }
 char* ptr = result+size-1, tmp_char;
 *ptr--='\0';
 int tmp_value;
 do {
  tmp_value = value;
  value /= base;
  *ptr-- = "zyxwvutsrqponmlkjihgfedcba9876543210123456789abcdefghijklmnopqrstuvwxyz" [35 + (tmp_value - value * base)];
 } while ( value );
 if (tmp_value < 0) *ptr-- = '-';
 return ptr+1;}

При тестировании последовательного перевода 10000000 чисел в строки выигрыш составил около 30%.

Если не важно сохранение интерфейса, я бы соптимизировал 0.4 так, что бы строка сразу записывалась задом наперед для избежания ее развертывания.

Но при этом результат будет лежать по некому смещению относительно result.

16ричный:

void foo(uint64 value, char * output)
{

typedef __m64 m64;
typedef __m128i m128;

const m128 val_0x0A = _mm_cvtsi32_si128 (0x0A0A0A0A);
const m128 val_0x30 = _mm_cvtsi32_si128 (0x30303030);
const m128 val_0x41 = _mm_cvtsi32_si128 (0x41414141);
const m128 mask = _mm_cvtsi32_si128 (0x0F0F0F0F);

m128 lower = _mm_set_epi64(value, value);
m128 upper = _mm_srli_epi16(value, 4);
m128 masked= _mm_and_si128(mask, _mm_unpacklo_epi8(lower, upper));
m128 cmp   = _mm_cmplt_epi8(masked, val_0x0A);
m128 result= _mm_or_si128(_mm_and_si128(cmp, val_0x30), _mm_andnot_si128(cmp, val_0x41));
_mm_store_si128((m128*)output, result);
result[16]=0;
}
                           

насчет 10чного надо подумать. идея такова: делим на 100000000(например) с остатком. есть два числа. получившиеся значения делим на 10000 с остатком. есть четыре числа. делим их на 100 с остатком. есть 8 чисел. делим их на 10 с остатком, есть 16 чисел. добавляем ко всем 0х30

По моим замерам исправленная версия K&R быстрее всех:

void reverse(char s[])
{
    for(unsigned i = 0, j = strlen(s) - 1; i < j; i++, j--)
    {
        int c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}
void itoa3(int n, char s[])
{
    int i, sign;
    sign = n;

    i = 0;
    do
    {
        s[i++] = abs(n % 10) + '0';
    } while(n /= 10);
    if(sign < 0)
        s[i++] = '-';

    s[i] = '\0';
    reverse(s);
}

Но у нее base = 10

Если в 0.4 сделать базу 10, то 0.4 будет существенно быстрее версии K&R.

Можешь рассказать как это работает?

число%=10 +'0'--> суём массив подсчитывая символы, полученную строку переворачиваем. Всё упрётся в операцию %.

Ъ-сишное форматирование.

Что-нибудь в стиле (у тебя же соответствующий коду endianess? ;)

uint64_t number;
unsigned char *p = (void *)&number;
int i;

for (i = 0; i < sizeof(number); i++)
        p[i] += '\0';

ТС даже K&R не удосужился почитать...

Чтобы ещё быстрее — надо писать задом-наперёд.

Ну не зря же функция возвращает указатель на начало данных.

поправка:

const m128 val_0x41 = _mm_cvtsi32_si128 (0x37373737);

m128 result= _mm_or_si128(_mm_and_si128(cmp, val_0x30), _mm_andnot_si128(cmp, val_0x41)); result = _mm_add_epi8(result, masked);

пусть у нас есть 64битное число. делаем из него 2 128 битных, так что каждое составлено из двух исходных чисел, но одно сдвинуто вниз на 4 бита(lower и upper) потом маской вырезаем нужные биты. это если в лоб а на самом деле мы пересовываем(unpacklo) байты из lower и upper так ,что в ответе стоят такие байты, где нижние 4 бита соотвествуют одному 16ричному разряду числа, а старшие чем то засраны. мы их режем маской.

сравниваем каждый байт с 0xA, получаем маску (байт <10), если маска =0хff, то в ответ идет число + '0', иначе число+'A'-0xA

ответил ниже

Ну не зря же функция возвращает указатель на начало данных.

Возвращает указатель только для удобства: printr(«%s», itoa(...)), но начало буфера с мусором - это плохо.

забыл - у меня ответ пишется задом наперед. а не как у людей принято.

задержка 10ричного ~1000 циклов на i5

перевод в десятичную форму можно резко ускорить на SSE

пусть Х - число c фиксированной запятой с N знаками после запятой. Y=X/10;

Y*(2^n)=X*(2^n)/10 ~= X*((2^n)/10)

но без пива я отказываюсь это считать. примеры как делить умножением и мануалы по SSE есть в интернете

Если не важно сохранение интерфейса, я бы соптимизировал 0.4 так, что бы строка сразу записывалась задом наперед для избежания ее развертывания.

Но при этом результат будет лежать по некому смещению относительно result.

можно заменить цикл рекурсией которая будет правильно размещать результат. А компилер это уже соптимизирует

в общем, если вам не лень ждать до выходных, то нарисую оптимизированную функцию для удесятичивания числа. т.е. вариант с делением, но без большей части делений, которые дают ~700 из порядка 1000 циклов. + разворот строки и подсчет длины, все на sse.

Это было бы круто.. Я подумаю, что сделать для hex. Но там вроде не должно быть так все критично. Все-таки сдвиг и and быстро работaет

для hex я написал выше. там две ошибки я не успел исправить, откоментили. исправления парой коментов позже. в конце неплохо бы еще побайтный shuffle чтоб развернуть строку, напишу к выходным.

десятичный написан выше, но он тупит на делении. я могу срезать 24 из 27 делений но на это надо время. к воскресенью будет готово.

подсчет колва символов делается на sse элементарно.

подсчет колва символов делается на sse элементарно.

Это реально круто, но что делать с arm?

там есть неон. как я понял автору топика арм не интересен и поэтому я не смотрел про арм. думаю там будут небольшие различия в развороте строки и поиске конца строки.остальное отличается только названиями команд

там есть неон.

Угу, есть. Но и это не кросс-плтформенно - кроме армов есть и другие архитектуры.

да кого это волнует. убогим процам место в жопе

Как быстро прeобразовать число в строчку (char a[100]). Интересует и 10-тичный и 16-тиричный вариант.

делением.

если есть быстрое умножение целых, нужно заменить деление на умножение. Т.е. вместо деления на 10, умножай на 429496729 (по модулю 2^32).

12345*429496729=>5302137119505
5302137119505==1234(mod2^32)

идея ясна? Делай реализацию.

А вот ПОСЛЕ того, как сделаешь, костыль SIMD(sse/mmx). Там можно на одном ядре 2 умножения в 64 бита сразу делать.

если есть быстрое умножение целых, нужно заменить деление на умножение. Т.е. вместо деления на 10, умножай на 429496729

GCC и так умеет заменять деление умножением, когда это возможно и имеет смысл. Посмотри ассемблерный выхлоп

#include <talloc2/tree.h>
#include <math.h>

char * bt_size_t_to_str ( void * ctx, size_t number )
{
    char * result;

    if ( number == 0 ) {
        result = talloc ( ctx, sizeof ( char ) * 2 );
        if ( result == NULL ) {
            return NULL;
        }
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    // size of number + 1 for '\0'
    uint8_t length = ( uint8_t ) floor ( log10 ( number ) ) + 2;
    result = talloc ( ctx, sizeof ( char ) * length );
    if ( result == NULL ) {
        return NULL;
    }
    result[length - 1] = '\0';
    char * walk        = result + length - 1;

    uint8_t digit;
    while ( number > 0 ) {
        walk--;
        digit  = number % 10;
        number /= 10;
        * walk = '0' + digit;
    }

    return result;
}

вот у меня такой вариант. самый очевидный.

GCC и так умеет заменять деление умножением, когда это возможно и имеет смысл. Посмотри ассемблерный выхлоп

я знаю. Но в данном случае gcc мало, нужно ручки приложить. Ведь стандартное itoa, как я понял, ТСу недостаточно.

Я так понимаю у тебя задача сохранять/передавать большие объёмы чисел?

А не думал над бинарными форматами? http://leopard.in.ua/2013/10/13/binary-serialization-formats/

Но в данном случае gcc мало, нужно ручки приложить. Ведь стандартное itoa, как я понял, ТСу недостаточно.

ТСу надо решение на сях. На сях оптимизировать деление через умножение бессмысленно, компилятор сам с этим успешно справляется. Если же писать на ассемблере, это уже имеет смысл. Но на ассемблере ситуация немного меняется. Инструкция idiv, насколько я знаю, считает и результат деления, и остаток от деления. Таким образом, если у нас число 12345678 и сделать idiv 10000, получим сразу два куска 1234 (частное) и 5678 (остаток), эти куски тоже можно idiv-ом делить на два куска, и так далее, пока не останутся отдельные циферки, которые потом можно впихнуть в регистр, и прибавить к нему 0x3030303030303030 (ascii коды нулей), после чего вывести как текст

ТСу надо решение на сях. На сях оптимизировать деление через умножение бессмысленно, компилятор сам с этим успешно справляется.

в данном случае на сях нужно делить не на числа, а на константы. Т.е. сначала на 100000000, потом на 10000000, и так далее. Если делить частное на 10, то компилятор может не разобраться, что частное == константа.

Это будет преждевременная оптимизация.

ИМХО нужно сначала сделать простую программу на сях, как в K&R, а потом попытаться её оптимизировать, если компилятор НЕ справится. И если это НУЖНО.

Да, лично мне — не нужно. Потому — я чисто теоретически.

Нет, у меня просто логи пишутся. В том числе в лог пишутся некоторые поля бинарных сообщений

Инструкция idiv, насколько я знаю, считает и результат деления, и остаток от деления

Если что, в C есть div, ldiv и lldiv, которые сразу возвращают и частное, и остаток.

Вы, конечно, будете смеяться, но Boost::Spirit/Boost::Karma :)

Алекс Отт некоторое время назад публиковал веселый тестик, в котором целочисленный парсер на Spirit-е уделывал atoi как Бог черепаху.

Чукча не читалель, чукча писатель. Нужна обратная операция. Т.е. не atoi a itoa

да кого это волнует. убогим процам место в жопе

Эти убогие процы стоят в смартфонах, для которых пишут игры.

Я ж написал, Boost::Karma, не?

Сравнение производительности

И тормозят, no matter what. А на нормальных процах пусть летает вдвойне.

И тормозят, no matter what.

Где тормозят?

А на нормальных процах пусть летает вдвойне.

Это x86 нормальный проц?

Тут ещё есть буква С без ++. Можно конечно, сделать обёртка но как-то некрасиво. Или оно на С?

Я подумаю, что сделать для hex
сдвиг и and быстро работaет

16-ричное можно же таблицами выводить? Скажем, завести таблицу на 2**16 элементов, всего 4 выборки и все. Никакой математики, вообще.

10-чное тоже можно таблицами, но там придется считать.

Вот, кстати, готовый itoa на таблицах: http://sourceforge.net/projects/itoa/

Нет, это, конечно, злой C++. По-настоящему злой, без шуток.

В общем, это шаблонная библиотека, которая предоставляет Вам возможность создавать EBNF-грамматики прямо в C++ коде. Своего рода связка flex/bison, но pure C++, что облегчает связывание пользовательского и генерённого по грамматике кода. Но если нужен голый C, то, конечно, такой вариант не подойдёт.

Ну это уже перебор... Надо будет побенчить ращные варианты. Для печасти в хексах с ведущим нулем пока делаю так.

#define SET_CHAR(number) str[number]="0123456789ABCDEF"[(data >> (sizeof(data)*8-(number+1)*4)) & 0xF];

rx_retcode_t dump_0hex32(out_buff_t* out_buff, uint32_t data) {
    char str[MAX_INT64_STR_LEN_16 + 1];
    SET_CHAR(0);
    SET_CHAR(1);
    SET_CHAR(2);
    SET_CHAR(3);
    SET_CHAR(4);
    SET_CHAR(5);
    SET_CHAR(6);
    SET_CHAR(7);
    return out_buff->p_dump_cat_len(out_buff, str, 8);
}