Привет всем.
Решил сравнить по скорости 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 сборку - то слинкуется. но будет падать по сегфолту.