В продолжение этой

Автор: ionicman
Дата: 16.08.07

темы. Там уже началась философия — поэтому в отдельный топик.

Быстрее всего, причём очень заметно, причём как всегда, работают табличные функции конвертации.
Недавно убеждался, что это справедливо и для конвертации bin->hex и для переворачивания битов в слове.
Вот результаты замеров времени (msvc2005sp1, /Ox, а тактах):

\	itoa*	ionicman**	табличная
1	60	32	4
2	116	60	4
3	168	92	4
4	224	124	4
5	276	152	24
6	336	204	24
7	384	228	24
8	444	264	24
9	524	288	80
10	584	320	80

* — стандартная библиотечная
** — оригинальный код, предложенный здесь

Автор: ionicman
Дата: 16.08.07

Вот собственно код функции конвертации:

unsigned table [10000 + 1];
unsigned atable [10000 + 1];
unsigned char xtable [10000];

void init_table()
{
    for (int i = 0; i != 10000; ++i)
    {
        xtable[i] = (i < 10) ? 1 : ((i < 100) ? 2 : ((i < 1000) ? 3 : 4));
        itoa(i, (char*)&table[i], 10);
        atable[i] = 0x30303030;
        itoa(i, (char*)&atable[i] + 4 - xtable[i], 10);
    }
}

char* table_itoa_helper(unsigned i, char* o)
{
    if (i < 100000000u)
    {
        unsigned x1 = i/10000u;
        unsigned x2 = i%10000u;
        reinterpret_cast<unsigned&>(*(o + 5)) = 0;
        reinterpret_cast<unsigned&>(*(o + 0)) = table[x1];
        reinterpret_cast<unsigned&>(*(o + xtable[x1])) = atable[x2];
        return o;
    }
    else
    {
        unsigned x1 = i/100000000u;
        unsigned x2 = i/10000u%10000u;
        unsigned x3 = i%10000u;
        reinterpret_cast<unsigned&>(*(o + 9)) = 0;
        reinterpret_cast<unsigned&>(*(o + 0)) = table[x1];
        reinterpret_cast<unsigned&>(*(o + xtable[x1])) = atable[x2];
        reinterpret_cast<unsigned&>(*(o + xtable[x1] + 4)) = atable[x3];
        return o;
    }
}

char* table_itoa(unsigned i, char* o)
{
    if (i < 10000u)
    {
        reinterpret_cast<unsigned&>(*(o + 0)) = table[i];
        reinterpret_cast<unsigned&>(*(o + 4)) = 0;
        return o;
    }
    else return table_itoa_helper(i, o); // вынесено для лучшего встраивания
}

Единственный минус — возросшее давление на кэш — в данном случае таблицы занимают 90k. В L2 кэш это определённо влезет. Т.ч. если у программы основная работа — перевод чисел, то всё нормально.
Возможно тут как-то можно оптимизировать размер таблиц — не думал на эту тему.



З.Ы. По поводу того, что если писать на ассемблере, то можно использовать "прикольную" фичу — после одной инструкции деления (div) получить сразу и результат деления, и остаток. Это лажа. Объясняю почему. У меня компилятор на:

        unsigned x1 = i/10000u;
        unsigned x2 = i%10000u;

вообще не сгенерировал инструкций div, он сгенерировал инструкцию mul, инструкцию imul и некую хитрую константу 3518437209 (десятичное). Смотрим таблицу таймингов для последних процессоров Intel:
MUL: 10, 14-18 (в зависимости от семейства)
IMUL: 3, 4, 10, 14 (в зависимости от семейства)
DIV: 66-80, 56-70 (в зависимости от семейства)
IDIV: 66-80, 56-70, 22, 22, 38 (в зависимости от семейства)

Получай, не получай за одну инструкцию результат и остаток — код компилятора всё равно быстрее. И даже если бы div был быстрее, то компилятор бы всё равно тоже использовал бы его. Получается бессмысленная гонка с заранее известным проигравшим.



З.З.Ы. По поводу использования паковыных BCD чисел (такая идея тоже проскакивала). Это тоже лажа. Объясняю почему. Инструкция конвертации в packed BCD число FBSTP работает порядка 450 тактов...