C ++: самый быстрый способ получить целое число в диапазоне
Мне нужно сгенерировать ключи хеш-функции для N = 100 миллионов ключей. Из моего исследования видно, что murmur3 (MurmurHash3_x86_32, см. murmur3 hash) будет самой быстрой функцией хеширования с лучшей задержкой и достаточно малой частотой столкновений. Проблема, с которой я сталкиваюсь, заключается в том, что функция возвращает ключ как void *, Более конкретно, шаблон выглядит так:
void MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out);
Поскольку размер моей хеш-таблицы будет меньше, чем самый большой хеш, который он может сгенерировать, мне нужно поместить его в диапазон таблицы [0, N-1]. Кажется, самое простое решение — использовать % оператор. Но поскольку это, как известно, медленный оператор, мне интересно, есть ли более быстрый способ решения проблемы.
Одно интересное предложение, которое я нашел, было дано Есть ли альтернатива использованию% (модуль) в C / C ++? на самом StackOverflow. Он предлагает «степень двойки, следующие работы (в предположении, что два дополняют представление)»:
return i & (n-1);
Моя проблема с этим заключается в том, что на более новых процессорах иногда (или это происходит чаще всего?) Производительность снижается примерно до размеров 2 ^ n, IIRC, из-за многоканальных строк кэша. (Эта ссылка предоставляет иллюстрацию относительно вставок Большая память, часть 3.5: Google sparsehash!).
В настоящее время преимущества murmur3, по-видимому, сводятся на нет из-за проблем, связанных с аппаратным обеспечением, и известной неэффективности % оператор. Поскольку производительность является ограничением, я запрашиваю решения с низкой задержкой и более быстрые решения для моего требования, даже если это не MurmurHash3_x86_32.
Решение
Проблема, с которой я сталкиваюсь, заключается в том, что функция возвращает ключ как
void *,
Это не. Ничего не возвращает (void). Результат хеширования записывается в указанный вами буфер (указатель на) с помощью последнего аргумента. За MurmurHash3_x86_32(), имеет смысл для этого быть указателем на uint32_t,
Поскольку размер моей хеш-таблицы будет меньше, чем самый большой хеш, который он может сгенерировать, мне нужно поместить его в диапазон таблицы [0, N-1]. Кажется, самое простое решение — использовать оператор%. Но поскольку это, как известно, медленный оператор, мне интересно, есть ли более быстрый способ решения проблемы.
% это не только самое простое решение, но и самое обычное. «Медленный» относительный — % медленнее, чем +, но очень, много быстрее, чем один звонок MurmurHash3_x86_32(),
Одно интересное предложение, которое я обнаружил […], предполагает [использование размера таблицы степеней двух и вычисление модуля с помощью
&оператор]
Обратите внимание, что вопреки утверждению в ответе SO, на самом деле это вообще не зависит от представления комплемента двойки.
Моя проблема с этим заключается в том, что на более новых процессорах иногда (или это происходит чаще всего?) Производительность снижается примерно до размеров 2 ^ n, IIRC, из-за многоканальных строк кэша. (Эта ссылка содержит иллюстрацию относительно вставок Big Memory, часть 3.5: Google sparsehash!).
Понижение производительности, описанное в отчете, который вы связали, связано с повторным хэшированием, что кажется вполне вероятным. Это не имеет ничего общего с операциями, о которых вы спрашиваете. Вполне возможно, что ассоциативность кэша (отсутствие) может повлиять на производительность для больших хеш-таблиц, но, вероятно, не более, чем обычно, если иметь большие хеш-таблицы. Шаблоны доступа к памяти, присущие использованию хэш-таблицы, естественно, создают плохую локальность кэша. Это практически точка.
На данный момент преимущества murmur3, по-видимому, сводятся на нет из-за проблем, связанных с аппаратным обеспечением, и известной неэффективности оператора%. Поскольку производительность является ограничением, я запрашиваю решения с низкой задержкой и более быстрые решения для моего требования, даже если это не MurmurHash3_x86_32.
Вы слишком обдумываете это. Недостаток эффективного использования кэша вашего процессора — это просто цена, которую вы платите за использование большой хеш-таблицы. Он не связан с хеш-функцией (если хеш-функция хорошо работает). Стоимость одной арифметической операции, будь то % или же &, не будет заметно по сравнению со стоимостью вычисления хеша для работы на, поэтому вряд ли имеет значение, кого из них вы выберете. Если вы хотите получить крошечное преимущество для этой операции, тогда используйте таблицу размером два и & оператор. С другой стороны, это отбрасывает некоторые хэш-биты, которые вы так усердно вычисляете. Рассмотрите вместо выбора простое число размер хеш-таблицы и % оператор — тогда все биты хеша будут способствовать выбору сегмента, что может улучшить ваш спред.
Другие решения