Что: dffa894abeab4eaec509b95af9d23b51e4e0f844
Когда: 2023-12-28 22:13:52+03:00
Познакомился с xxHash, XXH3 https://en.wikipedia.org/wiki/Cyclic_redundancy_check https://en.wikipedia.org/wiki/List_of_checksum_algorithms https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html https://fastcompression.blogspot.com/2019/01/opaque-types-and-static-allocation.html https://fastcompression.blogspot.com/2019/01/the-type-system_19.html Понадобилась тут быстрая, простая, приемлемая для (относительно) не быстрых процессоров, функция проверки целостности данных. Криптографические хэши и медленные и избыточные для этой задачи. CRC32 в принципе мог бы быть достаточен. Но он, строго говоря, не является контрольной суммой, судя по Wikipedia, ибо например перестановка местами блоков не сыграет роли. Fletcher, который по умолчанию используется в ZFS, жутко быстрый, является контрольной суммой, но в крайних случаях (когда сплошные нули или единицы) ведёт себя плохо. Я помнил что Zstandard использует какой-то быстрый хэш, про который я оказывается в этом году вспоминал: bd11d713558b26f0c5da3f61b67a252ac6b13698. Автор LZ4 (а также Zstandard) написал его, ибо был не удовлетворён тем, что бутылочным горлышком при сжатии данных может оказаться именно хэш, контрольная сумма. xxHash быстрее CRC32 (без аппаратного ускорения). А позже он сделал XXH3 -- ещё более быстрый, более надёжный вариант с 512-бит состоянием, из которого можно 64 или 128 бит хэш получить. И XXH3, в отличии от xxHash-64, хорошо работает и на 32-бит системах. Плюс проходит все тесты SMHasher как хэш-функция. Посмотрел на его исходный код. Один из лучших Си кодов которые я только видел. Не то чтобы я тут большой спец и имею опыт, но по сравнению с OpenSSL, являющимся просто дерьмодемоном каким-то, этот верх идеала. А также копался в GNU GMP, GnuTLS -- крайне не нравилось что там очень упарываются по define-ам, и чёрт поймёшь что конкретно за код будет компилироваться. В xxHash автор упарывается по выжиманию производительности и дружбой с компиляторами. Может показаться что там много define-ами обмазано, но нет -- они по сути что-то типа как вместо autoconf используются для определения что у нас за компилятор и какие специфичные для него можно передать атрибуты и подсказки. А если слишком старый компилятор, то просто опускать какие-нибудь "static inline". Это всё только в начале, дальше не мешает. В некоторых циклах даёт подсказки компиляторам, явно описывая что вот тут GNU GCC себя плохо ведёт, а Clang рвёт его как Тузик грелку по производительности, и всё в таком духе. Аккуратная работа с преобразованием типов cast/alias данных, мой Clang -Weverything ни на что не ругается, что не часто встретишь. Много заморачивается с выравниванием данных корректным и strict aliasing-ом. В блоге про это у него несколько статей есть. И да, он реально делается struct с единственным unsigned char * полем для хранения сериализованного представления хэша (то что он называет shell type-ом). Но это всё не мешает. Дробит код на много маленьких аккуратных static inline функций даже в одну строчку, очень здорово увеличивая читабельность. В коде можно define-ами выбирать: поменьше размер бинарника (меньше оптимизаций), или побольше скорость (больше оптимизаций, больше кода). И всё это дружелюбно к тому, чтобы встроить xxHash/XXH3 в программу просто делая include <xxhash.h>, и делать inline. Очень понравился проект!