Какая структура самая быстрая для поиска по числовым ключам без хэширования?

Question

[Eugene Usachev]

Я хочу переиспользовать память объектов разного размера (неизвестного на этапе разработки, только на этапе компиляции). Мне нужно создать структуру, которая держит ключ - размер, значение - вектор указателей. Проблема только с самой структурой (примитивы синхронизации не нужны).

Я попробовал взять HashMap из std. Производительность удручающая - я теряю больше, чем выигрываю, на объектах до 8 КБ.

Тогда я подумал, что теряю много на хэш функции. Мне она не нужна, так как в этом случае я не нуждаюсь в защите от DoS attack. Я написал свой Hasher и BuildHasher, который не хэширует ключи. Это дало некоторый выигрыш, но особо лучше не стало.

Я думаю, что ошибка именно в выборе структуры. Какую структуру лучше использовать в этом случае?

Comments

[mayton2019]

У тебя 8 килобайтные ключи??

[Василий Банников]

mayton2019, думаю, имеется в виду хешмапа на 8кб. В вопросе же говорится, что в качестве ключей - числа

[Василий Банников]

А какое распределение у ключей?
Я бы ещё в бенчмарки BTreeMap добавил без хеширования

[Василий Банников]

Я хочу переиспользовать память объектов разного размера (неизвестного на этапе разработки, только на этапе компиляции). Мне нужно создать структуру, которая держит ключ - размер, значение - вектор указателей. Проблема только с самой структурой (примитивы синхронизации не нужны

Не совсем понял, как задача использовать повторно память перетекает в то что тебе нужна какая-то особенная хешмапа.

Ты уверен, что тебе точно не подходит какой-нибудь альтернативный аллокатор или арены?

[mayton2019]

Если ключи числовые (int32) и имеют ярко выраженную последовательность, то хеш-мапу
можно свести к массиву с дырками. Но это надо исследовать саму природу ключей.
Как они генерируются. Как идет ротация.

значение - вектор указателей

Еще наблюдение. Работа с хеш-мапой - это работа не только к ключами но и с value.
Надо в реальном времени посмотреть как часто читается value или насколько удачно
оно заполняет например L1/L2. При неудачных раскладах у нас будет рециркуляция
значений в кешах и алгоритм хеширования будет здесь вообще не причем. А будет
идти работа с медленной памятью. Тоесть векторов оптимизации у нас много
и алгоритм хеширования здесь просто - один из факторов.

[res2001]

Eugene Usachev, Вам бы посмотреть профайлером что у вас съедает производительность.
Судя по всему хэш таблица вполне подходящая структура. Возможно вектор указателей - не совсем подходит.

[ALLIGATOR]

const primenumber = ***
index = key mod primenumber
void* [0..primenumber -1] value;