информация для ПМИ
завтра (ср 05 октября) 1 потоку ПАДИИ буду читать тоже самое, что собирался сегодня, постараюсь сделать так, чтобы была трансляция и запись

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

если и этого не хватит, дочитаем где-нибудь ещё одну пару, но уже позже

информация для ПАДИИ 2 поток
я готов провести недостающую пару в чт и в сб на этой неделе, а также в пн и в чт на следующей

в чт с 13 до примерно 15 обычно занят

выбирайте время, но, как вы понимаете, желательно не рано утром :)

[здесь была ссылка на старую трансляцию!]

Ссылка на трансляцию

Ссылка на сегодняшнюю практику: cs-sh.xyz/ottergottaott/programming-basics-2022/src/branch/main/05

(!) выложил слайды прошедней лекции на csc wiki

(!) добавил ссылки на код семинаров к каждой лекции на csc wiki

слайды лекции по git скоро тоже появятся (до сб включительно, я думаю)

потоку ПМИ: полистайте слайды лекции, мб, посмотрите запись, если будут вопросы, задавайте во вт (или можно попробовать прийти в пн, когда буду проводить пару для 2 потока ПАДИИ)
upd: и обязательно откройте и прорешайте задание с семинара!

ссылка на слайды по git и linux от Д. Халанского: [на cscwiki за 21 год]

вдруг кому пригодится: тут мои конфиги для kakoune, neovim и не только https://cs-sh.xyz/ottergottaott/dotfiles

Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно.

Что такое хорошая хеш-функция?

Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.

Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.

В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.

И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.

Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?

Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?

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

А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)

Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.

Попытка 1: crc

Инструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.

Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).

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

Попытка 2: 128 битное умножение

Мы в abseil выбрали approach слегка другой, а название ему 128 битное умножение

(seed + number) * prime_number

Далее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.

На удивление это имеет достаточно хорошее распределение.

Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.

Похожую идею можно увидеть даже у MurMur:

uint64_t fmix64 ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;
return k;
}

Попытка 3: перебор

Для 16 байт мы знаем, что есть хэш функция с хорошим распределением в 6 инструкций. Вопрос, а какое минимальное? Можно взять какой-нибудь set и перебрать. Вопрос в том, какие данные брать: я решил брать около 1000 входов, где есть случайные числа и все их соседи, где отличаются на 2 бита.

3 инструкции не работают совсем, лучшая 4 инстручная последовательность

r0 = hi - seed;
r1 = lo + 0x71b1a19b907d6e33;
r2 = r0 * r1;
r3 = r2 ^ r2_hi;
return r3;

Ломается на распределениях побольше. Всего перебор дал где-то 40 вариантов, все сломались на бОльших распределениях.

Можно перебирать 5 инструкций, но количество операций уже растёт слишком экспоненциально. На каждом шаге выбор где-то из 100 вариантов (все пары переменных * операции (+-^*,shift,rotate,crc,&,|)), в итоге даже если не разрешать все сдвиги или rotate, получается много. 115^n примерно, где n количество инструкций, на каждую итерацию надо проверить около 1000 входов на коллизии, что достаточно затратно. В итоге для n = 5, 10^15-10^16 итераций, ну можно запустить map reduce pipeline на часы. Ура, нашли 25k вариантов.

Дальше я пока сдался, потому что ощущение, что я схожу с ума. Чтобы отсеивать дальше, надо уметь больше распределений или запускать прям smhasher на все найденные.

Ну либо пойти к DeepMind, пусть их RL штуки находят хэш функции, наверное, можно поумнее.

Но мне кажется я вот вот либо докажу, что не существует хорошей 5 инстручной хеш функции для 16 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор.

Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.

https://www.cognitoforms.com/АлексейЗубаков/ЛогиныНаCsshxyz

друзья, важная просьба ко всем: укажите, пожалуйста свои данные и логин в cs-sh в форме выше
иначе я не смогу добавить вас в приватный репозиторий и, как следствие, выдать/проверить домашку

прошедшая в среду пара