Здравствуйте, 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 для поиска в наборе.
Здравствуйте, MTD, Вы писали:
MTD>Здравствуйте, c-smile, Вы писали:
CS>>Я про это тоже написал. Это примерно то что генерирует perfect hash (gperf).
MTD>Ну генерирует он сильно другое (насколько я помню), кроме того, при чем в контексте обсуждения он (это же генератор хеш-функции)?
gperf генерирует функцию в которой strcmp используется ровно один раз (т.е. полный проход строки). В качестве дискриминатора используется длина строки и один или несколько значений characters. Примерно тот же FSA что и ты написал как я понял.
Здравствуйте, 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)."
подвигла мя на написание статьи на тему. U>ты, к сожалению, не понял, что та дискуссия совсем не производительность, а про качество кода U>тебе даже форматтер кода намекнул об этом
Что есть такое "качество кода" в обсуждаемом контексте?
Здравствуйте, 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>ну и так далее — строка нарезается стандартными порциями по 4 байта, переводится к нижнему регистру (SIP заголовки — case-insensitive) и затем задача компилятора — выбрать правильный вариант разложить case (обычно он строит что-то вроде дерева). Да, это очень жёсткая целевая оптимизация. Но там она оправдана.
Да вот тоже не факт на самом деле ...
1) endianness 2) перевод в нижний регистр это O(n) и 3) switch на разреженных case values это всё тот же linear lookup.
Немного лучше, но тем не менее нужно смотреть на конкретное распределение tokens probability. Про которые компилятор не знает ничего и может сгенерировать плохой lookup.
Здравствуйте, 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 она как раз может оказать решающее влияние на скорость.
Здравствуйте, 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 лажаются.)
Здравствуйте, c-smile, Вы писали:
CS>Не ходите дети в Африку гулять используйте std::map не по назначению.
А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?
а можешь такой вариант проверить? идея в том чтобы положить все данные в массив и последовательно, так чтобы хорошо работал кэш, сравнивать куски памяти с помощью memcmp.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, c-smile, Вы писали:
CS>>Не ходите дети в Африку гулять используйте std::map не по назначению.
Pzz>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
А как это помогает?
Pzz>При использовании perfect hash в реальной жизни было бы не лишне сделать в конце проверку, что мы нашли именно то, что искали. На заданном наборе он, конечно, не дает коллизий, но кто сказал, что его с гарантией накормят одной из валидных строк?
Здравствуйте, c-smile, Вы писали:
Pzz>>А если бы ты в своем линейном поиске свел проверку к memcmp(), он победил бы во всех случаях.
CS>А как это помогает?
Быстрее работает, чем сравнивать строки в цикле побайтово.
Здравствуйте, Engler, Вы писали: E>Здравствуйте, c-smile, Вы писали: E>Если честно, я бы присмотрелся к Вашему тесту более внимательно.
Посмотрел немного более внимательно.
Мне все-таки кажется, что сравнение в тесте не совсем корректное.
Функция,
FormatterType if_t2e(std::string name)
Сам код в этой функции дает определенные подсказки компилятору.
Судя по всему очень хорошо инлайнится, + возможно еще есть магия опцимизации ( я там не во всем разбирался ).
И это, не совсем честный линейный поиск. Вместо этого, по хорошему надо делать поиск в std::vector.
Тогда получится, что вы сравниваете похожие вещи.
А вот кстати, поведение std::unordered_map::find меня удивило.
Она вызывает lower_bound, которая в свою очередь уже
1) строит хеш [вызывается кастомный функтор], что в общем-то естесвенно
2) вызывает опреатор == ( для поиска элеметна в листе , на который указывает bucket )
3) вызывает опреатор == еще раз ( пока не понял зачем ).
В итоге мы имеем хорошо оптимизированную функцию if_t2e,
против непонятно какой реализации unordered_map.
Здравствуйте, MTD, Вы писали:
MTD> Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска
Какая-то фигня.
Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.
Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами. Тогда не придётся "слепо верить", а просто тупо считать.
По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).
Здравствуйте, 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;
}
Здравствуйте, MTD, Вы писали:
MTD>Речь не только про малые n.
Ух ты. Хотелось бы посмотреть, как линейный поиск обойдет лучшие асимптотически алгоритмы при n хотя б в миллион. А лучше в миллиард.
MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.
Кеш промахи и все такое имеют значение только для малых n. Но даже без учетов архитектуры современных процессоров, алгоритмы в лоб чаще проще и в результате за 1 проход выполняется меньшее количество команд. Соответственно да, для малых n простой алгоритм может быть быстрее и даже скорее всего будет. Но с ростом n всегда получится дерьмо. Учетом архитектуры процессора и тому подобного на больших n ты максимум поднимешь производительность в 10 раз. Ладно, даже в 100. Ладно, даже в тысячу, хоть это и маловероятно. Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз. Главное чтоб памяти хватило чтоб это n вместить.
Читать написанное мной не пробовал? Попробуй, потом покажи пальцем, где я там линейный поиск называл панацеей.
E>Кеш промахи и все такое имеют значение только для малых n.
Да что ты говоришь. Вот у тебя есть 100 терабайт данных — это малое n? Теперь представь, что у тебя есть оперативная память (кеш) и дисковый массив. Тебе все еще не очевидно, что количество промахов надо минимизировать?
E>Вот только смена асимптотики — это ускорение может быть в миллионы и миллиарды раз.
Да, так обычно получается, если не прочитать, но начать отвечать.
·>Бинарное дерево можно реализовать in-place в массиве. А упорядоченный массив может быть массивом указателей с кеш-промахами. И внезапно дерево заработает быстрее упорядоченного массива.
Молодец. Любопытно, что побудило тебя написать это?
·>Просто надо учитывать конкретные реализации структур данных — чем именно занимается процессор, а не оперировать абстрактными типами.
Я никак не пойму, ты с чем споришь? Я где-то отрицал, что надо учитывать конкретные реализации структур данных?
·>По сабжу: мне кажется самым эффективным и универсальным будет std::vector<std::pair<char[MAX_KEY_SIZE], FormatterType>> отсортированный по pair.first и искать в нём используя binary_search (кстати, там имхо реализована оптимизация для малых размеров).
Универсальное решение всегда проигрывает в каком-то случае частному. Я думаю, до какого-то n (не знаю какого — надо бенчмаркать) ничего быстрее автомата не будет, потом возможно начнет рулить бинарный поиск, а затем хеш-таблица, дальше уже начнутся всякие фильтры Блума вместе со всякими экзотическими структурами.
