Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 17.08.07 19:27
Оценка: 4 (4)
В продолжение этой
Автор: ionicman
Дата: 16.08.07
 темы. Там уже началась философия — поэтому в отдельный топик.

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

\itoa*ionicman**табличная
160324
2116604
3168924
42241244
527615224
633620424
738422824
844426424
952428880
1058432080
* — стандартная библиотечная
** — оригинальный код, предложенный здесь
Автор: 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 тактов...


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: Шахтер Интернет  
Дата: 17.08.07 22:10
Оценка:
Здравствуйте, remark, Вы писали:

R>char* table_itoa(unsigned i, char* o)
R>{
R> if (i < 10000u)
R> {
R> reinterpret_cast<unsigned&>(*(o + 0)) = table[i];
R> reinterpret_cast<unsigned&>(*(o + 4)) = 0;


Балуешься с невыровнеными адресами? На очень многих платформах это работать не будет.

R> return o;
R> }
R> else return table_itoa_helper(i, o); // вынесено для лучшего встраивания
R>}
R>[/ccode]
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[2]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 17.08.07 22:34
Оценка:
Здравствуйте, Шахтер, Вы писали:

R>> reinterpret_cast<unsigned&>(*(o + 0)) = table[i];
R>> reinterpret_cast<unsigned&>(*(o + 4)) = 0;

Ш>Балуешься с невыровнеными адресами? На очень многих платформах это работать не будет.

Ну нашёл к чему прикопаться
Да, балуюсь. Ничего плохого в этом не вижу.
Во-первых, раз уж пошла такая заворушка, то можно и потребовать выровненный буфер. Там правда ниже обращения идут совсем по-плохому относительно выравнивания.
Во-вторых, там "тех" платформах возможно есть хардварная поддержка ковертации или может там деления дещёвые. Это всё надо уже конкретно смотреть.
В-третьих, те "многие" платформы занимают не более 5% общего числа компьютеров

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 17.08.07 22:36
Оценка:
Здравствуйте, remark, Вы писали:

Самое главное забыл. Первый столбец — число десятичных цифр в числе.

\itoa*ionicman**табличная
160324
2116604
3168924
42241244
527615224
633620424
738422824
844426424
952428880
1058432080

R>
1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 17.08.07 22:39
Оценка:
Здравствуйте, remark, Вы писали:

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


Если применять это в жизни, то, конечно, желательно сократить объём памяти под таблицы.
От atable скорее всего можно избавиться "алгоритмически", т.к. там лежит практически тоже самое, что и в table.
А xtable можно положить в 2 старших разряда table. Тогда надо будет всего один bit-and, что бы вычистить их оттуда, и один shift, что бы выделить из оттуда.

R>
1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: Programador  
Дата: 18.08.07 16:17
Оценка:
Здравствуйте, remark, Вы писали:

R>вообще не сгенерировал инструкций div, он сгенерировал инструкцию mul, инструкцию imul и некую хитрую константу 3518437209 (десятичное). Смотрим таблицу таймингов для последних процессоров Intel:
чет я когдато развлекался чемто подобным, типа нахождение логарифма и степени за время логарифм. Можно найти magic такое что magic*5==1 , ( ИМХО за время логарифм, но не будем заморачиватся для 32 можно и перебором )

Чет набросал такое
#include "stdio.h"

int main(int argc, const char *argv[])
{   unsigned int _1,_2,j,k;
    if(1)
        j= -858993459;
    else
    for(j=1;j;j++)
        if(5*j==1)
            break;
    _1=j,printf(" magic= %d %x",_1,j);    

        int _5_rest[]={0,0xcccccccd,0x9999999a,0x66666667,0x33333334};

    for(j=1;j;j++)
    { int d5=j*_1,d5_minus=-666;
      for(k=0;k<5;k++)
      if(!((d5^_5_rest[k])&0xF0000000))
      {   d5_minus= d5-_5_rest[k];
          break;
      }
    
      printf("\n%d %x %x %d %d",j,j/5,d5,d5_minus,k);
       if(j/5!=j*_1)
            asm("nop");
    }
    return 0;
}

этот magic делит на 5 все что делится, только остаток не обнуляется. резулитат умножения на magic это результат деления на 5 + magic умноженний на остаток, по старшим разрядам можно определить этот остаток (примерно).
В общем для 5 Х/5 и X%5 считается уможением. Для тесяти фишка в том что нет magic*10==1
Re[2]: Оптимальная процедура число -> строка [2]
От: Programador  
Дата: 18.08.07 17:14
Оценка:
поакураьней переписал
#include "stdio.h"
int main(int argc, const char *argv[])
{   unsigned int magic,_2,j,k;
    if(1)
        j= -858993459;
    else
    for(j=1;j;j++)
        if(5*j==1)
            break;
    magic=j,printf(" %d %x",magic,j);    

    for(j=1;j;j++)
    { int d5=j*magic,rest=0;
      if(!(d5&0xF0000000))
        goto prnt;    
      d5-=magic,rest++;
      if(!(d5&0xF0000000))
        goto prnt;    
      d5-=magic,rest++;
      if(!(d5&0xF0000000))
        goto prnt;    
      d5-=magic,rest++;
      if(!(d5&0xF0000000))
        goto prnt;    
      d5-=magic,rest++;

      prnt:
      printf("\n%d %d %d   %8x  %d %d",j,j/5,j%5, j*magic ,d5,rest);

      asm("nop");
    }

    return 0;
}
Re[3]: Оптимальная процедура число -> строка [2]
От: Шахтер Интернет  
Дата: 20.08.07 00:35
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, Шахтер, Вы писали:

R>>> reinterpret_cast<unsigned&>(*(o + 0)) = table[i];
R>>> reinterpret_cast<unsigned&>(*(o + 4)) = 0;

Ш>>Балуешься с невыровнеными адресами? На очень многих платформах это работать не будет.

R>Ну нашёл к чему прикопаться
R>Да, балуюсь. Ничего плохого в этом не вижу.

А я вижу.

R>Во-первых, раз уж пошла такая заворушка, то можно и потребовать выровненный буфер. Там правда ниже обращения идут совсем по-плохому относительно выравнивания.
R>Во-вторых, там "тех" платформах возможно есть хардварная поддержка ковертации или может там деления дещёвые. Это всё надо уже конкретно смотреть.
R>В-третьих, те "многие" платформы занимают не более 5% общего числа компьютеров

Ошибаешься. По числу процессоров x86 -- далеко не самая распространённая платформа сейчас.

R>
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re: Оптимальная процедура число -> строка [2]
От: ionicman  
Дата: 20.08.07 03:17
Оценка:
R>В продолжение этой
Автор: ionicman
Дата: 16.08.07
 темы. Там уже началась философия — поэтому в отдельный топик.

Класс алгоритм. его еще поотимизировать можно. буду эксперментировать, спс
Re[4]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 20.08.07 08:39
Оценка: 9 (1) -1 :)
Здравствуйте, Шахтер, Вы писали:

R>>В-третьих, те "многие" платформы занимают не более 5% общего числа компьютеров

Ш>Ошибаешься. По числу процессоров x86 -- далеко не самая распространённая платформа сейчас.

Я имел в виду, не считая игровых консолей

R>>
1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: machine3000  
Дата: 20.08.07 09:07
Оценка:
Здравствуйте, remark, Вы писали:

R>Т.ч. если у программы основная работа — перевод чисел, то всё нормально.

Вопрос в том, что нужно делать с программистами, которые пишут программы, у которых основная работа — перевод чисел.
Re[2]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 20.08.07 09:17
Оценка:
Здравствуйте, ionicman, Вы писали:

R>>В продолжение этой
Автор: ionicman
Дата: 16.08.07
 темы. Там уже началась философия — поэтому в отдельный топик.

I>Класс алгоритм. его еще поотимизировать можно. буду эксперментировать, спс

Как чо заоптимизируешь — пиши
Интересно будет поглядеть.

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 20.08.07 09:24
Оценка:
Здравствуйте, machine3000, Вы писали:

M>Здравствуйте, remark, Вы писали:

R>>Т.ч. если у программы основная работа — перевод чисел, то всё нормально.

M>Вопрос в том, что нужно делать с программистами, которые пишут программы, у которых основная работа — перевод чисел.

Большая часть ПО, и серверного в том числе, в конечном итоге все равно что-нибудь да форматируют и конвертируют. Необходимость возникает при общении с БД, например. Или если надо что-то hex кодировать/раскодировать, или uri кодировать/раскодировать. Или просто надо ответный xml сформировать. И т.д. и т.п.
Если при этом сервер получается CPU-bound, то оптимизация этих конвертаций/форматирований напрямую поднимает производительность.
Я лично видел такой пример. На основном пути было формирование нескольких строк. Заменил форматирование с boost::format, на printf. Получилось вместо 90 мкс, 12 мкс. Производительность сервера сразу немного, но заметно поднялась.

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Оптимальная процедура число -> строка [2]
От: VEAPUK  
Дата: 22.08.07 13:05
Оценка:
Здравствуйте, remark, Вы писали:

Смотрим таблицу таймингов для последних процессоров Intel:
R>MUL: 10, 14-18 (в зависимости от семейства)
R>IMUL: 3, 4, 10, 14 (в зависимости от семейства)
R>DIV: 66-80, 56-70 (в зависимости от семейства)
R>IDIV: 66-80, 56-70, 22, 22, 38 (в зависимости от семейства)

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

R>З.З.Ы. По поводу использования паковыных BCD чисел (такая идея тоже проскакивала). Это тоже лажа. Объясняю почему. Инструкция конвертации в packed BCD число FBSTP работает порядка 450 тактов...
Откуда дровишки, т.е. хуже чем на 486?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Оптимальная процедура число -> строка [2]
От: Кодт Россия  
Дата: 22.08.07 14:50
Оценка:
Здравствуйте, remark, Вы писали:

R>Я имел в виду, не считая игровых консолей

Все ARM'ы, включая парк винмобайловых КПК.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[6]: Оптимальная процедура число -> строка [2]
От: Left2 Украина  
Дата: 22.08.07 15:00
Оценка:
К>Все ARM'ы, включая парк винмобайловых КПК.
+ включая все симбианы, шоб им пусто было...
Re[6]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 23.08.07 05:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, remark, Вы писали:

R>>Я имел в виду, не считая игровых консолей

К>Все ARM'ы, включая парк винмобайловых КПК.

Сколько это процентов?

В любом случае моё дело предложить, а ваше — отказаться

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 23.08.07 05:18
Оценка:
Здравствуйте, VEAPUK, Вы писали:

VEA>Здравствуйте, remark, Вы писали:

VEA>Смотрим таблицу таймингов для последних процессоров Intel:
R>>MUL: 10, 14-18 (в зависимости от семейства)
R>>IMUL: 3, 4, 10, 14 (в зависимости от семейства)
R>>DIV: 66-80, 56-70 (в зависимости от семейства)
R>>IDIV: 66-80, 56-70, 22, 22, 38 (в зависимости от семейства)

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

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

VEA>Откуда дровишки, т.е. хуже чем на 486?

Имхо делать заключения по современным процессорам исходя из данных по 486 совершенно не адекватно. Там мало чего общего осталось, кроме набора команд.
Дровишки непосредственно из референсов Intel (можно открыто качнуть с их сайта в pdf).
По поводу FBSTP — по собственным замерам. В литературе просто пишут, что медленно.

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[7]: Оптимальная процедура число -> строка [2]
От: Кодт Россия  
Дата: 23.08.07 09:38
Оценка:
Здравствуйте, remark, Вы писали:

К>>Все ARM'ы, включая парк винмобайловых КПК.
R>Сколько это процентов?
Чего в мире больше, персоналок или телефонов?
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[8]: Оптимальная процедура число -> строка [2]
От: remark Россия http://www.1024cores.net/
Дата: 23.08.07 09:54
Оценка: +1
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, remark, Вы писали:

К>>>Все ARM'ы, включая парк винмобайловых КПК.
R>>Сколько это процентов?
К>Чего в мире больше, персоналок или телефонов?

Кого в мире больше, программистов под персоналки или под телефоны?

1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.