Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 15.10.17 23:58
Оценка: 4 (2) :)
Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.

Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.

Не ходите дети в Африку гулять используйте std::map не по назначению.
Отредактировано 16.10.2017 5:38 c-smile . Предыдущая версия .
Re: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 07:18
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].


Поэтому Кнута и ко надо читать с осторожностью — хоть парни и толковые, но инфа несколько устарела, если не учитывать устройство современного процессора (всякие кеши, предсказание переходов), то можно легко напороться на то, что алгоритм с худшей асимптоматикой внезапно уделывает алгоритм с хорошей. Ну и вообще стоит прикидывать стоимость операций — внезапно может оказаться, что при вставке на небольшом массиве со сдвигом, чтобы сохранить упорядоченность и бинарный поиск, уделывают деревья только так.
Re: Когда linear search быстрее hash map
От: fin_81  
Дата: 16.10.17 07:29
Оценка:
Здравствуйте, c-smile, Вы писали:

#if ENTRIES > 4
...
#if ENTRIES > 5
...
#if ENTRIES > 6
...
#if ENTRIES > 7
...
#if ENTRIES > 8
...
#if ENTRIES > 9
...
#endif
#endif
#endif
#endif
#endif
#endif

Бобер, выдыхай!

По теме, без комментариев.
Re: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 07:31
Оценка: +1
Здравствуйте, c-smile, Вы писали:

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


А если еще с этим сравнить, то это еще быстрей будет:

switch (*str++)
{
case 'p':
    switch (*str++)
    {
    case 'o':
        if (length == 4 && *str++ == 'r' && *str++ == 't')
        {
            ...
        }
        break;
    case 'u':
        if (length == 9 && *str++ == 'b' && *str++ == 'l' && *str++ == 'i' && *str++ == 'c' && *str++ == 'K' && *str++ == 'e' && *str++ == 'y')
        {
            ...
        }
        break;
    }
    break;
}


Но и это еще не все, ведь можно сравнивать не по байту, а сразу по 4, например.
Re: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 16.10.17 07:34
Оценка: +2
Здравствуйте, c-smile, Вы писали:

Если честно, я бы присмотрелся к Вашему тесту более внимательно.

1. Например, настораживает передача строки по значению.
FormatterType t2e(std::string s) { ... }


2. В контейнерах, std::map / std::unordered_map вы храните объекты std::string,
в то время когда в функция if_t2e сравнение идет с использованием обертки slice.

3. Дальше, маленькие объемы + еще std::string тот случай, когда нужно быть особенно внимательным,
поэтому еще нужно посмотреть как компилятор работает со строками ( какие там оптимизации ),
вполне возможно что разные компиляторы дадут разный результат.

4. Различные реализации std::hash / std::equal_to / std::less для std::string могут дать разные результат.

5. Можно попробовать хранить const char* вместо std::string, возможно тоже покажет другой результат.

И.т.д.
Re: Когда linear search быстрее hash map
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 16.10.17 07:41
Оценка: +2
Здравствуйте, c-smile, Вы писали:

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу.


В полтора раза (3.44 против 2.13) это "как бык овцу"?
"Ну извините..." ((с) Вовочка)
И заметим, всего-то при 9 записях линейный поиск уже хуже мапы. А что дальше?

CS> А над O(log N) — вообще сплошное надругательство.


Аж на пару десятков процентов.

Нет, тут понятно, что std::map обычно медленнее std::unordered_map (если не слишком дорого вычислять хэш), но Ваш пример как раз _против_ того, чтобы тут был выбран линейный поиск по умолчанию.
Потому что какая-то мапа тут по природе вещей и хорошо масштабируется, а замена на линейный поиск будет типичной преждевременной оптимизацией со всеми своими последствиями. Если это место станет узким и будет гарантия неувеличения количества ключевых строк — тогда можно сократить до линейного поиска. Если хотя бы одно условие не выполняется — закат солнца вручную отменяется.

А если тут нужен действительно быстрый поиск — то как это делать — смотреть, например, в Kamailio:

#define _acce_ 0x65636361   /* "acce" */
#define _allo_ 0x6f6c6c61   /* "allo" */
#define _auth_ 0x68747561   /* "auth" */
#define _oriz_ 0x7a69726f   /* "oriz" */
#define _atio_ 0x6f697461   /* "atio" */
#define _call_ 0x6c6c6163   /* "call" */
#define __id2_ 0x2064692d   /* "-id " */
#define __id1_ 0x3a64692d   /* "-id:" */

[...]

#define FIRST_QUATERNIONS       \
        case _via1_: via1_CASE; \
        case _from_: from_CASE; \
        case _to12_: to12_CASE; \
        case _cseq_: cseq_CASE; \
        case _call_: call_CASE; \
        case _cont_: cont_CASE; \
        case _rout_: rout_CASE; \
        case _max__: max_CASE;  \


ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.

CS>Не ходите дети в Африку гулять используйте std::map не по назначению.


Вы не показали, на каком количестве значений std::map эффективнее линейного поиска. Это уже некрасиво.
И VS-only code тоже сейчас как-то "не очень".
The God is real, unless declared integer.
Re: Когда linear search быстрее hash map
От: Vain Россия google.ru
Дата: 16.10.17 07:46
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Не ходите дети в Африку гулять используйте std::map не по назначению.

Игра в бирюльки по сравнению с оптимизацией критического по времени кода через интринсики, форсинлайн, гоуту и т.д..
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Когда linear search быстрее hash map
От: rg45 СССР  
Дата: 16.10.17 07:56
Оценка: +4
Здравствуйте, c-smile, Вы писали:

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 16.10.2017 8:15 rg45 . Предыдущая версия .
Re[2]: Когда linear search быстрее hash map
От: samius Япония http://sams-tricks.blogspot.com
Дата: 16.10.17 08:10
Оценка: +2
Здравствуйте, MTD, Вы писали:

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


CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].


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

Асимптотика описывает поведение при стремлении переменной к чему-то. В применении к сложностям алгоритмов рассматривается характер поведения при увеличении переменной, или стремлении к бесконечности. Кроме того, O(f(n)) — это верхняя оценка по определению, которая лишь указывает что существует константа и такое n0, что рост сложности алгоритма при n >= n0 будет соответствовать некоторой модели с точностью до этих констант. То есть, асимптотика не предназначена для описывания нижних оценок на малых n.

Причем Кнут — не понятно. Он не утверждает обратного.
Re: Когда linear search быстрее hash map
От: so5team https://stiffstream.com
Дата: 16.10.17 08:19
Оценка: 9 (2)
Здравствуйте, c-smile, Вы писали:

CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.


CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


CS>Не ходите дети в Африку гулять используйте std::map не по назначению.


Пару лет назад столкнулись с похожей историей. Посмотрели, как ведут себя разные структуры данных для хранения подписок агентов в зависимости от количества этих самых подписок. Оказалось, что если подписок всего один-два десятка, то хранение подписок в std::vector и простой линейный перебор по нему работает эффективнее всего. Если количество подписок находится в районе от пары десятков до пары сотен, то эффективнее работает std::map. А вот от 200+ подписок -- самым эффективным оказывается std::unordered_map.
Re[3]: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 08:47
Оценка: +1
Здравствуйте, samius, Вы писали:

S>То есть, асимптотика не предназначена для описывания нижних оценок на малых n.


Речь не только про малые n.

S>Причем Кнут — не понятно.


При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.

S>Он не утверждает обратного.


Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
Re: Когда linear search быстрее hash map
От: uzhas Ниоткуда  
Дата: 16.10.17 08:55
Оценка: -3
Здравствуйте, c-smile, Вы писали:

CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.

ты, к сожалению, не понял, что та дискуссия совсем не производительность, а про качество кода
тебе даже форматтер кода намекнул об этом

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.

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

CS>Не ходите дети в Африку гулять используйте std::map не по назначению.


сам-то понял, что сказал? (с)

у меня для тебя плохие новости: назначение мапы быть ассоциативным контейнером, то есть хранить ключи и значения и искать по ключам
ты хоть выводы может внятно сформулировать? вот сортировка пузырьком тоже в топ иногда выходит, но выводы из этого надо ещё уметь сделать
Re[4]: Когда linear search быстрее hash map
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 16.10.17 09:17
Оценка: +3
Здравствуйте, MTD, Вы писали:

S>>Причем Кнут — не понятно.


MTD>При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.


Я бы сказал "каждый раз надо измерять", а не "думать". "Думать" оно надо, но не это ключевое.

А "неучёт на современном железе" это специфика не только Кнута. Я навскидку сейчас посмотрел Кормена, Сиену, Седжвика — нигде не упоминается — по крайней мере нет ни в оглавлении, ни в предметном указателе. Поэтому следует полагать, что им в пару обязательно читать "Computer achitecture: a quantitative approach" или аналог.

Ещё Вы почему-то распространяете паразитную логическую связь "алгоритмы, сложность -> Кнут". Кнут — фундамент и историческая база, но сейчас его использовать в качестве абсолюта уже поздновато.

S>>Он не утверждает обратного.


MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.


Реальный мир надо всегда учитывать. Где-то алгоритм в 100 раз быстрее на RAM, но в 2 раза прожорливее по объёму памяти затормозится из-за трэшинга свопа. Где-то очень эффективная обычно сортировка станет вдруг медленнее пузырька из-за того, что сравнение в 1000 раз дороже обмена.

Вы читая Кнута почему-то смотрите только на выводы, а не на проведённый им анализ. А ведь то, чему он учит — это именно анализировать от основ. И при всём при этом не знаете никого, кроме Кнута... просто пугаете этим.
The God is real, unless declared integer.
Re[5]: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 09:20
Оценка: -2 :)
Здравствуйте, netch80, Вы писали:

N>Вы читая Кнута почему-то смотрите только на выводы, а не на проведённый им анализ. А ведь то, чему он учит — это именно анализировать от основ. И при всём при этом не знаете никого, кроме Кнута...


Телепатам привет!

N>просто пугаете этим.


Шапочка из фольги спасет от голосов в голове и вернет душевное здоровье.
Re[4]: Когда linear search быстрее hash map
От: samius Япония http://sams-tricks.blogspot.com
Дата: 16.10.17 10:34
Оценка: +1
Здравствуйте, MTD, Вы писали:

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


S>>То есть, асимптотика не предназначена для описывания нижних оценок на малых n.


MTD>Речь не только про малые n.

Но таки про нижние оценки?

S>>Причем Кнут — не понятно.


MTD>При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.

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

S>>Он не утверждает обратного.


MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно.

Это не так. Асимптотику предлагается использовать для прогноза роста стоимости алгоритма при увеличении n. При том, что M и x0 неизвестны, как об этом и указал Кнут.

MTD>Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.

Речь тут ровно о том, что вы сделали неверную оценку и прогноз. Неверно выбрали M и x0 при оценке скорости работы алгоритмов на дереве в условиях постоянных промахов. Нет никаких оснований утверждать на одинаковую эффективность алгоритмов с одной асимптотикой, не зная констант. Именно об этом Кнут и писал.
Re: Когда linear search быстрее hash map
От: kov_serg Россия  
Дата: 16.10.17 12:54
Оценка: 6 (1)
Здравствуйте, c-smile, Вы писали:

CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.


CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


А какой дикий восторг у них вызовет, что сортированный массив может в разы быстрее обрабатываться чем тот же но не сортированный.
    Without std::sort(data, data + arraySize);, the code runs in 11.54 seconds.
    With the sorted data, the code runs in 1.93 seconds.
Re: Когда linear search быстрее hash map
От: Mr.Delphist  
Дата: 16.10.17 13:26
Оценка: +1
Здравствуйте, c-smile, Вы писали:



CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.


CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


Ну, это не новость давно уже. "Умелки" процессора, размер кэшей, характер данных, их расклад в памяти и прочие вроде бы мелочи способны смешать с грязью самые теоретически-лучшие алгоритмы.
Re[2]: Когда linear search быстрее hash map
От: Erop Россия  
Дата: 16.10.17 13:57
Оценка: +1
Здравствуйте, MTD, Вы писали:

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


CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].


MTD>Поэтому Кнута и ко надо читать <...> внезапно может оказаться, что при вставке на небольшом массиве со сдвигом, чтобы сохранить упорядоченность и бинарный поиск, уделывают деревья только так.


1) Дык потому структуры вроде B-tree и придумали...
2) У того Кнута, которого когда-то читал я, было прямо написано, что какой бы распрекрасный рекурсивный алгоритм с очень хорошей асимптотикой вы не придумали, обычно начиная с некоторого размера и меньше, надо переключаться на что-то быстрое на маленьких данных
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Когда linear search быстрее hash map
От: Erop Россия  
Дата: 16.10.17 14:02
Оценка: 22 (1) +1
Здравствуйте, so5team, Вы писали:

S>Пару лет назад столкнулись с похожей историей. Посмотрели, как ведут себя разные структуры данных для хранения подписок агентов в зависимости от количества этих самых подписок. Оказалось, что если подписок всего один-два десятка, то хранение подписок в std::vector и простой линейный перебор по нему работает эффективнее всего. Если количество подписок находится в районе от пары десятков до пары сотен, то эффективнее работает std::map. А вот от 200+ подписок -- самым эффективным оказывается std::unordered_map.



Можно было сделать B-tree на 10-20 подписок на узел, -- совместило бы достоинства разных подходов...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 15:35
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>А если еще с этим сравнить, то это еще быстрей будет:


Я про это тоже написал. Это примерно то что генерирует perfect hash (gperf).
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 15:41
Оценка:
Здравствуйте, Engler, Вы писали:

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


E>Если честно, я бы присмотрелся к Вашему тесту более внимательно.


E>1. Например, настораживает передача строки по значению.

E>
E>FormatterType t2e(std::string s) { ... }
E>


Не важно. Ибо эта сигнатура используется во всех сравниваемых функциях.

E>2. В контейнерах, std::map / std::unordered_map вы храните объекты std::string,

E>в то время когда в функция if_t2e сравнение идет с использованием обертки slice.

А это причем?

E>3. Дальше, маленькие объемы + еще std::string тот случай, когда нужно быть особенно внимательным,

E>поэтому еще нужно посмотреть как компилятор работает со строками ( какие там оптимизации ),
E>вполне возможно что разные компиляторы дадут разный результат.

E>4. Различные реализации std::hash / std::equal_to / std::less для std::string могут дать разные результат.

E>5. Можно попробовать хранить const char* вместо std::string, возможно тоже покажет другой результат.

Я про это и говорю. Надо смотреть на реальную ситуацию, а не тупо брать std::map для поиска в наборе.
Re[3]: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 16.10.17 16:10
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Я про это тоже написал. Это примерно то что генерирует perfect hash (gperf).


Ну генерирует он сильно другое (насколько я помню), кроме того, при чем в контексте обсуждения он (это же генератор хеш-функции)?
Re[4]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 16:51
Оценка:
Здравствуйте, MTD, Вы писали:

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


CS>>Я про это тоже написал. Это примерно то что генерирует perfect hash (gperf).


MTD>Ну генерирует он сильно другое (насколько я помню), кроме того, при чем в контексте обсуждения он (это же генератор хеш-функции)?


gperf генерирует функцию в которой strcmp используется ровно один раз (т.е. полный проход строки). В качестве дискриминатора используется длина строки и один или несколько значений characters. Примерно тот же FSA что и ты написал как я понял.
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 16:59
Оценка:
Здравствуйте, rg45, Вы писали:

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


CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


R>Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...


Ну собственно об этом и речь. Это все про эту вот цитату:

Практик: "Если он вызывается не один раз, то очевидно что std::map будет эффективнее, т.к. инициализация дерева будет происходить только один раз. И это кстати не теория — я использую на практике именно такой подход (только со string_view, а не string в качестве ключа для map)."
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 17:01
Оценка:
Здравствуйте, uzhas, Вы писали:

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


CS>>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.

U>ты, к сожалению, не понял, что та дискуссия совсем не производительность, а про качество кода
U>тебе даже форматтер кода намекнул об этом

Что есть такое "качество кода" в обсуждаемом контексте?
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 18:29
Оценка:
Здравствуйте, netch80, Вы писали:

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


CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу.


N>В полтора раза (3.44 против 2.13) это "как бык овцу"?

N>"Ну извините..." ((с) Вовочка)
N>И заметим, всего-то при 9 записях линейный поиск уже хуже мапы. А что дальше?

CS>> А над O(log N) — вообще сплошное надругательство.


N>Аж на пару десятков процентов.


Ну дык, тут копеечка, там копеечка...


N>А если тут нужен действительно быстрый поиск — то как это делать — смотреть, например, в Kamailio:


N>
N>#define _acce_ 0x65636361   /* "acce" */
N>#define _allo_ 0x6f6c6c61   /* "allo" */
N>#define _auth_ 0x68747561   /* "auth" */
N>#define _oriz_ 0x7a69726f   /* "oriz" */
N>#define _atio_ 0x6f697461   /* "atio" */
N>#define _call_ 0x6c6c6163   /* "call" */
N>#define __id2_ 0x2064692d   /* "-id " */
N>#define __id1_ 0x3a64692d   /* "-id:" */

N>[...]

N>#define FIRST_QUATERNIONS       \
N>        case _via1_: via1_CASE; \
N>        case _from_: from_CASE; \
N>        case _to12_: to12_CASE; \
N>        case _cseq_: cseq_CASE; \
N>        case _call_: call_CASE; \
N>        case _cont_: cont_CASE; \
N>        case _rout_: rout_CASE; \
N>        case _max__: max_CASE;  \
N>


N>ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.


Да вот тоже не факт на самом деле ...

1) endianness 2) перевод в нижний регистр это O(n) и 3) switch на разреженных case values это всё тот же linear lookup.
Немного лучше, но тем не менее нужно смотреть на конкретное распределение tokens probability. Про которые компилятор не знает ничего и может сгенерировать плохой lookup.
Re[2]: Когда linear search быстрее hash map
От: prog123 Европа  
Дата: 16.10.17 18:44
Оценка:
Здравствуйте, rg45, Вы писали:

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


CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


R>Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...


В этих формулах еще есть константа, про которую забывают, которая и есть все эти хэши, кэши, предсказания ветвлений, прифечинг и прочее. При большом n ее влияние не значительно, поэтому в формулах ее и отбрасывают, а при малых n она как раз может оказать решающее влияние на скорость.
Re[3]: Когда linear search быстрее hash map
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 16.10.17 19:34
Оценка:
Здравствуйте, c-smile, Вы писали:

N>>Аж на пару десятков процентов.

CS>Ну дык, тут копеечка, там копеечка...

Ну если уверены, что эта копеечка на что-то повлияет — ok, делать так. Оставив под, условно говоря, `#if 0` простой вариант.

N>>ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.


CS>Да вот тоже не факт на самом деле ...

CS>1) endianness

Решено основным случаем (для BE разворачивают порядок).

CS> 2) перевод в нижний регистр это O(n)


Он делается через or с 0x20202020 (или чуть меньшей маской, где не буква).

CS> и 3) switch на разреженных case values это всё тот же linear lookup.


Компиляторы часто строят switch как дерево ifʼов.

CS>Немного лучше, но тем не менее нужно смотреть на конкретное распределение tokens probability. Про которые компилятор не знает ничего и может сгенерировать плохой lookup.


Оно для этой задачи, грубо говоря, равномерно — вероятность встретить поле заголовка слабо зависит от букв начала его имени.
(Хуже то, что на нём любые branch prediction лажаются.)
The God is real, unless declared integer.
Re: Когда linear search быстрее hash map
От: Pzz Россия https://github.com/alexpevzner
Дата: 16.10.17 19:47
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Не ходите дети в Африку гулять используйте std::map не по назначению.


А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.

При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?
Re: Когда linear search быстрее hash map
От: prog123 Европа  
Дата: 16.10.17 20:47
Оценка:
Здравствуйте, c-smile, Вы писали:



CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.


CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.


CS>Не ходите дети в Африку гулять используйте std::map не по назначению.


а можешь такой вариант проверить? идея в том чтобы положить все данные в массив и последовательно, так чтобы хорошо работал кэш, сравнивать куски памяти с помощью memcmp.
#include<memory.h>
#include<string.h>
#include<string>
#include<iostream>

//enum FormatterType {
//    simple_formatter,        0
//    integer_formatter,        1
//    decimal_formatter,        2
//    currency_formatter,        3
//    date_formatter,            4
//    date_local_formatter,    5
//    time_formatter,            6
//    time_local_formatter,    7
//    enum_formatter,            8
//    duration_formatter        9
//};

int str2enum(std::string const& s)
{    
    static int const ssize = strlen("          ");
    static char  m[] =        
        "          "
        "text      "
        "integer   "
        "decimal   "
        "currency  "
        "date      "
        "date-local"
        "time      "
        "time-local"
        "enum      "
        "duration  "
        ;
    static int const msize = strlen(m) / ssize;

    if (s.size() > ssize)
        return 0; // 0-simple_formatter

    memset(m, ' ', ssize);
    memcpy(m, s.c_str(), s.size());

    for (int i = 1; i < msize; ++i)
    {
        if (memcmp(m, m + i * ssize, ssize) == 0)
            return i - 1;
    }
    
    return 0; // 0-simple_formatter
}

int main(int , char**)
{
    std::cout << str2enum("text") << std::endl;
    std::cout << str2enum("date-local") << std::endl;
    std::cout << str2enum("duration") << std::endl;
    std::cout << str2enum("abc") << std::endl;
    std::cout << str2enum("abcdefjhiklmnopst") << std::endl;

    return 0;
}
Re[2]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 16.10.17 21:11
Оценка:
Здравствуйте, Pzz, Вы писали:

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


CS>>Не ходите дети в Африку гулять используйте std::map не по назначению.


Pzz>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.


А как это помогает?

Pzz>При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?


Ну дык оно же там есть:

// gperf approach +++

FormatterType gperf_t2e(std::string name)
{
  const struct enum_def * ed = enum_names::find_def(name.c_str(), (unsigned int)name.size());
  return ed ? FormatterType(ed->value) : simple_formatter;
}
// gperf approach ---


Gperf возвращает nullptr если не найден. И потом входной поток содержит токены не из набора.
Re[3]: Когда linear search быстрее hash map
От: Pzz Россия https://github.com/alexpevzner
Дата: 16.10.17 21:22
Оценка:
Здравствуйте, c-smile, Вы писали:

Pzz>>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.


CS>А как это помогает?


Быстрее работает, чем сравнивать строки в цикле побайтово.
Re[2]: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 16.10.17 21:32
Оценка:
Здравствуйте, Engler, Вы писали:

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


E>Если честно, я бы присмотрелся к Вашему тесту более внимательно.

Посмотрел немного более внимательно.
Мне все-таки кажется, что сравнение в тесте не совсем корректное.
Функция,
FormatterType if_t2e(std::string name)

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


И это, не совсем честный линейный поиск. Вместо этого, по хорошему надо делать поиск в std::vector.
Тогда получится, что вы сравниваете похожие вещи.
  Код
std::vector<std::pair<std::string, FormatterType>> vector_map = {
    std::pair<std::string,FormatterType> { "text", simple_formatter },
    std::pair<std::string,FormatterType> { "integer", integer_formatter },
    std::pair<std::string,FormatterType> { "decimal", decimal_formatter },
    std::pair<std::string,FormatterType> { "currency", currency_formatter },
#if ENTRIES > 4
    std::pair<std::string,FormatterType> { "date", date_formatter },
#if ENTRIES > 5
    std::pair<std::string,FormatterType> { "date-local", date_local_formatter },
#if ENTRIES > 6
    std::pair<std::string,FormatterType> { "time", time_formatter },
#if ENTRIES > 7
    std::pair<std::string,FormatterType> { "time-local", time_local_formatter },
#if ENTRIES > 8
    std::pair<std::string,FormatterType> { "enum", enum_formatter },
#if ENTRIES > 9
    std::pair<std::string,FormatterType> { "duration", duration_formatter }
#endif
#endif
#endif
#endif
#endif
#endif
};

FormatterType vector_search(const std::string& name)
{
    auto it = std::find_if(vector_map.begin(), vector_map.end(),
        [&name](const std::pair<std::string, FormatterType>& p) { return name == p.first; });
        
    return (it != vector_map.end()) ? it->second : simple_formatter;
}

// это в main
run_test(vector_search, "vector_search");


Вот что у меня получилось,

  Результаты

map_t2e 6.85883 359490000
unordered_map_chars_t2e 4.56228 359490000
unordered_map_string_index 5.755 359490000
if_t2e 2.12067 359490000
gperf_t2e 2.27001 359490000
vector_search 6.77989 359490000



А вот кстати, поведение std::unordered_map::find меня удивило.
Она вызывает lower_bound, которая в свою очередь уже
1) строит хеш [вызывается кастомный функтор], что в общем-то естесвенно
2) вызывает опреатор == ( для поиска элеметна в листе , на который указывает bucket )
3) вызывает опреатор == еще раз ( пока не понял зачем ).

В итоге мы имеем хорошо оптимизированную функцию if_t2e,
против непонятно какой реализации unordered_map.

P.S: VS VS2015
Re[4]: Когда linear search быстрее hash map
От: · Великобритания  
Дата: 16.10.17 22:56
Оценка:
Здравствуйте, MTD, Вы писали:

MTD> Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска

Какая-то фигня.
Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.
Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами. Тогда не придётся "слепо верить", а просто тупо считать.

По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).
avalon/2.0.6
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Когда linear search быстрее hash map
От: alex_public  
Дата: 17.10.17 00:09
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Эта вот дискуссия
Автор: c-smile
Дата: 05.10.17
подвигла мя на написание статьи на тему.

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.

Хм, я тебе вроде как всё понятно разъяснил в этом http://rsdn.org/forum/cpp/6934121.1
Автор: alex_public
Дата: 15.10.17
сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))
Re[4]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 17.10.17 01:57
Оценка:
Здравствуйте, Pzz, Вы писали:

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


Pzz>>>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.


CS>>А как это помогает?


Pzz>Быстрее работает, чем сравнивать строки в цикле побайтово.


Нет, не быстрее:

Это вот 2.82 секунды

bool operator == ( const slice& r ) const
      {
        if( length != r.length )
          return false;
        for( unsigned int i = 0; i < length; ++i )
          if( start[i] != r.start[i] )
            return false;
        return true;
      }


А это

bool operator == ( const slice& r ) const
      {
        if( length != r.length )
          return false;
        return memcmp(start, r.start, length) == 0;
      }


3.06 секунды. Затраты на вызов функции и подготовка поиска в memcmp.
memcmp выигрывает на больших последовательностях, но не в этом случае.
Re[3]: Когда linear search быстрее hash map
От: c-smile Канада http://terrainformatica.com
Дата: 17.10.17 02:05
Оценка:
Здравствуйте, Engler, Вы писали:

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


E>В итоге мы имеем хорошо оптимизированную функцию if_t2e,


Что там оптимизировано-то?

Банальный же if-elif-elif-else... т.е. последовательный (линейный) перебор.
Re[4]: Когда linear search быстрее hash map
От: elmal  
Дата: 17.10.17 05:01
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>Речь не только про малые n.

Ух ты. Хотелось бы посмотреть, как линейный поиск обойдет лучшие асимптотически алгоритмы при n хотя б в миллион. А лучше в миллиард.

MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.

Кеш промахи и все такое имеют значение только для малых n. Но даже без учетов архитектуры современных процессоров, алгоритмы в лоб чаще проще и в результате за 1 проход выполняется меньшее количество команд. Соответственно да, для малых n простой алгоритм может быть быстрее и даже скорее всего будет. Но с ростом n всегда получится дерьмо. Учетом архитектуры процессора и тому подобного на больших n ты максимум поднимешь производительность в 10 раз. Ладно, даже в 100. Ладно, даже в тысячу, хоть это и маловероятно. Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз. Главное чтоб памяти хватило чтоб это n вместить.
Re[5]: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 17.10.17 05:33
Оценка:
Здравствуйте, elmal, Вы писали:

E>Ух ты.


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

E>Кеш промахи и все такое имеют значение только для малых n.


Да что ты говоришь. Вот у тебя есть 100 терабайт данных — это малое n? Теперь представь, что у тебя есть оперативная память (кеш) и дисковый массив. Тебе все еще не очевидно, что количество промахов надо минимизировать?

E>Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз.


Я где-то это отрицал? Ткни пальцем.
Re[5]: Когда linear search быстрее hash map
От: MTD https://github.com/mtrempoltsev
Дата: 17.10.17 05:40
Оценка:
Здравствуйте, ·, Вы писали:

·>Какая-то фигня.


Да, так обычно получается, если не прочитать, но начать отвечать.

·>Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.


Молодец. Любопытно, что побудило тебя написать это?

·>Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами.


Я никак не пойму, ты с чем споришь? Я где-то отрицал, что надо учитывать конкретные реализации структур данных?

·>По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).


Универсальное решение всегда проигрывает в каком-то случае частному. Я думаю, до какого-то n (не знаю какого — надо бенчмаркать) ничего быстрее автомата не будет, потом возможно начнет рулить бинарный поиск, а затем хеш-таблица, дальше уже начнутся всякие фильтры Блума вместе со всякими экзотическими структурами.
Re[6]: Когда linear search быстрее hash map
От: · Великобритания  
Дата: 17.10.17 07:32
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>·>Какая-то фигня.

MTD>Да, так обычно получается, если не прочитать, но начать отвечать.
Я наверное просто к словам придираюсь. " асимптотика поиска одинакова — логарифм" — это верно для абстактной структуры "дерево", "массив". А имплементация даёт изменение асимтотики — индирекция, промах в кеш это по сути дополнительный lookup для процессора, который начинает использовать ассоциативный контейнер страниц памяти для их подгрузки в свой кеш. Т.е. на уровне языка программирования вроде как одно и то же, но если смотреть все слои всего вычислительного устройства — то уже фигня получается. То же и с предсказанием ветвления — это ведь тоже по сути алгоритм со своей сложностью — не всегда его влияние можно отбрасывать.
Т.е. проблема не в асимтотике, а в том как её считают — не учитывают "незначительные" детали.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[6]: Когда linear search быстрее hash map
От: Vain Россия google.ru
Дата: 17.10.17 07:42
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>Шапочка из фольги спасет от голосов в голове и вернет душевное здоровье.

Шапочка из фольги на самом деле отражает внутренние голоса обратно в голову. Из-за чего процесс зацикливается и из него нету выхода. Перегрев одним словом наступит.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[4]: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 17.10.17 07:58
Оценка: 2 (1)
Здравствуйте, c-smile, Вы писали:

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


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


E>>В итоге мы имеем хорошо оптимизированную функцию if_t2e,


CS>Что там оптимизировано-то?

Например gcc, вначале сравнивает строки одинаковой длинны (4 байта), потом более длинной, и.т.д
Это если я правильно понял, конечно.
( update: причем компилятор разварачивает сравнение вот таким вот образом

if (str[0] != 't') goto ...
if (str[1] != 'e') goto ...
if (str[2] != 'x') goto ...
if (str[3] != 't') goto ...


И так для всех строк

)

CS>Банальный же if-elif-elif-else... т.е. последовательный (линейный) перебор.

Банальность, это ключ

gcc.godbolt

Я немного добавил тестов, что бы точнее понять, что присходит.
Я добавил 2 вектора [вооще 4, с разным порядком строк, отсортированным по длине, и оригинальным]
std::vector<pair< string, FormatterType> > и
std::vector<pair< aux::chars, FormatterType> > и
Еще в клоне if_t2e немного нагадил компилятору с помощью volatile, потому что могу
и что бы он не харкодил значения, а "честно" читал их как в случае c std::vector



  Код
#include <iostream>

#include <string>
#include <vector>
#include <chrono>
#include <algorithm>
#include <unordered_map>
#include <string.h>
#include <cassert>

//elements in array literal
#define ITEMS_IN(a) (sizeof(a)/sizeof(a[0]))
//chars in sting literal
#define CHARS_IN(s) (sizeof(s) / sizeof(s[0]) - 1)

namespace aux
{

    template <typename T >
    struct slice
    {
        const T*       start;
        unsigned int   length;

        slice() : start(0), length(0) {}
        slice(const T* start_, size_t length_) { start = start_; length = (unsigned int)length_; }
        slice(const slice& src) : start(src.start), length(src.length) {}
        slice(const std::basic_string<T>& src) : start(src.c_str()), length((unsigned int)src.length()) {}

        slice& operator = (const slice& src) { start = src.start; length = src.length; return *this; }

        const T*      end() const { return start + length; }

        bool operator == (const slice& r) const
        {
            if (length != r.length)
                return false;
            for (unsigned int i = 0; i < length; ++i)
                if (start[i] != r.start[i])
                    return false;
            return true;
        }

        bool operator == (volatile const slice& r) const
        {
            if (length != r.length)
                return false;
            for (unsigned int i = 0; i < length; ++i)
                if (start[i] != r.start[i])
                    return false;
            return true;
        }

        bool operator != (const slice& r) const { return !operator==(r); }

        T operator[] (unsigned int idx) const
        {
            assert(idx < length);
            if (idx < length)
                return start[idx];
            return 0;
        }

        T last() const
        {
            if (length)
                return start[length - 1];
            return 0;
        }

        // [idx1..length)
        slice operator() (unsigned int idx1) const
        {
            assert(idx1 < length);
            if (idx1 < length)
                return slice(start + idx1, length - idx1);
            return slice();
        }
        // [idx1..idx2)
        slice operator() (unsigned int idx1, unsigned int idx2) const
        {
            assert(idx1 < length);
            assert(idx2 <= length);
            assert(idx1 <= idx2);
            if (idx1 < idx2)
                return slice(start + idx1, idx2 - idx1);
            return slice();
        }

        int index_of(T e) const
        {
            for (unsigned int i = 0; i < length; ++i) if (start[i] == e) return i;
            return -1;
        }

        int last_index_of(T e) const
        {
            for (unsigned int i = length; i > 0;) if (start[--i] == e) return i;
            return -1;
        }

        int index_of(const slice& s) const
        {
            if (s.length > length) return -1;
            if (s.length == 0) return -1;
            unsigned int l = length - s.length;
            for (unsigned int i = 0; i < l; ++i)
                if (start[i] == *s.start)
                {
                    const T* p = s.start;
                    unsigned int last = i + s.length;
                    for (unsigned int j = i + 1; j < last; ++j)
                        if (*(++p) != start[j])
                            goto next_i;
                    return i;
                next_i: continue;
                }
            return -1;
        }

        int last_index_of(const slice& s) const
        {
            if (s.length > length) return -1;
            if (s.length == 0) return -1;
            const T* ps = s.end() - 1;
            for (unsigned int i = length; i > 0; )
                if (start[--i] == *ps)
                {
                    const T* p = ps;
                    unsigned int j, first = i - s.length + 1;
                    for (j = i; j > first; )
                        if (*(--p) != start[--j])
                            goto next_i;
                    return j;
                next_i: continue;
                }
            return -1;
        }

        void prune(unsigned int from_start, unsigned int from_end = 0)
        {
            unsigned int s = from_start >= length ? length : from_start;
            unsigned int e = length - (from_end >= length ? length : from_end);
            start += s;
            if (s < e) length = e - s;
            else length = 0;
        }


    };

    typedef slice<char>          chars;
    typedef slice<wchar_t>       wchars;
    typedef slice<unsigned char> bytes;

    // Note: CS here is a string literal!
#define CHARS(CS) aux::slice<char>(CS,CHARS_IN(CS))
#define WCHARS(CS) aux::slice<wchar_t>(WSTR(CS),CHARS_IN(_WSTR(CS)))

    inline wchars  chars_of(const wchar_t *t) { return t ? wchars(t, (unsigned int)wcslen(t)) : wchars(); }
    inline chars   chars_of(const char *t) { return t ? chars(t, (unsigned int)strlen(t)) : chars(); }


    template<typename T>
    slice<T> chars_of(const std::basic_string<T> &s) { return slice<T>(s.c_str(), s.length()); }

    template<typename T>
    slice<T> elements_of(const std::vector<T> &s) { return slice<T>(s.cbegin(), s.size()); }

    template<typename T, int size>
    slice<T> elements_of(T(&arr)[size]) { return slice<T>(&arr[0], size); }

    template<typename T, int size>
    slice<T> elements_of(const T(&arr)[size]) { return slice<T>(&arr[0], size); }

    template<typename T>
    std::basic_string<T> make_string(aux::slice<T> s) { return std::basic_string<T>(s.start, s.length); }

}

enum FormatterType {
    simple_formatter,
    integer_formatter,
    decimal_formatter,
    currency_formatter,
    date_formatter,
    date_local_formatter,
    time_formatter,
    time_local_formatter,
    enum_formatter,
    duration_formatter
};

enum { TOTAL_RUNS = 10000 };

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)]));
}

FormatterType if_t2e(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);
    auto result =
        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
        : name_chars == CHARS("duration") ? duration_formatter
        : simple_formatter;
    return result;
}

volatile aux::chars aux_text = CHARS("text");
volatile aux::chars aux_integer = CHARS("integer");
volatile aux::chars aux_decimal = CHARS("decimal");
volatile aux::chars aux_currency = CHARS("currency");
volatile aux::chars aux_date = CHARS("date");
volatile aux::chars aux_datelocal = CHARS("date-local");
volatile aux::chars aux_time = CHARS("time");
volatile aux::chars aux_timelocal = CHARS("time-local");
volatile aux::chars aux_enum = CHARS("enum");
volatile aux::chars aux_duration = CHARS("duration");

FormatterType if_t2e_disable_opt(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);
    return name_chars == aux_text ? simple_formatter
        : name_chars == aux_integer ? integer_formatter
        : name_chars == aux_decimal ? decimal_formatter
        : name_chars == aux_currency ? currency_formatter
        : name_chars == aux_date ? date_formatter
        : name_chars == aux_datelocal ? date_local_formatter
        : name_chars == aux_time ? time_formatter
        : name_chars == aux_timelocal ? time_local_formatter
        : name_chars == aux_enum ? enum_formatter
        : name_chars == aux_duration ? duration_formatter
        : simple_formatter;
}

std::vector<std::pair<std::string, FormatterType>> vector_string_no_order = {
    std::pair<std::string,FormatterType> { "text", simple_formatter },
    std::pair<std::string,FormatterType> { "integer", integer_formatter },
    std::pair<std::string,FormatterType> { "decimal", decimal_formatter },
    std::pair<std::string,FormatterType> { "currency", currency_formatter },
    std::pair<std::string,FormatterType> { "date", date_formatter },
    std::pair<std::string,FormatterType> { "date-local", date_local_formatter },
    std::pair<std::string,FormatterType> { "time", time_formatter },
    std::pair<std::string,FormatterType> { "time-local", time_local_formatter },
    std::pair<std::string,FormatterType> { "enum", enum_formatter },
    std::pair<std::string,FormatterType> { "duration", duration_formatter }
};

std::vector<std::pair<std::string, FormatterType>> vector_string_order = {
    std::pair<std::string,FormatterType> { "text", simple_formatter },
    std::pair<std::string,FormatterType> { "date", date_formatter },
    std::pair<std::string,FormatterType> { "time", time_formatter },
    std::pair<std::string,FormatterType> { "enum", enum_formatter },
    std::pair<std::string,FormatterType> { "integer", integer_formatter },
    std::pair<std::string,FormatterType> { "decimal", decimal_formatter },
    std::pair<std::string,FormatterType> { "currency", currency_formatter },
    std::pair<std::string,FormatterType> { "duration", duration_formatter },
    std::pair<std::string,FormatterType> { "date-local", date_local_formatter },
    std::pair<std::string,FormatterType> { "time-local", time_local_formatter },
};

std::vector<std::pair<aux::chars, FormatterType>> vector_slice_no_order = {
    std::pair<aux::chars,FormatterType> { CHARS("text"), simple_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("integer"), integer_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("decimal"), decimal_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("currency"), currency_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date"), date_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date-local"), date_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time"), time_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time-local"), time_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("enum"), enum_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("duration"), duration_formatter }
};

std::vector<std::pair<aux::chars, FormatterType>> vector_slice_order = {
    std::pair<aux::chars,FormatterType> { CHARS("text"), simple_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date"), date_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time"), time_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("enum"), enum_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("integer"), integer_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("decimal"), decimal_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("currency"), currency_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("duration"), duration_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date-local"), date_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time-local"), time_local_formatter },
};

FormatterType search_vector_string_no_order(const std::string& name)
{
    auto it = std::find_if(vector_string_no_order.begin(), vector_string_no_order.end(),
        [&name](const std::pair<std::string, FormatterType>& p) { return name == p.first; });

    return (it != vector_string_no_order.end()) ? it->second : simple_formatter;
}

FormatterType search_vector_string_order(const std::string& name)
{
    for (auto& value : vector_string_order)
    {
        if (value.first == name) return value.second;
    }

    return simple_formatter;
}

FormatterType search_vector_slice_no_order(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);

    for (auto& value : vector_slice_no_order)
    {
        if (value.first == name_chars) return value.second;
    }

    return simple_formatter;
}

FormatterType search_vector_slice_order(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);

    for (auto& value : vector_slice_order)
    {
        if (value.first == name_chars) return value.second;
    }

    return simple_formatter;
}

int main(int argc, char *argv[])
{
    generate_input();

    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)if_t2e(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 << "if_t2e" << " " << elapsed_seconds << " " << tn << std::endl;

    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)if_t2e_disable_opt(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "if_t2e_disable_opt  " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_string_no_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_string_no_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_string_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_string_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_slice_no_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_slice_no_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_slice_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_slice_order " << elapsed_seconds << " " << tn << std::endl;


    return 0;
}


А вот результаты:
  Результатики

VS 2015:
if_t2e 2.06238 359490000
if_t2e_disable_opt 2.58692 359490000
search_vector_string_no_order 6.19423 359490000
search_vector_string_order 6.65881 359490000
search_vector_slice_no_order 4.20195 359490000
search_vector_slice_order 3.93327 359490000


[root@server tests]# ./run-4.9.2.sh
if_t2e 1.26558 359540000
if_t2e_disable_opt 1.99513 359540000
search_vector_string_no_order 2.27271 359540000
search_vector_string_order 2.45472 359540000
search_vector_slice_no_order 1.86913 359540000
search_vector_slice_order 1.98669 359540000

[root@server tests]# ./run-5.3.0.sh
if_t2e 1.17153 359540000
if_t2e_disable_opt 2.02901 359540000
search_vector_string_no_order 2.25595 359540000
search_vector_string_order 2.35924 359540000
search_vector_slice_no_order 1.89309 359540000
search_vector_slice_order 1.89116 359540000

[root@server tests]# ./run-6.1.0.sh
if_t2e 1.0725 359540000
if_t2e_disable_opt 1.97939 359540000
search_vector_string_no_order 2.3664 359540000
search_vector_string_order 2.43029 359540000
search_vector_slice_no_order 1.90254 359540000
search_vector_slice_order 1.93222 359540000



Вот теперь, попытка интерпретации результатов.
Что мы имеем.


"Банальный поиск" выигрывает у поиска по std::string в std::vector и у slice в std::vector.

"Банальный поиск" в результате превращается в оптимизированный вариант сравнения с констатами.
Оптимизированный, потому что строки выклаюыватся по длине в определенным образом.
Сравнение с константами, потому что компилятор может их подставить.

Давай-те попробуем усложнить задачу, и попробовать запретить подстановку строк с помощью volatile ( пришлось дописать конструктор с volatile ).
И увидим, что if_t2e_disable_opt уже выросла в почти 2 раза ( и равно обычному линейном поиску в std::vector для slice ),
что подталкивает не мысль, что обращение к памяти ( или кешу, тут уже не знаю ) ухудшает работу.

Но все равно поиск по строкам занимает больше времени.
Если взглянуть на реализацию сравнения std::string и slice мы увидим, что:
slice делает меньше телодвижений ( сравнивается только длина и значения )
std::string делает больше работы ( во всяком случае под дебагом в VS ):
1. Есть сравнение длинны строки ( из за SSO оптимизации ) это раз.
2. Сравнение реализовано через int compare, т.е результат может быть "равно" , "больше", "меньше",
а это требует, как минимум еще одного сравнения длинны. И только потом уже мы можем перейти непосредсвенно к сравнению строк.
Похоже, что на 10,000,000 итерации эти несколько "лишних" сравнений и ухудшают результат.
Это кстати ответ, на вопрос в вашем другом посте ( в чем разница, между хранением std::string и slice: короткий ответ в реализации operator==)

А вот ручное выкладывание строк по порядку, результато не дало.
Отредактировано 17.10.2017 9:12 Engler . Предыдущая версия .
Re[2]: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 17.10.17 13:42
Оценка:
Здравствуйте, alex_public, Вы писали:

_>Хм, я тебе вроде как всё понятно разъяснил в этом http://rsdn.org/forum/cpp/6934121.1
Автор: alex_public
Дата: 15.10.17
сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))


Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю? Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?
Re[3]: Когда linear search быстрее hash map
От: alex_public  
Дата: 19.10.17 21:24
Оценка:
Здравствуйте, Engler, Вы писали:

_>>Хм, я тебе вроде как всё понятно разъяснил в этом http://rsdn.org/forum/cpp/6934121.1
Автор: alex_public
Дата: 15.10.17
сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))

E>Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю?

И у std::string и у std::string_view оператор сравнения является лексикографическим, о чём я собственно и написал в сообщение по ссылке выше. Однако std::map совершенно не обязан его использовать — это всего лишь значение по умолчанию для 3-го параметра шаблона map, который в случае принципиальности быстродействия естественно устанавливается свой.

E>Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?


Да как угодно, лишь бы работал быстро и позволял реализовывать некую сортировку. Например по ссылке выше есть рабочий пример подобного оператора, с которым std::map работает быстрее линейного поиска даже на маленьких перечислениях.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.