Хеширование табуляции и N3980

У меня возникли проблемы с адаптированием ожидающего предложения С++ 1z N3980 от @HowardHinnant для работы с хэширование табуляции.

Ab initio computing хэширование табуляции работает так же, как и для алгоритма хэширования (Spooky, Murmur и т.д.), описанного в N3980. Это не так сложно: просто сериализуйте объект любого пользовательского типа с помощью hash_append() и пусть хеш-функция обновляет указатель на таблицу случайных чисел по мере продвижения.

Проблема возникает при попытке реализовать одно из приятных свойств хэширования табуляции: очень дешево вычислять инкрементные обновления для хеша, если объект мутирован. Для хэшей таблиц "ручной работы" один только перекомпонует хэш объектов, затронутых байтами.

Мой вопрос: как передавать инкрементные обновления объекту функции uhash<MyTabulationAlgorithm>, сохраняя истинную центральную тему N3980 (Типы не знают #)

Чтобы проиллюстрировать трудности проектирования: скажем, у меня есть пользовательский тип X с N элементами данных xi различных типов Ti

struct X 
{
   T1 x1;
   ...
   TN xN;
};

Теперь создайте объект и вычислите его хэш

X x { ... }; // initialize
std::size_t h = uhash<MyTabulationAlgorithm>(x);

Обновите один элемент и пересчитайте хэш

x.x2 = 42;
h ^= ...; // ?? I want to avoid calling uhash<>() again

Я мог бы вычислить инкрементное обновление как нечто вроде

h ^= hash_update(x.x2, start, stop);

где [start, stop) представляет диапазон таблицы случайных чисел, которые соответствуют элементу данных x2. Однако, чтобы постепенно (то есть дешево!) Обновлять хэш для произвольных мутаций, каждый член данных должен каким-то образом знать свой собственный поддиапазон в сериализованном потоке байтов его содержащего класса. Это не похоже на дух N3980. Например, добавление новых членов данных в класс, содержащий класс, изменит макет класса и, следовательно, смещения в потоке с последовательным байтом.

Приложение: хэширование табуляции очень старое, и недавно было показано, что он имеет очень хорошие математические свойства (см. ссылку в Википедии). Он также очень популярен в сообществе программистов (компьютерные шахматы и идут, например,), где он идет под названием Хоббирование Zobrist. Там положение платы играет роль X и перемещает роль небольшого обновления (переместите кусок из своего источника в его пункт назначения, например). Было бы неплохо, если бы N3980 можно было не только адаптировать к такому хищению в виде табулирования, но также можно было бы разместить дешевые инкрементные обновления.

Ответы

Ответ 1

Кажется, что вы должны это сделать, сообщив MyTabulationAlgorithm игнорировать значения всех членов класса, кроме того, что изменилось:

x.x2 = 42;
IncrementalHashAdaptor<MyTabulationAlgorithm, T2> inc{x.x2};
hash_append(inc, x);
h ^= inc;

Все, что требуется IncrementalHashAdaptor, это проверить диапазон памяти, который он передал, чтобы увидеть, включен ли в него x2:

template<class HashAlgorithm, class T>
struct IncrementalHashAdaptor
{
    T& t;
    HashAlgorithm h = {};
    bool found = false;
    void operator()(void const* key, std::size_t len) noexcept
    {
        if (/* t contained within [key, key + len) */) {
            assert(!found);
            found = true;
            char const* p = addressof(t);
            h.ignore(key, (p - key));
            h(p, sizeof(T));
            h.ignore(p + sizeof(T), len - (p - key) - sizeof(T));
        }
        else {
            h.ignore(key, len);
        }
    }
    operator std:size_t() const { assert(found); return h; }
};

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

Вероятно, вы захотите обернуть IncrementalHashAdaptor и следующий hash_append в утилиту uhash_incremental; это остается как упражнение для читателя.

Существует знак вопроса над производительностью; предполагая, что HashAlgorithm::ignore(...) виден компилятору и он несложный, он должен хорошо оптимизировать; если этого не происходит, вы должны иметь возможность вычислить адрес байтового потока X::x2 при запуске программы, используя аналогичную стратегию.