Я тут писал про оптимальное нахождение коротких и хороших хэш функций. В общем, после моих страданий мы нашли хэш функцию (коммит в 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 получилась только с одним:
https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e
* Быстрее процентов на 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