단어당 11나노초, 애너그램 최적화에 미쳐버린 개발자
11 Nanoseconds per Word: Over-Optimizing Anagrams
Word Ladder 게임 변형을 풀려고 Rust로 솔버를 만든 저자는 기준 구현이 단어당 173나노초(총 31ms) 걸리자 최적화에 돌입한다. Vec 할당 제거, u128 문자 개수 패킹, FxHashMap 전환을 거쳐, 마지막에는 Scrabble 사전의 어떤 단어도 64비트를 넘지 않도록 소수를 알파벳에 영리하게 배정하는 Gödel 번호 방식으로 충돌 없는 식별자를 만들어 단어당 13나노초까지 끌어내린다.
우리는 (Scrabble) 단어의 글자 묶음에 대해 충돌 없는 정규 64비트 식별자를 찾아낸 것이다.