Re[8]: C++ code formatter
От: c-smile Канада http://terrainformatica.com
Дата: 13.10.17 21:09
Оценка:
Здравствуйте, alex_public, Вы писали:


_>Так это зависит от того, как используется данный код. Если он вызывается не один раз, то очевидно что std::map будет эффективнее

Не всем настолько "очевидно" ...

А если не гадать на кофейной гуще то вот результаты теста — меньше run time — лучше:

map_resolveFormatter 0.039
if_resolveFormatter 0.025


Т.е. мой вариант не то что не хуже, а вообще в два раза быстрее.

Вот те функции что тестировались:

Твоя:
// std::map approach +++

// build formatter index
std::map<std::string, FormatterType> index = {
  { "text", simple_formatter },
  { "integer", integer_formatter },
  { "decimal", decimal_formatter },
  { "currency", currency_formatter },
  { "date", date_formatter },
  { "date-local", date_local_formatter },
  { "time", time_formatter },
  { "time-local", time_local_formatter },
  { "enum", enum_formatter }
};


FormatterType map_resolveFormatter(std::string name)
{
  auto it = index.find(name);
  return (it != index.end()) ? it->second : simple_formatter;
}
// std::map approach ---

Моя

// if approach +++
FormatterType if_resolveFormatter(std::string name)
{
  tool::chars name_chars = tool::chars(name.c_str(), name.size());
  return 
      name_chars == CHARS("text") ? simple_formatter
    : name_chars == CHARS("integer") ? integer_formatter
    : name_chars == CHARS("decimal") ? decimal_formatter
    : name_chars == CHARS("currency") ? currency_formatter
    : name_chars == CHARS("date") ? date_formatter
    : name_chars == CHARS("date-local") ? date_local_formatter
    : name_chars == CHARS("time") ? time_formatter
    : name_chars == CHARS("time-local") ? time_local_formatter
    : name_chars == CHARS("enum") ? enum_formatter 
    : simple_formatter;
}

// if approach ---


На этом вот наборе

enum { TOTAL_RUNS = 1000 };

std::string input_tokens[] = { "", "text", "integer", "decimal", "currency", "date", "date-local", "time", "time-local", "enum"  };

std::vector<std::string> input;

void generate_input() {
  for (int n = 0; n < TOTAL_RUNS; ++n)
    input.push_back(std::string(input_tokens[std::rand() % items_in(input_tokens)]));
}


Таким вот образом:

void run_test(FormatterType(*test)(std::string name), const char* name)
{
  auto start = std::chrono::steady_clock::now();
  unsigned tn = 0;
  for(int n = 0; n < TOTAL_RUNS; ++n)
    for (int i = 0; i < TOTAL_RUNS; ++i)
      tn += (unsigned)test(input[i]);
  auto finish = std::chrono::steady_clock::now();
  double elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();
  std::cout << name << " " << elapsed_seconds << " " << tn << std::endl;
}

int main() {
  generate_input();
  run_test(map_resolveFormatter, "map_resolveFormatter");
  run_test(if_resolveFormatter, "if_resolveFormatter");
  return 0;
}
Отредактировано 13.10.2017 21:11 c-smile . Предыдущая версия .
Re[9]: C++ code formatter
От: night beast СССР  
Дата: 14.10.17 12:19
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Не всем настолько "очевидно" ...

CS>Твоя:
CS>
CS>// std::map approach +++

CS>// build formatter index
CS>std::map<std::string, FormatterType> index = {
CS>  { "text", simple_formatter },
CS>  { "integer", integer_formatter },
CS>  { "decimal", decimal_formatter },
CS>  { "currency", currency_formatter },
CS>  { "date", date_formatter },
CS>  { "date-local", date_local_formatter },
CS>  { "time", time_formatter },
CS>  { "time-local", time_local_formatter },
CS>  { "enum", enum_formatter }
CS>};
CS>


насколько критично по производительности?
вариант с поиском в сортированном векторе/массиве не пробовал?
добавление простого хэша как ситуацию изменит?
Re[10]: C++ code formatter
От: c-smile Канада http://terrainformatica.com
Дата: 14.10.17 15:41
Оценка:
Здравствуйте, night beast, Вы писали:

NB>Здравствуйте, c-smile, Вы писали:

CS>>Не всем настолько "очевидно" ...

CS>>Твоя:
CS>>
CS>>// std::map approach +++

CS>>// build formatter index
CS>>std::map<std::string, FormatterType> index = {
CS>>  { "text", simple_formatter },
CS>>  { "integer", integer_formatter },
CS>>  { "decimal", decimal_formatter },
CS>>  { "currency", currency_formatter },
CS>>  { "date", date_formatter },
CS>>  { "date-local", date_local_formatter },
CS>>  { "time", time_formatter },
CS>>  { "time-local", time_local_formatter },
CS>>  { "enum", enum_formatter }
CS>>};
CS>>


NB>насколько критично по производительности?

В моем случае производительность всегда критична. Во всяком случае желательна.
Иначе получается Electron.

NB>вариант с поиском в сортированном векторе/массиве не пробовал?

Сортированный вектор из 8 элементов? Зачем?

NB>добавление простого хэша как ситуацию изменит?

А как это меняет дело?

Я в скрипте как-то проводил исследование — представление object в памяти:
{ foo: 1,
  bar: 2,
  zed: 3 }

Оказалось что если кол-во key/value пар меньше 7-8 то линейный поиск быстрее — меньше накладных расходов на подготовку поиска.
Поэтому если элементов больше 8 я object конвертирую в hash table.

Но это все индивидуально — зависит от того что есть ключ в конкретном случае.
Re[9]: C++ code formatter
От: alex_public  
Дата: 14.10.17 18:04
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>А если не гадать на кофейной гуще то вот результаты теста — меньше run time — лучше:
CS>
CS>map_resolveFormatter 0.039
CS>if_resolveFormatter 0.025
CS>

CS>Т.е. мой вариант не то что не хуже, а вообще в два раза быстрее.

К сожалению не могу проверить данные результаты, т.к. не знаю кто такие tool::chars и т.п.

CS>Вот те функции что тестировались:
CS>Твоя:

Вообще то это не моя функция — её предложил uzhas. Я вроде как вполне однозначно написал выше, что использую немного другой вариант.
Re[10]: C++ code formatter
От: alex_public  
Дата: 14.10.17 18:32
Оценка:
Здравствуйте, night beast, Вы писали:

NB>насколько критично по производительности?
NB>вариант с поиском в сортированном векторе/массиве не пробовал?
NB>добавление простого хэша как ситуацию изменит?

Нет, там немного другой расклад — гораздо критичнее совсем другие параметры.

У варианта с map используется чуть менее медленное сравнение (отношение, а не равенство) чем в варианте с if, но при этом само количество сравнение меньше (причём принципиально — O(n) vs O(log(n)) ). Соответственно чем больше элементов в нашем списке вариантов, тем больше будет преимущество кода с map над вариантом с if.

Ну и ещё отдельно можно отметить, что нахождение среди тестируемых образцов вариантов не входящих в список определённых существенно деградирует эффективность кода с if (т.к. надо всегда проходить весь путь сравнения) и почти никак не влияет на производительность кода с map.
Re[10]: C++ code formatter
От: c-smile Канада http://terrainformatica.com
Дата: 14.10.17 19:15
Оценка:
Здравствуйте, alex_public, Вы писали:

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

CS>>А если не гадать на кофейной гуще то вот результаты теста — меньше run time — лучше:
CS>>
CS>>map_resolveFormatter 0.039
CS>>if_resolveFormatter 0.025
CS>>

CS>>Т.е. мой вариант не то что не хуже, а вообще в два раза быстрее.

_>К сожалению не могу проверить данные результаты, т.к. не знаю кто такие tool::chars и т.п.

tool::chars это пара 
struct chars { 
  const char* start; 
  size_t length; 
}


Вот вариант этой конструкции https://github.com/c-smile/sciter-sdk/blob/master/include/aux-slice.h#L48

CS>>Вот те функции что тестировались:
CS>>Твоя:

_>Вообще то это не моя функция — её предложил uzhas. Я вроде как вполне однозначно написал выше, что использую немного другой вариант.

Ты как я понял используешь map string_view.
Т.е. можешь переписать мой вариант со string_view — получишь тот же результат — map медленнее.
Это если string_view::operator=() правильно написан конечно.
Re[11]: C++ code formatter
От: c-smile Канада http://terrainformatica.com
Дата: 14.10.17 19:26
Оценка:
Здравствуйте, alex_public, Вы писали:

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

Это вот ты написал?

_>то очевидно что std::map будет эффективнее, т.к. инициализация дерева будет происходить только один раз. И это кстати не теория — я использую на практике именно такой подход (только со string_view, а не string в качестве ключа для map).

Если "да" то вот тебе пример когда map медленнее перебора.
Re[11]: C++ code formatter
От: Vi2 Удмуртия http://www.adem.ru
Дата: 14.10.17 19:29
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>tool::chars это пара 
CS>struct chars { 
CS>  const char* start; 
CS>  size_t length; 
CS>}

CS>Вот вариант этой конструкции https://github.com/c-smile/sciter-sdk/blob/master/include/aux-slice.h#L48

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

bool operator == ( const slice& r ) const
      {
        if( length != r.length )
          return false;
>>>        if( start == r.start )
>>>          return true;
        for( unsigned int i = 0; i < length; ++i )
          if( start[i] != r.start[i] )
            return false;
        return true;
      }
Vita
Выше головы не прыгнешь, ниже земли не упадешь, дальше границы не убежишь! © КВН НГУ
Re[12]: C++ code formatter
От: c-smile Канада http://terrainformatica.com
Дата: 14.10.17 20:24
Оценка:
Здравствуйте, Vi2, Вы писали:

Vi2>Похоже, что твой вариант останавливается на сравнении указателей, поэтому и ощутимо быстрее.

Нет, ибо

void generate_input() {
  for (int n = 0; n < TOTAL_RUNS; ++n)
    input.push_back(std::string(input_tokens[std::rand() % items_in(input_tokens)]));
}
Re[11]: C++ code formatter
От: alex_public  
Дата: 15.10.17 01:58
Оценка:
Здравствуйте, c-smile, Вы писали:

_>>К сожалению не могу проверить данные результаты, т.к. не знаю кто такие tool::chars и т.п.
CS>tool::chars это пара
CS>
CS>struct chars { 
CS>  const char* start; 
CS>  size_t length; 
CS>}
CS>

CS>Вот вариант этой конструкции https://github.com/c-smile/sciter-sdk/blob/master/include/aux-slice.h#L48

А, ну т.е. это как раз самопальный аналог string_view. )))

_>>Вообще то это не моя функция — её предложил uzhas. Я вроде как вполне однозначно написал выше, что использую немного другой вариант.
CS>Ты как я понял используешь map string_view.
CS>Т.е. можешь переписать мой вариант со string_view — получишь тот же результат — map медленнее.
CS>Это если string_view::operator=() правильно написан конечно.

Эм, оператор равенства? ) У тебя какое-то весьма странное представление об алгоритмах... Как ты себе представляешь бинарное дерево на основе оператора равенства? )))

В реальном мире std::map очевидно использует оператор сравнения (а конкретно оператор "меньше"), а не оператор равенства. Причём если не указать иного, то используется стандартный оператор "меньше" для указанного в качестве ключа типа. И как раз в этом и заключается причина медленности твоей реализации варианта с map: стандартный оператор сравнения у std::string (да и у std::string_view тоже) является лексикографическим, что абсолютно логично для строкового типа, но совершенно избыточно для ключа бинарного дерева. Однако стоит нам указать более подходящий оператор сравнения, например так:
struct my_less{bool operator()(string_view x, string_view y) const {return x.size()==y.size()?x<y:x.size()<y.size();}};
const map<string_view, FormatterType, my_less> index = {...};

как сразу же данный код с map становится быстрее твоего варианта с if'ми даже для указанного в твоём примере небольшого перечисления (для больших перечислений map будет эффективнее даже со стандартным лексикографическим оператором сравнения).
Re[12]: C++ code formatter
От: alex_public  
Дата: 15.10.17 02:01
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Это вот ты написал?
_>>то очевидно что std::map будет эффективнее, т.к. инициализация дерева будет происходить только один раз. И это кстати не теория — я использую на практике именно такой подход (только со string_view, а не string в качестве ключа для map).

Зачем задавать риторические вопросы? )

CS>Если "да" то вот тебе пример когда map медленнее перебора.

Пока что подобного примера не видел. А видел только неумение пользоваться стандартными средствами языка и как следствие этого написание самопальных велосипедов. )
Re[11]: C++ code formatter
От: night beast СССР  
Дата: 15.10.17 09:23
Оценка:
Здравствуйте, c-smile, Вы писали:

NB>>вариант с поиском в сортированном векторе/массиве не пробовал?

CS>Сортированный вектор из 8 элементов? Зачем?

бинарный поиск -- меньше сравнений.

NB>>добавление простого хэша как ситуацию изменит?

CS>А как это меняет дело?

ну, сравнить два инта проще чем строки. но накладные расходы на вычисление хэша добавляются.
Re[7]: C++ code formatter
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 07:25
Оценка: +2
Здравствуйте, c-smile, Вы писали:

CS>Ты думаешь что условно 9 if:
CS>if(s.length = A && strcmp(...) == 0) t = 1;
CS>[/ccode]
CS>будет медленнее чем создание std::map и поиск по дереву?

Конечно if зарулит, если еще построить автомат, чтобы без strcmp, думаю, будет еще быстрее. А уж если собрать статистику, что чаще ищется и использовать чтобы минимизировать branch mispredict, то еще лучше. map здесь делает код чище, поэтому если овчинка выделки не стоит я за map (unordered_map), а в плане быстродействия вообще сравнивать смысла нет.
Re[8]: C++ code formatter
От: alex_public  
Дата: 16.10.17 23:56
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>Конечно if зарулит, если еще построить автомат, чтобы без strcmp, думаю, будет еще быстрее. А уж если собрать статистику, что чаще ищется и использовать чтобы минимизировать branch mispredict, то еще лучше. map здесь делает код чище, поэтому если овчинка выделки не стоит я за map (unordered_map), а в плане быстродействия вообще сравнивать смысла нет.

В данном конкретном случае unordered_map будет менее эффективным решением, по сравнению с просто map. )
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.