Должен ли я кэшировать хеш-код строки STL, используемой в качестве хеш-ключа?

Question

Я провел некоторый анализ производительности разрабатываемого программного обеспечения и обнаружил, что поиск в глобальном словаре URL-адресов занимает около 10% времени фазы загрузки приложения. Словарь реализован в виде std :: map C ++ STL, который имеет O (lg n) поисков. Я собираюсь переместить его в hash_map, который имеет примерно фиксированный поиск по времени. Строковый класс stl не имеет свойства хеш-кода и, конечно, не кэширует хеш-код. Это означает, что каждый поиск требует повторной генерации хеш-кода.

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

У кого-нибудь есть опыт кеширования строковых хеш-кодов? Стоило ли когда-нибудь оправдывать свои усилия?

Answer 1

Когда вы сравниваете хеш-карту с картой, попробуйте также Trie или связанную структуру данных (что вы можете получить с полки):

Трия реализации

К сожалению, вы можете потратить много времени, беспокоясь о безопасности кэша. В этом отношении Trie похож на дерево, которое у вас уже есть, и карта хеша, вероятно, будет вести себя лучше, чем дерево, выделенное наивно.

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

Если вы имеете в виду кэширование значений ключей, уже находящихся в хеш-таблице, это до хеш-таблицы.

Answer 2

У меня нет опыта с кешированием хеш-кодов, но я недавно проделал некоторую работу по преобразованию std::map в std::tr1::unordered_map. На ум приходят две мысли. Во-первых, сначала попробуйте профилировать это относительно простое изменение, потому что оно иногда ухудшает ситуацию , в зависимости от того, что делает ваш код. Это может дать вам достаточное ускорение, прежде чем вы попытаетесь оптимизировать дальше. Во-вторых, что говорит ваш профилировщик о других 90% вашего времени инициализации? Даже если вы оптимизируете глобальный словарь до 0 раз, вы максимально увеличите производительность на 10%.

Answer 3

Одно слово предупреждения.

Хотя хэш-карта может иметь поиск по фиксированному времени, она также может иметь O (N) поисков.Хотя это не частый случай, это происходит.

Так что, хотя вам всегда приходится платить за время O (log N) на карте, вам также гарантировано, что оно не будет хуже.

Answer 4

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

Сам компилятор будет знать, не была ли изменена строка, и, вероятно, сможет кешировать результат для вас (в той же области видимости). Тем не менее, вы не хотите наследовать от std::string; Классы STL не были созданы для этого.

Скорее, сделайте std::pair и передайте это:

std::pair<const std::string, const size_t> string_hash_pair;

Затем вам нужно было бы перегрузить (здесь это происходит с помощью Boost, а не TR1; я не знаю, насколько они похожи) hash_value для вашего типа в том же пространстве имен, что и определенная пара:

size_t hash_value(const string_hash_pair& pPair)
{
    return pPair.second; // don't actually hash
}

И это все. Обратите внимание, что в паре и string, и size_t являются неизменными. Это потому, что если string изменяется, ваш хэш неверен. Таким образом, мы делаем это const, и мы можем также сделать хэш const.

Вам понадобится вспомогательная функция:

string_hash_pair make_string_hash(const std::string& pStr)
{
    return std::make_pair(pStr, boost::hash_value(pStr));
}

Теперь, если вы собираетесь использовать строку для поиска, просто сделайте из нее пару, и вы получите хэширование в постоянном времени.

Тем не менее, я действительно сомневаюсь, что такая большая работа необходима. Хеш-функции обычно тривиальны. Кроме того, не делает свой собственный . Используйте уже существующий проверенный хэш; довольно просто сделать дерьмовый хеш.

Answer 5

Я сделал несколько сравнений неупорядоченного набора со строками 4–64 тыс. В моем словаре.

Я обнаружил, что std :: set и unordered_set имели примерно одинаковое время выполнения в моей ситуации, потому что вычисление hash_value занимало около 80% времени выполнения для неупорядоченного набора.

Это уменьшило экономию при поиске (используется boost :: hash_value для std :: string FWIW)

YMMV, и в общих случаях я бы сказал, что профиль и не будут обмануты теоретическим масштабированием, которое не учитывает архитектуру процессора и т. Д. Хеш-карта может работать медленнее из-за стоимости хэш-памяти и будет занимать больше памяти .

В моем случае я храню информацию в течение длительного времени и регулярно получаю обновления, которые не изменяют хэш information_id, но могут изменять другое содержимое.

Затем каждое обновление передается в мою функцию поиска, чтобы решить, нужно ли мне извещать об этом обновлении извне.

Список информационных_идей для уведомления находится в этом поиске и может изменяться независимо от информации.

Кэшируя хеш-код для information_id, он, вероятно, будет повторно использован 10 раз за время существования информации.

Мое изменение в две строки для кэширования хэша улучшило время выполнения unordered_set на> x8

Тестовый набор: тестируется в MSVC 2012, обновление 4 1M записей посмотрел 10 раз каждая против словаря 4k и 64k: Все проверки, кроме 10, - промахи в 4К, 500 попаданий в 64К (больше aardvarks:))

набор: 1373 мс / 1938 мс

мультисеть: 1376 мс / 1913 мс

unordered_set начальные 64 КБ / коэффициент загрузки 0,5: 168 мс / 362 мс

unordered_set 4k / 1.0: 331 мс / 452 мс

c.f предварительный кеш

unordered_set 64k / 0,5: 1519 мс / 1881 мс

FWIW То же самое работает с MinGW 4.9.1 -O3

набор: 2003 мс / 2490 мс

мультисеть: 1978 мс / 2306 мс

unordered_set начальные 64 КБ / 0,5 коэффициент загрузки: 140 мс / 605 мс

unordered_set 4k / 1.0: 318 мс / 683 мс

c.f предварительный кеш

unordered_set 64k / 0,5: 1619 мс / 2455 мс