Привет всем.
Решил сравнить по скорости std::map и boost::unordered_map.
Почему-то думал, что для такого map< int, int > stl должен быть быстрее, т.к. он ведёт поиск в отсортированном дереве (или сбалансированном), а boost::unordered_map - в обычном, и хэш по int должен быть сам int, но оказалось всё с точностью до наоборот (unordered_map прилично быстрее). Объясните, пожалуйста, почему. 

вот код:

http://liveworkspace.org/code/b5b3d5f77cb5...09535c8e83dc5d8

Вот вывод:


stl - из состава minGW 4.4.0 (который в свою очередь из состава QtSDK)
boost - с офф.сайта. версия 1.47.0 

P.S. Может ещё кто подскажет, почему поиск функцией find быстрее поиска оператором []...

Спасибо.

borisbn, дополни свой тест еще std::unordered_map, плиз.

boostcoder,


Всё никак руки не доходят скачать твой minGW (с поддержкой 0x11) и прикрутить его к QtCreator'у.
Кста, может кто-нибудь это делал ?
Тогда подскажите как.

Tools -> Options -> Qt4
Tools -> Options -> Tool Chains

Это сообщение отредактировал(а) Alca - 10.11.2011, 17:00

Alca, там указывается, где расположен qmake, а не minGW

borisbn, если я ничего не путаю, то в 4.4.0 уже есть std::unordered*

Добавлено через 4 минуты

Итак.
1. Сделал std::unordered_map в minGW 4.4.0
Вот код
http://liveworkspace.org/code/bc7579812ea4...a364184425dcffd
Вот рез-ты (на моей машине)


2. Судя по всему что std::, что boost:: unordered_map ведут себя одинакого
3. Мне всё равно непонятно, почему unordered быстрее "ordered"
4. А что с вопросом про operator[] vs unordered_map::find() ?
5. 2 boostcoder: что отсюда (http://code.google.com/p/mingw-builds/downloads/list) из этого списка

мне поставить, чтобы: 1) была стабильная версия 2) чтобы был только Си++ (мне не нужен ни objC, ни fortran). Спасибо.

описание для кого писал?  

без фортрана и обжектив-си сборок нет. чтоб не плодить процесс сборки и архивы.

так что рекомендую эту:
4.6.2-release-c,c++,objc,objc++,fortran-dwarf
zip - http://mingw-builds.googlecode.com/files/m...rtran-dwarf.zip
7z - http://mingw-builds.googlecode.com/files/m...ortran-dwarf.7z

Тестировался оптимизированный код?

boostcoder, премного благодарен. Скачаю, установлю, настрою - отпишусь.
А если, всё-таки, "вернуться к нашим баранам"... Что по теме ?
Почему unordered быстрее ordered ?


Честно говоря, просто выбрал тип сборки Release...
Сейчас посмотрел сгенерённый qmake'ом Makefile.Release:

больше ничего относящегося к компилятору не нашёл. Нужно будет - могу весь Makefile выложить

тут неплохо описывается: http://lanzkron.wordpress.com/2010/06/02/o...tz-for-klutzes/

Добавлено через 14 минут и 27 секунд
borisbn, так ты допишешь в тест std::unordered_map?

скачал, установил, настроил - работает   
правда долго тупил, что дать креатору в качестве компилятора - c++.exe, g++.exe, gcc.exe, i686-pc-mingw32-c++.exe, i686-pc-mingw32-g++.exe, i686-pc-mingw32-gcc-4.6.2.exe или i686-pc-mingw32-gcc.exe...
в общем остановился на g++.


Да. интересно. Так что, получается в unordered_map используется не дерево, а тупо массив, а мой ключ переводится в обычный индекс...
хммм. интересно...

угу.


я этого тоже не понял. мне кажется это не верный вывод. наверняка автор что-то напутал... но разобраться в исходниках std::unordered_map ой как не просто.


как-то я не заметил 

Добавлено через 1 минуту и 18 секунд

а с 4.6.2 результаты такие же? а то со времен 4.4.0 многое изменилось.

Добавлено через 2 минуты и 44 секунды
мои результаты:

стандартный умап однозначно рвет всех. это не может не радовать 

вот на 4.6.2


относительно 4.4.0 поменялось только время получения элемента оператором [] - оно теперь равно find'овскому ( что также не может не радовать  ). Так что вопрос по оператору [] снимается

А ещё не может не радовать, что теперь exe-шник не требует minGW-шных и libc-шных dll-ек


я попытался и бросил - unordered_map наследуется от Hashtable, который, в свою очередь наследуется от Rehash_base, Hash_code_base, Map_base и Equality_base... бррррррр.

я в своих сборках использую CRT проекта wingw-w64, что в свою очередь делает библиотеки собранные стандартным MinGW, несовместимыми с моей сборкой. так, к примеру, моей сборкой не получится слинковать QtSDK. Qt нужно пересобирать.
но я такой путь выбрал не зря. во первых - mingw.org предоставляет CRT только для 32-ух битных компиляторов. во вторых - проект очень слабо развивается, и, как признаются сами авторы, не имеет смысла на продолжение. он не будет переписан для 64-ех битных компиляторов.

по поводу же пересборки всего, что предполагается юзать с моей сборкой MinGW - я работаю над проектом, который будет включать в себя кучу предкомпилированных либ, которые можно будет установить и обновлять используя онлайн-инсталлятор.

Добавлено через 2 минуты и 22 секунды
ах да. об этом я уже писал тут  
http://forum.vingrad.ru/index.php?showtopi...t&p=2403408

Добавлено через 11 минут и 46 секунд

если же использовать sjlj сборку - то слинкуется. но будет падать по сегфолту.

Пообщался на ИРКе на эту тему - стало яснее. Приведу выдержки

это чё?

http://ru.wikipedia.org/wiki/IRC - онлайн чат (древний как понятно что мамонта, но всё ещё актуальный).
Существует несколько серверов, предоставляющих IRC-чат. Самый крупный - freenode.net.
На каждом сервере есть н-ное количество тематических каналов. На freenode - ~30000 каналов.
Я там зависаю на #c++ (~1500 участников), #qt (~1000) и #boost (~800).
Клиенты - Веб-клиент из браузера ( http://webchat.freenode.net/ ), Miranda, mIRC, QIP Infium + плагин для протокола IRC.
Я пользую последний. Не самый удобный, но так я получаю 3 в 1 (jabber, twitter, IRC).

borisbn, очень познавательно  
но дело в том, что я, около полугода назад, перестал пользоваться всеми мессенджерами. слишком много времени уходит на треп.

borisbn, интересный тест, спасибо.

Безусловно, буст работает шустро, особенно на коротких значениях ключа, типа инт.
Тест на студии вашего кода, полностью подтвердил ваши данные, (с поправкой того что мой комп, в ~1.5 раза медленее вашего ).
Но относительные занчения были прмерно такие-же.
Студийный стл::мап, надежно проигрывал, против буст-анордеред.
Студийный stdext::hash_map оказался не на много лучше.

И меня заинтересовало, насколько буст будет хорош, на длинных значениях.
В качестве ключей использовал std::string с разной длиной. 4, 30 и 300.
При длине 4, результаты полностью совпали с вашими.

При длине ключа 30:
hash_map, уже догнал, и даже немного перегнал boost


При длине ключа 300:
boost отстает не только от hash_map, но даже и от std::map



Код, на котором я тестировал. (На 95% процентов, код скопиапщен у borisbn)


-----------

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

Но на длинных, возможно стоит выбрать что-то другое...

volatile, очень интересно... Как раз следующим этапом я собирался сделать ключ из строки...
А вот результат Вашего нашего кода (со строкой), скомпилированного minGW 4.6.2 (вместо stdext::hash_map взят std::unordered_map)



Вывод: и компилятор тоже 

P.S. Недавно возился со студийным hash'ем... У меня получилось, что он игнорирует последний символ в строке, т.е.
hash( "abcdefg0" ) == hash( "abcdefg1" )... м.б. это так и надо, а м.б. это глюк...

Добавлено через 2 минуты и 37 секунд
я так понял, что делить на [] и find теперь уже не нужно - это был глюк minGW 4.4.0

Не совсем понял, как это игнорирует?
   hash_m ["abcdefg0"] = 1;
   hash_m ["abcdefg1"] = 2;
   hash_m ["abcdefg2"] = 3;
   std::cout << hash_m.size () << std::endl;
Вывод 3, т.е разные хеши.

Конкретно сами числа хешей тоже можно посмотреть, приватный метод _Hashval. Там для данных строк хеши разные (2,3,0) соответственно.


Да, там безусловно буст рулит. (Или стд не рулит?... )

не... я смотрел непосредственно ф-цию std::tr1::hash. для приведённых Вами строк она выдаст одно и то же значение. потом, конечно, map это всё разрулит

Щас, поставил брекпоинты, и посмотрел в дебагере значения хешей.
Для приведенных строк, значения подсчитываются в следеющей процедуре (файл <xhash>)

Брякпоинты ставил на выходе функции.
Конкретно значения хешей, для приведенных строк: 
_Val = 3802362189
_Val = 3802362188
_Val = 3802362191

FNV-1x

в GCC этот алгоритм используется только для строковых типов.

Добавлено @ 00:42
тут специализации: http://gcc.gnu.org/git/?p=gcc.git;a=blob;f...ab4ba92;hb=HEAD
тут реализация мур-мур хеш и FNV-1: http://gcc.gnu.org/git/?p=gcc.git;a=blob;f...217bf36;hb=HEAD


Это сообщение отредактировал(а) boostcoder - 12.11.2011, 00:42

boostcoder, ну здесь для разных типов тоже разные хеши. В данном случае здесь именно строки. Видимо мелкомягкие (стл правда писали не они), сперли алгоритм у линуксоидов. ...