Rust의 Hash/Hasher 추상화가 실제 빠른 블록 단위 해싱과 어떻게 맞지 않는지, 그리고 그로 인해 발생하는 성능 문제와 설계상 한계를 사례와 벤치마크, 코드 생성 관찰을 통해 분석하고 대안을 모색합니다.
파이썬, 자바, C++ 같은 언어에서는 값의 타입 작성자가 구현한 “나를 해시해” 메서드를 호출해 해시합니다. 이 고정 크기 해시는 바로 해시 테이블 등에서 사용됩니다. 이 설계에는 몇 가지 명백한 문제가 있습니다.
정수를 어떻게 해시할까요? 아무 것도 하지 않는 해셔를 쓰면(부우우), 해시 테이블에 DoS 공격이 필연적입니다. 반대로 정수를 충분히 강하게 해시하면, 동등성 비교 최적화를 위해 해시만 캐시하는 소비자들은 성능을 잃습니다.
해시를 어떻게 섞을까요? 할 수 있는 선택지는:
x ^ y 같은 끔찍한 믹서를 각자 발명할 겁니다. 둘 다 의사난수라서 뭐가 문제겠냐고요? 하하.a * x + y. 그런 다음 사람들이 mix(mix(x, y), z) 대신 mix(x, mix(y, z))를 써서 CVE가 터집니다.입력 데이터가 이미 랜덤이라면? 사이클만 낭비하는 겁니다.
해시 값에 대해 어떤 보장을 제공하나요?
해시 함수가 시드가 있나요?
Rust는 책임을 분리함으로써 이런 실수들로부터 배웠습니다.
Hash 트레이트를 구현하여, 자신의 기저 데이터를 Hasher에 써 넣을 수 있습니다.Hasher 트레이트를 구현하여, Hash 객체들이 써 넣은 데이터를 해싱합니다.객체는 구조화된 데이터를 정수 스트림으로 바꿔 주고; 해셔는 그 스트림을 숫자 해시로 바꿉니다.
겉보기에는, 이건 좋은 해법입니다.
Hash 구현을 바꾸지 않고도 빠른 단순 해셔를 쓸 수 있습니다.실제로도 이게 최적이고 빠른 해싱을 가능하게 해 줄까요?
Hasher API를 보죠:
pub trait Hasher {
// Required methods
fn finish(&self) -> u64;
fn write(&mut self, bytes: &[u8]);
// Provided methods
fn write_u8(&mut self, i: u8) { ... }
fn write_u16(&mut self, i: u16) { ... }
fn write_u32(&mut self, i: u32) { ... }
fn write_u64(&mut self, i: u64) { ... }
fn write_u128(&mut self, i: u128) { ... }
fn write_usize(&mut self, i: usize) { ... }
fn write_i8(&mut self, i: i8) { ... }
fn write_i16(&mut self, i: i16) { ... }
fn write_i32(&mut self, i: i32) { ... }
fn write_i64(&mut self, i: i64) { ... }
fn write_i128(&mut self, i: i128) { ... }
fn write_isize(&mut self, i: isize) { ... }
fn write_length_prefix(&mut self, len: usize) { ... }
fn write_str(&mut self, s: &str) { ... }
}
이 API는 다항식 해시 같은, 이른바 “스트리밍 해시”에 맞춰져 있습니다. 하지만 암호화와 마찬가지로, 요즘 해싱은 블록 단위입니다.
블록 해시는 내부 상태를 가지고, 고정 길이의 입력 블록을 반복적으로 “흡수”합니다. 데이터가 끝나면 마지막 블록은 길이로 패딩해 역시 고정 길이 블록으로 흡수합니다. 그 다음 최종화 단계에서 내부 상태를 64비트(혹은 용례에 따라 그 이상)로 축약합니다.
SHA-2와 많은 다른 암호학적 해시들이 이렇게 동작합니다. 놀랍게도 SMHasher 목록의 상위 해시들도 모두 같은 방식을 씁니다.
블록 방식은 스트리밍 방식보다 객관적으로 우수합니다. 가능한 한 많이 한 번에 소비하면, 아발란치 비용의 평균이 줄어들고, 스트리밍 해시가 달성할 수 있는 것보다 더 안전하면서도 더 빠른 해시 함수가 가능해집니다. 블록 단위 해시는 레이턴시도 더 낮습니다. 레이턴시가 스트림 입력마다가 아니라 블록마다 누적되기 때문이죠.
Hasher API는 블록 해시에 맞추려는 노력이 전혀 없습니다. 해셔는 데이터의 길이나 구조를 통지받지 않습니다. 해셔는 항상 “u8 하나만 더” 흡수할 수 있어야 합니다. 진짜로요, 브로, 약속함. 이걸 처리할 수 있는 방법은 둘뿐입니다.
두 접근법의 문제를 보죠.
아주 단순한 블록 해시를 생각해 봅시다.
fn absorb(state: &mut u64, block: &[u8; 8]) {
let block = u64::from_ne_bytes(*block);
*state = state.wrapping_mul(K).wrapping_add(block);
}
이건 그냥 곱셈 해시입니다. FNV-1과 비슷하지만, 한 번에 1바이트 대신 8바이트를 소비하죠.
이제 이 해시로 32비트 정수 두 개를 해시하면 어떻게 될까요? 패딩하면 곱셈이 두 번 일어납니다. 한 번이면 될 일을요. 처리량은 반 토막, 레이턴시는 증가.
실용적인 해시들은 훨씬 더 큰 블록을 씁니다. rapidhash는 상태가 24바이트이고 한 번에 48바이트를 흡수합니다. ahash는 상태가 48바이트이고 64바이트 블록을 흡수합니다. meowhash는 상태가 128바이트이고 256바이트를 흡수합니다. (제가 커널을 잘 아는 해시라 이 셋을 예로 들었을 뿐, 다른 해시들도 유사한 설계를 가집니다.)
이들은 전 세계에서 가장 빠른 비암호학적 해시들입니다. 8바이트 입력을 48, 64, 256바이트로 패딩해 성능을 폭파시키고 싶나요? 아마 아니겠죠.
좋아요, 그럼 편법을 써서, 해시 함수를 “작은” 데이터를 전체 블록을 흡수하는 것보다 더 효율적으로 흡수하도록 바꾸면 어떨까요?
이를테면, rapidhash 커널은 사실상 이렇습니다:
fn absorb(state: &mut [u64; 3], seed: &[u64; 3], block: &[u64; 6]) {
for i in 0..3 {
state[i] = mix(block[i] ^ state[i], block[i + 3] ^ seed[i]);
}
}
독립적인 반복이 셋이니, 분명히 더 작은 64비트 블록은 이렇게 흡수할 수 있겠죠?
fn absorb_64bit(state: &mut [u64; 3], seed: &[u64; 3], block: u64) {
state[0] = mix(block ^ state[0], seed[0]);
}
이러면 6배 느려지던 게 적어도 2배 수준으로는 줄 거라구요, 그렇죠?
rapidhash가 애초에 왜 세 개의 독립 체인을 쓰는 걸까요? 맞아요, 레이턴시!
mix는 최신 x86에서 레이턴시가 5틱이지만, 스루풋은 1입니다. 체인 독립성 덕분에 16바이트 블록을, 이전 16바이트가 섞이는 걸 기다리지 않고 소비할 수 있습니다. 방금 그 최적화를 내다 버렸네요.
좋아요, 그러니까 패딩은 끔찍한 아이디어입니다. 버퍼를 모았다가 내보낼 수 있을까요? SMHasher에서 이 접근을 택한 Rust 구현을 하나 찾기까지 스크롤을 얼마나 해야 했는지는 이미 경고음입니다.
제가 찾은 구현은 예상대로 Vec<u8>을 저장하고, finish에서 기저 해셔에 전달합니다. 해시 함수에서 할당한다는 게 왜 그리 밝은 생각이 아닌지는 굳이 설명할 필요가 없겠죠.
또 다른 구현은 고정 크기 버퍼를 저장합니다. 어라, if와 for가 잔뜩 보이네요. Godbolt가 뭐라고 할지 궁금합니다. 아주 단순한 걸 시도해 봅시다.
struct StreamingHasher {
block_hasher: BlockHasher,
buffer: [u8; 8],
length: usize,
}
impl StreamingHasher {
fn write(&mut self, input: &[u8]) {
// 입력이 버퍼의 남은 공간에 다 들어가면 그냥 복사한다.
let rest = unsafe { self.buffer.get_unchecked_mut(self.length..) };
if input.len() < rest.len() {
rest[..input.len()].copy_from_slice(input);
self.length += input.len();
return;
}
// 아니면, 들어가는 만큼 복사하고 청크를 해시한다.
let (head, tail) = input.split_at(rest.len());
rest.copy_from_slice(head);
self.block_hasher.feed(self.buffer);
// 나머지 입력을 블록들로 나눠 개별적으로 해시하고, 마지막 것은 버퍼로 옮긴다.
let chunks = tail.array_chunks();
let remainder = chunks.remainder();
self.buffer[..remainder.len()].copy_from_slice(remainder);
self.length = remainder.len();
for chunk in chunks {
self.block_hasher.feed(*chunk);
}
}
}
펼치기
이게 _좋은 코드_로 컴파일되겠죠? :ferrisClueless:
이 해셔에 바이트 1개(정확히 1)를 쓰면 다음처럼 컴파일됩니다.
write_u8:
push r15
push r14
push r13
push r12
push rbx
sub rsp, 16
mov rbx, rdi
mov byte ptr [rsp + 15], sil
mov r14, qword ptr [rdi + 16]
add rdi, r14
add rdi, 8
cmp r14, 6
ja .LBB0_2
mov byte ptr [rdi], sil
mov r14, qword ptr [rbx + 16]
inc r14
jmp .LBB0_3
.LBB0_2:
lea r15, [rbx + 8]
mov edx, 8
sub rdx, r14
lea r12, [rsp + rdx]
add r12, 15
add r14, -7
lea rsi, [rsp + 15]
mov r13, qword ptr [rip + memcpy@GOTPCREL]
call r13
movabs rax, 5512829513697402577
imul rax, qword ptr [rbx]
add rax, qword ptr [rbx + 8]
mov qword ptr [rbx], rax
mov rsi, r14
and rsi, -8
add rsi, r12
mov rdi, r15
mov rdx, r14
call r13
.LBB0_3:
mov qword ptr [rbx + 16], r14
add rsp, 16
pop rbx
pop r12
pop r13
pop r14
pop r15
ret
펼치기
와우, 무슨 일이죠? 맞아요, 바로 copy_from_slice입니다! LLVM은 가변 길이 복사를 memcpy 말고는 어떤 것으로도 컴파일할 수 없습니다. 반복 횟수에 상한이 보장된 루프를 직접 썼다고요? 안타깝지만 그것도 memcpy 구멍으로 들어갑니다.
그래서 야생의 크레이트들은 이걸 잘못 처리합니다. 그럼 표준 Rust 해셔는 어떻게 처리할까요? 아예 write_*를 정의하지 않습니다. 설계적으로요. 이 중요한 최적화가 컴파일 타임을 조금 늘리기 때문이라네요. 그…렇군요.
siphasher _크레이트_는 그래도 짧은 길이의 memcpy를 비트 연산으로 최적화합니다. 한 번 써 봅시다.
fn write(&mut self, input: u64, input_len: usize) {
assert!(input_len <= 8);
if input_len != 8 {
assert!(input >> (8 * input_len) == 0);
}
// 들어가는 만큼은 버퍼에 즉시 소비한다.
let old_length = self.length;
self.buffer |= input << (8 * self.length);
self.length += input_len;
// 오버플로가 나면, 버퍼를 블록 해셔에 먹이고 꼬리로 버퍼를 초기화한다.
if self.length > 8 {
self.block_hasher.feed(self.buffer);
self.buffer = input >> (8 * (8 - old_length));
self.length -= 8;
}
}
write_u8:
mov rax, qword ptr [rdi + 16]
movzx ecx, sil
lea edx, [8*rax]
lea rsi, [rax + 1]
shlx rdx, rcx, rdx
or rdx, qword ptr [rdi + 8]
mov qword ptr [rdi + 8], rdx
mov qword ptr [rdi + 16], rsi
cmp rsi, 9
jb .LBB0_2
movabs rsi, 5512829513697402577
imul rsi, qword ptr [rdi]
add rsi, rdx
mov edx, eax
add rax, -7
neg dl
mov qword ptr [rdi], rsi
shl dl, 3
shrx rcx, rcx, rdx
mov qword ptr [rdi + 8], rcx
mov qword ptr [rdi + 16], rax
.LBB0_2:
ret
펼치기
이건 좀 낫나요? 이제 Rust가 하듯 (u8, u8)을 해시해 봅시다.
#[no_mangle]
fn write_u8_pair(&mut self, pair: (u8, u8)) {
self.write(&[pair.0]);
self.write(&[pair.1]);
}
write_u8_pair:
mov r8, qword ptr [rdi + 16]
movzx r9d, sil
movabs rax, 5512829513697402577
lea ecx, [8*r8]
shlx rsi, r9, rcx
or rsi, qword ptr [rdi + 8]
lea rcx, [r8 + 1]
cmp rcx, 9
jb .LBB1_2
mov rcx, qword ptr [rdi]
imul rcx, rax
add rcx, rsi
mov qword ptr [rdi], rcx
mov ecx, r8d
add r8, -7
neg cl
shl cl, 3
shrx rsi, r9, rcx
mov rcx, r8
.LBB1_2:
lea r8d, [8*rcx]
movzx edx, dl
shlx r8, rdx, r8
or r8, rsi
lea rsi, [rcx + 1]
mov qword ptr [rdi + 8], r8
mov qword ptr [rdi + 16], rsi
cmp rcx, 8
jb .LBB1_4
imul rax, qword ptr [rdi]
add rax, r8
mov qword ptr [rdi], rax
mov eax, ecx
add rcx, -7
neg al
shl al, 3
shrx rax, rdx, rax
mov qword ptr [rdi + 8], rax
mov qword ptr [rdi + 16], rcx
.LBB1_4:
ret
펼치기
와우. 참 우아하네요. 뭐가 잘못됐을까요?
돌이켜 보면 이유는 자명합니다. 첫 번째 쓰기가 버퍼를 끝까지 채우면 두 쓰기가 “찢어질” 수 있습니다. 옵티마이저는 둘을 합칠 수 있다고 눈치채지 못하니, 이런 기괴한 결과를 얻습니다.
좀 더 일반적으로, 문제는 write_* 메서드가 버퍼의 현재 상태를 예측할 수 없다는 데 있습니다. 그래서 분기와 가변 인덱스 접근을 소거할 수 없습니다. 그럼 write가 상태를 고정된 것으로 강제하면 어떨까요? 음, 그건 데이터를 전체 블록으로 패딩하는 것과 같습니다. 으엑.
좋아요, 그런데 제 말 좀 들어 보세요. 분명히 hash와 write_* 호출이 인라인되면 상태를 예측할 수 있지 않을까요? 자, 여기:
fn hash_u8_pair(pair: (u8, u8)) -> u64 {
let mut hasher = Self::new();
hasher.write_u8(pair.0);
hasher.write_u8(pair.1);
hasher.finish()
}
hash_u8_pair:
movzx eax, sil
movzx ecx, dil
shl eax, 8
or eax, ecx
ret
좋은 주장입니다만, 변수 길이 컬렉션을 소개해 드리죠. Vec<T>는 길이를 쓰고, 그 다음 원소를 하나씩 해시해 나갑니다. 원소 해싱이 벡터화된다고 하더라도(안 됩니다, LLVM은 바보예요), 이 변수 길이 컬렉션 뒤에 오는 건 어떤 것도 효율적으로 해시할 수 없습니다.
분명히 누군가 이미 이 문제를 생각했겠죠? 정수 슬라이스가 어떻게 해시되는지 보세요.
#[inline]
fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
let newlen = mem::size_of_val(data);
let ptr = data.as_ptr() as *const u8;
// SAFETY: `ptr` is valid and aligned, as this macro is only used
// for numeric primitives which have no padding. The new slice only
// spans across `data` and is never mutated, and its total size is the
// same as the original `data` so it can't be over `isize::MAX`.
state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
}
이건 좋습니다.
한편 뉴타입들은 구석에서 울고 있죠. #[derive(Hash)]가 이 최적화를 그들에게(혹은 다필드 구조체와 튜플에도) 적용하지 않기 때문입니다. 표준 해셔는 오늘날에도 가능한 것보다 2.5배나 나쁜 코드를 사용하고, 그 결과 당신의 명령어 캐시에 불필요하게 많은 공간을 차지하게 됩니다.
몇 가지 코드를 벤치마크해 볼까요?
use std::any::type_name;
use std::hash::{DefaultHasher, Hash, Hasher};
use std::time::Instant;
fn time<T: Hash>(obj: T) {
let start = Instant::now();
let mut hasher = DefaultHasher::new();
obj.hash(&mut hasher);
let h = hasher.finish();
println!("{}: {:?} (-> {h:0x})", type_name::<T>(), start.elapsed());
}
#[derive(Hash)]
struct NewType(i32);
fn main() {
let n = 100000000;
time((0..n).collect::<Vec<i32>>());
time((0..n).map(NewType).collect::<Vec<NewType>>());
}
[i32]를 해시하면 슬라이스를 [u8]로 트랜스뮤트하고 write를 한 번만 호출합니다. 반면 [NewType]을 해시하면 원소를 하나씩 해시합니다. 즉, 이 벤치마크는 개별 호출의 비용을 측정합니다. 또한 거의 400MiB의 메모리를 해시한다는 점에 주목하세요. 캐시에 들어가지 않아서, 몇몇 비효율이 가려질 수도 있습니다. 제가 관대해진 셈이죠.
alloc::vec::Vec<i32>: 117.756736ms (-> 1984796e743a33f5)
alloc::vec::Vec<ruined_portal::NewType>: 469.774204ms (-> 1984796e743a33f5)
헉, 말 그대로 1984.
정확히 같은 해시를 계산하는데도 5배 더 느립니다. siphasher 크레이트를 써 봅시다.
alloc::vec::Vec<i32>: 196.330253ms (-> 95697c476562afec)
alloc::vec::Vec<ruined_portal::NewType>: 243.031408ms (-> 95697c476562afec)
이건 낫네요. 그래도 25% 차이는 여전히 으으. 다만 이건 암호학적 해시라 블록 해시 시간이 많이 듭니다. 비암호학적 해시에서는 차이가 더 벌어질 겁니다.
rapidhash:
alloc::vec::Vec<i32>: 54.224434ms (-> 1908e25736ad8479)
alloc::vec::Vec<ruined_portal::NewType>: 278.101368ms (-> 949efa02155c336a)
ahash:
alloc::vec::Vec<i32>: 56.262629ms (-> 217325aa736f75a8)
alloc::vec::Vec<ruined_portal::NewType>: 177.900032ms (-> 4ae6133ab0e0fe9f)
highway:
alloc::vec::Vec<i32>: 53.843217ms (-> f2e68b031ff10c02)
alloc::vec::Vec<ruined_portal::NewType>: 547.520541ms (-> f2e68b031ff10c02)
상태가 좋지 않습니다. 모든 해셔가 Vec<i32>에서는 거의 같은 성능을 보인다는 점에 주목하세요. 이건 RAM 속도에 가깝습니다. 캐시에 들어가는 작은 배열에서는 차이가 더 두드러집니다. (검증은 안 했지만, 제가 방에서 제일 똑똑하니 당연히 맞겠죠.)
제가 진짜 원하는 건, 대부분의 실용적 용례에 충분히 좋고, DoS에도 어느 정도 강하지만 꼭 암호학적일 필요는 없는 범용 해시입니다. 짧은 입력에서 빨라야 하므로, “진짜” 블록 해시일 수는 없고 rapidhash에 가까운 무언가여야 합니다.
우리가 원하는 건:
consume(a,x,y)=mix(x⊕︎a,y⊕︎C).
그렇죠, Rust는 이걸 지원하지 않습니다. 좋아요, 구현이 더 쉬울 법한 또 다른 비교적 잘 알려진 스킴을 시도해 봅시다. 병렬적이니 분명 도움이 될 겁니다?
64비트 워드 시퀀스 (x 1,…,x 2 n)를 해시하려면,
mix(x 1⊕︎a 1,x 2⊕︎a 2)+⋯+mix(x 2 n−1⊕︎a 2 n−1,x 2 n⊕︎a 2 n),
를 계산합니다. 여기서 (a 1,…,a 2 n)는 랜덤 데이터(가능하면 시드에서 한 번 생성)이고,
mix(x,y)=(x⋅y mod 2 64)⊕︎(x⋅y d i v 2 64).
이는 잘 알려진 프리미티브들의 UMAC식 결합입니다. 문제는 a i를 미리 계산해 두어야 한다는 겁니다. 고정 길이 키(예: 정수들로 이루어진 구조체)에는 문제가 되지 않습니다. rustc 같은 곳에서 자주 쓰이는 거죠.
불행히도 Rust는 각 해셔에게, 길이가 서로 다른 경우를 포함한 모든 가능한 입력을 처리하도록 강제합니다. 그래서 이 스킴은 쓸 수 없습니다. 해셔는 해시되는 객체의 타입으로 파라미터화되어 있지도 않습니다. 64비트 정수 네 개가 잘 레이아웃되어 있어, 전체 폭 곱셈 두 번만으로 쉽게 섞을 수 있다고요? 아니요, write_u64가 브르르르릉——
저는 몇 달 동안 빠른 해시 기반 자료구조를 설계하다가, 해싱 성능 때문에 사실 빠르지 않다는 걸 깨달았습니다. C++과 파이썬에서 문제가 아닌 게 Rust에서도 문제가 아닐 거라고, 당연히 생각했거든요.
그러니까… 엄살 좀 부렸네요, 미안합니다.
자명한 전진 방향은 데이터의 구조를 다시 그림에 끌어오는 것입니다. 해셔가 고정 크기 데이터를 해시한다는 걸 알면 a i 접근법을 쓸 수 있습니다. 해셔가 배열을 해시한다는 걸 알면 개별 해시 계산을 벡터화할 수 있습니다. 해셔가 구조체의 필드 타입들을 안다면, 찢어짐을 방지하거나, 작은 필드들을 64비트 블록으로 효율적으로 합칠 수 있을 겁니다. 안타깝게도 해셔는 아무 것도 모릅니다…
제 생각에, Hasher와 Hash는 잘못된 추상화입니다. Hash가 Hasher를 미치게 모는 대신, 반대로 되어야 합니다. 즉 Hash는 내성(introspection) 기능을 제공하고, Hasher가 해시 대상 객체를 재귀적으로 순회해야 합니다. 보너스로 (옵트인) 이식성 있는 해셔도 가능해질 수 있습니다.
이 API가 어떤 모습이어야 하는지, 기존 인터페이스에 어떻게든 끼워 넣을 수 있을지는 지켜봐야 합니다. 저는 아직 설계를 시작하지도 않았고, 어쩌면 이 글이 시기상조일지도 모릅니다. 하지만 제가 정말 명백한 걸 놓쳤는지(혹은, 사실 Rust는 충분히 빠르고 아무도 신경 쓰지 않는지)에 대한 여러분의 생각을 듣고 싶습니다.
자바, C++, 파이썬이 택한 길도 문제점이 없지는 않다는 점을 짚고 싶습니다. 좋은 소식은, 곱(product) 타입의 필드들이 다른 필드 값과 무관하게 같은 방식으로 해시된다는 겁니다. 예컨대 (Vec<T>, U)를 해시할 때는 항상 U에 같은 해시를 적용하고, 그것을 Vec<T>의 해시와 섞습니다. Rust와 다르게요.
하지만 이 접근은 일반적으로 최적이 아닙니다. UMAC 예로 돌아가 봅시다. ((a,b),c)를 mix(mix(a,b),c)로 해시하면 필요 이상으로 레이턴시가 높습니다. mix(a,b)⊕︎mix(c,0)만으로 충분하거든요. 그런데 이 규칙을 일반적으로 mix(a,0)⊕︎mix(b,0)⊕︎mix(c,0)로 적용하면 역시 최적이 아닙니다.
이 기묘한 mix(a,b)/mix(a,0)의 이원성은, UMAC식 접근의 블록 크기가 최소 두 개의 64비트 워드인 반면 해시 값은 64비트이기 때문에 생깁니다. 더 큰 블록 크기에서는 이 구분이 훨씬 더 나빠집니다.
이 글이 게시된 후, 여러 분들이 특수화(specialization)를 보라고 조언해 주셨습니다. 이것도 문제를 해결하지 못하는 이유를 조금 더 얘기하고자 합니다.
특수화는 중첩 객체의 효율적인 해싱을 지원하지 못합니다. 비록 (u8, u8, u8, u8)은 write_u32로 해시하도록 특수화할 수 있지만, 다음 같은 타입에서는 복잡해집니다.
struct S {
a: (u8, u16),
b: u8,
}
이 타입을 직렬화(=해시용 선형화)하는 최선은 a의 패딩 바이트에 b를 끼워 넣는 것입니다. 레이아웃 단계에서는 할 수 없지만, 해싱에서는 가능합니다. 이걸 순수 특수화만으로 자동으로 해 내기는 매우 어렵고, 사람들이 Hash를 수동 구현한다면 거의 불가능합니다.
결론은 이겁니다. 곱 타입의 해싱이 효율적이려면 선형화되어야 합니다. 구조체로 이뤄진 구조체의 해싱은 _중첩 필드_를 고려해야만 합니다. 각 필드는 _정적인 인덱스_와 연계되어야 하며, 그래야 상수 풀의 상수, 블록 내 오프셋 등과 연결할 수 있습니다.
&[T]/Vec<T> 같은 가변 길이 필드 뒤에 저장되는 필드들도, 어쨌든 정적 인덱스를 가져야 합니다.
이 규칙은 배열에도 적용됩니다. [T; 2]를 T::hash를 두 번 호출해 해싱하는 건 비최적입니다. 그건 상수의 재사용을 낳고, 괜찮은 해시 품질을 위해 더 철저한 믹싱을 요구하게 되니까요.
이건 _슬라이스_에도 적용됩니다. [T] 해싱은 슬라이스를 고정 크기 청크로 나눈 다음, 각 청크를 하나의 블록으로 해시해야 합니다. API를 확장해 [T] 슬라이스에 대해 시작/끝 주석을 뿌리게 해도 역시 도움이 안 됩니다. 각 T 안의 필드 인덱스들도 예측 가능해야 하기 때문이죠. Hash for T가 단어 3개를 내보내고 블록 크기가 8단어라면, 정렬 불일치로 인해 끔찍하게 벡터화될 겁니다.
이 규칙들은 곱 타입에 적용되는 만큼, 합(sum) 타입에도 적용됩니다. Result<T, E>의 해싱은 h 1(ok) 또는 h 2(err)를 내야 하며, 여기서 h i는 서로 다른 해시 패밀리의 원소들입니다. 이건 판별자(discriminant)를 앞에 붙여 흉내낼 수는 있지만, 비최적입니다. 아마 더 분명한 예로, Option<T>는 값이 있을 때는 그 값을 해시하고, None일 때는 랜덤(하지만 정적) 상수를 돌려야 합니다.
이 규칙은 비원시 타입을 담은 객체에도 적용됩니다. 다음을 해시할 때를 보죠.
struct Key {
top: u64,
middle: u64,
low: u64,
meta: Option<String>,
}
meta가 None인 경우에는 [u64; 3]을 해시하는 것보다 느려서는 안 되며, Some인 경우에도 문자열이 짧다면 거의 그 수준이어야 합니다. 이건 마법이 아닙니다. Rust가 그 해법을 타입 시스템으로 표현할 수 없을 뿐이죠.