Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > hex to int

Автор: GoldFinch 6.2.2011, 18:05

Надо написать быструю функцию парсинга шестнадцатеричных чисел.
Язык - С++0х (MSVC2010), платформа - win32

код для замера производительности:

Код


#define _SECURE_SCL 0
#define _CRT_SECURE_NO_DEPRECATE 1
#define WIN32_LEAN_AND_MEAN
#define VC_EXTRALEAN
#define NOMINMAX

#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
#include <intrin.h>
#include <Windows.h>

struct test_suite
{
    // config
    static const size_t DATA_COUNT = 1024;
    static const size_t RESTARTS_COUNT = 1024 * 4;

    // uint32 random numbers generator
    static unsigned random_next()
    {
        static auto seed = (unsigned)__rdtsc();
        return seed = seed * 0x8088405 + 1, seed;
    }

    class statistics_collector
    {
    public:
        void append(__int64 ticks, const char* name)
        {
            stat_elem_t statElement = {ticks, name};
            table_.push_back(statElement);
        }

        void print() const
        {
            std::cout << std::fixed << std::setprecision(1);
            auto refTicks = table_.front().ticks;
            for each(auto entry in table_)
            {
                std::cout << entry.name << ": " << (100.0 * entry.ticks) / refTicks << "%\n";
            }
            std::cout << "=============\n";
        }

    private:
        struct stat_elem_t
        {
            __int64 ticks;
            const char* name;
        };
        
        std::list<stat_elem_t> table_;
    } stats;

    struct data_element_t
    {
        char buf[16];
    };

    static data_element_t init_data_element()
    {
        data_element_t element;
        wsprintfA(element.buf, "0%x##", random_next());
        return element;
    }

    template<typename F>
    static void process_data_element(F f, const data_element_t& element)
    {
        auto s = element.buf;
        f(s); 
    }

    template<typename F>
    void measure(F f, const char* name)
    {
        data_element_t data[DATA_COUNT];
        std::generate_n(data, DATA_COUNT, init_data_element);

        __int64 totalTicks = 0;
        for(auto i = 0; i != RESTARTS_COUNT; ++i)
        {
            Sleep(0);

            auto startTicks = __rdtsc();
            static_assert(DATA_COUNT % 4 == 0, "DATA_COUNT must be divisible by 4");
            for(auto iter = data; iter != data + DATA_COUNT;)
            {
                process_data_element(f, *iter); ++iter;
                process_data_element(f, *iter); ++iter;
                process_data_element(f, *iter); ++iter;
                process_data_element(f, *iter); ++iter;
            }
            auto endTicks = __rdtsc();
            totalTicks += (endTicks - startTicks);
        }

        stats.append(totalTicks, name);
    }

    ~test_suite()
    {
        stats.print();
    }
};

тест моего велосипеда и strtol

Код


int strtol_wrap(const char*& s)
{
    return strtol(s, (char**)&s, 16);
}

int parse_hex_table(const char*& s)
{
    static const char table[256] =
    {
        /*   0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F */
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 00
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 10
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 20
        +0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, // 30
        -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 40
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 50
        -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 60
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 70
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 80
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 90
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // A0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // B0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // C0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // D0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // E0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // F0
    };

    auto hexNum = 0;
    auto pos = s;
    for(;;)
    {
        auto value = table[(unsigned char)*pos];
        if(value == -1)
        {
            s = pos;
            return hexNum;
        }
        hexNum = hexNum * 16 + value;
        ++pos;
    }
}

int main()
{
    test_suite suite;
    suite.measure(strtol_wrap, "strtol_wrap");
    suite.measure(parse_hex_table, "parse_hex_table");    
}

опции компиляции:

Код


/Zi /nologo /W4 /WX /O2 /Ob2 /Oi /Ot /Oy- /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm- /EHa /MT /GS- /Gy /fp:precise /Zc:wchar_t /Zc:forScope /Gd /analyze-

результаты

Код


strtol_wrap: 100.0%
parse_hex_table: 12.3%
=============

что написать, чтоб было еще быстрее?

Автор: bsa 6.2.2011, 21:02

Если только развернуть цикл...

Автор: volatile 6.2.2011, 23:41

У Вас ошибка в программе.

Цитата(GoldFinch @ 6.2.2011, 18:05

)

auto value = table[*pos];

*pos - это чар, причем сигнед чар. Диапазон [-128..127]

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

Автор: mes 7.2.2011, 00:23

Цитата(volatile @ 6.2.2011, 22:41

)

причем сигнед чар

поправка: причем может быть сигнед чар (зависит от компилятора)
smile

Автор: volatile 7.2.2011, 00:31

Цитата(mes @ 7.2.2011, 00:23

)

зависит от компилятора

Цитата(GoldFinch @ 6.2.2011, 18:05

)

MSVC2010

Автор: GoldFinch 7.2.2011, 00:40

volatile, спасибо

Автор: volatile 7.2.2011, 02:03

GoldFinch, да ничего, со всяким бывает. smile

Кстати в MSVС есть опция, кажется '/J'
установить char по умолчанию unsigned.

А насчёт оптимизации, тут врядли что-то можно еще придумать, имхо.
hexNum = hexNum * 16 + value; ==> hexNum = (hexNum << 4) | value;
Но, оптимизатор и так такие вещи хорошо отлавливает.

Автор: mes 7.2.2011, 11:00

Цитата(volatile @ 7.2.2011, 01:03

)

.. есть опция .. установить char по умолчанию unsigned.

Добавлено через 5 минут и 20 секунд

Цитата

Код


        ++pos;

а для "красоты кода" как минимум инкрементацию счетчика удобнее поместить в оглавление цикла..

Автор: xvr 7.2.2011, 12:11

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

Автор: GoldFinch 7.2.2011, 13:47

xvr, как?

Автор: xvr 7.2.2011, 16:24

Цитата(GoldFinch @ 7.2.2011, 13:47)

xvr, как?

Надо смотреть доки, их там много smile

Основная идея - собирать по 4 (или 8) символа в регистр, и обрабатывать их в параллель. Преобразование 1 цифры hex -> dec делается на арифметике и сравнениях, и то и другое существует в SSE. Потом результат упаковать в 16 бит, это тоже делается 1 командой в SSE (IMHO)
Не уверен, что это даст выигрышь, т.к. набор 4х цифр в регистр может съесть весь прирост производительности smile

Автор: GoldFinch 7.2.2011, 17:28

xvr, основные проблемы - это найти конец числа, и упаковать байты в полубайты.
это убивает все плюсы от распараллеливания.

Автор: xvr 7.2.2011, 19:33

Цитата(GoldFinch @ 7.2.2011, 17:28)

xvr, основные проблемы - это найти конец числа, и упаковать байты в полубайты.

Упаковать полубайты в байты SSE может, а вот с нахождением конца числа - облом. Чистым SSE тут не обойтись smile

Цитата

это убивает все плюсы от распараллеливания.

Скорее всего да, но категорично я бы заявлять не стал smile

Автор: borisbn 7.2.2011, 19:51

Очень хочется избавиться от if внутри цикла. М.б. хранить в массиве метки (labels), т.е. адреса перехода, и делать

Код


jmp table[ (unsigned char)*pos ]

в таблице вместо -1 хранить метку по которой будет код

Код


return hexNum;

а в "полезных" ячейках хранить метку по которой будет код

Код


hexNum = hexNum * 16 + value;
++pos;

вот только придётся делать на ассемблере, и, честно говоря, я не знаю как это сделать и можно ли вообще smile

P.S. Сделать то же самое switch'ем на 256 значений не удалось - смотрел ассемблерный код, сгенерённый компилятором (правда VS2008, а не 2010) - там тоже cmp и ja в цикле

Автор: GoldFinch 7.2.2011, 19:59

borisbn, это плохое решение. условный переход по известному адресу лучше перехода по неизвестному.

Автор: mes 7.2.2011, 20:48

GoldFinch, если *16 убрать (допустим заменив на +16), производительность сильно увеличивается ?
если да, то "полезный" ряд (где не -1) таблицы можно сделать косвенным, и представить как отображение на двухмерный массив чисел,
значение которого равно pow (0x10, строка) +столбец.

тогда для 4х-значных 16-ричных чисел потребуется 4*16*sizeof(int) дополнительной памяти и одно косвенное обращение к ней..

Добавлено @ 20:50
если ничего не напутал smile

Автор: borisbn 7.2.2011, 21:10

GoldFinch, вообще-то так и предполагал, но точно не знал. Жалко.

А у меня ещё столько идей ... (С) какой-то анекдот про Вовочку smile

Автор: mes 8.2.2011, 01:33

Цитата(mes @ 7.2.2011, 19:48

)

, если *16 убрать

вот накалякал, развернув цикл: http://liveworkspace.org/code/3884c626a7058a262594cf3ea895ebe5
осталось сравнить по скорости..

Автор: GoldFinch 8.2.2011, 02:27

mes, там должно быть 8 цифр, а не 4.

если сделать 8 - то производительность будет такой же как и в моей версии.
http://paste.org.ru/?wixlwl

Автор: mes 8.2.2011, 10:09

Цитата(GoldFinch @ 8.2.2011, 01:27

)

если сделать 8 - то производительность будет такой же

да, я вчера чего то упустил из виду, что *16 и так оптимальное.. так что tabled_mul излишний..
так что надежда могла быть лишь на исключение лишний операций, при развороте цикла..
хотя исключение пары сдвигов на общем фоне заметно не будет.. так же как и пользы от замены "+" на "|"...

Автор: volatile 9.2.2011, 00:49

Сегодня немного повозился с вашей функцией.
оптимизировать её практически бесполезно, так как на вызов/возврат тратится больше времени.
чем собственно на само тело функцию. Если есть возможность ее надо вызывать инлайн.

Но тем не менее, вот что получилось:

Код


int parse_hex_table2(const char * & s)
{
    // char[] заменил на int[] 
    // меньше преобразований char<->int дало львиную долю ускорения на ~12%

    // В таблицу добавил смещение.
    const int k = 1; // Есть смысл выбирать только между k=1 и k=0.  при k=0 вернется к тому что было.
                     // при k=1 дало ускорение ~1-2% см.ниже.
    static const int table[256] =
    {
      // 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F 
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 00
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 10
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 20
        +0+k,  1+k,  2+k,  3+k,  4+k,  5+k,  6+k,  7+k,  8+k,  9+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 30
        -1+k, 10+k, 11+k, 12+k, 13+k, 14+k, 15+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 40
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 50
        -1+k, 10+k, 11+k, 12+k, 13+k, 14+k, 15+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 60
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 70
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 80
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // 90
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // A0
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // B0
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // C0
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // D0
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // E0
        -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, -1+k, // F0
    };    

    int hexNum;
    const char * pos = s;
       {
          int value = table[(unsigned char)*pos];
          if( value == k - 1 ) return 0; // при к=1 фактически имеем сравнение (value==0) что на ~1-2% быстрее чем (value==-1)
          ++pos;                         // Даже с учетом последующей корректировки результата.
          hexNum = value - k;
       }
    for(;;)
    {
          // Нижеслеюующий блок можно дублировать
          // Пробовал дублировать до 8 раз. реальной производительности не увеличивается, даже наоборот
          // Но возможно на другой машине будет по другому. (Зависит от кеша процессора). Оставил 2 раза. 
       {  
          int value = table[(unsigned char)*pos];
          if( value == k - 1 ) break;
          ++pos;
          hexNum = hexNum * 16 + value - k;
       }
       {  
          int value = table[(unsigned char)*pos];
          if( value == k - 1 ) break;
          ++pos;
          hexNum = hexNum * 16 + value - k;
       }
    }
    s = pos;
    return hexNum;
}

Результаты по времени на моём компе.
исходный вариант - 100%
этот вариант ~ 84.8%