O(1) 시간 복잡도, 메모리 지역성 향상! 자유 리스트 없는 메모리 풀
자유 리스트(Free List) 대신 비트 배열(Bit Array)을 사용하여 메모리 풀을 구현, O(1) 시간 복잡도를 유지함
tzcnt 명령어를 활용하여 비트 배열 내 사용 가능한 슬롯을 빠르게 검색, 메모리 지역성(Memory Locality)을 개선
AoSoA(Arrays of Structures of Arrays) 방식을 통해 SIMD 연산을 지원, 파티클 시스템(Particle System) 등에서 활용 가능
멀티 레벨 비트 풀(Multi-level Bit Pool) 구조를 통해 대규모 데이터셋(Dataset)에 대한 확장성을 확보, 성능 향상 도모
비트 배열 기반 메모리 풀의 핵심 원리
본 논의는 기존 자유 리스트(Free List) 방식 대신 비트 배열(Bit Array)을 사용하여 메모리 풀을 구현하는 방법을 제시한다. 핵심은 각 슬롯의 사용 여부를 나타내는 단일 비트를 저장하는 것이다. 특히, tzcnt 명령어(Trailing Zero Count Instruction)를 활용하여 사용 가능한 슬롯을 빠르게 찾을 수 있으며, 이를 통해 O(1) 시간 복잡도를 유지한다. 이러한 방식은 메모리 지역성(Memory Locality)을 향상시키는 데 기여한다.
tzcnt 명령어 활용과 성능 최적화
저자는 tzcnt 명령어(Trailing Zero Count Instruction)를 사용하여 비트 배열 내에서 사용 가능한 슬롯을 효율적으로 검색하는 방법을 설명한다. 이 명령어는 x64 아키텍처에서 지원되며, 단일 사이클 내에 최하위 0 비트의 인덱스를 찾을 수 있다. 이를 통해, 반복적인 비트 검사 루프(Loop)를 피하고, 디버그 빌드(Debug Build)에서도 빠른 성능을 보장한다. 메모리 풀(Memory Pool) 구현 시 성능 최적화에 중요한 역할을 한다.
AoSoA(Arrays of Structures of Arrays)를 활용한 SIMD 최적화
저자는 비트 배열 기반 메모리 풀을 AoSoA(Arrays of Structures of Arrays) 방식과 결합하여 SIMD 연산을 활용하는 방법을 제시한다. L0 마스크(Mask)는 사용 가능한 슬롯을 결정하는 'ground truth' 역할을 하며, SIMD 연산의 op mask로 사용될 수 있다. 이러한 접근 방식은 파티클 시스템(Particle System)과 같은 분야에서 성능을 크게 향상시킬 수 있다. 특히, SIMD(Single Instruction, Multiple Data) 연산을 통해 데이터 처리 속도를 극대화한다.
멀티 레벨 비트 풀(Multi-level Bit Pool) 구조와 확장성
저자는 메모리 풀의 크기가 커질 경우, 멀티 레벨 비트 풀(Multi-level Bit Pool) 구조를 통해 확장성을 확보할 수 있다고 설명한다. L1, L2 비트 배열을 추가하여 검색 범위를 확장할 수 있으며, 여전히 O(1) 시간 복잡도를 유지한다. 멀티 레벨 구조(Multi-level Structure)는 대규모 데이터셋(Dataset)을 처리하는 데 필요한 성능과 효율성을 제공한다. 하지만, 현재는 작은 크기의 풀을 사용하므로 이 방식을 적용하지 않았다고 언급한다.
