Comments 38
HT понятно, что макрос из-за параметров для типов, а другие функции без key_type и value_type почему макросы, чтобы усложнить себе жизнь в отладчике?
пока в C нету оператора аналогичного
typeofиз C++
Это точно про C++? Там нет такого оператора. Есть ключевые слова auto и decltype.
Также интересным наблюдением является то, что компилятор от Microsoft ощутимо хуже оптимизирует C++ код
Где бенчмарки или хотя бы намёки на используемые ключи компиляции?
В статье есть бенчмарк. Для всех компиляторов используются дефолтные ключи CMake для релизной сборки.
Можно заметить, что С код по производительности равен такому же коду собранному GCC и Clang, а один и тот же код на C++ собранный этими же компиляторами выполняется ощутимо быстрее, чем код от MSVC.
Справедливости ради, MSVC зато быстрее собирает C++ проект :-)
В статье нет бенчмарка, есть только таблица. А что там и как измерялось, не показано.
В статье указано, что измеряется время исполнения алгоритма генерации икосферы через 4 подразделения меша. Сам алгоритм можно посмотреть в любой из трех реализаций, какой язык вам больше нравится. Он одинаков. Детально разбирать алгоритм генерации икосферы выходит за рамки данной публикации, могу вам лишь сказать, что бенчмарк помещает около 2500 пар ключ-значение в хештаблицу (и все их запрашивает). Ключ - композитный из двух целых чисел, значение - одно целое число. Добавил эту информацию в статью.
Мне кажется такой бенчмарк примером реального применения хештаблицы и более объективным, чем, например, заполнение случайными данными. К тому же алгоритм одинаков для всех языков и библиотек, так что все находятся в равных условиях.
Алгоритм генерации исходно взят из первых результатов (они разные по используемым языкам, но одинаковые по самому алгоритму и используемым структурам данных) по запросу в Гугле "icosphere generation algorithm": первый (JavaScript), второй (C++), третий (C#).
Алгоритм запускается 10 тысяч раз, при этом измеряется суммарное время исполнения и делится на количество повторений. Между повторениями все структуры данных уничтожаются и создаются заново. При этом сам алгоритм оптимизирован (используется reserve для избегания перехеширования во всех реализациях).
Все функции принимают в качестве аргумента структуру неизвестного типа. Некоторым функциям также нужен компаратор и хеш-функция. Разумеется, можно сохранить указатели на функции в структуре, но это два косвенных вызова в горячем коде... Скорее всего у хеш-таблицы была бы ощутимо хуже производительность (особенно при использовании в программе нескольких хештаблиц с разными хешфункциями, чтобы компилятору было сложно делать девиртуализацию). Усложение отладки это цена C за обобщенное программирование без потери производительности. Впрочем, в идеале пользователю и не нужно отлаживать хеш-таблицу, это библиотечный код. Головная боль в первую очередь для меня.
Кстати, в популярном uthash тоже всё на макросах.
Да, я перепутал, речь про аналоги auto/decltype, которых нет в С (в GCC есть __auto_type, но прощай совместимость с MSVC).
Не все. Навскидку, ht_init, ht_destroy, ht_clear могут обойтись без макросов. Причём последняя - багнутая, если бы не макрос, то даже не скомпилировалась бы.
Какой баг вы нашли в ht_clear? Там максимально простая логика с обнулением счётчика элементов, а затем с обнулением собственно таблицы флагов. И отлаживать то нечего. Кстати, она вызывается в одном из тестов в библиотеке и отрабатывает без ошибок. Если вы нашли какой-то граничный случай, укажите его, пожалуйста.
Вообще, именно эти три функции очень маленькие и я не вижу каких-либо минусов от их принудительного инлайнинга. Вот ht_reserve, ht_get и ht_put хотелось бы не инлайнить (и там есть что поотлаживать), потому что они большие, но им как раз больше всего нужно из параметров.
В любом случае и указанные вами три функции принимают на вход структуру неизвестного типа так как макрос HT генерирует уникальный с точки зрения компилятора тип для каждого набора типов ключей и значений. Мы знаем какие поля в ней должны быть, но для компилятора это разные типы. Вы же не предлагаете принимать void* и приводить к структуре с совместимым layout?
Точно так же мне не нравится идея сделать универсальный тип хештаблицы с void указателями на ключи и значения, потому что это потребует передавать типы в макросы ht_key и ht_value, а они вызываются гораздо чаще функций создания и уничтожения хеш-таблицы целиком.
Я не знаю, что не так с ht_clear, что она бы не скомпилировалась, но вызов memset(NULL, 0, 0) — это как минимум unspecified behaviour, которое в некоторых реализациях UB. Или UB уже по стандарту: на SO есть разбор ситуации.
Т.е. её нельзя использовать на пустых таблицах.
А с uthash сравнивали? Есть какие-то плюсы/минусы?
То есть, чтобы сделать например мапу на миллион пар int->int, «в лоб» нужно делать миллион malloc-ов под ключ/значение, либо решать проблему оптимального хранения пар своими силами.
Для решения из этой статьи просто миллион раз вызываешь ht_put(int,int) и таблица сама думает, как это оптимально положить в память.
uthash отдельно аллоцирует память на каждый элемент (точно так же, кстати, как и std::unordered_map). Аллокация это медленно (и не cache friendly). А ещё у него к каждому элементу добавляется служебная структура на несколько десятков байт (для сравнения - в моей хештаблице оверхед 1 байт на элемент, а при желании можно свести к 0.25 байта на элемент).
То есть по скорости и потреблению памяти uthash точно уступает моей реализации (в бенчмарке я сравнивал с другими хеш-таблицами с открытой адресацией, потому что хештаблицы на цепочках элементов гарантированно медленнее, особенно на маленьких ключах).
Теперь к плюсам uthash. Он даёт стабильность указателей на элементы (вы можете свободно сохранять указатели на элементы и они будут жить до самого удаления элемента). Иногда это важно. В целом в моей реализации ничто не мешает при объявлении таблицы указать в качестве типов указатели вместо значений и написать соответствующие хешфункции и компаратор, но это лишние телодвижения.
А ещё у uthash функции работы не требуют указания типов элементов, а мне они нужны. Это уже деталь реализации (uthash хранит в каждом элементе размер его ключа, а аллокацию памяти под элемент выполняет пользователь), но, кстати, тоже влияющая на производительность.
Короче, если нет особых требований к производительности или потреблению памяти, то uthash лучше из-за более простого API.
Если нужна высокая производительность или низкое потребление памяти (например, в embedded, кстати, все мои функции имеют обработку нехватки памяти и переполнения size_t, что опять же актуально именно для embedded), то лучше моя хеш-таблица.
аллоцирует память на каждый элемент (точно так же, кстати, как и std::unordered_map)Сомневаюсь. Это в какой реализации STL такое?
Да в любой. Если вы почитаете документацию на unordered_map, то увидите, что он предоставляет гарантию, что ссылки на элементы не инвалидируются при вставке/удалении других элементов. Этого можно добиться только выделяя отдельно память под каждый элемент.
Посмотрев разные реализации в популярных библиотеках, я увидел, что часто используют не открытую адресацию (когда в случае коллизии пишем в следующую ячейку), а отдельную память для цепочки коллизий.
Динамически выделять память я категорически не хотел.
В итоге, у меня сложился такой велосипед:
— выделяем память под ключи и значения, но не в размере capacity, а в размере capacity*1.5, чтобы во второй половинке хранить данные при возникновении коллизий.
— выделяем вспомогательную память (аналог вашего flags), назовём её index, но с типом не char, а unsigned. Старший бит — BUSY «ячейка занята», младшие 31 бит — ссылка на следующую ячейку в цепочке.
— вторую половину размером capacity/2 в таблице index организуем в односвязный список, оттуда будем брать ячейки для коллизий, и возвращать их обратно в голову связного списка при освобождении ключа.
метод get:
вычислям i = hash(key) % capacity;
L: если index[i] & BUSY == 0, в хеше ключа нет, выход.
если key==keys[i], ключ найден, выход
i = (index[i] & ~BUSY),
если i=0, это признак конца списка, выход.
иначе переходим к метке L
вставку, удаление, несложно додумать.
А теперь внимание вопрос, зачем это писать на С, если существует С++
Если char == signed char, то куда будет обращение counts[-15] ?
Ну и сравнивая с стандартной С++ мапой вы не приводите кода, к тому же С++ мапа обладает совершенно другими гарантиями и она не flat
Спасибо за замечание, исправил код. В целом этот пример просто демонстрирует идею, что можно использовать ключ как индекс в массиве, в дальнейшем коде вроде всё нормально.
Производительность я сравниваю с аналогичными реализациями с аналогичными гарантиями - Abseil flat_hash_map и AHashMap (фактически стандартная HashMap, просто с более быстрым хешером) из Rust. Иначе, действительно, сравнение было бы нечестным.
unordered_map из STL действительно даёт больше гарантий - а именно, стабильность ссылок на элементы при вставке новых элементов. Однако, это происходит ценой ощутимого уменьшения производительности (я не приведу конкретных чисел, но тест с генериацией икосферы отрабатывал за 200-300 мкс на итерацию до того как я применил absl::flat_hash_map). К тому же, при желании и в "плоской" хештаблице можно получить стабильность ссылок используя указатели в качестве типов ключей и значений и выделяя под них память самостоятельно (впрочем, это норма для C, библиотека uthash построенная на другом принципе тоже требует от пользователя ручной аллокации-деаллокации добавляемых и удаляемых элементов, а лишь структурирует их внутри себя).
Также, unordered_map (как и HashMap из Java) по-разному реагирует на коллизии (иными словами, худший набор ключей приводящий к O(N) сложности будет различаться для "плоской" и "списочной" хештаблицы).
Реализация на C просто из интереса, ну и чтобы заодно продемонстрировать обобщённое программирование на макросах. Забавно, что она получилась быстрее всех остальных реализаций.
Возможно, я мог бы написать статью с более детальным разбором отличий разных хештаблиц, в данной статье я ставил основной целью описать устройство именно "плоских" хештаблиц, а устройство других ассоициативных контейнеров было приведено в первую очередь для бекграунда и лучшего понимания какие дизайнерские решения были приняты при разработке конкретного контейнера.
Каким образом MinGW оказался в два раза быстрее MSVC и в полтора раза быстрее clang?
Вообще, сначала я тоже был удивлён и подумал, что случайно собрал бинарник с помощью MSVC в 32-битном режиме и даже проверил PE-заголовки, но нет - все 3 EXE сгенерированные всеми 3 компиляторами были 64-битными.
Я думаю, что корень всей проблемы в MSVC. Тесты производились на Windows, соответственно, clang использовал STL из поставки MSVC, а MinGW свою собственную STL.
С учётом того, что все три компилятора компилировали один и тот же C++ исходник, то у меня есть гипотеза, что MSVC хуже оптимизирует C++ код, чем GCC и Clang, а также имеет менее оптимизированную стандартную библиотеку. Как следствие, самую большую просадку к производительности получает сам MSVC (так как он и мой код компилирует, и использует свою стандартную библиотеку). Clang оказывается на втором месте (потому что генерирует оптимальный код сам, но использует стандартную библиотеку от MSVC). А GCC побеждает, потому что он и код хорошо генерирует, и имеет более оптимизированную стандартную библиотеку (отмечу, что более высокая производительность некоторых стандартных классов/функций не единственный показатель качества библиотеки - в пользу MSVC можно, например, указать, что он поддерживает некоторые фичи из свежих стандартов C++, которые пока не завезли в GCC, хотя и наоборот точно были и наверняка до сих пор есть примеры).
О том что Clang способен генерировать производительный код говорит тот факт, что Rust (который тоже использует LLVM, но при этом не зависит от библиотеки STL из MSVC) показывает примерно такую же производительность как и GCC (но, конечно, это не очень корректное сравнение, потому что это разные языки программирования).
Есть вторая гипотеза, что конкретно Abseil flat_hash_map может быть лучше оптимизирован под GCC/Clang, однако раньше, когда в коде был std::unordered_map, MSVC тоже проигрывал GCC/Clang, но я не приведу конкретные числа.
А вот код на C не зависит в своей производительности от стандартной библиотеки (кроме аллокатора памяти, но я думаю, что он во всех тестах используется из MSVCRT.DLL), да и оптимизировать C код, похоже, легче чем C++, в итоге все компиляторы справляются на одинаковом уровне.
Если что у меня GCC из MSYS2 и имеет версию 11.3.0. То есть это относительно свежий GCC. Clang имеет версию 15.0.2. Компилятор MSVC из комплекта Visual Studio Community 2022 17.2.3.
к тому же С++ мапа обладает совершенно другими гарантиямиПолучается, в C++ STL нет эффективной мапы для случая, когда не требуется гарантии сохранения адресов хранимых объектов. То есть, если мне нужна большая мапа int->int или int->(MyObject*), то std::unordered_map не самое эффективное решение.
Для того, чтобы обобщённый C нормально работал с отладчиком можно заменить макросы на параметризованные макросами #include. Пример: typval_encode.c.h, использование.
Плюсы такой техники:
- лучше работает с отладчиком и анализаторами кода;
- можно иметь намного больше параметров, не сходя с ума;
- можно иметь параметры по‐умолчанию.
Минусы:
- инстанцирование всегда растягивается на несколько строчек;
- с помощью этой техники можно определить функции, переменные, типы, числовые константы (через enum), но нельзя макросы;
- параметры для такого файла загрязняют пространство имён макросов, и при повторном инстанцировании в рамках одной единицы трансляции их приходится очищать;
- продемонстрированный пример не определяет символов, которые бы использовались в иных единицах трансляции, если это требуется, то работать с
.c.hфайлами становится ещё менее удобно (но всё ещё не невозможно).
Есть подозрение, что компиляторы выкидывают цикл, в котором происходит вызов функции testIcoSphere (строки 179-182). Это объясняет разницу времени исполнения между MSVC и остальными компиляторами (см. код функции getTimestamp).
А зачем использовать do { ... } while(0)? Разве нельзя просто обернуть в фигурные скобки? Это какой-то негласный стандарт или просто исторически сложилось?
Чтобы после вызова "функции" требовалось ставить точку с запятой, для однородного использования с настоящими функциями.
Спасибо, отличный трюк. Сам хотел как-то сделать подобный хеш-мап, но на плюсах и с использованием виртуальной памяти. Не подскажете какие могут быть подводные камни при ее использовании?
Что вы имеете ввиду под использованием виртуальной памяти? Работа с отображением файла в ОЗУ? Просто прямая работа с API аллокации памяти ОС в обход стандартной библиотеки?
Возможно я не правильно исползовал термин. Я имел ввиду использование памяти, которая вроде уже выделена для нашей программы, но физически она нигде не занимает место (ни в ram, ни в swap, ни на диске), до момента обращения к ней. Подозревал что подобный функционал реализован на железном уровне, но для его использования необходимы специальные вызовы. Ещё не копал в эту сторону, поэтому буду благодарен за какую-нибудь ссылку.
Изм: Быстрым гуглением ничего не нашел. Похоже придется реализовывать подобное на уровне программы.
Изм 2: нашел - называется overcommit, и похоже есть только на Линукс. Работает через обычный malloc, требуется настройка ядра. Вот и подводный камень.
в любой современной ОС с поддержкой виртуальной памяти выделение блока памяти для процесса резервирует регион виртуальных адресов без аллокации под него физических страниц памяти
Эта штука называется "memory overcommitment" и реализуется в ОС. Причём её статус странный — она больше похожа на баг чем на фичу, но починить-отключить нельзя, иначе некоторые жадные до памяти программы сломаются.
Чтобы её "использовать", достаточно получить память напрямую у ОС.
Нашел статью у себя в закладках, может кому-то пригодится: https://habr.com/p/537568
... квадратичный поиск (quadratic probing). Идея в том, что мы после первого обнаруженного занятого места, смотрим в следующее. Если и оно занято, то смотрим не в следующее, а через одно. Если и там занято, то через два и т. д.
Не понимаю, в чём "квадратичность" такого поиска? Если перейти по ссылке, там будет пример скорее, как через 1, через 4, через 9 и т.д. Похожую схему Вы использовали при вычислении ближайшего размера, кратного степени двойки. Но вот поиск мне не показался таковым.
.Описанное возможно при 
. Тогда как раз получается 
. Что эквивалентно 
Пишем обобщённую хеш-таблицу с открытой адресацией на чистом C