История использования структур была такой:
- std::map
- Так как предыдущий тормозил, решено было взять: unordered_map С++ 11
- Но std::unordered_map сегфолтился на пустом месте и был не особо стабилен: http://www.stableit.ru/2013/11/unorderedmap-c11-debian-wheezy.html
- Мы вернулись на std::map
- Но он тормозил и мы решили попробовать boost::unordered_map, он был быстр:
http://tinodidriksen.com/2009/07/09/cpp-map-speeds/
standard map: 41% cpu in top boost::unordered_map: 25% cpu in top
Но он постоянно сегфолтился и оказывается не был совершенно thread safe: http://boost.2283326.n4.nabble.com/boost-unordered-map-thread-safety-td2585435.html http://meetingcpp.com/tl_files/2013/talks/Containers%20in%20Boost%20-%20Boris%20Schaeling.pdf
Стоит обратить внимание, что сегфолтился он как раз в итераторе, который читал данные, но писал их лишь из под mutex
- Мы по-прежнему на std::map
Что нам нужно?
Нам нужна структура, которая позволит с максимальной скоростью и минимальными потерями памяти сохранить значение по целочисленному беззнаковому 32 битному ключу. Особенность ключа в том, что он лежит в интервале от нуля о 2^32, но строго не последовательно, а непрерывными 50-100 блоками (разыне подсети).
При этом, структура должна обеспечивать возможность работы в многопоточном режиме в конфигурации - один пишет, а другой читает, по возможности с минимальным использованием блокировок.
Требования к скорости ~ 1^-6 для записи.