Как создать специфичиную структуру данных для хранения большого числа записей по беззнаковому 32 битному ключу?

Question

[pavelodintsov]

Нам нужна структура, которая позволит с максимальной скоростью и минимальными потерями памяти сохранить значение по целочисленному беззнаковому 32 битному ключу. Особенность ключа в том, что он лежит в интервале от нуля о 2^32, но строго не последовательно, а непрерывными 50-100 блоками (разыне подсети).

При этом, структура должна обеспечивать возможность работы в многопоточном режиме в конфигурации - один пишет, а другой читает, по возможности с минимальным использованием блокировок.

Требования к скорости ~ 1^-6c. для записи.

Пробовал std::map, std::unordered_map, boost::unordered_map, все хорошо, но медленно.

Update:

Самое эффективное, что придумал - создать вот такую структуру:
typedef vector subnet_counters

В ней будет хранить от 256 до нескольких миллионов записей про каждый IP в заданной сети. Размер сети должен быть выделен при инициализации структуры. В процессе работы никаких выделений памяти.

Потом поместить эту структуру ее в свою очередь уже в std::map, использовав имя сети как ключ, а по ключу будет лежать уже указанынй массив.

Итого, чтобы прочесть или записать данные нужно будет сделать только следующее:
1) Найти, к какой сети относится IP (сети НЕ пересекаются)
2) Найти по ключу адрес вектора хранящего данные все IP данной сети
3) Используя адресную часть IP адреса внутри сети статически получить смещение в векторе
4) Внести/прочесть значение

Answer 1

[throughtheether]

что он лежит в интервале от нуля о 2^32, но строго не последовательно, а непрерывными 50-100 блоками (разыне подсети).

Если это IPv4-адреса, и необходимо находить longest-match, то посмотрите в сторону patricia trie. Пример промышленного использования: PySubnetTree (модуль для python, написан на C). По поводу многопоточности не могу подсказать, к сожалению.

Comments

[pavelodintsov]

Patricia используется в проекте, но тут она не особо к месту. Нужно хранить набор метрик по каждому IP из очень крупной сети. То есть такой огромный массив счетчиков.

Answer 2

[vasiliev]

Насколько я понимаю, std:::map реализована через сбалансированные деревья; unordered_map - через хэш.
Согласно замечательной таблице имеем, что в случае std::map операции поиска/записи занимают O(log N) и в среднем, и в худшем случаях; во втором случае, они занимают O(1) в среднем и O(N) в худшем. То, как будет работать хэш, во многом зависит от качества хэш-функции. Мне кажется, вам надо посмотреть именно в сторону
Ещё один момент, связанный с хэшем - число "корзин". У меня в реализации unordered_map стоит 10 по умолчанию (задаётся в конструкторе), и эта реализация, похоже, перераспределяет корзины динамически при достижении определённого числа добавленных элементов. Вот здесь показано, что правильно инициализированный unordered_map должен так же быстро работать для вставки, как и для извлечения.

Comments

[pavelodintsov]

К сожалению, std::map, std::unordered_map и boost::unordered_map не подходят по причине, что std::map очень медленный, std::unordered_map решительно быстрее, но в текущей реализации С++ он нестабилен и постоянно сегфолтится (Debian Wheezy gcc 4.7). boost::unordered_map очень быстр (вдвое быстрее std::map и быстрее процентов на 20, чем std::unordered_map), но он потоконебезопасен - при активном изменении из другого потока (меняются только значения, текущие ключи не изменяются) нельзя читать даннные в отдельном потоке - это приводит к сегфолтам.

[vasiliev]

Значит, хэш-таблица в принципе подходит вам по скорости, но реализации из стандартной библиотеки и boost не подходят, поскольку они не являются потокобезопасными (по-моему, и в документации потокобезопасность не гарантируется). Дальше есть три варианта:
1) защищать функции доступа самому (что может привести к деградации произодительности)
2) искать thread-safe реализации
3) попробовать использовать lock-free реализации, например nbds. Здесь stackoverflow.com/questions/7086267/optimal-strate... ситуация похожа на вашу.

Answer 3

[Миша Кринкин]

Если есть возможность использовать Intel TBB, то там есть concurrent_unordered_map. Если нет возможности, то почему не реализовать unordered_map самостоятельно? В самом простом случае просто делаете shared_mutex на каждый карман, над перехешированием надо будет подумать, но с другой стороны, оно вам возможно и не понадобится, просто создайте достаточно большую таблицу с самого начала.