Карта и набор, который использует непрерывную память и имеет резервную функцию

Я использую несколько карт и множеств. Недостаток смежной памяти и большое количество (де) распределений являются узким местом производительности. Мне нужна, в основном, карта, совместимая с STL, и заданный класс, который может использовать непрерывный блок памяти для внутренних объектов (или нескольких блоков). Он также должен иметь функцию reserve, чтобы я мог предварительно распределить ожидаемые размеры.

Прежде чем написать свой собственный, я хотел бы проверить, что доступно в первую очередь. Есть ли что-то в Boost, которое это делает? Кто-нибудь знает о доступных реализациях в другом месте?

Интрузивные типы сбора не могут использоваться здесь, поскольку одни и те же объекты должны существовать в нескольких коллекциях. Насколько я знаю, пулы памяти STL относятся к одному типу, а не к экземпляру (вроде, не к чему, многие оговорки). Эти глобальные пулы неэффективны в отношении местоположения памяти в обработке mutli-cpu/core.

Пулы объектов не работают, поскольку типы будут совместно использоваться экземпляром, но их пул не должен.

Во многих случаях хеш-карта может быть опцией.

Ответ 1

Посмотрите на это: Google Редкая хэш-карта. Это была моя любимая библиотека С++, так как я наткнулся на нее несколько лет назад.

Его производительность невероятна, имеет как карту, так и заданный класс, и имеет запрошенные резервные функции. Я переключил бесчисленные проекты из различных других картографических структур данных в google sparsehash с невероятными результатами. Синтаксис совместим с С++ 0x unordered_map (ужасное, страшное имя!), Но имеет дополнительные функции и функции.

Внутри он реализуется с помощью хэш-таблицы с использованием техники sparsehashing.

EDIT (13 мая 2015 г.)

Поскольку это стало популярным ответом, я просто хотел указать на две другие структуры, подобные карте, которые я использовал в последние годы. M различный C контейнер T эмблемы (MCT) обеспечивает совместимые с высокой пропускной способностью версии unorderd_map в нескольких вариантах:

Он предоставляет шесть универсальных контейнеров хэш-таблиц - closed_hash_set, closed_hash_map, linked_hash_set, linked_hash_map, forward_hash_set и forward_hash_map. Первые два очень похожи на TR1 unordered_set и unordered_map. Связанные дополнительные функциональные возможности, тогда как передовые хеш-таблицы более эффективны чем связаны, но имеют ограниченный интерфейс. В некоторых случаях производительность контейнеров closed_hash_ * можно еще больше улучшить опциональная поддержка навязчивости.

И folly на facebook есть несколько действительно отличных структур. Они не имеют замену на unordered_map per se, но там безопасная/потокобезопасная реализация unordered_map и создание вещей вокруг fbvector может привести к огромному увеличению производительности за счет лучшего использования памяти и макета.

В моем тестировании для однопоточного кода Google dense_hash_map по-прежнему остается моим предпочтительным вариантом максимальной производительности.

Ответ 2

В недавнем post в списке рассылки Boost обсуждалось нечто похожее на это.

Говард Хиннант создал распределитель, который может использовать стек вместо кучи.

http://howardhinnant.github.io/stack_alloc.html

Ответ 3

Boost.Interprocess и Boost.Container предоставляют плоский набор и плоскую карту, которые могут помочь вам улучшить производительность вашего приложения.

См. https://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/boost_container_reference.html#header.boost.container.flat_set_hpp

Ответ 4

Вы можете просто использовать векторный и двоичный поиск для непрерывного хранения и резервирования(), а также поддерживать O (logn). Однако вставка будет дороже.

Ответ 5

Возможно, вы захотите взглянуть на Google TCMalloc. Это замена для malloc, которая может ускорить вашу программу. TCMalloc специально разработан для нескольких потоков.