11나노초로 단어 하나씩 처리하기: 아나그램 검색 과도하게 최적화하기

데이비드 G. 앤더슨(David G. Andersen)은 스크래블 사전의 178,690개 단어에서 아나그램을 찾는 코드를 최적화해 처리 시간을 31밀리초에서 1.96밀리초로 줄였다. 글의 측정 환경은 MacBook Pro M1이며, 최종 방식은 기준 구현보다 15.8배 빨랐다.

앤더슨은 단어 사다리 게임의 변형을 풀기 위해 solver를 만들었다. 이 게임에서는 한 글자를 바꾸거나 더하거나 빼는 것뿐 아니라 글자 순서를 바꿔 아나그램을 만드는 것도 허용된다. 그는 사전의 모든 아나그램을 미리 찾는 작업을 대상으로 최적화했다. 특정 단어의 아나그램만 찾는다면 더 단순한 해시 테이블로 충분할 수 있다고 덧붙였다.

기준 구현은 각 단어의 글자를 정렬해 문자열 키를 만들고, 해시 테이블에 단어를 묶었다. 이 방식은 31밀리초, 단어당 173나노초가 걸렸다. 이후 동적 메모리 할당을 줄이는 자료구조를 적용해 20밀리초로 줄였고, 글자 수를 u128에 압축해 저장하면서 5.6밀리초까지 단축했다.

rustc_hash의 FxHashMap으로 바꾼 뒤에는 4.1밀리초가 걸렸다. 다음으로 각 알파벳에 소수를 배정하고 단어에 들어 있는 소수들을 곱해 64비트 식별자를 만들었다. 소수 배정은 스크래블 사전의 단어에서 오버플로가 나지 않도록 조정했다. 이 방식으로 처리 시간은 2.6밀리초가 됐다.

앤더슨은 단어를 5비트씩 담은 u128 표현과 두 개의 누산기를 사용하는 명령어 수준 병렬화(instruction-level parallelism)를 더해 2.3밀리초를 기록했다. 마지막으로 분기문을 없앤 고정 길이 반복과 자동 벡터화를 적용해 1.96밀리초까지 줄였다.

  • 기준 구현: 31밀리초, 단어당 173나노초
  • 최종 구현: 1.96밀리초, 단어당 10.9나노초, 기준보다 15.8배 빠름

이 결과는 글에 제시된 스크래블 사전과 측정 환경에 한정된다. 앤더슨은 다음 글에서 찾아낸 아나그램을 활용해 단어 사다리 문제 전체를 푸는 방법을 다루겠다고 밝혔다.

부록: 원문 예시

text
letter_count("spot") -> "[... o:1, p: 1, s: 1, t:1 ...]"
text
for word in dictionary:
 table[letter_sort(word)] += word
text
"opst" : ["spot", "post", "tops", "stop"]
text
fn anagram_dictionary(words: &[String]) -> HashMap<String, Vec<String>> {
 let mut anagrams: HashMap<String, Vec<String>> = HashMap::new();
 for word in words {
 let key: Vec<u8> = word.bytes().sorted().collect();
 let key = String::from_utf8(key).expect("dictionary words must be ASCII");
 anagrams.entry(key).or_default().push(word.clone());
 }
 anagrams
}
text
heads: HashMap::<K, u32>,
 next: Vec<u32>,
 word: Vec<u32>
text
fn u128_lettercount(words: &[String]) -> KeyGroups {
 let items = words.iter().enumerate().map(|(idx, word)| {
 let mut lettercount = 0u128;
 for letter in word.bytes() {
 lettercount += 1u128 << ((letter - b'A') as u32 * 4);
 }
 (lettercount, idx as u32)
 });
 KeyGroups::new(words.len(), items)
}
text
const LETTER_PRIMES: [u64; 26] = [
 5, 61, 37, 53, 2, 71, 47, 41, 3, 101, 73, 23, 59, 19, 7, 43, 97, 11, 17, 29, 31, 89, 67, 83, 13, 79, ];
text
fn prime_anagramdict(words: &[String]) -> KeyGroups {
 let items = words.iter().enumerate().map(|(idx, word)| {
 let mut product = 1u64;
 for letter in word.bytes() {
 product = product.wrapping_mul(LETTER_PRIMES[(letter - b'A') as usize]);
 }
 (product, idx as u32)
 });
 KeyGroups::new::<FxBuildHasher, _>(words.len(), items)
}
text
fn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {
 let items = packed_words.iter().enumerate().map(|(idx, &packed)| {
 let mut even = 1u64;
 let mut odd = 1u64;
 let mut rest = packed;
 while rest != 0 {
 even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);
 odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);
 rest >>= 10;
 }
 (even.wrapping_mul(odd), idx as u32)
 });
 KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)
}
text
fn packed_prime_product(packed: u128) -> u64 {
 debug_assert!(packed >> 80 == 0, "word longer than 16 letters");
 let mut even = 1u64;
 let mut odd = 1u64;
 let mut rest = packed;
 for _ in 0..8 {
 even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);
 odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);
 rest >>= 10;
 }
 even.wrapping_mul(odd)
} 

fn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {
 let products: Vec<u64> = packed_words.iter().map(|&p| packed_prime_product(p)).collect();
 let items = products.iter().enumerate().map(|(idx, &product)| (product, idx as u32));
 KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)
}