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

   Я уже сравнивал производительность самодельного ООП на Си со встроенными в язык реализациями на 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, представлены в таблице.

Реализация	map	unordered
Время	2,65	1,39
Размер всех исходников	0,81	0,90
Размер исходников массива	0,52	0,75
Размер всех объектников	2,44	2,04
Размер объектников массива	4,1	3,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

Реализация	map	unordered
Время	2,19	1,87
Размер всех объектников	1	1

2-е обновление: по наводке пользователя habrahabr 0xd34df00d добавил резервирование массива для unordered map, заодно протестировав сборку с помощью clang 4.0.0.

Реализация	gcc	g++ map	g++ unordered	clang	clang++ map	clang++ unordered
Время	1,22	2,76	1,32	1	2,82	1,36
Размер объектников	1,63	1,63	1,65	1	1,66	1,68

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