Страницы

Производительность ассоциативных массивов на Си и С++

   Я уже сравнивал производительность самодельного ООП на Си со встроенными в язык реализациями на C++  и Objective-C для одного конкретного случая. Настало время для сравнения рукописного ассоциативного массива на основе расстановочной(хэш) таблицы и реализации с помощью стандартной библиотеки шаблонов C++.


    В качестве опытного материала я выбрал набор ключевых слов языка программирования Си и набор слов из настоящей программы. Если слово является ключевым - нужно вернуть его номер, если нет - (-1). Список ключевых слов был взят из lex - грамматики, составленной по мотивам стандарта 2011 ISO C. Фильтр слов был составлен из фрагментов той же грамматики. Вот, кстати, весь его код:
%%
([a-zA-Z_])([a-zA-Z_0-9])* puts(yytext);
([\t\v\n\f])                           ;
.                                      ;
%%
    Как тестовый набор слов послужила сама тестовая программа, пропущенная через препроцессор и этот фильтр.
    Для всех вариантов ассоциативных массивов был создан единый интерфейс, позволивший протестировать их производительность одним и тем же кодом, что позволило мне сэкономить время, но лишила каждый из вариантов некоторых преимуществ.
    Для создания рукописного массива я воспользовался некогда прочитанным материалом из книги "Алгоритмы и структуры данных" Н. Вирта. Несмотря на то, что я никогда до этого не использовал и не реализовывал эту структуру, с ней не возникло затруднений и она заработала сразу после успешной компиляции, чему способствовала изрядная простота алгоритма. Наличие одной ошибки в расстановочной(хэш) функции лишь замедляло поиск в массиве, но на корректность не влияло.
    С шаблонным решением на C++ оказалось сложнее. Я  воспользовался помощью человека, смыслящего в этом языке значительно больше меня. Он написал два варианта: один для С++98, другой - более быстрый, для С++11.
typedef std::map<const char *, int> Array;
typedef std::unordered_map<const char *, int> Array;
    Первые результаты тестирования вызывали восхищение демонстрируемой ими производительностью, недостижимой для наколенного варианта. Но заподозрив неладное, я заменил предопределенный массив слов, на загружаемый из файла. С++ реализации перестали работать корректно - они индексировали не по содержимому строк, а по указателям. Для восстановления исправности я искал решение уже самостоятельно. В итоге общее время, потраченное на стандартную библиотеку, у меня превысило время создания "велосипедного" решения.

    Результаты для двух реализаций на C++, поделенные на результаты для C, представлены в таблице.
Реализацияmapunordered
Время2,651,39
Размер всех исходников0,810,90
Размер исходников массива0,520,75
Размер всех объектников2,442,04
Размер объектников массива4,13,14

    Тестовый набор пригоден для сборки на UNIX - подобных операционных системах. Я проверял работоспособность на Ubuntu GNU/Linux 10.04 и Mac OS X 10.6.8. Численные данные получены на GNU, компилятор - gcc 4.4.

Обновление: 2-е тестовое окружение. GNU/Linux Ubuntu 17.04, gcc 6.3.0, -O3 -flto
Реализацияmapunordered
Время2,191,87
Размер всех объектников11

2-е обновление: по наводке пользователя habrahabr 0xd34df00d добавил резервирование массива для unordered map, заодно протестировав сборку с помощью clang 4.0.0.
Реализация gcc g++ mapg++ unorderedclangclang++ mapclang++ unordered
Время 1,222,76 1,32 1 2,82 1,36
Размер объектников1,631,63 1,65 1 1,66 1,68


Для ARM расклад другой, местами противоположный, но оформлять эти результаты мне пока лень.

2 комментария:

  1. Djn bВот и верь после этого, что велосипед -- это плохо.
    Кастомные решения всегда компактней и шустрей.

    ОтветитьУдалить
    Ответы
    1. Справедливости ради надо сказать, что при определённых настройках версия на С++ unordered map будет такой же быстрой или почти такой же в зависимости от компилятора и целевой платформы. Правда, для этого потребуется знать всё то же, что нужно знать для создания "велосипеда" и, вдобавок, библиотеку С++.

      Удалить