Rust는 niche value optimization (또는 niche filling이라고도 불립니다)을 사용하여 변종에서 비유효 비트 패턴을 포함하는 타입의 열거형에 대한 식별자 저장소를 제거합니다. **Option<&T>**의 경우, None 변종은 널 포인터 값으로 표현됩니다. 이것은 &T에 대해 유효하지 않은 비트 패턴입니다. 왜냐하면 참조는 항상 널이 아니어야 하기 때문입니다. 이를 통해 컴파일러는 포인터 자체 내에 암시적으로 식별자를 저장할 수 있어 **Option<&T>**가 정확히 하나의 기계 단어를 차지하게 됩니다. 이 최적화는 niche 값, 즉 NonZeroU32의 경우 0 또는 bool의 경우 0이나 1과 같은 유효하지 않은 비트 패턴이 있는 모든 타입에 적용됩니다. 또는 #[repr(C)] 구조체의 특정 센티넬 값과 같은 경우도 포함됩니다.
수백만 개의 노드를 처리하는 컴파일러를 위한 고성능 추상 구문 트리 (AST)를 개발하면서 우리는 부모 및 자식 포인터로 인해 심각한 메모리 압박을 겪었습니다. 각 노드는 부모, 좌측 자식 및 우측 자식에 대한 선택적 참조가 필요하며, 초기에는 **Option<Box<Node>>**로 구현되었습니다.
**Option<Box<Node>>**를 사용할 경우 64비트 시스템에서 포인터당 16바이트가 소모되었습니다. 이는 Box 포인터에 8바이트와 식별자 및 패딩에 8바이트가 필요하기 때문입니다. 1천만 개의 노드를 가진 트리의 경우 링크 포인터만으로 480메가바이트에 달하여 메모리 예산을 초과했습니다.
세 가지 접근 방식을 고려했습니다. 첫째, Option<Box<Node>>를 원시 포인터 (*mut Node)로 교체하여 None에 대해 널을 사용하는 방법입니다. 이 방법은 오버헤드를 제거했지만, 코드 전반에 걸쳐 unsafe 블록을 요구하게 되어 덩어리 포인터의 위험과 Rust의 안전 보장을 위반할 수 있었습니다. 둘째, 포인터 대신 인덱스를 사용하는 아레나 할당자를 사용했습니다 (usize). 캐시 친화적이긴 했지만, **Option<usize>**는 usize의 niche 부족으로 인해 여전히 16바이트가 필요했으며 인덱스 산술이 API를 복잡하게 만들었습니다.
셋째 접근법인 **Option<NonNull<Node>>**를 선택했습니다. 이는 안전한 ParentPtr 추상화로 감쌌습니다. **NonNull<T>**는 주소 0에서 niche를 보유하므로 **Option<NonNull<Node>>**는 8바이트를 유지할 수 있습니다. 우리는 메모리 안전성을 유지하면서 제로비용 추상화를 달성하기 위해 감싸는 메소드에 unsafe 역참조를 캡슐화했습니다. 이로 인해 AST의 메모리 발자국이 50% 줄어들어 256MB 제약 내에 맞게 조정되었습니다.
**Option<Option<bool>>**가 한 바이트를 유지하는 이유는 무엇인가요? 반면 **Option<Option<usize>는 16바이트까지 확장되는 이유는 무엇인가요?
bool은 유효한 비트 패턴이 0과 1밖에 없기 때문에 254개의 niche 값을 보유합니다. 첫 번째 Option 레이어는 None을 표현하기 위해 하나의 niche (예: 2)를 소모하여 253개의 나머지 niche를 남깁니다. 두 번째 Option 레이어는 또 다른 niche (예: 3)를 사용하여 None 변종을 만듭니다. 따라서 **Option<Option<bool>>**는 여전히 한 바이트 내에 들어갈 수 있습니다. 반대로 usize는 유효하지 않은 비트 패턴이 없기에 모든 2^64 값이 유효한 메모리 주소 또는 데이터입니다. niche가 없으면 **Option<usize>**는 식별자 바이트를 추가해야 하므로 16바이트 (데이터 8바이트, 정렬 8바이트)를 차지하게 됩니다. 중첩된 Option 레이어는 추가적인 niche가 없어서 더 최적화할 수 없기에 **Option<Option<usize>>**도 내부 식별자 논리와 함께 16바이트를 유지합니다.
왜 컴파일러는 #[repr(C)]로 표시된 열거형에 대한 niche 최적화를 거부하나요? 비록 페이로드 타입이 niches를 포함하고 있더라도 말입니다.
#[repr(C)] 속성은 고정된 필드 순서와 예측 가능한 오프셋에서의 명시적인 식별자 저장소를 갖는 C 호환 메모리 레이아웃을 보장합니다. C 언어 표준은 페이로드 데이터와 중복되는 식별자 값을 지원하지 않으며, 식별자는 FFI 호환성을 보장하기 위해 전용 메모리 위치에 있어야 합니다. **NonNull<T>**와 같은 구조체는 niche를 포함할 수 있지만 (null pointer), #[repr(C)] 열거형은 외부 C 코드가 고정된 오프셋에서 별도의 식별자 값을 읽기를 기대하므로 이를 식별자와 중첩하여 사용하지 못합니다. 이 제약 사항은 메모리 효율성을 저하시키면서 상호 운용성을 보장하며, #[repr(C)] 하에서 **sizeof(Option<&T>)**가 **sizeof(&T) + sizeof(discriminant)**와 같게 만듭니다. 이는 일반적으로 16바이트가 됩니다.
std::mem::discriminant는 명시적인 식별자 저장소가 메모리에 없는 타입에 대해 어떻게 작동합니까?**
std::mem::discriminant는 기본 메모리 표현과 관계없이 열거형 변종을 고유하게 식별하는 불투명한 Discriminant<T> 값을 반환합니다. **Option<&T>**의 경우, 컴파일러는 포인터 값을 검사하여 식별자를 파생하는 코드를 생성합니다. 즉, 포인터가 널이 아닌 경우에는 Some을 나타내는 상수를 반환하고, 널인 경우에는 None을 나타내는 상수를 반환합니다. 식별자 태그를 별도의 메모리 위치에 저장하지 않지만, Discriminant 타입은 이 계산을 추상화하여 **==**를 통해 변종 비교를 할 수 있게 해 주며, niche 인코딩 세부정보를 노출하지 않습니다. 이는 discriminant가 물리적 메모리 레이아웃이 아닌 의미론적 변종 식별성에 따라 작동함을 보여주며, 최적화된 열거형 표현과 비최적화된 열거형 표현 모두에서 일관된 동작을 가능하게 합니다.