Блог

Я хочу эффективно находить индексы набора. Я использую unordered_map и создаю обратную карту следующим образом

 std::unordered_map <int, int> myHash (size); 
Int i = 0;
for (it = someSet.begin(); it != someSet.end(); it  )
{
    myHash.insert({*it , i  });
 }
  

Это работает, но неэффективно. Я сделал это, чтобы в любое время, когда мне нужны индексы, я мог получить к ним доступ O (1). Анализ производительности показывает мне, что эта часть стала горячей точкой моего кода.

VTune сообщает мне, что new operator — моя точка доступа. Я предполагаю, что что-то происходит внутри unordered_map. Мне кажется, что этот случай должен быть обработан эффективно. Я пока не смог найти хороший способ. Есть ли лучшее решение? правильный конструктор? Возможно, мне следует передать больше информации конструктору. Я просмотрел список инициализации, но это не совсем то, что я хочу.

Обновление: Позвольте мне добавить еще немного информации. Набор не так важен; я сохраняю набор в массив (отсортированном). Позже мне нужно найти индекс уникальных значений. Я могу сделать это в logn, но это недостаточно быстро. Именно поэтому я решил использовать хэш. После этого размер набора (столбцов подматрицы) не изменяется.

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

Проблема заключается в том, std::unordered_map что, в основном реализованный в виде списка векторов, крайне недружелюбен к кешированию и будет особенно плохо работать с небольшими ключами / значениями (как int,int в вашем случае), не говоря уже о том, что требуется множество (повторных) распределений.

В качестве альтернативы вы можете попробовать стороннюю хэш-карту, реализующую открытую адресацию с линейным зондированием (полный рот, но базовая структура — это просто вектор, т. Е. Гораздо Более удобный для кэша). Например, Google dense_hash_map или this: flat_hash_map . Оба могут использоваться в качестве замены для unordered_map , и только дополнительно требуется назначить одно int значение в качестве «пустого» ключа.

std::unordered_map<int, int> часто реализуется так, как если бы это было

 std::vector<std::list<std::par<int, int>>> 
  

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

Вы можете немного помочь этому, используя emplace вместо insert, или вы можете прыгнуть в фантастический новый мир распределителей pmr. Если ваше создание и уничтожение pmr ::unordered_map является однопоточным, вы сможете получить от этого большую дополнительную производительность. Смотрите Jason Turners C Weekly — Ep 222 — В 3,5 раза быстрее стандартных контейнеров с PMR!, его пример немного маловат, но вы можете получить общую идею.