search

cpp-ru / ideas

Идеи по улучшению языка C++ для обсуждения
https://cpp-ru.github.io/proposals
Creative Commons Zero v1.0 Universal
90 stars 0 forks source link

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

Open apolukhin opened 3 years ago

apolukhin commented 3 years ago

Перенос предложения: голоса +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 и реализуют поддержку хеширования значений конкретных типов, приводя их к единственной реализации хеширования произвольного набора байт.

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

Как всё это встроить в текущую модель. Стандартом предполагается наличие "включенных" и "выключенных" реализаций 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 commented 3 years ago

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 commented 2 years ago

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

apolukhin commented 2 years ago

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

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

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

target-san commented 2 years ago

Посмотрите ещё на 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 должен быть объектом, при этом у него может быть огромный стейт

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

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

target-san commented 2 years ago

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

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

target-san commented 2 years ago

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

apolukhin commented 2 years ago

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

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

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

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

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

target-san commented 2 years ago

С частью 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 commented 2 years ago

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

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

    int a; 
    int b;
};

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

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

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

target-san commented 2 years ago

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

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

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

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

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

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

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

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

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

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

target-san commented 2 years ago

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

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

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

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

apolukhin commented 2 years ago

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