Кодт wrote:

[]

>

> typedef std::pair<const char*, void (YourClass::*)()> command_entry;
// ...
>     (this->*(cmd->second))();
> }
>

А простые ф-ции нынче в опале?

--
Maxim Yegorushkin

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

...
K>и я вот думаю менять его или нет:
K>может заменить эту конструкцию на std::map
K>или ещё какой вариант, который вы мне здесь, я надеюсь, подскажете.
K>а может оставить как есть, в надежде что компилятор сделает подобие map за меня?

Насколько я понял словарь фиксированный, тогда можно сделать для него ДКА (детерминированный конечный автомат). Если памяти не жалко, то можно сделать O(m), где m — длина конкретной строки, а не количество слов в словаре, т.е. очень быстро . Пример как делать ДКА

Автор: sergey_shandar
Дата: 13.04.04

.

PS. Но что то я не уверен что понадобяться все эти выверты, std::map наверняка хватит.

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

ME>korzhik wrote:

>> и я вот думаю менять его или нет:
>> может заменить эту конструкцию на std::map
>> или ещё какой вариант, который вы мне здесь, я надеюсь, подскажете.
>> а может оставить как есть, в надежде что компилятор сделает подобие map за меня?

ME>Надежды, я думаю, нет.

ME>Если бы мне нужен был бы absolute raw perfomance, я бы посчитал хэши для твоих контсант ("#PAGE_PLOT", "#WELL"), подобрав такую хэш ф-цию, чтобы хэши по модулю N для всех констант были уникальными. Далее я бы использовал массив[N] указателей на ф-ции.

Например, можно попробовать gperf, или подобный кодогенератор.
А можно попробовать symbols<void (*)()> из boost.spirit. В доках написано, что он основан на Ternary State Trees. Не надо будет генерировать код внешней утилитой и перфоманс должен быть хороший (я сам это не проверял).

Кстати, недавно Joel de Guzman написал письмо о том, что hash целых чисел быстрее чем switch. Есть надежна, что он это добавит в sririt.

Date: Thu, 05 Aug 2004 12:40:15 +0800
From: Joel de Guzman
Subject: [boost] Sparse tables and perfect hashing [ was: multidimensional
arrays (was Boost Mathematicians) ]

Larry Evans wrote:

>I'd be very interested. I'm thinking about using a sparse matrix
>where T is symbol_set, where symbol_set is the set of terminal
>and non-terminal symbols in a grammar. This could be used by
>spirit in deriving LL(k) parser as described in:
>
> http://facweb.cs.depaul.edu/tchristopher/llkppr.pdf

Larry, I've recently experimented on perfect hashing (minimal
and non-minimal) where the input is a char or wchar_t or int.
What's interesting is that, based on my tests, I exceeded the
speed of C++'s switch-case.

I did a test on perfect hashing of integers and tested it against
a switch in a loop:

int test(int i)
{
switch (i)
{
case 1: return 0;
case 4: return 1;
case 9: return 2;
case 16: return 3;
case 25: return 4;
case 36: return 5;
case 49: return 6;
default: return -1;
}
}

vs. a corresponding perfect hash table. I got 6.6 secs (switch)
vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster
(i got 2.2) but still 4X slower than the perfect hash. The perfect
hash generation can be done at runtime using metaprogramming. I
based the algorithms on Bob Jenkin's perfact hash stuff:

http://burtleburtle.net/bob/hash/perfect.html

I think I've got the makings of an extremelely fast LL(1) engine.
See attached test.

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net

#include <boost/timer.hpp>
#include <iostream>

int test(int i)
{
switch (i)
{
case 1: return 0;
case 4: return 1;
case 9: return 2;
case 16: return 3;
case 25: return 4;
case 36: return 5;
case 49: return 6;
case 88: return 7;
default: return -1;
}
}

int const n = 8;
int in[] = { 1,4,9,16,25,36,49,88 };

//1,4,6,0,3,7,2

int g;

typedef unsigned long ub4;
typedef unsigned char ub1;

ub1 tab[] = {
0, 2, 2, 7, 5, 0, 5, 0,};

/* The hash function */
ub4 phash(ub4 val)
{
ub4 a, b, rsl;
b = (val >> 3) & 0x7;
a = ((val << 31) >> 29);
rsl = (a^tab[b]);
return rsl;
}

int look[] = {0,0,0,0,0,0,0};

int
main()
{
{
boost::timer t;
for (int i = 0; i < 100000000; ++i)
{
g = test(in[i & 7]);
// if (g != i & 7)
// {
// std::cout << "switch error at:" << i << ", expected: " << (i & 7) << " got: " << g << std::endl;
// break;
// }
}

double el = t.elapsed();
std::cout << "switch took " << el << " seconds" << std::endl;
}

{
for (int i = 0; i < 8; ++i)
{
std::cout << i << ", " << in[i] << ", " << phash(in[i]) << std::endl;
look[phash(in[i])] = i;
}

std::cout << std::endl;
std::cout << std::endl;

for (int i = 0; i < 8; ++i)
{
std::cout << look[i] << std::endl;
}

std::cout << std::endl;
std::cout << std::endl;

boost::timer t;
for (int i = 0; i < 100000000; ++i)
{
g = look[phash(in[i & 7])];
// std::cout << i << ", " << in[i & 7] << ", " << g << std::endl;
// if (g != i % n)
// {
// std::cout << "phash error at:" << i << ", expected: " << (i & 7) << " got: " << g << std::endl;
// break;
// }
}

double el = t.elapsed();
std::cout << "phash took " << el << " seconds" << std::endl;
}
}

Здравствуйте,

всем спасибо

вот почему я люблю постить сюда вопросы, потому что на простой вроде бы вопрос
получил множество различных вариантов, причём очень интересных.
Ещё раз всем спасибо.
Сейчас не имею возможности проанализировать все варианты.
Но в будущем постараюсь их рассмотреть.
Пока переделал на std::map:
код стал проще и красивее
время обработки файла уменьшилось (на ничтожно малую величину):
для 1000 обработки файла:
вариант с if else if else ... 0.734 s
вариант с std::map 0.720 s

alnsn wrote:

[]

> vs. a corresponding perfect hash table. I got 6.6 secs (switch)
> vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster
> (i got 2.2) but still 4X slower than the perfect hash. The perfect
> hash generation can be done at runtime using metaprogramming. I
> based the algorithms on Bob Jenkin's perfact hash stuff:

[]

Joel de Guzman — острейший перец

--
Maxim Yegorushkin

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

K>Здравствуйте,

K>всем спасибо

K>вот почему я люблю постить сюда вопросы, потому что на простой вроде бы вопрос
K>получил множество различных вариантов, причём очень интересных.
K>Ещё раз всем спасибо.
K>Сейчас не имею возможности проанализировать все варианты.
K>Но в будущем постараюсь их рассмотреть.
K>Пока переделал на std::map:
K>код стал проще и красивее
K>время обработки файла уменьшилось (на ничтожно малую величину):
K>для 1000 обработки файла:
K>вариант с if else if else ... 0.734 s
K>вариант с std::map 0.720 s

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

inline UINT    hash(const char* str)
{
    UINT nHash = 0;
    while (*str)
        nHash = (nHash<<5) + nHash + *str++;
    return nHash;
}

inline UINT    hash(const char* str, size_t count)
{
    UINT nHash = 0;
    size_t    i = 0;
    while ( i<count )
        nHash = (nHash<<5) + nHash + str[i++];
    return nHash;
}

typedef    void (*PFn)();
typedef    std::map<UINT, PFn>    func_map_t;

void F1()
{
}

void F2()
{
}

void F3()
{
}

int _tmain(int argc, _TCHAR* argv[])
{
    func_map_t    handlers;
    handlers[hash("#PAGE_PLOT")] = F1;
    handlers[hash("#WELL")] = F2;
    handlers[hash("#PWDW")] = F3;

    handlers[hash("#WELL")]();

    return 0;
}

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

>>

>> typedef std::pair<const char*, void (YourClass::*)()> command_entry;
ME>// ...
>>     (this->*(cmd->second))();
>> }
>>

ME>А простые ф-ции нынче в опале?

Судя по m_tok — это всё пребывает в контексте некоторого объекта (мифический YourClass).

А переделать на простые функции — как два пальца об асфальт.

std::pair<const char*, void(*)()>

make_pair("xxx", parse_xxx)

(cmd->second)()

Но это значит, что есть глобальные данные, что нехорошо.
Можно передавать контекст в функцию явным параметром (а не this'ом)

typedef void (*ParseFunc)(YourContext*);

std::pair<const char*, ParseFunc>

this_context->m_tok

(cmd->second)(this_context)

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

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

спасибо.

размер карты 30.

Результаты для 1000 обработок файла:
вариант с if else if else ... 0.734 s
вариант с std::map<> 0.720 s
вариант Batiskaf'а 0.700 s

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

K>в этом случае я бы пользовался std::map, быстрее обработчик искать будет.

Или как вмриант, std::hashmap<>

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


K>вариант с if else if else ... 0.734 s
K>вариант с std::map 0.720 s


Это значит, что твой if/else является даааалеко не самым узким местом
Ты бы попрофилировал сначала, что б знать что именно
надо оптимизировать для получения более ощутимого результата.

Hi!

A>Кстати, недавно Joel de Guzman написал письмо о том, что hash целых чисел быстрее чем switch. Есть надежна, что он это добавит в sririt.

Я очень удивился результату, и пошел смотреть почему так.
Мда. Кэш проца рулит

1) функция со свитчем инлайнится только по __forceinline.
кстати, разница сразу _сильно_ сокращается.
2) суммарный объём кода варианта со свитчем ощутимо больше.

соответственно такая ошеломляющая скорость в общем то
результат отсутствия полезной нагрузки.

В общем-то в некоторых случаях это действительно может заролять.
Надо будет взять на заметку

Здравствуйте, e-Xecutor, Вы писали:

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


K>>вариант с if else if else ... 0.734 s
K>>вариант с std::map 0.720 s


EX>Это значит, что твой if/else является даааалеко не самым узким местом
EX>Ты бы попрофилировал сначала, что б знать что именно
EX>надо оптимизировать для получения более ощутимого результата.


Не обязательно, может в первых ифах расположились наиболее часто вызываемые функции, вот и не вызывается часто strcmp, а поменяй очередность проверок может все станет иначе

Здравствуйте, e-Xecutor, Вы писали:

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


K>>вариант с if else if else ... 0.734 s
K>>вариант с std::map 0.720 s


EX>Это значит, что твой if/else является даааалеко не самым узким местом
EX>Ты бы попрофилировал сначала, что б знать что именно
EX>надо оптимизировать для получения более ощутимого результата.

согласен. оптимизировать ещё рано.
просто глянул я на два экрана ифелсовифелсов... и решил переделать.

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

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

_>...
K>>и я вот думаю менять его или нет:
K>>может заменить эту конструкцию на std::map
K>>или ещё какой вариант, который вы мне здесь, я надеюсь, подскажете.
K>>а может оставить как есть, в надежде что компилятор сделает подобие map за меня?

_>Насколько я понял словарь фиксированный, тогда можно сделать для него ДКА (детерминированный конечный автомат). Если памяти не жалко, то можно сделать O(m), где m — длина конкретной строки, а не количество слов в словаре, т.е. очень быстро . Пример как делать ДКА

Автор: sergey_shandar
Дата: 13.04.04

.

_>PS. Но что то я не уверен что понадобяться все эти выверты, std::map наверняка хватит.

И еще, в дополнение... IMHO, если действительно нужно скорость (а не простота чтения программы). Обратим внимание прежде всего на вот этот кусок кода, а не на if(){} else if:

aux::tokenizer::token tk = m_tok.current_token();
...

Ёлки, это же токинайзер... так а че он токинайзит в строки? Пусть токинайзит в адреса функций . Т.е. ДКА рулит одназначно

PS. Простите за сленг...

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

_>Ёлки, это же токинайзер... так а че он токинайзит в строки? Пусть токинайзит в адреса функций . Т.е. ДКА рулит одназначно

Может быть, язык команд описан так, что имя команды — нетерминальный символ. И лексический парсер выполняет тупую работу, а распознавание команды — уже задача следующей ступени.

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

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

_>>Ёлки, это же токинайзер... так а че он токинайзит в строки? Пусть токинайзит в адреса функций . Т.е. ДКА рулит одназначно

К>Может быть, язык команд описан так, что имя команды — нетерминальный символ. И лексический парсер выполняет тупую работу, а распознавание команды — уже задача следующей ступени.

Согласен. Судя по всему так и сделано. Но если надо ускорять алгоритм, то это и есть узкое место, так как проверка символов происходит как минимум два раза (первый раз токинайзер, второй раз распазнование команды), с такой же скоростью можно в конце распознавания токена иметь не строку, а адрес функции (это все что я хотел сказать ).

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


Хочу поделиться своим скромным опытом (тоже ГИС )
В моей софтине похожая задача, использовал раньше map. Сейчас наверное буду переделывать (в частности под влиянием данного topic).


К>Во-первых, strncmp


Вот именно, что во-первых. Но только в другом смысле. Не знаю как на VC, но в BCB функция strncmp почему-то странно реализована. Короче говоря, когда я подменил strncmp на собственную тупую реализацию (простую strcmp написанную в виде for с break безо всяких оптимизаций и asm-ов), скорость parsing выросла раз в 10. Я прекрасно понимаю, что здесь дело не в strncmp, а скорее в стечении нескольких факторов. Тогда я разбираться не стал, очень торопился. А сейчас мне прямо стало интересно, почему тогда такой трюк сработал. Память что ли внутри strncmp выделялась динамически. Понятное дело, в VC такого не случилось бы, компилятор НЕкривой. В любом случае, std::strcmp можно попрофилировать.

К>

К>YourClass::parse()
К>{
К>  aux::tokenizer::token tk = m_tok.current_token();
К>  command_entry* cmd = std::find_if(commands, commands_end, tk, match_command());
К>  if(cmd != commands_end)
К>    (this->*(cmd->second))();
К>}
К>

Вот и у меня

 (this->*(cmd->second))();

используется... Посмотрел я на дизассемблер этой протенькой строчки и ужаснулся. ПРАВДА У МЕНЯ ИСПОЛЬЗОВАЛСЯ ВРУЧНУЮ НАПИСАННЫЙ MAP. В этом, а также в особенностях BCB наверное всё дело. Однако, в любом случае, если бы было у меня поменьше this, и не было бы никакого ООП, то всё бы наверное работало бы побыстрей...

Понимаю, что лезу со свинным рылом в калашный ряд. У меня всё было сделано заумно, второпях, давно, когда был я ещё совсем маленький . К тому же в BCB. Однако, может всё мною сказанное будет кому-то полезно, а кому-то будет интересно прокомментировать мои глупые комментарии.

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

K>Здравствуйте,

K>имею такой код:
K>

K>  aux::tokenizer::token tk = m_tok.current_token();

K>  if (is_command(tk))
K>  {
K>    if (std::strncmp(tk.ptr, "#PAGE_PLOT", tk.len) == 0)
K>    {
K>      parse_page_plot_cmd();
K>    }
K>    else
K>    if (std::strncmp(tk.ptr, "#WELL", tk.len) == 0)
K>    {
K>      parse_well_cmd();
K>    }
K>    else
K>    if (std::strncmp(tk.ptr, "#PWDW", tk.len) == 0)
K>    {
K>      parse_pwdw_cmd();
K>    }
K>    else
K>    if ()
K>    // . . .
K>    // и дальше штук двадцать
K>

K>и я вот думаю менять его или нет:
K>может заменить эту конструкцию на std::map
K>или ещё какой вариант, который вы мне здесь, я надеюсь, подскажете.
K>а может оставить как есть, в надежде что компилятор сделает подобие map за меня?


Мне кажется, что самое быстрое (но и, конечно, самое сложное по реализации) решение — это закодировать распознающий конечный автомат для этих строк и читать посимвольно. Автомат можно закодировать следующим образом:
каждое состояние автомата представляется массивом из 256 элементов, где изначально все элементы установлены в нуль. Потом для переходов из текущего состояния в те элементы, которые соответствуют символам перехода (например, в элемент под номером 65 записывается номер состояния перехода по символу A, не помню что там, маленькое или большое). Работать будет бустрее не придумаешь. Вот пример для трех слов вверху:

#PAGE_PLOT
#WELL
#PWDW


первое состояние начальное, переход только по символу #, значит ставим переход в состояние 2 только для этого символа:

int state1[ 256 ] = {0};
state1[ '#' ] = 2;

второе состояние для символа 'P' в третье и для символа 'W' в другое, добавим позже.

int state2[ 256 ] = {0};
state2[ 'P' ] = 3;
после этого строим переходы из состояния 3, их два: по символам 'A' и 'W'.


int state3[ 256 ] = {0};
state3[ 'A' ] = 4;
state3[ 'W' ] = 5;

ну и так далее... Вот пример небольшой, сделан на скорую руку, конечно, его надо оптимизировать, но все равно, работает в два раза быстрее мэпа:

#include <iostream>
#include <map>

#include <windows.h>


// #PAGE_PLOT
// #WELL
// #PWDW



int automata_parse( const char* input, int* automata[] )
{
    int state_num = 1;
    while( true )
    {
        state_num = (automata[ state_num ])[ *input ++ ];
        if( state_num == 0 ) return 0;
        else if( state_num == 17 ) return 1;
        else if( state_num == 18 ) return 2;
        else if( state_num == 19 ) return 3;
    }


    return 0;
}

int map_parse( const char* input, std::map< const char*, int>& map_ )
{
    return map_[ input ];
}


int main()
{

        int state1[ 256 ] = {0};
    state1[ '#' ] = 2;

    int state2[ 256 ] = {0};
    state2[ 'P' ] = 3;
    state2[ 'W' ] = 14;

    int state3[ 256 ] = {0};
    state3[ 'A' ] = 4;
    state3[ 'W' ] = 5;

    int state4[ 256 ] = {0};
    state4[ 'G' ] = 6;

    int state6[ 256 ] = {0};
    state6[ 'E' ] = 7;

    int state7[ 256 ] = {0};
    state7[ '_' ] = 8;
        
    int state8[ 256 ] = {0};
    state8[ 'P' ] = 9;

    int state9[ 256 ] = {0};
    state9[ 'L' ] = 10;

    int state10[ 256 ] = {0};
    state10[ 'O' ] = 11;

    int state11[ 256 ] = {0};
    state11[ 'T' ] = 17;

    int state5[ 256 ] = {0};
    state5[ 'W' ] = 12;

    int state12[ 256 ] = {0};
    state12[ 'D' ] = 13;

    int state13[ 256 ] = {0};
    state13[ 'W' ] = 18;

    int state14[ 256 ] = {0};
    state14[ 'E' ] = 15;

    int state15[ 256 ] = {0};
    state15[ 'L' ] = 16;

    int state16[ 256 ] = {0};
    state16[ 'L' ] = 19;

    int* automata[] = { 0, state1, state2, state3, state4, state5, state6, state7, state8, state9, state10,
                        state11, state12, state13, state14, state15, state16, 0, 0, 0 };

    std::map< const char*, int > map_;
    map_[ "#PAGE_PLOT" ] = 1;
    map_[ "#PWDW" ] = 2;
    map_[ "#WELL" ] = 3;


    LARGE_INTEGER  first;
    QueryPerformanceCounter( &first );
    std::cout << automata_parse( "#WELL", automata ) << std::endl;
//    std::cout << map_parse( "#WELL", map_ ) << std::endl;
    LARGE_INTEGER  second;
    QueryPerformanceCounter( &second );
    std::cout << "time = " << (DWORD)(second.QuadPart-first.QuadPart) << std::endl;

    return 0;
}

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

M>Мне кажется, что самое быстрое (но и, конечно, самое сложное по реализации) решение — это закодировать распознающий конечный автомат для этих строк и читать посимвольно.

Так вроде Сергей Шандар уже это предлагал здесь

Автор: sergey_shandar
Дата: 18.08.04

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

>я бы посчитал хэши для твоих контсант ("#PAGE_PLOT", "#WELL"), подобрав такую хэш ф-цию, чтобы хэши по модулю N для всех констант были уникальными.

вот можно ещё использовать ternary tree

Автор: c-smile
Дата: 25.09.04