Post #210

Я тут писал про оптимальное нахождение коротких и хороших хэш функций. В общем, после моих страданий мы нашли хэш функцию (коммит в abseil), которая * Быстрее процентов на 20, чем мы имели в absl::Hash * Работает на входных данных от 9 до 16 байт * Проходит так же SMHasher, что и предыдущая с исключением очень sparse inputs Мы побенчмаркали на больших бинарях и не увидели никаких проблем в проде. Так вот, одно дело поменять хеш функцию, другое дело найти её. Чтобы её найти, мы с Deepmind очень много поработали. Идея была такая: загрузить много входных данных с SMHasher, микробенчмарков. Загрузить очень похожие на входные -- буквально поменять 1-2 битика. Дальше взять эти входные данные, загрузить в AlphaZero инструкции x86, описать правила игры в ассемблер, дать оптимизировать количество коллизий и latency. В итоге сработало и не очень следующее: 1. Считать количество коллизий на обычные 64 бита дало плохие результаты. Плохие в том плане, что AlphaZero любило находить хэш функции, которая не меняет нижние биты или верхние 32. В итоге стоило считать коллизии верхних/нижних 32 бит, нижних 16 и 8. После этого стало получше. 2. Запретить агенту играть с инструкциями по типу crc32, потому что из них получаются хорошие 32 битные хеши, но не 64. В целом всё, дальше агент нашёл несколько вариантов. Мы посмотрели, побенчмаркали. Очень много времени убили, чтобы просто запустить эту махину, потому что по памяти промахиваться нельзя, странные load операции нельзя и тд. AlphaZero реально полюбила трюк с умножением и xor двух частей умножения 64x64->128 бит. Не думаю, что такой подход (ML-based assembly generation) полюбится комьюнити, да и результат объяснить сложно. Плюс ещё тут функция оптимизации полегче. В целом так как нашим business needs удовлетворяет, мы себе и оставим пока не увидим проблем. Философский вывод для меня был в том, что AlphaZero легче научить играть в шахматы, чем писать ассемблер. В целом, с людьми так же. Для 9-16 байт была имплементация, которая умножала два раза. Новая имплементация от AlphaZero получилась только с одним: uint64_t lo = UnalignedLoad64(p); uint64_t hi = UnalignedLoad64(p + len - 8); lo = rotr(lo, 53); // right rotate by 53 state += kConstantPrime; lo += state; state ^= hi; uint128 mul = static_cast<uint128>(state) * lo; return static_cast<uint64_t>(mul) ^ (mul >> 64); https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e