Вменяемый хэш для значений SIMD? - PullRequest
Новая
       44

Вменяемый хэш для значений SIMD?

0 голосов
/ 19 февраля 2019

Я хотел бы использовать в качестве теста простую хэш-карту с __m128i, но C ++ жалуется, что хеш-функция несовместима: 

/Applications/Xcode.app/[...]/c++/v1/__hash_table:880:5: error: static_assert failed due to requirement [...] "the specified hash does not meet the Hash requirements"

    static_assert(__check_hash_requirements<_Key, _Hash>::value,
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In file included from [...] note: in instantiation of template class [...] requested here
    std::unordered_map<__m128i, std::size_t> hmap;

Теперь я мог бы предоставить хеш-функцию простоиспользуя код, подобный следующему: 

    class hash128i
    {
    public:
        std::size_t operator()(const __m128i &r) const
        {
            return something;
        }
    };

С придуманным мной something, как OR -из старших и младших 64-битовых __m128i, а затем используйте std::hash.

Однако, учитывая чувствительную природу хеш-функций, я не знаю, является ли этот подход разумным.

Что было бы хорошей хэш-функцией C ++ для __m128i (или другой переменной SIMD?))

1 Ответ

0 голосов
/ 19 февраля 2019

Практическое качество хеш-функции в некоторой степени зависит от того, какие свойства вам нужны и как распределяются ваши данные.

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

Для коротких целых чисел Крис Уэллонс провел немало анализа , используя свою программу hash-prospector .

Упомянутая им хорошая 64-битная функция такова: здесь : 

uint64_t splittable64(uint64_t x)
{
    x ^= x >> 30;
    x *= UINT64_C(0xbf58476d1ce4e5b9);
    x ^= x >> 27;
    x *= UINT64_C(0x94d049bb133111eb);
    x ^= x >> 31;
    return x;
}

Вы можете хешировать обе половины 128-битного целого и объединять их через XOR, вращатьодин из них, если вы ожидаете, что половинки часто идентичны.Таким образом, ваше решение может выглядеть примерно так: 

class hash128i
{
public:
    std::size_t operator()(const __m128i &r) const
    {
        uint64_t lower_hash = splittable64(static_cast<uint64_t>(r));
        uint64_t upper_hash = splittable64(static_cast<uint64_t>(r >> 64));
        uint64_t rotated_upper = upper_hash << 31 | upper_hash >> 33;
        return lower_hash ^ rotated_upper;
    }
};

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

...