Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> hex to int, оптимизация по скорости 
:(
    Опции темы
GoldFinch
Дата 6.2.2011, 18:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
Надо написать быструю функцию парсинга шестнадцатеричных чисел.
Язык - С++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%
=============


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

Это сообщение отредактировал(а) GoldFinch - 7.2.2011, 00:43
PM MAIL ICQ   Вверх
bsa
Дата 6.2.2011, 21:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196
Если только развернуть цикл...


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
volatile
Дата 6.2.2011, 23:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
У Вас ошибка в программе.
Цитата(GoldFinch @  6.2.2011,  18:05 Найти цитируемый пост)
       auto value = table[*pos];

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


При встрече символов из саршей части таблицы, программа будет обращаться неизвестно куда.
PM MAIL   Вверх
mes
Дата 7.2.2011, 00:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(volatile @  6.2.2011,  22:41 Найти цитируемый пост)
 причем сигнед чар

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


--------------------
http://opendots.net
PM MAIL WWW   Вверх
volatile
Дата 7.2.2011, 00:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(mes @  7.2.2011,  00:23 Найти цитируемый пост)
зависит от компилятора


Цитата(GoldFinch @  6.2.2011,  18:05 Найти цитируемый пост)
MSVC2010
PM MAIL   Вверх
GoldFinch
Дата 7.2.2011, 00:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
volatile, спасибо
PM MAIL ICQ   Вверх
volatile
Дата 7.2.2011, 02:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
GoldFinch, да ничего, со всяким бывает. smile 
Кстати в MSVС есть опция, кажется '/J'
установить char по умолчанию unsigned.

А насчёт оптимизации, тут врядли что-то можно еще придумать, имхо.
hexNum = hexNum * 16 + value; ==> hexNum = (hexNum << 4) | value;
Но, оптимизатор и так такие вещи хорошо отлавливает.
PM MAIL   Вверх
mes
Дата 7.2.2011, 11:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(volatile @  7.2.2011,  01:03 Найти цитируемый пост)
.. есть опция .. установить char по умолчанию unsigned.

 smile

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

Код

        ++pos;


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



--------------------
http://opendots.net
PM MAIL WWW   Вверх
xvr
Дата 7.2.2011, 12:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Попробовать задействовать SSE (обрабатывать по несколько символов одновременно)
PM MAIL   Вверх
GoldFinch
Дата 7.2.2011, 13:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
xvr, как?
PM MAIL ICQ   Вверх
xvr
Дата 7.2.2011, 16:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Цитата(GoldFinch @ 7.2.2011,  13:47)
xvr, как?

Надо смотреть доки, их там много  smile Основная идея - собирать по 4 (или 8) символа в регистр, и обрабатывать их в параллель. Преобразование 1 цифры hex -> dec делается на арифметике и сравнениях, и то и другое существует в SSE. Потом результат упаковать в 16 бит, это тоже делается 1 командой в SSE (IMHO)
Не уверен, что это даст выигрышь, т.к. набор 4х цифр в регистр может съесть весь прирост производительности  smile 
PM MAIL   Вверх
GoldFinch
Дата 7.2.2011, 17:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
xvr, основные проблемы - это найти конец числа, и упаковать байты в полубайты.
это убивает все плюсы от распараллеливания.
PM MAIL ICQ   Вверх
xvr
Дата 7.2.2011, 19:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Цитата(GoldFinch @ 7.2.2011,  17:28)
xvr, основные проблемы - это найти конец числа, и упаковать байты в полубайты.

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

это убивает все плюсы от распараллеливания.
Скорее всего да, но категорично я бы заявлять не стал  smile 
PM MAIL   Вверх
borisbn
Дата 7.2.2011, 19:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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

jmp table[ (unsigned char)*pos ]

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

return hexNum;

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

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


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

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

Это сообщение отредактировал(а) borisbn - 7.2.2011, 19:56


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
GoldFinch
Дата 7.2.2011, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
borisbn, это плохое решение. условный переход по известному адресу лучше перехода по неизвестному.
PM MAIL ICQ   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0636 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.