Отделить функцию хеширования std::hash от собственно хешируемых данных

[apolukhin]

Перенос предложения: голоса +6, -0 Автор идеи: Igor Baidiuk

Разделить процесс хеширования на "провайдер данных" и собственно "хешер", попутно позволив реализовывать "провайдер данных" для типов независимо от std::hash

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

1. Свой функтор. Достоинства:

• очевидно и "прямолинейно" Недостатки:

• надо явно использовать во всех контейнерах
• надо вручную реализовывать "микширование" хешей компонентов в единый хеш
• хешер оказывается "прибит гвоздями" к конкретному алгоритму хеширования

2. Специализация std::hash Достоинства:

• Будет использован автоматически Недостатки:

• "Влазить" в namespace std не поощряется стандартом за исключением оговорённых случаев
• надо вручную реализовывать "микширование" хешей компонентов в единый хеш
• хешер оказывается "прибит гвоздями" к конкретному алгоритму хеширования

Итак, собственно proposal sketch

Типы, желающие быть хешированными, добавляют либо метод

template<typename Hasher>
void hash(Hasher& hasher) const;

либо свободную функцию

template<typename Hasher>
void hash(MyType const& self, Hasher& hasher);

Метод при выборе имеет приоритет. Свободная функция позволяет реализовать хеш для типов, для которых автор забыл это сделать. Назначение - передать набор значимых для хеша конкретного экземпляра байт в экземпляр хешера, при этом не принимая никаких решений относительно того, как эти байты будут хешироваться и комбинироваться. Пример реализации:

struct MyVec {
    double x, y, z;

    template<typename Hasher>
    void hash(Hasher& hasher) const {
        hasher(x);
        hasher(y);
        hasher(z);
    }
};

Вторым компонентом этой системы является непосредственно хешер (ниже пример примитивного хешера)

struct MyHasher {
    void operator()(const void* bytes, size_t nBytes) {
        accumulated = myFancyHashFunc(accumulated, bytes, nBytes);
    }

    template<typename T>
    void operator()(T&& value) {
        hasher_traits<MyHasher>{}(*this, std::forward<T>(value));
    }

    size_t hash() const noexcept { return accumulated; }
private:
    size_t accumulated = StarterHashConstant;
};

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

Преимущества:

• Каждому конкретному типу не требуется ни знать про хеширование как таковое, ни даже про метод "примешивания" байт к имеющемуся хешу - к примеру, отпадает головная боль как правильно соединить хеши трёх чисел с плавающей точкой
• Тип может быть хеширован любым подходящим по месту способом, а не так, как решил автор типа
• В месте использования контейнера можно использовать нестандартный алгоритм хеширования без необходимости переопреелять его для всех типов по месту
• Наконец, результат хеширования не обязан быть всегда size_t, и конкретному типу совершенно не нужно об этом знать. Любой тип, поддерживающий хеширование, можно при необходимости пропустить через CRC32, MD5, SHA1, SHA512 и т.п. При этом стандартные контейнеры могут всё так же спокойно требовать size_t как тип результата хеширования.

Как всё это встроить в текущую модель. Стандартом предполагается наличие "включенных" и "выключенных" реализаций std::hash. При этом большинство реализаций выключены по умолчанию с помощью бланкет-реализации для любого типа T. Эту бланкет-реализацию можно расширить поддержкой указанных систем хеширования. Таким образом, std::hash по умолчанию приобретает примерно следующий вид

namespace std {
    template<Hashable T>
    struct hash {
        size_t operator()(T const& value) const {
            std::hasher hasher;
            hasher(value);
            return hasher.hash();
        }
    };
}

[apolukhin]

yndx-antoshkka, 28 декабря 2018, 15:35 Подобные предложения уже рассматриваются комитетом: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0199r0.pdf, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0814r2.pdf

Igor Baidiuk, 28 декабря 2018, 15:46 yndx-antoshkka, спасибо за ссылки. Если я правильно понимаю, первый концентрируется на default hash operator, а второй - на hash_combine. Первый ортогонален, а второй - не решает проблему "прибитости гвоздями" хеш-оператора к конкретному алгоритму. Это же предложение лежит в несколько иной плоскости.

Igor Baidiuk, 28 декабря 2018, 15:52 Нашёл этот пропозал: p0029r0 Пока что наиболее близко к теме.

Айдар Фаттахов, 2 февраля 2019, 14:26

Отделить функцию хэширования от данных Типы добавляют метод

Igor Baidiuk, 27 мая 2019, 14:29 asschool, не вижу противоречия. Упоминаемый метод ничего не говорит об алгоритме хеширования, а только о том, какие данные передаются в хешер. Алгоритм вычисления хеша лежит отдельно. Под "функцией хеширования" как правило понимают именно алгоритм.

Айдар Фаттахов, 27 мая 2019, 16:29 Igor Baidiuk,

Каждому конкретному типу не требуется ни знать про хеширование как таковое

Вы добавляете метод hash

Мне кажется в вашей модели визитор является лишним элементом, достаточно std::hash::operator() прнимать hasher

[target-san]

Решил воскресить эту идею. Постарался расписать основные моменты, в т.ч. кратко сравнить с P0814: Separate type hashing method from hash algorithm

[apolukhin]

Отличное начало!

Посмотрите ещё на https://wg21.link/p0029r0, там схожие идеи но сильно устеревшее предложение.

Ещё стоит продумать следующие моменты:

• как использовать с контейнерами
• нужна функция для получения результата из хешера, результат не надо считать на каждый hash_combine (есть хеширующие функции, с дорогим финальным шагом, не надо этот шаг повторять на кажый hash_combine)
• добавить хеширование изкоробки для pair и tuple
• Hasher в текущем описании приведёт к бесконечной рекурсии
• HashFunc должен быть объектом, при этом у него может быть огромный стейт

[target-san]

Посмотрите ещё на https://wg21.link/p0029r0, там схожие идеи но сильно устеревшее предложение.

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

как использовать с контейнерами

Контейнер будет просто вызывать compute_hash_value(hash_func, value). Забыл добавить примеров, как раз опишу этот момент.

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

Для этого я и расписал Alternative HashFunc, представляющую собой короткоживущий stateful объект. У него есть метод result, возвращающий значение хеш-функции.

добавить хеширование изкоробки для pair и tuple

Да, безусловно. Просто я решил, что их имеет смысл делать в рамках reference implementation, чуть позже.

Hasher в текущем описании приведёт к бесконечной рекурсии

Спасибо за замечание, проверю. Я писал этот код как скетч, из головы. По хорошему, нужно делать реализацию в виде форка stdlib CLang'а, и уже её основательно гонять.

HashFunc должен быть объектом, при этом у него может быть огромный стейт

В общем, вы склоняетесь к альтернативному варианту.

Пара вопросов:

• Стоит ли требовать от HashFunc copy-constructible или default constructible? В первом случае можно будет инициализировать контейнер объектом-функцией с неким первичным состоянием, а внутри контейнера делать копии для вычисления хешей. Во втором новые объекты-функции будут просто спавниться, по одному на каждое вычислене хеша. Первый подод выглядит более гибким, второй более простым.
• Что думаете по поводу endian-ness? Может, стоит просто опционально реализовывать у объекта-функции перегрузки для всех числовых типов?

[target-san]

По ссылкам обнаруживается масса пропозалов на эту тему. Общий список примерно следующий:

• P0814R2 - текущий, простенький хелпер hash_combine
• P0029R0 - предыдущий, наиболее близок к этому документу, отличается разделением HashFunc на std::hash_code и std::hash_combine.
• N3333 - hash_value с поиском через ADL, hash_combine для комбинирования значений; один алгоритм хеширования.
• N3980 - похоже, отличается от P0029 только в мелких деталях
• N3876 - почти чистый hash_combine

Самый интересный вопрос - почему ни один из них так и не приняли.

[target-san]

@apolukhin Обновил proposal. Пока не осветил сравнение с предыдущими предложениями.

[apolukhin]

Proposal состоит как бы из двух частей:

1. объект для хеширования
2. visit по всем значимым полям класса

С частью 1. всё неплохо. Надо ли сделать чтобы хешеры могли возвращать разные типы результата (например std::unit32_t, чтобы хеш можно было сохранять и передавать по сети/диску между разноразрядными платформами). Продумать интеграцию со стандартными контейнерами - как сразу начать использовать новые хеши? Расставить noexcept (или расписать, почему не расставили) для concept HashFunc

Часть 2. меня пугает. Кажется что это более общий механизм, который можно применять не только для хеширования, но и для сериализации/десериализации и т.п. Нужно либо расписать, почему это плохая идея, использовать этот механизм для других вещей, либо расписать его использование для других сценариев.

В любом случае, кажется часть 2 надо вынессти отдельно - по ней будет очень много вопросов и споров в комитете, в частности, как это соотносится с предложенной рефлексией.

[target-san]

С частью 1. всё неплохо.

Спасибо, стараюсь по мере возможности.

Надо ли сделать чтобы хешеры могли возвращать разные типы результата (например std::unit32_t, чтобы хеш можно было сохранять и передавать по сети/диску между разноразрядными платформами).

По сути, пропозал это и предлагает. HashFunc::result() может возвращать произвольный тип. Он фиксирован как std::size_t только для стандартных хешеров.

Продумать интеграцию со стандартными контейнерами - как сразу начать использовать новые хеши?

Этот момент описан в отдельном разделе. Я так понимаю, недостаточно внятно. Чего может не хватать:

1. Примера реализации blanket std::hash с enabledness по наличию новых функций хеширования
2. Примера выбора между старым и новым хешером внутри контейнера

Что-то ещё?

Расставить noexcept (или расписать, почему не расставили) для concept HashFunc

Бесспорно, это надо сделать. Но, как мне кажется, уже после "устаканивания" первичной идеи.

Часть 2. меня пугает. Кажется что это более общий механизм, который можно применять не только для хеширования, но и для сериализации/десериализации и т.п. Нужно либо расписать, почему это плохая идея, использовать этот механизм для других вещей, либо расписать его использование для других сценариев.

В любом случае, кажется часть 2 надо вынессти отдельно - по ней будет очень много вопросов и споров в комитете, в частности, как это соотносится с предложенной рефлексией.

Вот здесь не совсем понимаю. В тексте нигде не упоминаются какие-либо варианты автогенерации hash_value. Пропозал, по сути, нейтрален относительно подобной рефлексии. Всё, что предлагается - сделать максимально эргономичную композицию для реализации пользовательского кода. Хешер ничего не генерирует, он просто выбирает из пачки доступных реализаций, используя ADL. Если же вы говорите о коде вида hasher(value.first), то это просто более эргономичный вариант через перегрузку оператора (). Похожий подход применяется в cereal. К примеру, в пропозале P0029 для этого требуется явно использовать hash_combine.

Или я вас неправильно понял. Тогда укажите пожалуйста на "2ю часть", о которой вы говорите.

[apolukhin]

Вы фактически предлагаете концепт HashFunc, который отвечает за то как хешировать, и hash_value говорящий что хешировать:

struct foo {
    void hash_value(auto& hasher) {
        hasher(a);
        hasher(b);
    }

    int a; 
    int b;
};

auto kHash = sha512hasher(foo{4, 2});

Люди в комитете зададут вопросы:

• hash_value - это ведь функция, применяющая функтор к каждому из полей класса. Можно ли обобщить hash_value для других целей? Например для сериализации/дессериализации?
• не хочется писать hash_value руками для агрегатов, почему бы компилятору не генерировать эту функцию за нас?
• в предложении делается интроспекция типа, как предложение соотносится с разрабатываемой рефлексией?

Именно поэтому, вторая часть меня и беспокоит - непонятно куда заведёт обсуждение, и если обсуждение зайдёт в страшные дебри, то всё предложение будет под вопросом/затянется.

[target-san]

Спасибо, теперь вопрос понятен.

Короткий ответ:

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

Ответ по пунктам:

hash_value - это ведь функция, применяющая функтор к каждому из полей класса. Можно ли обобщить hash_value для других целей? Например для сериализации/дессериализации?

В двух словах - нет. Сериализуемые данные в общем случае не равны хешируемым данным. Сам подход можно применить аналогичным образом. Сейчас в качестве примера можно смотреть ту же библиотеку cereal, упомянутую мной ранее. Но в любом случае это будет отдельный "микро-фреймворк".

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

Можно и генерировать, но этот пропозал намеренно не затрагивает вопрос автоматической генерации и полностью ортогонален ему. Ничто не мешает реализовать генерацию потом, или отдельным пропозалом, или через рефлексию (когда и если она будет).

в предложении делается интроспекция типа, как предложение соотносится с разрабатываемой рефлексией?

Вынужден не согласиться. То, что код похож на интроспекцию типа, не означает, что там эта интроспекция есть. В этом плане любая реализация hash_value использует не больше интроспекции, чем существующие сейчас специализации std::hash.

[target-san]

Обновил пропозал.

По замечаниям:

1. Возможность возвращать типы, отличные от std::size_t, явно указана в этом разделе - второй абзац и первый элемент в списке "Properties of proposed design".
2. Интеграция с существующими хеш-контейнерами. Необходимые изменения вынесены в отдельный подраздел. Остальная часть раздела - объяснение, почему именно так.
3. Добавлен отдельный раздел Out of scope, в котором явно указано, что интроспекция и рефлексия в пропозале не рассматриваются.

[apolukhin]

@target-san ещё немного комментов:

• HashFunc
  • нужно подумать над названием, это больше не функция, а объект/алгоритм
  • нужно описать требования на возвращаемый из hashFunc.result() тип данных. Нужно чтобы результаты были сравнимы... а для использования в unordered контейнерах необходимо чтобы к результату можно было применять операции %, /, &, ~. Возможно, что нужно требовать чтобы возвращался целочисленный тип, но тогда возникнут проблемы со всякими sha512
  • концепты в C++23 описываются в нижнем регистре, в snake_case
• Hasher
  • привести к единому виду, где-то с заглавной буквы, где-то с малой
  • непонятно, как туда передаётся объект удовлетворяющий HashFunc
  • в using std::hash_value; вы намекаете на стандартные хешеры, но больше в proposal их нет. Надо сделать целостно
  • static_assert(false - надо сделать false зависимым от T, иначе assert всегда будет срабатывать
  • HashableUsingFreeFunc не сработает если hash_value находится в std и тип является фундаментальным (например double), надо поправить operator(). Сейчас он никогда не будет использовать std::hash_value
  • наверное вы подразумеваете наследование std::hasher от алгоритма хеширования. Если этого не делать, то compute_hash_value не нужен, можно просто звать std::hasher(hash_algo, data).result(). Наследоваться нельзя, алгоритм может быть помечен пользователем как final
• Добавьте секцию Wording и перечислите там все сигнатуры функций и классов, которые предлагаете добавить в стандарт

[apolukhin]

Чуть не забыл:

• Раз алгоритм хеширования теперь отделён от данных, то ничего не мешает методам std::hasher быть constexpr. Если передадут constexpr HashFunc, то можно будет подсчитать на этапе компиляции. Нет - подсчитается в рантайме.