Во время работы над своей презентацией для 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 только в случае, если вам нужно отсортированное содержимое или вы знаете, что в вашем словаре всегда содержится небольшое количество элементов.
Автор: epicfailguy93
