제너레이션 핸들과 잘 어울리는 풀 자료구조를 프리 리스트 없이 구현하는 방법을 비트셋과 tzcnt, 다단계 비트 배열로 설명한다.
2026-02-20
풀(pool) 같은 자료구조는 믿을 수 없을 정도로 실용적입니다. 특히 제너레이션 핸들(generational handles)과 결합하면 더 그렇죠. 재사용 가능한 아이템 슬롯들의 배열을 가질 수 있게 해주고, 더 중요한 점은 삽입, 삭제, 조회 같은 모든 동작이(버퍼를 미리 할당해 둔다는 가정 하에) 최악의 경우까지 포함해 항상 O(1) 이라는 것입니다!
슬롯 재사용 메커니즘을 구현하는 일반적인 방식은 현재 사용되지 않는 슬롯들의 어떤 “리스트”를 저장해 두는 것입니다. 이 리스트는 슬롯 인덱스를 담는 단순한 배열부터, intrusive/non-intrusive 단일 연결 리스트까지 여러 방식으로 구현할 수 있습니다. 약간의 메모리 오버헤드 차이를 제외하면 본질적으로는 다 비슷한 일을 합니다.
자료구조 내부는 대략 이렇게 생겼을 수 있습니다:
c1Pool :: struct($N: int, $T: typeid) { 2 data: [N]T, 3 next: [N]u32, // 아이템별 free list의 'next' 4 free: u32, // free list head 5 max: u32, // 사용된 슬롯의 최대 인덱스 6}
하지만 저는 최근 들어, 어떤 종류의 프리 리스트 기반 시스템도 쓰지 않는 완전히 다른 접근을 사용하고 있습니다. 이 방식은 몇 가지 좋은 성능 특성이 있습니다:
이 접근은 TLSF 메모리 할당기에서 영감을 받았지만, 개념적으로는 훨씬 단순해서 처음부터 구현하고 이해하기도 쉬울 겁니다.
프리 리스트 기반 풀에는 사람들이 잘 이야기하지 않는 이상한 특성이 있습니다. 어느 시점이 되면 슬롯 할당 패턴이 거의 무작위처럼 되어 버립니다.
하지만 프리 리스트를 전혀 사용하지 않는 대안적 접근도 있습니다. 최근 저는 다단계 비트 풀(multi-level bit pool)을 쓰고 있어요: pic.twitter.com/zx1zaoT0un
— Jakub Tomšů (@jakubtomsu_) February 23, 2026
아이디어는 간단히, 슬롯이 사용 중인지 아닌지를 나타내는 단 하나의 비트만 저장하는 것입니다. 우선 여기서 시작해 봅시다(나중에 많이 개선할 겁니다):
c1Pool :: struct($N: int, $T: typeid) 2 where N % 64 == 0 3{ 4 data: [N]T, 5 used: [N/64]u64, 6}
이 글의 나머지 부분에서는 모든 풀이 64의 배수 개수의 원소를 저장한다고 가정합니다.
물론 여기에는 치명적인 결함이 있습니다. 아이템이 수천 개만 되어도 개별 비트를 전부 훑어봐야 합니다.
각 used 필드의 64비트를 shr+mask+branch 같은 루프로 하나씩 검사하는 건 낭비입니다.
여기 tzcnt가 있습니다. trailing zero count의 약자로, x64 명령어이며 수년간 대부분의 소비자용 CPU에서 지원되어 왔습니다. 컴파일러 intrinsic 형태로 프로그래머에게 노출되어 있고, 사실상 한 사이클에 가장 낮은 위치의 1비트 인덱스를 찾아낼 수 있습니다.
똑똑한 최적화 컴파일러라면 작은 루프를 tzcnt 호출로 바꿔줄 수도 있겠지만, 직접 명시적으로 쓰면 무엇을 하는지 더 명확해지고 디버그 빌드에서도 빠르게 동작합니다.
Odin에서는
base:intrinsics패키지의count_trailing_zeros프로시저를 사용합니다. 이는 이 기능을 크로스 플랫폼으로 구현해 둔 것입니다.
단일 u64에서 빈 슬롯을 찾으려면 count_trailing_zeros(~used[index]) 를 호출하기만 하면 됩니다. 사용 중 마스크를 부정(~)해서 실제로는 뒤따르는 1(사용 중 슬롯들)을 세는 대신, 첫 번째 0(미사용) 비트의 인덱스를 찾는 셈입니다.
코드는 대략 이렇게 될 수 있습니다:
c1find_empty_slot :: proc(pool: $T/$Pool($N, $V)) -> (result: int, ok: bool) { 2 for i in 0..<N/64 { 3 bit := int(intrinsics.count_trailing_zeros(~pool.used[i])) 4 // 블록이 꽉 찼는지 확인 5 if bit != 64 { 6 return i * 64 + bit 7 } 8 } 9 // 풀이 가득 참 10 return 0, false 11}
좋습니다. 꽤 큰 개선이지만, 여전히 최악의 경우 N/64개의 u64를 모두 검색해야 합니다. 더 개선할 수 있을까요? 이 u64들 중 “꽉 차지 않은” 블록을 더 빨리 찾을 수는 없을까요?
답은 예입니다. 해결책은 더 작지만 또 하나의 비트 배열을 두는 것입니다. 기존 비트 배열이 슬롯마다 0/1을 저장한다면, 블록마다 1비트를 저장하는 배열을 하나 더 추가해 그 블록이 가득 찼을 때 1이 되게 할 수 있습니다.
최종 구조체는 대략 이렇게 됩니다. 여기서는 데이터 자체는 빼고 비트 풀 부분만 구현하겠습니다(제 코드에서도 이런 식으로 씁니다).
c1Bit_Pool :: struct($N: int) 2 where N % 64 == 0 3{ 4 // 64*64로 나눈 값을 올림 5 l1: [(N + 4095) / 4096]u64, 6 // 앞서의 'used' 배열 7 l0: [N / 64]u64, 8}
L1 배열의 각 원소는 L0의 64개 원소에 대한 정보를 저장합니다. 이 방식이면 tzcnt 한 번이 사실상 4096개의 슬롯을 검색하는 효과를 냅니다.
아래 그림의 화살표는 데이터 간의 암묵적 매핑을 보여줍니다:
data L0 L1
┌──────────┐ ┌──────┐ ┌────────┐
│0..63 │◄──┤0 │◄─────┤0 │
├──────────┤ ├──────┤ ├────────┤
│64..127 │◄──┤1 │ ┌──┤1 │
└──────────┘ ├──────┤ │ ├────────┤
│... │ │ │... │
┌──────────┐ ├──────┤ │ │────────│
│4032..4095│◄──┤63 │ │ │N/4096-1│
└──────────┘ └──────┘ │ └────────┘
┌──────────┐ ┌───────┐ │
│4096..8191│◄──┤64..127│◄─┘
└──────────┘ └───────┘
코드는 이렇게 됩니다. 루프가 있기 때문에 “이론적 점근 복잡도”는 여전히 N에 기반합니다. 하지만 실제로는 N이 꽤 작아서 이 루프가 몇 번만 돌거나, 또는 레벨을 더 추가해서 메모리 풋프린트에 대해 로그 스케일로 확장할 수 있습니다(각 추가 레벨마다 아주 작은 상수 오버헤드만 듭니다).
c1find_0 :: proc(bp: Bit_Pool($N)) -> (index: int, ok: bool) { 2 l0_index := N > 64 ? -1 : 0 // 작은 풀에서는 L1을 무시 3 // L1을 검색해서 적절한 L0 블록을 찾기 4 for used, i in bp.l1 { 5 l1_slot := int(intrinsics.count_trailing_zeros(~used)) 6 if l1_slot != 64 { 7 l0_index = 64 * i + l1_slot 8 break 9 } 10 } 11 12 if l0_index == -1 || l0_index >= (N / 64) { 13 return -1, false // 풀이 가득 참 14 } 15 16 // L0 블록 내부에서 실제 슬롯 찾기 17 l0_slot := int(intrinsics.count_trailing_zeros(~bp.l0[l0_index])) 18 if l0_slot != 64 { 19 return l0_index * 64 + l0_slot, true 20 } 21 22 return -1, false // 풀이 가득 참 23}
보시다시피, 이 방식은 항상 가장 낮은 인덱스부터 슬롯을 할당하는 “앞쪽 채우기(front loading)” 특성이 있습니다. 이는 특히 버스트처럼 한꺼번에 슬롯을 많이 할당하는 패턴에서 메모리 지역성 측면에서 아주 좋습니다. 일반적인 리스트 기반 풀은 값을 풀 전체에 흩뿌려 버릴 수 있으니까요!
생성되는 코드도 꽤 괜찮습니다. LLVM은 많은 경우 루프를 언롤하고 심지어 제거까지 할 수 있습니다. N = 8192인 경우를 보여주는 Godbolt 예제를 확인해 보세요.
전체 구현은 제 Raven 엔진의 일부로 Github에 올려두었습니다. 여기에는 실제로 비트를 설정하고 조회하는 프로시저들도 포함되어 있습니다.
N이 4096보다 훨씬 커진다면, 레벨을 더 추가하는 건 정말 trivial합니다. 모든 경우에 여전히 O(1)입니다. 제가 그렇게 하지 않는 이유는 제 풀들이 대체로 비교적 작아서 많아야 수만 개 아이템 정도이기 때문입니다.
예를 들어 l2 비트 배열을 추가하면 tzcnt 한 번이 사실상 64^3(262144)개의 슬롯을 검색하는 효과를 내게 됩니다. 슬롯이 엄청나게 많죠.
이 블록 기반 접근은 SIMD AoSoA(배열들의 구조체들의 배열, arrays of structures of arrays)에 잘 맞습니다.
L0 마스크가 빈 슬롯을 결정하는 “근거(ground truth)”인데, packed된 원소들의 비트마스크이기 때문에 SIMD 연산 마스크나 비슷한 용도로 쓸 레이아웃과 정확히 일치합니다.
저는 여러 겹의 제네릭 컨테이너로 모든 걸 감싸기보다는, 자료구조를 단순하게 유지하는 걸 꽤 좋아합니다. 아래는 파티클 시스템 같은 것에서 AoSoA와 Bit_Pool을 결합한 예시입니다:
c1MAX_FOOS :: 1024 * 16 2 3Foo_Batch :: struct { 4 pos: [3]#simd[64]f32, // xyz 64개 5 vel: [3]#simd[64]f32, // xyz 64개 6 timer: #simd[64]f32, 7 flags: #simd[64]u16, 8} 9 10// used.l0의 각 값은 하나의 배치에 대응 11Foos :: struct { 12 used: Bit_Pool(MAX_FOOS), 13 batches: [MAX_FOOS / 64]Foo_Batch, 14}
이걸 더 자세히 설명하는 건 이 글의 범위를 벗어나지만, 영감을 위한 막연한 아이디어로서 남겨두겠습니다.
아직 깊게 파보진 않았지만, 원자 연산(atomic)을 사용해 삽입/삭제를 완전히 lockless로 만들 수 있을지 궁금합니다. 1레벨 케이스에서는 비교적 간단해 보이는데, 메모리 쓰기 순서를 잘 정해서 데이터 레이스를 제거할 수 있을까요?
혹시 무언가를 알아내시면 꼭 알려주세요! 실험 결과와 정합성 증명 모두에 관심이 많습니다.
이 접근은 “멍청한” 빈 슬롯 배열보다 조금 더 복잡하긴 하지만, 기본 비트 배열일 뿐이고 관리해야 할 엄청 복잡한 메타데이터가 없다는 사실이 정말 마음에 듭니다.
반드시 이 접근을 쓰라고 설득하려는 건 아닙니다. 다만 이런 종류의 알고리즘은 아직 비교적 흔치 않다고 생각해서, 글로 남겨볼 가치가 있었습니다. 새롭다고 할 만한 건 전혀 아니지만, 유용하길 바랍니다!
읽어주셔서 감사합니다!
Jakub
2026-02-22: 소폭 업데이트, 프리 리스트 메모리 오버헤드 수정
2026-02-23: 오타 수정, 데모