Zig에서의 뉴타입 인덱스 패턴

matkladAboutLinksBlogroll

Zig에서의 뉴타입 인덱스 패턴

2025년 12월 23일

효율을 중시하는 코드에서는 포인터보다 인덱스를 사용하는 것이 관용적이다. 인덱스에는 몇 가지 장점이 있다.

첫째, 메모리를 절약한다. 보통 32비트 인덱스면 충분하므로, 64비트 아키텍처에서 포인터 하나당 4바이트를 아낄 수 있다. 이를 측정한 적은 없지만, 내 직감으로는 이 절약이 처음 생각하는 것보다 훨씬 영향이 크다. 현대 아키텍처에서는 메모리를 절약하는 것이 시간(과 에너지)도 절약하는데, 계산 자체보다 메모리와 CPU 사이의 비트 파이프가 병목인 경우가 자주 있기 때문이다. 조밀한 데이터 구조는 CPU 캐시를 더 효율적으로 사용하여, 메모리 접근의 금지 수준의 지연을 없앤다. 대역폭 절감은 더 좋다. 항목 크기가 작아지면 당연히 대역폭 활용이 좋아지고, 캐시에 더 많은 항목이 들어가면 애초에 대역폭을 사용할 필요가 줄어든다. 최상의 경우 작업 집합(working set)이 CPU 캐시에 들어간다!

메모리 절약이 고르게 퍼져 있다는 점도 유의하자. 인덱스를 사용하면 모든 데이터 구조가 조금씩 더 컴팩트해지며, 핫스팟 분포와 무관하게 전반적인 성능이 향상된다. 이런 절약 가능성은 프로파일러에서 알아차리기 어렵고, 실험으로 확인하기는 더 어렵다. 이런 두 가지 이유 때문에, 속도가 중요한 코드라면 아직 프로파일할 코드가 없더라도 기본값으로 인덱스를 선택하겠다!

또 인덱스가 메모리를 절약하는 더 미묘한 방식이 있다. 인덱스를 사용한다는 것은 여러 항목을 배열에 저장한다는 뜻인데, 이런 조밀 저장은 항목들의 상대적 위치에 추가 정보가 들어 있다. 항목 목록을 저장해야 한다면, 공유 저장소에 “가리키는” 범위를 저장하여 인덱스 목록을 실체화(materialize)하지 않아도 되는 경우가 많다. 가끔은 UTF-8 트릭처럼 리스트의 끝을 표시하는 데 단 1비트만 써도 된다.

둘째 장점은, 순환(cyclic) 및 재귀(recursive) 데이터 구조를 더 자연스럽게 모델링할 수 있다는 것이다. 사이클을 만든다는 것은 근본적으로 어딘가에 가변성이 필요하다(하스켈에서 “매듭을 묶는(tying the knot)” 기법도 지연 thunk의 가변성에 의존한다). 이는 일부 포인터를 nullable로 만들어야 한다는 뜻이고, 빌림 검사기 같은 것이 없어도 보통은 어색해진다. 사이클이 없고 단지 재귀만 있더라도, 포인터는 두 효과가 결합되며 문제가 된다:

• 포인터는 재귀 함수를 부추기고,
• 재귀 데이터 구조는 임의로 길 수 있는(하지만 유한한) 포인터 체인을 만든다.

작은 규모에서는 잘 동작하지만, 규모가 커지면 실서비스에서 매번 스택 오버플로로 실패하고, 어색한 우회책이 필요해진다. 예를 들어 rustc는 중첩된 매크로 확장으로부터의 오류 트레이스를 JSON 객체의 매우 깊게 중첩된 트리로 직렬화하는데, 출력 파싱 시 stacker 해킹을 써야 한다(그리고 이런 것은 매크로를 즐기는 사용자 손에서 크래시가 난 뒤에야 알게 된다).

마지막으로, 인덱스는 직렬화에 큰 도움이 된다. 데이터 구조를 공간을 가로질러(네트워크 메시지로 전송) 혹은 시간을 가로질러(디스크에 저장하고 나중에 읽기) 전달하는 것이 매우 쉬워진다. 인덱스는 본질적으로 재배치 가능(relocatable)해서 메모리의 어디에 있든 상관없다. 하지만 이것은 직렬화 이점의 절반일 뿐이다. 다른 절반은, 모든 것이 몇 개의 배열 안에 있으므로 벌크 직렬화가 가능하다는 점이다. 항목을 하나씩 쓰지 않아도 되고, 배열을 그대로 memcpy로 옮길 수 있다(다만 패딩을 통해 데이터가 누출되지 않도록 주의하고, 결과에 체크섬을 반드시 붙여라).

“순진한” u32 인덱스의 큰 문제는 당연히 잘못된 배열에 올바르지 않은 인덱스를 쓰거나, 그 반대로 하는 것이다. 여기서 표준적인 해결책은 원시 인덱스 주위를 newtype 래퍼로 감싸는 것이다. @andrewrk가 최근 Zig에서 이를 위한 멋진 “언어 설계의 행복한 우연(happy accident of language design)” 패턴을 대중화했다. 핵심 아이디어는 비소진(non-exhaustive) enum으로 인덱스를 정의하는 것이다:

zig
const ItemIndex = enum(u32) {
    _
};

---

Zig에서 enum은 Rust 스타일 ADT가 아니라(그건 union(enum)이 있다), 강하게 타입이 붙은 정수 상수들의 집합을 나타낸다. 기본적으로는 컴파일러가 backing 정수 타입을 고르지만, enum(u32) 문법으로 수동 지정할 수 있다:

const Color = enum(u16) { red, green, blue };

마지막으로 Zig는 _로 enum을 비소진으로 만들 수 있다. 비소진 enum에서는 어떤 수치 값이든 유효하며, 그중 일부에는 심볼릭 레이블이 붙는다:

zig
const FontWeight = enum(u16) {
    normal = 400,
    bold = 700,
    _,

    pub fn value(weight: FontWeight) u16 {
        return @intFromEnum(weight);
    }
}

test FontWeight {
    assert(FontWeight.value(.normal) == 400);

    const bold: FontWeight = @enumFromInt(700);
    assert(bold == .bold);
}

@intFromEnum과 @enumFromInt 빌트인은 원시 정수와 enum 값 사이에서 추상화 수준을 전환한다. 따라서,

zig
const ItemIndex = enum(u32) {
    _
};

는 “u32이지만, 구별되는 별개의 타입”이라고 쓰는 방법이다. 여기엔 강한 캡슐화 경계가 없다는 점에 유의하자. 누구나 @enumFromInt를 호출할 수 있다. Zig는 언어가 강제하는 캡슐화 메커니즘을 제공하지 않는다.

모든 것을 합치면, Zig에서 부모 포인터가 있는 n-항 트리를 나는 이렇게 모델링하겠다:

zig
pub const Tree = struct {
   nodes: []const Node.Data,

   pub const Node = enum(u32) {
       root = 0,
       invalid = std.math.maxInt(u32),
       _,

       pub const Data = struct {
           parent: Node, // .invalid는 부모가 없음을 의미.
           children: struct {
               index: u32,
               count: u32,
           },

           comptime {
               assert(@sizeOf(Data) == 12);
           }
       };
   };

   fn get(
       tree: *const Tree,
       node: Node,
   ) Node.Data {
       return tree.nodes[@intFromEnum(node)];
   }

   pub fn parent(
       tree: *const Tree,
       node: Node,
   ) ?Node {
       const result = tree.get(node).parent;
       return if (result == .invalid) null else result;
   }

   pub fn children(
       tree: *const Tree,
       node: Node,
   ) []const Node {
       const range = tree.get(node).children;
       return tree.nodes[range.index..][0..range.count];
   }
};

몇 가지 주목할 점:

• 인덱스를 쓸 때 늘 그렇듯, 먼저 집합 명사(collective noun)부터 정의한다. Node가 아니라 Tree를 먼저.
• 내 경험상 인덱스 타입에는 보통 Index 접미사가 없어도 된다. 그래서 Node는 기반 데이터가 아니라 그냥 enum(u32)다.
• 중첩 타입은 좋다! Node.Data는 딱 알맞은 느낌이다.
• 가독성을 위해, 순서는 필드 → 중첩 타입 → 함수로 한다.
• Node에는 심볼릭 상수를 몇 개 둔다. .root는 첫 번째에 저장되는 루트 노드를 위한 것이고, .invalid는 공격적 프로그래밍(offensive programming)을 적용해 잘못된 인덱스가 폭발하도록 만들고 싶을 때 쓴다. 여기서는 .invalid를 “null 부모”로 사용한다. 대안으로 ?Node를 쓸 수도 있지만 그러면 공간 낭비가 되거나, 또는 루트가 자기 자신을 부모로 갖게 만들 수도 있다.
• 성능이 중요하다면 다음처럼

zig
comptime
              assert

구조체의 크기를 확인하는 것이 좋다. 변경을 막기 위해서라기보다, 독자에게 구조체가 얼마나 큰지 설명하는 주석 같은 역할을 한다.

• 범위를 나타낼 때 index/count가 좋은지 start/end가 좋은지는 잘 모르겠지만, 나는 단지 이름 길이가 맞아 떨어져서 전자를 쓴다.
• API 형태로 tree.method(node)도, node.method(tree)도 모두 타당하다. 어느 쪽을 더 선호하는지는 모르겠다. 여러 node 인자가 있을 때도 동작한다는 점 때문에 나는 기본적으로 전자를 택한다.

P.S. 분명 예전에 이 글의 Rust 버전도 썼던 것 같다? https://matklad.github.io/2018/06/04/newtype-index-pattern.html

오타 수정구독연락하기matklad