프로젝트 05 · 독립 저장소

STL-free Container

DynamicArray, StaticArray, HashMap/HashSet(Robin Hood Hashing), 그리고 그 아래를 받치는 Allocator들 — Arena, LinearArena, TLSFArena로 구성함. TLSFArena는 임의 바이트 범위에서 O(1)로 할당·해제·분할·병합할 수 있음.

github.com/Winteradio/Container

01핵심 내용
02상세 내용 & 다이어그램
03개발 히스토리
04RTree — 공간 인덱스
05이슈
06버그

01 / INTRO

핵심 내용

왜 STL을 안 쓰는지: 커스텀 Arena/Pool Allocator와 맞물려 동작해야 하는데, std::allocator 기반 STL Container로는 Allocator를 자료구조와 독립적으로 교체하기 어려움 — Allocator를 Template 인자로 분리해서 전략을 바꿀 수 있게 직접 구현.

연산	컨테이너	시간	비고
삽입(100만 개)	std::unordered_map	743 ms	1.0×
삽입(100만 개)	wtr::HashMap	430 ms	1.72× 빠름
조회(100만 개)	std::unordered_map	274 ms	1.0×
조회(100만 개)	wtr::HashMap	216 ms	1.26× 빠름

100만 개 랜덤 정수 키, Ryzen 7 5800H · MSVC C++17 Debug 빌드 기준 — 벤치마크 코드/원본 결과 → Open Addressing으로 Node 기반 Chaining보다 Cache Miss가 적은 게 주요 원인.

Robin Hood Hashing의 규칙 하나"가난한 쪽이 이긴다"

삽입할 때 자기보다 PSL(제자리에서 얼마나 멀어졌는지)이 낮은, 즉 "부자"인 원소만 밀어냄. 밀려난 원소는 계속 앞으로 탐색하며 자기 PSL을 올림.

tombstone 없는 삭제backward-shift

빈 슬롯이 생기면 뒤따르는 원소들을 자기 PSL만큼 앞으로 당겨서 구멍을 물리적으로 없애버림 — Find()의 조기 종료 조건이 영원히 유효하게 유지되는 이유.

분기 없는 TLSFArena 탐색Bit 연산만으로 완료

필요한 크기보다 작은 Class를 Bitmask로 지워버리고, 남은 것 중 최하위 Bit를 찾으면 그게 가장 가까운 free Block임. Block 리스트를 훑을 필요 없음.

특징

실측 벤치마크 근거

std::unordered_map 대비 삽입 1.72배, 조회 1.26배 — Open Addressing의 Cache 지역성 이득이 "느낌"이 아니라 숫자로 남아 있음.

TLSF 기반 O(1) 할당 · 해제 · 병합

FL/SL Bitmap 덕분에 Block 리스트를 훑지 않고, 물리적 offset 비교로 병합 방향을 정해서 인덱스 순서에 의존하지 않음.

Template 인자로 분리한 Allocator자료구조와 메모리 전략의 독립 교체

Container 자료구조와 메모리 전략을 독립적으로 교체할 수 있다는 의도 자체가 STL-free 라이브러리를 직접 만드는 핵심 이유.

주요 내용

2026.08 데모 전까지 죽은 코드나 다름없던 RTree

Boundary가 private라 외부에서 Insert()를 호출할 방법조차 없었고, SplitNode()엔 컴파일이 깨지는 오타가 있었음 — 한 번도 실행 안 해본 코드가 라이브러리에 포함돼 있었다는 뜻 → 접근 범위를 고치고 데모로 돌려서 버그 2건까지 수정함.

절반만 실현된 "Allocator 교체 가능" 설계

LinearArena가 실제로는 다른 Container들이 기대하는 Allocator Interface(1인자 Allocate, Deallocate 존재)와 안 맞아서, DynamicArray<T, LinearArena>로는 실제로 못 씀.

테스트 안 된 경로에 몰려 있던 실제 버그수정됨 · #34 #36

List::Splice 특정 오버로드는 Instance화하면 아예 컴파일이 안 되고, HashMap의 rBegin()/rEnd()는 실제로는 정방향으로 순회했음 — 둘 다 2026.08 코드 리뷰에서 처음 찾았고 바로 수정함.

02 / MODULES

상세 내용 & 다이어그램

Robin Hood Hashing과 TLSF Bitmap 탐색을 실제 동작 단위로

TLSFArena · 실시간 블록 추적 0 / 0 B

할당됨해제됨

블록에 마우스를 올려보세요

Class 다이어그램 — Container와 Allocator

사용 예시

wtr::HashMap<int, std::string> map;

map[1] = "Apple";           // operator[] — 없으면 삽입, 있으면 갱신
map.Emplace(2, "Banana");

for (const auto& pair : map) { /* Robin Hood 슬롯을 순서대로 순회 */ }

if (map.Find(2) != map.End())
    std::cout << map.At(2);

// Allocator는 템플릿 인자로 교체 가능 — 기본은 wtr::Arena
wtr::DynamicArray<int, wtr::Arena> explicitArena;

Robin Hood Hashing

Slot 구조

{ Data data; int16_t psl; }, 기본값 psl = -1 — 이게 빈 Slot을 나타내는 sentinel. 별도 tombstone 플래그는 어디에도 없음.

삽입 = 선형 탐사 + "부자" 밀어내기

한 칸씩 나아가며 신규 원소의 PSL을 올림. 점유된 Slot에 도달하면 if (newSlot.psl > oldSlot.psl) swap(newSlot, oldSlot) — 신규 원소는 자기보다 PSL이 낮은(제자리에 더 가까운) 원소만 밀어냄. 밀려난 원소는 계속 앞으로 탐사함.

증설

load factor 70%에서 Rehash하며 용량을 두 배로 늘리고, 같은 삽입+swap 로직을 새 배열에 다시 돌림.

삭제 = backward-shift, tombstone 미사용

비운 Slot은 psl = -1로 표시하고, 같은 탐사 Chain의 뒤따르는 원소들을 자기 PSL만큼 뒤에서 앞으로 당겨오며 PSL을 줄임 — 제자리이거나 빈 Slot을 만날 때까지 반복. 구멍을 표시만 하는 게 아니라 물리적으로 없애버려서, Find()의 조기 종료 규칙(탐사 거리가 Slot의 PSL을 넘으면 중단)이 영원히 유효함.

Sequence 다이어그램 — Robin Hood Hashing Insert/Delete

Robin Hood Hashing Insert/Delete 시퀀스 다이어그램

TLSFArenaFL/SL Bitmap 탐색

2단계 분류

FL 인덱스 = 크기의 최상위 Bit 위치(64행). SL 인덱스 = 그 2의 거듭제곱 범위 안에서의 4Bit 선형 세분(16열). bucketIndex = fl*16 + sl이 평평한 free-list 헤드 배열을 가리킴.

분기 없는 탐색

FL 행마다 uint64_t Bitmap 하나, SL 열마다 Bit 하나. Allocate()는 필요한 크기보다 작은 Class를 전부 마스킹해서 지우고 (bitmap[fl] & (~0 << sl)), 남은 것 중 최하위 Bit를 취함 — Block 리스트를 전혀 훑지 않고 순수 Bit 연산만으로 가장 가까운 free Class를 찾음.

Free() 병합 방향

물리적으로 인접하면서 둘 다 free인 Block만 병합함 — 인접 여부는 배열 인덱스가 아니라 바이트 offset 비교로 결정됨. 흡수된 Block의 Slot은 Block 배열을 줄이는 대신 free-index 목록으로 재활용됨.

Block마다 링크 쌍이 두 개인 이유

prev/next는 물리적 바이트 순서상의 이웃을 추적하며 free든 allocated든 항상 유효함 — Free()가 물리적으로 맞닿은 Block을 찾는 유일한 방법. prevFree/nextFree는 같은 크기 Class의 free-list Chain을 추적하며 free일 때만 의미 있음. 같은 Block의 서로 무관한 두 관계를 나타내기 때문에, 하나로 합치면 병합이나 크기 Class 조회 둘 중 하나가 깨짐.

Arena vs. LinearArena

Arena: 개별 해제 가능

모든 할당이 각자 ::operator new이고 Page 헤더가 이중 연결 리스트에 연결됨 — Pointer 하나가 OS 할당 하나, 리스트 Node 하나에 정확히 대응하므로 Deallocate(ptr)가 리스트를 훑어 그 하나만 정확히 해제 가능.

LinearArena: 처음부터 일괄 해제 전용

할당은 공유 Page 안에서 offset을 밀기만 함(넘치면 새 Page 추가). 어떤 Page를 누가 쓰고 있는지 기록이 없어서 하나만 골라 해제할 방법 없고, Page 전체 offset을 한 번에 초기화하는 Reset()만 존재함.

03 / HISTORY

개발 히스토리

실제 커밋 히스토리 기준
Variant 하나에서 Vulkan 메모리 할당기까지

커밋 기록을 불러오는 중…

1기Variant 하나로 시작2025.03 — 2025.04
2025.03.31
ContainerVariant 하나로 첫 커밋
2025.04.07
Container항상 0이 나오는 해시값 버그이틀 동안 커밋 네 번
04.06~07 이틀 동안 "Fix the hash code" 커밋만 네 번 — 마지막 커밋 메시지에 원인이 그대로 남아 있음: "hash value가 값이 이미 사라진 뒤에 계산돼서 항상 0으로 나옴". Copy/Move 때 소멸자 스킵을 막으려던 valid 플래그도 이때 처음 들어왔는데, 이게 1년 뒤 리뷰에서 찾은 #32(valid가 영원히 false) · #33(Move가 copy로 동작)의 뿌리였음 — 2026.08.05에 수정.
2기실사용 Container로 확장2025.12 — 2026.07
8개월 공백 뒤 재개
2025.12.09
ContainerDynamicArray · HashMap 등 실사용 Container 추가
12.11~12.16에 HashMap 타입 정리와 Hash Table erase 길이 계산 버그(길이가 max size의 배수면 0으로 나오던 것) 수정이 몰림.
2025.12.14
Containerstd::unordered_map 대비 벤치마크
100만 개 기준 삽입 1.72배 · 조회 1.26배 — Open Addressing이 Node 기반 Chaining보다 Cache Miss가 적은 효과를 숫자로 확인 (#16).
2026.01.01
ContainerArena 위에 LinearArena 추가
"마지막 Page를 재사용 안 하는" 버그는 실제로 쓰다가 2026.05.21에 다시 고침 — 계층을 한 번에 완성한 게 아니라 하나 쌓을 때마다 실사용하며 버그를 잡아나간 흔적.
2026.07.21
ContainerTLSFArena 추가→ 다음 날 Vulkan 메모리에 바로 사용
엔진의 VulkanArena가 07.22부터 이 TLSF를 그대로 상속해서 4MB VkDeviceMemory 블록을 서브 할당함.
2기코드 리뷰 → 수정2026.08
2026.08.05
ContainerRTree 첫 실행버그 2건 수정
Boundary가 private라 아무도 Insert()를 부를 수 없던 RTree에 순회 API를 붙이고 데모를 짜서, SplitNode()의 이중 해제 · 서브트리 유실 버그를 찾아 고침 (RTree 절).
2026.08.07
Container리뷰로 찾은 버그 6건 수정 + 테스트 재작성
#31~#36(TLSF 통계, Variant 소멸자 누락 · copy로 동작하던 move, List::Splice 다운캐스트, include guard 오타, HashMap 역방향 Iterator)을 고치고, 데모 테스트를 수명 추적 객체(TrackedObject) 기반으로 다시 짬 (PR #37, PR #38).

04 / DESIGN

RTree — 공간 인덱스

Boundary 하나로 재귀 분할되는 Tree
2026.08 첫 실행

2D/3D Bounding Box(Boundary{ min, max })로 값을 색인하는 R-tree. Node가 maxEntry개를 넘기면 SplitNode()가 두 개로 쪼개고, 그 결과로 생긴 새 형제 Node를 부모에 끼워 넣다가 부모까지 가득 차면 SplitNode → InsertNode → SplitNode로 재귀함 — 부모가 없으면(즉 Root가 쪼개지면) 완전히 새로운 Root를 하나 더 만듦.

Class 다이어그램 — Entry / DataEntry / NodeEntry / RTree

Sequence 다이어그램 — Insert()가 재귀적으로 SplitNode를 타는 경로

using Tree2D = wtr::RTree<std::string, float, 2>;
Tree2D tree(4, 2); // maxEntry=4, minEntry=2

tree.Insert(Tree2D::Boundary({0.f, 0.f}, {2.f, 2.f}), "Seoul");
...

tree.Traverse([](size_t depth, bool isLeaf, const Tree2D::Boundary& box, const std::string* value)
{
    // value == nullptr  -> 이 항목은 Node (내부 노드/leaf 노드)
    // value != nullptr -> 이 항목은 실제 Data, *value가 저장된 값
});

2026.08 전까지 사실상 실행된 적 없는 코드

Boundary가 private라 외부 코드는 그 타입 자체를 이름 붙일 수도 없었음 — Insert()가 public이어도 인자를 만들 방법이 없어 호출이 불가능했고, 실제로 기존 데모의 RTreeTest rtree(4,2);도 Insert()를 한 번도 부르지 않았음. Tree를 들여다볼 public API도 전혀 없었음.

추가한 것은 접근 범위 조정 + 순회 APIAlgorithm은 그대로

Boundary를 public으로 옮기고, 방문자 Pattern의 Traverse(Visitor&&)를 새로 추가함. RTree.h는 여전히 로깅 라이브러리를 전혀 모르고, 어떻게 출력할지는 호출자(데모 코드)가 정함.

데모로 잡은 버그 두 개 (둘 다 수정)

SplitNode() — allEntries 초기화 복사본과의 스왑비워지지 않는 node->entries 해결

- 원인:

DynamicArray<Entry*> allEntries = node->entries; std::swap(allEntries,
          node->entries);

— 스왑 전에 이미 node->entries를 복사해놨기 때문에, 스왑해봐야 서로 같은 내용을 가진 채로 끝나서 node->entries가 전혀 비워지지 않았음.
- 증상: 분할할 때마다 기존 Entry들이 재분배 Loop에 의해 다시 한번 추가되어 두 배로 들어갔고, 이 중복 Pointer가 소멸자에서 두 번 Destroy()되며 이중 해제로 Segfault가 났음. 실제로 5개(분할 1회)만 넣어도 재현됐음.
- 해결: DynamicArray<Entry*> allEntries{};로 빈 상태에서 시작해서 스왑하도록 수정 — Algorithm 자체는 안 건드리고 이 초기화 한 줄만 고쳤음.

SplitNode() — 재분배 Loop Entry 이동 시 parent Pointer 미갱신깊은 Tree에서 서브트리 통째로 유실 해결

- 원인: node->entries.PushBack(...)/newNode->entries.PushBack(...)로 Entry를 재분배하면서 그 Entry의 ->parent는 갱신하지 않았음.
- 증상: 나중에 그 Entry(자신도 Node일 수 있음)가 다시 가득 차서 분할될 때, node->parent가 낡은 값(보통 nullptr)을 가리켜서 "나는 부모가 없다=내가 Root다"로 오판 — 완전히 새로운 최상위 Root를 또 만들고 m_root를 거기로 덮어써버려서, 그 전까지 쌓인 진짜 Tree가 m_root에서 도달 불가능해짐. 6개 Cluster·24개 항목으로 재귀 분할을 유도하는 테스트를 직접 짜서 재현했음(1024×1024 안에 20개가 조용히 사라지는 걸 Traverse() 카운트로 확인).
- 해결: 재분배 Loop에서 ->parent를 매번 갱신하도록 수정. 수정 후 같은 24개 테스트에서 Node count: 13 | Data count: 24 (inserted 24)로 전부 정확히 살아있고, Node 깊이 3단(재귀 분할 확인)까지 나옴.

05 / ISSUES

이슈

#25 Use-After-Free in DynamicArray Move Constructor 해결

- 원인: 이동 생성자가 m_data는 옮겼지만 m_allocator 는 옮기지 않아서, 이동된 원본 객체가 더 이상 소유하지 않는 메모리를 소멸자에서 해제해버렸음.
- 해결: 초기화 리스트에서 Allocator도 함께 이동. move-assignment에도 동일하게 적용.

#24 HashMap::operator[] Reference Invalidation during Rehash 미해결

- 원인: m_map[A] = m_map[B]에서 RHS 참조를 먼저 얻는데, LHS 접근이 Rehash를 유발하면 기존 배열이 해제되면서 RHS 참조가 Dangling됨.
- 개선 방향: 연속 메모리 open addressing이라 Cache 지역성을 얻는 대신 생기는 근본적인 Trade-off로 기록해두고 아직 패치하지 않았음 — std::unordered_map은 Node가 이동하지 않아서 이 문제 없음.

TLSFArena를 직접 만들면서 잡은 버그

GitHub 이슈 티켓은 아니지만, 개발 과정에서 발견하고 고친 것들 — 설계가 왜 그렇게 됐는지 보여줘서 남겨둠.

병합 방향을 배열 인덱스로 판단하던 버그

- 원인: isLeft를 Block 배열 상의 인덱스로 비교했는데, 인덱스는 물리적 메모리 위치와 아무 관계 없음. offset이 인접한 두 Block이 배열 어디에나 있을 수 있음.
- 해결: offset을 직접 비교하도록 수정 — 위 설명의 현재 코드가 따르는 규칙 그대로.

free-list에서 제거할 때마다 Bitmap Bit를 무조건 지우던 버그

- 원인: 같은 Bucket에 다른 free Block이 남아있어도 Bitmap Bit를 지워버려서, Allocator가 여전히 존재하는 Block을 못 찾게 됨.
- 해결: 제거된 Block이 그 Bucket의 유일한 원소였을 때만 Bit를 지우도록 수정.

병합 결과가 조용히 덮어써지던 버그

- 원인: Free()가 물리적 이웃마다 한 번씩, Merge()를 두 번 호출하는데 결과를 =로 저장 — 왼쪽 병합 성공이 오른쪽 병합 실패로 덮어써지면서, 이미 병합되어 빠진 Block을 다시 free-list에 삽입하려 시도.
- 해결: 두 결과를 |=로 누적한 뒤 삽입 여부를 판단.

06 / BUGS

버그

2026.08 코드 리뷰에서 직접 찾아 등록한 이슈
8건 중 6건 수정 · 상태는 실시간 동기화

실제 버그 8건 — 6건 수정 완료 클릭해서 펼치기

#34 · include/List.h:336 List::Splice(4-인자 오버로드)의 잘못된 다운캐스트인스턴스화 시 컴파일 실패 해결

- Node* prev = node->prev;인데 node는 NodeBase*이고 NodeBase::prev도 NodeBase*임 — 명시적 Cast 없이 베이스 Pointer를 파생 Pointer에 대입하는 코드라 C++에서는 컴파일되지 않음. 바로 옆의 다른 Splice 오버로드 3개(257·298·400행)는 전부 NodeBase*로 맞게 타입을 씀 — 이 오버로드만 복붙 중 타입을 놓친 것으로 보이고, 실제로 이 특정 오버로드가 호출(Instance화)되기 전까지는 Template이라 드러나지 않음.
- 수정(2026.08.05): 이 오버로드도 NodeBase* prev로 타입을 맞춤.

#35 · include/TLSFArena.h:1-2 TLSFArena.h include guard 매크로 이름 불일치 해결

- #ifndef __WTR_TLSF_ARENA_H__로 체크하고 #define __WTR_TLSF_ANREA_H__("ANREA")로 정의 — 오타 때문에 guard가 걸리지 않음. 한 번역 단위에서 이 헤더가 두 번 include되면 재정의 에러 발생.
- 수정(2026.08.05): #define 쪽 오타를 __WTR_TLSF_ARENA_H__로 고침.

#36 · include/HashTable.h:263,266 HashMap의 ReverseIterator가 실제로는 정방향 해결

- Key != Data(HashMap) 케이스에서 ReverseIterator가 BaseIterator<true, false>로 풀립니다 — reverse 플래그가 꺼진 채로. HashMap의 rBegin()/rEnd()가 뒤가 아니라 앞으로 순회하고, const 여부도 Iterator와 어긋납니다.
- 수정(2026.08.05): ReverseIterator의 Template 인자를 바로잡아 실제로 역방향 · const로 동작함.

#33 · include/Variant.h:124-139 Variant::Move()가 실제로는 copy를 호출 해결

- 이름 붙은 T&& rhsValue 변수를 만든 뒤 T(rhsValue)에 그대로 넘김 — 이름 있는 rvalue 참조는 lvalue라서 copy 생성자/대입이 선택됨. operator==도 저장된 값이 아니라 m_nCurrentHash만 비교하는데, std::hash 특수화가 없는 타입은 항상 0을 반환해서 그런 타입의 모든 값이 내용과 무관하게 같다고 판정됨.
- 수정(2026.08.05): T(std::move(rhsValue)) / lhsValue = std::move(rhsValue)로 실제 move가 일어나게 바꿈.

#32 · include/Variant.h — Copy() / Move() / AlignedStorage::valid 영원히 false인 valid 플래그대입마다 기존 값의 소멸자 생략 해결

- 원인: AlignedStorage::valid는 생성자와 Destroy()에서 false로만 설정되고, 파일 전체 어디서도 true로 바뀌지 않음(Set<T>()조차 안 함). 그래서 TypeMatcher::Copy/Move의 "이미 유효하면 대입, 아니면 placement-new" 분기에서 항상 placement-new 쪽만 탐.
- 영향: Variant::Copy()/Move()(대입 연산자가 호출)는 대상이 이미 값을 들고 있어도 Destroy()를 먼저 부르지 않음 — 이미 살아있는 객체의 원본 바이트 위에 그냥 새 객체를 placement-new해버려서, 이전 값이 std::string/std::vector처럼 힙을 소유한 타입이었다면 그 소멸자가 절대 호출되지 않고 내부 Pointer까지 덮어써져서 나중에 정리할 방법도 없음 — 이미 값이 있는 Variant에 다른 Variant를 대입할 때마다 발생하는 실제 메모리 누수.
- 수정(2026.08.05): 대입 전에 Destroy()를 먼저 불러 기존 값의 소멸자가 호출되도록 함.

#31 · include/TLSFArena.h — Free() / Merge() / Remove() 병합된 Free()마다 더 깎이는 m_remainedSize진짜 누수는 아닌 통계 오류 해결

- 원인: Free()는 block.free = true만 찍고 병합을 시도하는데, Insert()는 병합이 전부 실패했을 때만 호출됨. 근데 Merge() 내부의 Remove(baseIndex)는 그 블록이 실제로 Insert()된 적 있는지 확인 안 하고 무조건 m_remainedSize -= block.size를 함 — 한 번도 더해진 적 없는 크기를 빼버리는 셈.
- 증상: 양쪽 이웃이 이미 free인 Block을 마지막에 Free()하는(한 번의 호출 안에서 좌우 병합이 동시에 일어나는) 패턴마다 m_remainedSize가 그 Block 크기만큼 실제보다 적게 나옴. 직접 만든 스트레스 테스트로 확인: 전부 해제한 뒤 IsEmpty()가 false를 반환.
- 실제로는 누수 아님: 같은 상태에서 전체 용량(1MB)을 다시 Allocate()해보면 offset=0, size=1048576로 정확히 성공 — free-list/Bitmap은 완전히 정상, m_remainedSize 통계만 신뢰할 수 없는 상태.
- 수정(2026.08.05): m_remainedSize를 병합 경로가 아니라 할당 · 해제 시점에 직접 갱신하도록 바꿈.

include/LinearArena.h:107, 37, 7-8 LinearArena와 Allocator 인터페이스의 불일치 설계 노트

- Allocate가 두 인자(size, align)를 요구하는데 나머지 Container가 기대하는 시그니처는 한 인자, Deallocate(void*)도 아예 없어서 DynamicArray<T, LinearArena>로 못 씀. Page::~Page()도 ::operator new로 받은 메모리를 delete data;로 해제해서 new/delete 형태가 안 맞음.

include/DynamicArray.h:250-257 복사 대입 후 실제 용량과 m_capacity의 불일치 가능성 설계 노트

- operator=(const DynamicArray&)가 기존 Buffer로 충분하면 재할당하지 않으면서도 m_capacity = other.m_size를 무조건 대입함. 실제 할당 크기가 기록된 값보다 커진 채로 남아서, 이후 Reserve()가 필요 이상으로 일찍 재할당함.

GitHub에 지금 열려 있는 이슈 (실시간)

불러오는 중…