Быстрейший способ конвертации int в hex-строку
От: Tuo_Bellas Россия  
Дата: 29.09.06 16:14
Оценка: :))
Всем привет!

GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего времени выполнения программы:

static const char * const s_hexChars[256] =
{
"00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0A", "0B", "0C", "0D", "0E", "0F",
/* ... */
"F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9", "FA", "FB", "FC", "FD", "FE", "FF"
};

bool putLong(char *buffer, int value)
{
  if (buffer)
  {
    buffer[0] = s_hexChars[(value & 0xFF000000) >> 24][0];
    buffer[1] = s_hexChars[(value & 0xFF000000) >> 24][1];
    buffer[2] = s_hexChars[(value & 0xFF0000) >> 16][0];
    buffer[3] = s_hexChars[(value & 0xFF0000) >> 16][1];
    buffer[4] = s_hexChars[(value & 0xFF00) >> 8][0];
    buffer[5] = s_hexChars[(value & 0xFF00) >> 8][1];
    buffer[6] = s_hexChars[(value & 0xFF)][0];
    buffer[7] = s_hexChars[(value & 0xFF)][1];
  }

  return !!buffer;
}


Возможна ли еще более быстрая реализация? О сокращении числа вызовов (10М+) — думаем.

Спасибо,
Tuo_Bellas.
Re: Быстрейший способ конвертации int в hex-строку
От: Roman Odaisky Украина  
Дата: 29.09.06 17:15
Оценка: 4 (1)
Здравствуйте, Tuo_Bellas, Вы писали:

T_B>GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего времени выполнения программы:

T_B>
T_B>static const char * const s_hexChars[256] =
T_B>{
T_B>"00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0A", "0B", "0C", "0D", "0E", "0F",
T_B>/* ... */
T_B>"F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9", "FA", "FB", "FC", "FD", "FE", "FF"
T_B>};

T_B>bool putLong(char *buffer, int value)
T_B>{
T_B>  if (buffer)
T_B>  {
T_B>    buffer[0] = s_hexChars[(value & 0xFF000000) >> 24][0];
T_B>    buffer[1] = s_hexChars[(value & 0xFF000000) >> 24][1];
T_B>    buffer[2] = s_hexChars[(value & 0xFF0000) >> 16][0];
T_B>    buffer[3] = s_hexChars[(value & 0xFF0000) >> 16][1];
T_B>    buffer[4] = s_hexChars[(value & 0xFF00) >> 8][0];
T_B>    buffer[5] = s_hexChars[(value & 0xFF00) >> 8][1];
T_B>    buffer[6] = s_hexChars[(value & 0xFF)][0];
T_B>    buffer[7] = s_hexChars[(value & 0xFF)][1];
T_B>  }

T_B>  return !!buffer;
T_B>}
T_B>


T_B>Возможна ли еще более быстрая реализация? О сокращении числа вызовов (10М+) — думаем.

Может, примерно так? Постараться выровнять все используемые данные?
void u32ToHex(U32 value, char buffer[8])
{
    static U32 const hexBytes[256] = { // 32 -- для выравнивания, используются только 16 бит
        . . .
        ('A' << 8) + '9',
        ('A' << 8) + 'A',
        ('A' << 8) + 'B',
        . . .
    };

    U32 hi = (hexBytes[. . .] << 16) ^ hexBytes[. . .]; // для него же (ведь 4 байта?)
    U32 lo = (hexBytes[. . .] << 16) ^ hexBytes[. . .];
    reinterpret_cast<U32 &>(buffer[0]) = hi; // если buffer -- массив, полученный new [], то по стандарту он выровнен так,
    reinterpret_cast<U32 &>(buffer[4]) = lo; // чтобы подходить под любой тип -- и 32-байтный unsigned в том числе
}

P. S. Проверка представляется явно лишней, параметр value так и просится unsigned.
До последнего не верил в пирамиду Лебедева.
Re: Быстрейший способ конвертации int в hex-строку
От: korzhik Россия  
Дата: 29.09.06 18:00
Оценка:
Здравствуйте, Tuo_Bellas, Вы писали:

T_B>Всем привет!

T_B>GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего времени выполнения программы:

а так?
bool putLong(char *buffer, int value)
{
    static char s_hexChars[] = "0123456789ABCDEF";

    if (buffer)
    {
        buffer[0] = s_hexChars[(value & 0xF0000000) >> 28];
        buffer[1] = s_hexChars[(value & 0x0F000000) >> 24];
        buffer[2] = s_hexChars[(value & 0xF00000) >> 20];
        buffer[3] = s_hexChars[(value & 0x0F0000) >> 16];
        buffer[4] = s_hexChars[(value & 0xF000) >> 12];
        buffer[5] = s_hexChars[(value & 0x0F00) >> 8];
        buffer[6] = s_hexChars[(value & 0xF0) >> 4];
        buffer[7] = s_hexChars[(value & 0x0F)];
    }

    return !!buffer;
}


код писал на ходу, так что может ошибся... всё побежал в кинотеатр
Re: Быстрейший способ конвертации int в hex-строку
От: MaximE Великобритания  
Дата: 29.09.06 18:46
Оценка: 4 (1) +1
Tuo_Bellas wrote:

> GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего
> времени выполнения программы:
>
> static const char * const s_hexChars[256] =
> {
> "00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0A", "0B", "0C", "0D", "0E", "0F",
> /* ... */
> "F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9", "FA", "FB", "FC", "FD", "FE", "FF"
> };
>
> bool putLong(char *buffer, int value)
> {
> if (buffer)
> {
> buffer[0] = s_hexChars[(value & 0xFF000000) >> 24][0];
> buffer[1] = s_hexChars[(value & 0xFF000000) >> 24][1];
> buffer[2] = s_hexChars[(value & 0xFF0000) >> 16][0];
> buffer[3] = s_hexChars[(value & 0xFF0000) >> 16][1];
> buffer[4] = s_hexChars[(value & 0xFF00) >> 8][0];
> buffer[5] = s_hexChars[(value & 0xFF00) >> 8][1];
> buffer[6] = s_hexChars[(value & 0xFF)][0];
> buffer[7] = s_hexChars[(value & 0xFF)][1];
> }
>
> return !!buffer;
> }

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

> Возможна ли еще более быстрая реализация? О сокращении числа вызовов
> (10М+) — думаем.

Может что-то похожее на http://rsdn.ru/Forum/?mid=1514879
Автор: MaximE
Дата: 30.11.05
 ?

--
Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re[2]: Быстрейший способ конвертации int в hex-строку
От: korzhik Россия  
Дата: 30.09.06 12:06
Оценка: 4 (1)
Здравствуйте, MaximE, Вы писали:

ME>Может что-то похожее на http://rsdn.ru/Forum/?mid=1514879
Автор: MaximE
Дата: 30.11.05
 ?

Если следовать идеям, который указаны по ссылке, то получаем такой код:
//-----------------------------------------------------------------------------
typedef unsigned char int8u;
typedef unsigned int  int32u;
//-----------------------------------------------------------------------------
inline void byte2hex(int8u v, char* l, char* h)
{
    int8u l_part = v & 0x0F;
    int8u h_part = v & 0xF0;
    
    h_part >>= 4;

    h_part += -(h_part > 9) & ('A' - '9' - 1); // for lower case use 'a'-'9'-1
    l_part += -(l_part > 9) & ('A' - '9' - 1);
    
    h_part += '0';    
    l_part += '0';

    *l = l_part;
    *h = h_part;
}
//-----------------------------------------------------------------------------
char* put_long(char *buffer, int32u value)
{
    int8u* p = (int8u*)(&value);

    byte2hex(p[0], buffer + 7, buffer + 6);
    byte2hex(p[1], buffer + 5, buffer + 4);
    byte2hex(p[2], buffer + 3, buffer + 2);
    byte2hex(p[3], buffer + 1, buffer + 0);

    return buffer;
}
//-----------------------------------------------------------------------------


Заметьте: данный код требует 2's compliment and little endian.
Re[3]: Быстрейший способ конвертации int в hex-строку
От: korzhik Россия  
Дата: 30.09.06 12:35
Оценка: :))
Здравствуйте, korzhik, Вы писали:

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

ME>>Может что-то похожее на http://rsdn.ru/Forum/?mid=1514879
Автор: MaximE
Дата: 30.11.05
 ?

K>Если следовать идеям, который указаны по ссылке, то получаем такой код:

что то я стормозил
оказывается по ссылке уже был нужный код, просто я посмотрел на функцию hex2bin,
а bin2hex чего то не заметил
Ну в общем утро субботы, так что это простительно
Re[3]: Быстрейший способ конвертации int в hex-строку
От: Roman Odaisky Украина  
Дата: 30.09.06 12:50
Оценка: 4 (1)
Здравствуйте, korzhik, Вы писали:

ME>>Может что-то похожее на http://rsdn.ru/Forum/?mid=1514879
Автор: MaximE
Дата: 30.11.05
 ?

K>Если следовать идеям, который указаны по ссылке, то получаем такой код:
K>Заметьте: данный код требует 2's compliment and little endian.

А я попробовал — и компиляторы (а какой, кстати, использует автор?) выказали мало желания инлайнить эти вложенные функции. Вроде лучше так:
template <unsigned> struct U;

template<> struct U<8> : boost::mpl::identity<unsigned char > { };
template<> struct U<16>: boost::mpl::identity<unsigned short> { };
template<> struct U<32>: boost::mpl::identity<unsigned int  > { };

#define IS_U(u, value) ( (value) >= 0 && (value) < (1u << (u)) )

#define GET_HALFBYTE_BY_INDEX(value, index) ( assert(IS_U(3, (index))), \
    ( (value) & (0xF << ((index) * 4)) ) >> ((index) * 4) ) 

#define U4_TO_HEX_CHAR(value) ( assert(IS_U(4, (value))), \
    '0' + (value) + (-( (value) > 9) & ('a' - '9' - 1)) )

#define FOUR_U8_TO_U32(p, q, r, s) ( assert(IS_U(8, (p)) && IS_U(8, (q)) && IS_U(8, (r)) && IS_U(8, (s))), \
    ((((p) << 8) ^ (q)) << 16) ^ ((r) << 8) ^ (s) )

inline void u32ToHex(U<32>::type const value, char buffer[8])
{
    reinterpret_cast<U<32>::type &>(buffer[0]) = FOUR_U8_TO_U32(
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 4)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 5)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 6)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 7))
    );

    reinterpret_cast<U<32>::type &>(buffer[4]) = FOUR_U8_TO_U32(
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 0)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 1)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 2)),
        U4_TO_HEX_CHAR(GET_HALFBYTE_BY_INDEX(value, 3))
    );
}

Опять же требуются маленькие (?) добренькие индейцы, и вообще всё это UB. Зато избавились от обращения по невыровненным адресам. Кто хочет побенчмаркить?

P. S. Если всё так плохо, то, может, лучше переписать сие сразу на асме?

P. P. S. compl[ie]ment — разные слова

P. P. P. S. Как кино?
До последнего не верил в пирамиду Лебедева.
Re[4]: Быстрейший способ конвертации int в hex-строку
От: korzhik Россия  
Дата: 30.09.06 13:03
Оценка:
Здравствуйте, Roman Odaisky, Вы писали:

RO>А я попробовал — и компиляторы (а какой, кстати, использует автор?) выказали мало желания инлайнить эти вложенные функции.

byte2hex все заинлайнились (VC7.1 /O2)

>Вроде лучше так:
[...]
возможно.
бенчмаркить надо.


RO>P. P. S. compl[ie]ment — разные слова

+1

RO>P. P. P. S. Как кино?

Смотрел Клерки-2. Редкостное дерьмо.
Re: Быстрейший способ конвертации int в hex-строку
От: glyph  
Дата: 30.09.06 19:03
Оценка:
Здравствуйте, Tuo_Bellas, Вы писали:

T_B>Возможна ли еще более быстрая реализация? О сокращении числа вызовов (10М+) — думаем.

А можно сформулировать задачу в более общем виде? Почему нельзя использовать crt? Можно ли отказаться от табличной подстановки? Какова таблица символов на целевой машине? Это должно быть переносимо?
Имхо, если вы уперлись в предел производительности, то оптимизация возможна только под конкретную машину. Кстати, какой на ней тип процессора?
... << Пикник — Мы как трепетные птицы (на польском языке) (бонус-трек)>>
Re: Быстрейший способ конвертации int в hex-строку
От: trophim Россия  
Дата: 30.09.06 23:29
Оценка: 4 (1)
Да будет начато тестирование...
Мне удалось ускорить первоначалльный вариант в 2.4 раза. Резервы для дальнейшего обдумывания еще есть.

const unsigned short s_hexCharsUS[256] =
{
    0x3030,0x3130,0x3230,0x3330,0x3430,0x3530,0x3630,0x3730,0x3830,0x3930,0x4130,0x4230,0x4330,0x4430,0x4530,0x4630,
    0x3031,0x3131,0x3231,0x3331,0x3431,0x3531,0x3631,0x3731,0x3831,0x3931,0x4131,0x4231,0x4331,0x4431,0x4531,0x4631,
    0x3032,0x3132,0x3232,0x3332,0x3432,0x3532,0x3632,0x3732,0x3832,0x3932,0x4132,0x4232,0x4332,0x4432,0x4532,0x4632,
    0x3033,0x3133,0x3233,0x3333,0x3433,0x3533,0x3633,0x3733,0x3833,0x3933,0x4133,0x4233,0x4333,0x4433,0x4533,0x4633,
    0x3034,0x3134,0x3234,0x3334,0x3434,0x3534,0x3634,0x3734,0x3834,0x3934,0x4134,0x4234,0x4334,0x4434,0x4534,0x4634,
    0x3035,0x3135,0x3235,0x3335,0x3435,0x3535,0x3635,0x3735,0x3835,0x3935,0x4135,0x4235,0x4335,0x4435,0x4535,0x4635,
    0x3036,0x3136,0x3236,0x3336,0x3436,0x3536,0x3636,0x3736,0x3836,0x3936,0x4136,0x4236,0x4336,0x4436,0x4536,0x4636,
    0x3037,0x3137,0x3237,0x3337,0x3437,0x3537,0x3637,0x3737,0x3837,0x3937,0x4137,0x4237,0x4337,0x4437,0x4537,0x4637,
    0x3038,0x3138,0x3238,0x3338,0x3438,0x3538,0x3638,0x3738,0x3838,0x3938,0x4138,0x4238,0x4338,0x4438,0x4538,0x4638,
    0x3039,0x3139,0x3239,0x3339,0x3439,0x3539,0x3639,0x3739,0x3839,0x3939,0x4139,0x4239,0x4339,0x4439,0x4539,0x4639,
    0x3041,0x3141,0x3241,0x3341,0x3441,0x3541,0x3641,0x3741,0x3841,0x3941,0x4141,0x4241,0x4341,0x4441,0x4541,0x4641,
    0x3042,0x3142,0x3242,0x3342,0x3442,0x3542,0x3642,0x3742,0x3842,0x3942,0x4142,0x4242,0x4342,0x4442,0x4542,0x4642,
    0x3043,0x3143,0x3243,0x3343,0x3443,0x3543,0x3643,0x3743,0x3843,0x3943,0x4143,0x4243,0x4343,0x4443,0x4543,0x4643,
    0x3044,0x3144,0x3244,0x3344,0x3444,0x3544,0x3644,0x3744,0x3844,0x3944,0x4144,0x4244,0x4344,0x4444,0x4544,0x4644,
    0x3045,0x3145,0x3245,0x3345,0x3445,0x3545,0x3645,0x3745,0x3845,0x3945,0x4145,0x4245,0x4345,0x4445,0x4545,0x4645,
    0x3046,0x3146,0x3246,0x3346,0x3446,0x3546,0x3646,0x3746,0x3846,0x3946,0x4146,0x4246,0x4346,0x4446,0x4546,0x4646
};

bool putLong4 (char *buffer, int value)
{
    unsigned short* out = (unsigned short*)buffer;
    unsigned int x = value;

    if (buffer)
    {
        out[3] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[2] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[1] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[0] = s_hexCharsUS[ x ];
    }
    return !!buffer;
}


P.S. Как выложить на форум тестовую программку? Сделал давеча. Как ее залить, чтоб желающие смогли проверить на других платформах и архитектурах? (У меня винда и AMD Athlon 2000).
[EOF]
Let it be! — Давайте есть пчелу!
Re[5]: Быстрейший способ конвертации int в hex-строку
От: trophim Россия  
Дата: 01.10.06 01:08
Оценка:
Здравствуйте, korzhik, Вы писали:

K>Здравствуйте, Roman Odaisky, Вы писали:

RO>>А я попробовал — и компиляторы (а какой, кстати, использует автор?) выказали мало желания инлайнить эти вложенные функции.

K>byte2hex все заинлайнились (VC7.1 /O2)

>>Вроде лучше так:
K>[...]
K>возможно.
K>бенчмаркить надо.

Я уже того. Накропал программу. Как ее забросить на форум?
[EOF]
Let it be! — Давайте есть пчелу!
Re[2]: Быстрейший способ конвертации int в hex-строку
От: apple-antonovka  
Дата: 01.10.06 02:16
Оценка: 4 (1) 
#include "stdafx.h"

#include <stdio.h>
#include <windows.h>
#include <assert.h>

#define TESTVER    0            //plain sprintf
//#define TESTVER    1        //code by Tuo_Bellas
//#define TESTVER    2        //code by trophim
//#define TESTVER    3        //code by apple-antonovka

#if (TESTVER==0)
void init_hexChars()
{
};

bool putLong(char *buffer, int value)
{
  if(buffer)
  {
      sprintf(buffer,"%08X",value);
  }
  return !!buffer;
}
#endif


#if (TESTVER==1)
void init_hexChars()
{
};

static const char * const s_hexChars[256] =
{
"00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0A", "0B", "0C", "0D", "0E", "0F",
"10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "1A", "1B", "1C", "1D", "1E", "1F",
"20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "2A", "2B", "2C", "2D", "2E", "2F",
"30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "3A", "3B", "3C", "3D", "3E", "3F",
"40", "41", "42", "43", "44", "45", "46", "47", "48", "49", "4A", "4B", "4C", "4D", "4E", "4F",
"50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "5A", "5B", "5C", "5D", "5E", "5F",
"60", "61", "62", "63", "64", "65", "66", "67", "68", "69", "6A", "6B", "6C", "6D", "6E", "6F",
"70", "71", "72", "73", "74", "75", "76", "77", "78", "79", "7A", "7B", "7C", "7D", "7E", "7F",
"80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "8A", "8B", "8C", "8D", "8E", "8F",
"90", "91", "92", "93", "94", "95", "96", "97", "98", "99", "9A", "9B", "9C", "9D", "9E", "9F",
"A0", "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "AA", "AB", "AC", "AD", "AE", "AF",
"B0", "B1", "B2", "B3", "B4", "B5", "B6", "B7", "B8", "B9", "BA", "BB", "BC", "BD", "BE", "BF",
"C0", "C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "CA", "CB", "CC", "CD", "CE", "CF",
"D0", "D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8", "D9", "DA", "DB", "DC", "DD", "DE", "DF",
"E0", "E1", "E2", "E3", "E4", "E5", "E6", "E7", "E8", "E9", "EA", "EB", "EC", "ED", "EE", "EF",
"F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9", "FA", "FB", "FC", "FD", "FE", "FF"
};

bool putLong(char *buffer, int value)
{
  if (buffer)
  {
    buffer[0] = s_hexChars[(value & 0xFF000000) >> 24][0];
    buffer[1] = s_hexChars[(value & 0xFF000000) >> 24][1];
    buffer[2] = s_hexChars[(value & 0xFF0000) >> 16][0];
    buffer[3] = s_hexChars[(value & 0xFF0000) >> 16][1];
    buffer[4] = s_hexChars[(value & 0xFF00) >> 8][0];
    buffer[5] = s_hexChars[(value & 0xFF00) >> 8][1];
    buffer[6] = s_hexChars[(value & 0xFF)][0];
    buffer[7] = s_hexChars[(value & 0xFF)][1];
  }

  return !!buffer;
}
#endif


#if (TESTVER==2)
void init_hexChars()
{
};

const unsigned short s_hexCharsUS[256] =
{
    0x3030,0x3130,0x3230,0x3330,0x3430,0x3530,0x3630,0x3730,0x3830,0x3930,0x4130,0x4230,0x4330,0x4430,0x4530,0x4630,
    0x3031,0x3131,0x3231,0x3331,0x3431,0x3531,0x3631,0x3731,0x3831,0x3931,0x4131,0x4231,0x4331,0x4431,0x4531,0x4631,
    0x3032,0x3132,0x3232,0x3332,0x3432,0x3532,0x3632,0x3732,0x3832,0x3932,0x4132,0x4232,0x4332,0x4432,0x4532,0x4632,
    0x3033,0x3133,0x3233,0x3333,0x3433,0x3533,0x3633,0x3733,0x3833,0x3933,0x4133,0x4233,0x4333,0x4433,0x4533,0x4633,
    0x3034,0x3134,0x3234,0x3334,0x3434,0x3534,0x3634,0x3734,0x3834,0x3934,0x4134,0x4234,0x4334,0x4434,0x4534,0x4634,
    0x3035,0x3135,0x3235,0x3335,0x3435,0x3535,0x3635,0x3735,0x3835,0x3935,0x4135,0x4235,0x4335,0x4435,0x4535,0x4635,
    0x3036,0x3136,0x3236,0x3336,0x3436,0x3536,0x3636,0x3736,0x3836,0x3936,0x4136,0x4236,0x4336,0x4436,0x4536,0x4636,
    0x3037,0x3137,0x3237,0x3337,0x3437,0x3537,0x3637,0x3737,0x3837,0x3937,0x4137,0x4237,0x4337,0x4437,0x4537,0x4637,
    0x3038,0x3138,0x3238,0x3338,0x3438,0x3538,0x3638,0x3738,0x3838,0x3938,0x4138,0x4238,0x4338,0x4438,0x4538,0x4638,
    0x3039,0x3139,0x3239,0x3339,0x3439,0x3539,0x3639,0x3739,0x3839,0x3939,0x4139,0x4239,0x4339,0x4439,0x4539,0x4639,
    0x3041,0x3141,0x3241,0x3341,0x3441,0x3541,0x3641,0x3741,0x3841,0x3941,0x4141,0x4241,0x4341,0x4441,0x4541,0x4641,
    0x3042,0x3142,0x3242,0x3342,0x3442,0x3542,0x3642,0x3742,0x3842,0x3942,0x4142,0x4242,0x4342,0x4442,0x4542,0x4642,
    0x3043,0x3143,0x3243,0x3343,0x3443,0x3543,0x3643,0x3743,0x3843,0x3943,0x4143,0x4243,0x4343,0x4443,0x4543,0x4643,
    0x3044,0x3144,0x3244,0x3344,0x3444,0x3544,0x3644,0x3744,0x3844,0x3944,0x4144,0x4244,0x4344,0x4444,0x4544,0x4644,
    0x3045,0x3145,0x3245,0x3345,0x3445,0x3545,0x3645,0x3745,0x3845,0x3945,0x4145,0x4245,0x4345,0x4445,0x4545,0x4645,
    0x3046,0x3146,0x3246,0x3346,0x3446,0x3546,0x3646,0x3746,0x3846,0x3946,0x4146,0x4246,0x4346,0x4446,0x4546,0x4646
};

bool putLong (char *buffer, int value)
{
    unsigned short* out = (unsigned short*)buffer;
    unsigned int x = value;

    if (buffer)
    {
        out[3] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[2] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[1] = s_hexCharsUS[ x & 0xFF ];
        x >>= 8;
        out[0] = s_hexCharsUS[ x ];
    }
    return !!buffer;
}
#endif


#if (TESTVER==3)
static unsigned int s_hexChars[0x10000];

void init_hexChars()
{
    char tmp[sizeof(unsigned int)+1];
    for(int i=0;i<0x10000;i++)
    {
        sprintf(tmp,"%04X",i);
        memcpy(&s_hexChars[i],tmp,sizeof(unsigned int));
    }
}

bool putLong(char *buffer, unsigned int value)
{
  if (buffer)      
  {
  *(unsigned int *)(buffer) = s_hexChars[(value & 0xFFFF0000) >> 16];
  *(unsigned int *)(buffer+4) = s_hexChars[(value & 0xFFFF)];
  }

  return !!buffer;
}
#endif

int main(int argc, char* argv[])
{
    init_hexChars();
    char buff[32];
    DWORD tm1=::GetTickCount();
#ifndef _DEBUG
    for(int ii=0;ii<50;ii++)
#endif
    for (int i=0;i<1000000;i++)
    {
        putLong(buff, i);
#ifdef _DEBUG
        char checkbuff[32];
        sprintf(checkbuff,"%08X",i);
        assert(!memcmp(buff,checkbuff,8));
#endif
    }
    printf("%u\n",GetTickCount()-tm1);
    return 0;
}

win32, sempron@1700Mhz

debug версии прошли все ассерты нормально
release, speed optimizations:
VC6:
TESTVER=0 — 49181 msec (itoa почти в 4 раза быстрее, но не умеет делать padding нулями слева)
TESTVER=1 — 1350 msec
TESTVER=2 — 580 msec
TESTVER=3 — 430 msec

iCPP9:
TESTVER=0 — 46137 msec
TESTVER=1 — 840 msec
TESTVER=2 — 420 msec
TESTVER=3 — 280 msec
Re[3]: Быстрейший способ конвертации int в hex-строку
От: apple-antonovka  
Дата: 01.10.06 03:17
Оценка:
Кстати забавно — если проставить тип вызова __fastcall вместо дефолтового __cdecl то скорость работы 2 и 3 значительно увеличивается для VC6 и уменьшаются для iCPP
Re[6]: Быстрейший способ конвертации int в hex-строку
От: korzhik Россия  
Дата: 01.10.06 07:51
Оценка:
Здравствуйте, trophim, Вы писали:

T>Я уже того. Накропал программу. Как ее забросить на форум?

Заходишь в свой профайл, там в верху немного левее будет ссылка "файлы" жмёшь на неё, ну а там думаю разберёшься
Re: Быстрейший способ конвертации int в hex-строку
От: Xander Zerge Россия www.zerge.com
Дата: 01.10.06 09:48
Оценка:
Здравствуйте, Tuo_Bellas, Вы писали:

T_B>GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего времени выполнения программы:
T_B>...
T_B>Возможна ли еще более быстрая реализация? О сокращении числа вызовов (10М+) — думаем.

А зачем вообще этот массив? Для преобразования тетрады числа в шестнадцатеричный символ достаточно вот этого:
int t;
char str[9] = "";
// ...
str[i] = ( ( t = n & ( 0x0F << i * 4 ) >> i * 4 ) < 0x0A ? '0' : 'A' - 0x0A ) + t;


Имеем четыре константы (пропишутся в код), четыре однотактовых арифметических операции и одну операцию сравнения с возможностью предсказания ветвления ( чаще будет случаться "< 0x0A" ). Операция с памятью — прописывание символа.
По сравнению с исходным кодом, добавились две арифметических операции и операция сравнения, но исчезло обращение к памяти к двумерному массиву (а это плюс две арифметических операции).
Такие простые вычисления в регистрах пойдут быстрее, чем обращения к памяти. А цикл компилятор и сам развернёт.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Серёжа Новиков,
программист
Re[3]: Быстрейший способ конвертации int в hex-строку
От: sc Россия  
Дата: 01.10.06 10:12
Оценка: 2 (1)
не смог не удержаться)) решил тряхнуть стариной и вспомнить ассемблерную молодость))
#if (TESTVER==4)
void init_hexChars()
{
};

bool putLong(char *buffer, unsigned int value)
{
    char* tbl = "0123456789ABCDEF";
    __asm{
        mov ebx, tbl;
        mov ecx, value;
        mov edx, buffer;
        xor esi, esi;
        xor edi, edi;
        ;1        
        mov eax, ecx;
        shr eax, 28;
        xlat;
        or esi, eax;
        ;2
        mov eax, ecx;
        shr eax, 24;
        and eax, 0x0000000f;
        xlat;
        shl eax, 8;
        or esi, eax;
        ;3
        mov eax, ecx;
        shr eax, 20;
        and eax, 0x0000000f;
        xlat;
        shl eax, 16;
        or esi, eax;
        ;4
        mov eax, ecx;
        shr eax, 16;
        and eax, 0x0000000f;
        xlat;
        shl eax, 24;
        or esi, eax;
        ;5
        mov eax, ecx;
        shr eax, 12;
        and eax, 0x0000000f;
        xlat;
        or edi, eax;
        ;6
        mov eax, ecx;
        shr eax, 8;
        and eax, 0x0000000f;
        xlat;
        shl eax, 8;
        or edi, eax;
        ;7
        mov eax, ecx;
        shr eax, 4;
        and eax, 0x0000000f;
        xlat;
        shl eax, 16;
        or edi, eax;
        ;8
        mov eax, ecx;
        and eax, 0x0000000f;
        xlat;
        shl eax, 24;
        or edi, eax;

        mov dword ptr [edx], esi;
        add edx, 4;
        mov dword ptr [edx], edi;
        mov eax, esi;
        and eax, 0x000000ff;
    }
}
#endif
Re[2]: Быстрейший способ конвертации int в hex-строку
От: MaximE Великобритания  
Дата: 01.10.06 13:18
Оценка: 4 (1)
Xander Zerge wrote:

> T_B>GCC 3.4.x. Пришли к тому, что следующая функция занимает 12% всего
> времени выполнения программы:
> T_B>...
> T_B>Возможна ли еще более быстрая реализация? О сокращении числа вызовов
> (10М+) — думаем.
>
> А зачем вообще этот массив? Для преобразования тетрады числа в
> шестнадцатеричный символ достаточно вот этого:
>
> int t;
> char str[9] = "";
> // ...
> str = ( ( t = n & ( 0x0F << i * 4 ) >> i * 4 ) < 0x0A ? '0' : 'A' — 0x0A ) + t;
>
> Имеем четыре константы (пропишутся в код), четыре однотактовых
> арифметических операции

С тактами вопрос тонкий. На суперскалярных процессорах несколько инструкций
выполняются параллельно, поэтому такты теряют смысл, говорят о instruction
throughput and latency.

> и одну операцию сравнения с возможностью
> предсказания ветвления ( чаще будет случаться "< 0x0A" ). Операция с
> памятью — прописывание символа.

От ненужного ветвления избавится достаточно просто:
http://rsdn.ru/Forum/?mid=1514879
Автор: MaximE
Дата: 30.11.05


--
[i]Maxim Yegorushkin

No Microsoft product was used in any way to write or send this text.
If you use a Microsoft product to read it, you're doing so at your own risk
Posted via RSDN NNTP Server 2.0
Re[4]: Быстрейший способ конвертации int в hex-строку
От: apple-antonovka  
Дата: 01.10.06 15:11
Оценка:
Вариант на асме — даже медленнее чем оригинальный вариант от Tuo_Bellas в VC6. Скока мона твердить миру — не соревнуйтесь с компиляторами
Re[5]: Быстрейший способ конвертации int в hex-строку
От: apple-antonovka  
Дата: 01.10.06 15:15
Оценка:
Кстати этот самый варианы на асме даже медленнее его алгоритмического аналога на С скомпиленного в VC6.
Re[5]: Быстрейший способ конвертации int в hex-строку
От: sc Россия  
Дата: 01.10.06 15:49
Оценка:
Здравствуйте, apple-antonovka, Вы писали:

AA>Вариант на асме — даже медленнее чем оригинальный вариант от Tuo_Bellas в VC6. Скока мона твердить миру — не соревнуйтесь с компиляторами
Ну в общем-то да)) , примерно в 2 раза. Но зато таблица всего 17 байт (которую можно уменьшить до 16), против 256*2 у 2-го варианта (разница ~30 раз) и 65536*4 у 3-го варианта (разница ~15000 раз!).
А компилятор тут скорее всего ни при чем. Четко прослеживается зависимость скорости от размера таблицы. Чем больше таблица, тем меньше кода, следовательно работы компилятору и оптимизатору. Причем заметно, что для небольшого увеличения скорости нужно существенно увеличить размер таблицы.
Может кто-нибудь еще быстрее напишет?)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.