QMap vs. QHash: небольшой бенчмарк

Во время работы над своей презентацией для Qt developer days 2012 (QtCore in depth), я произвёл сравнение производительности QMap и QHash и подумал, что неплохо было бы поделиться результатами в этой короткой статье.

Под капотом

Контейнеры Qt 4 были хорошо разобраны в этой старой статье (или в этой — на хабрахабре).
В Qt 4 QHash реализован с использованием Хеш-таблицы, а QMap — с использованием Списка с пропусками. В Qt 5 реализация контейнеров немного изменилась, но принципы остались теми же.
Главные отличия:

• QVector, QString и QByteArray теперь реализованы одинаково (QArrayData). Здесь основным отличием стало смещение (offset), которое может позволить в будущем ссылаться на внешние данные.
• Устройство QMap изменилось полностью: теперь это не Список с пропусками, а Красно-чёрное дерево.

Бенчмарк

Тест довольно простой: в цикле много раз выполняется поиск по контейнеру и считается количество совершённых итераций за одну секунду. Это не совсем научно. Цель состоит только в том, чтобы показать форму кривых.
Исходный код: pastebin.com/Ya6D4QUm

Результат

Тестирование проводилось на моём компьтере, GCC 4.7. Чем значение итераций выше, тем лучше. Шкала количества элементов — логарифмическая. Следует ожидать, что для QHash величина не будет изменяться с ростом числа элементов, а для QMap она должна быть равной O(log N), что соответствует прямой линии на логарифмической шкале.

Qt 4.8

QMap работает немного медленее, чем std::map. Поиск по QMap выполняется быстрее, чем по QHash при количестве элементов меньше 10.

Qt 5

Это была хорошая идея — заменить список с пропусками красно-чёрными деревьями. Производительность контейнеров Qt теперь почти такая же, как у контейнеров STL. Поиск по QMap выполняется быстрее, чем по QHash при количестве элементов меньше 20.
Если вы сравните показатели Qt 4 и Qt 5 то увидите, что производительность Qt 5 выше. Это может быть связано с изменениями в QString.

Заключение

Используйте QMap только в случае, если вам нужно отсортированное содержимое или вы знаете, что в вашем словаре всегда содержится небольшое количество элементов.