単語あたり11ナノ秒、アナグラム探索を極限まで最適化する

11 Nanoseconds per Word: Over-Optimizing Anagrams

Word Ladderのアナグラム変異に対応するため、Dave AndersenがRustでアナグラム辞書の構築を最適化した記録。文字列ソートによる素朴な実装は1語173ナノ秒だったが、Vec確保の排除、文字カウントのu128パック、rustc_hashへの切り替えを経て、各文字に素数を割り当てたゲーデル数方式で衝突のない64ビット識別子を実現。最終的に1語13ナノ秒まで高速化した。