LLVM의 여러 해시 테이블에서 tombstone과 in-band sentinel key를 제거하고 선형 탐사와 비트 배열 점유 추적으로 전환한 최근 개선 사항을 정리한다.
LLVM에는 여러 해시 테이블이 있습니다. 이들은 이차 탐사와 인밴드 센티널 키(빈 슬롯, tombstone)를 사용해 왔으며, 최근 작업에서는 이를 tombstone 키를 제거한 선형 탐사로 대체하고 있습니다.
DenseMap (std::unordered_map의 대체재): DenseMapInfo::getEmptyKey() / getTombstoneKey().SmallPtrSet (std::unordered_set<T *>의 대체재): 하드코딩된 -1(빈 슬롯)과 -2(tombstone).StringMap (std::unordered_map<std::string, V>의 대체재)오픈 어드레싱 방식의 DenseMap과 SmallPtrSet에서는 삽입 시 포인터, 참조, 반복자가 무효화됩니다. StringMap은 다릅니다. 각 엔트리가 힙에 할당된 StringMapEntry<V> 노드에 존재하므로, grow가 일어나도 엔트리 포인터는 살아남습니다. 노드 기반인 std::unordered_map은 삽입과 삭제 모두에서 살아남은 원소의 포인터를 유효하게 유지하며, 삭제된 원소 자신의 반복자만 무효화합니다. LLVM 코드에서는 그처럼 더 강한 계약이 필요한 경우가 드뭅니다. 호출자는 보통 변경을 가로질러 컨테이너 내부의 오래 사는 참조를 붙잡고 있지 않으며, 바로 그 차이 때문에 relocating erase와 비트 배열 점유 추적이 가능해집니다.
최근에는,
erase() 역시 포인터를 무효화합니다.int/unsigned/size_t)를 쓰는 DenseMap은 -1/-2를 예약하고 있었는데, 이는 함정이었고 이제 해결되었습니다.SmallPtrSet에는 원소 수가 임계값보다 적을 때 사용하는 small mode와 large mode가 있습니다. tombstone 상태는 2024년 #96762에서 제거되었습니다. 이 패치는 erase() 연산을 반복자 무효화 방식으로 바꾸었고, 그에 따라 트리 전반의 수정이 필요했습니다.
large mode는 두 개의 센티널 키(빈 슬롯, tombstone)를 쓰는 이차 탐사를 사용했습니다.
Knuth TAOCP Vol. 3 §6.4 Algorithm R은 lazy deletion을 피하는 알고리즘을 설명합니다. #197637에서 이를 구현했습니다.
저는 Robin Hood Hashing과 Abseil Swiss Table 계열 구현도 조사해 보았지만, 둘 다 성능이 더 나빠졌을 것입니다. Robin Hood Hashing은 주로 높은 적재율에서 find-miss를 개선하지만, find-hit와 삽입에는 작은 비용을 부과합니다.
두 가지 큰 변화가 병합되었습니다.
계측을 넣은 clang은 llvm/lib/Analysis/ScalarEvolution.cpp를 컴파일하는 동안 모든 (KeyT, ValueT) 연산을 셉니다. 서로 다른 DenseMap/DenseSet 타입이 597개, 사용자 연산은 약 1억 8600만 번입니다.
| op | count | probes mean |
|---|---|---|
| find-hit | 65.2M | 1.55 |
| find-miss | 65.7M | 1.28 |
| insert | 47.8M | 1.71 |
| erase | 7.0M | — |
| grow | 1.5M | — |
조회가 부하의 약 70%를 차지하고, 삽입은 약 26%, 삭제는 약 4%입니다. 평균 probe 수는 1.3에서 1.7 사이로, 선형 탐사가 충분히 잘 처리하는 범위 안에 있습니다. operator[]는 도달한 버킷 기준으로 분류됩니다. 키가 이미 있으면 find-hit, 빈 슬롯이면 insert로 계산됩니다.
몇몇 인스턴스화가 대부분의 트래픽을 담당합니다.
| type | find-hit | find-miss (mean) | insert | erase | grow | peak |
|---|---|---|---|---|---|---|
DenseMap<const void *, Pass *> | 680K | 24.8M (1.03) | 202K | 202K | 9.3K | 1 KiB |
DenseMap<Value *, ValueHandleBase *> | 2.8M (2.02) | 0 | 2.2M | 2.2M | 11 | 1 MiB |
DenseMap<const Value *, StringMapEntry<Value *> *> | 3.0M | 1.4M (2.26) | 540K | 439K | 13 | 4 MiB |
DenseMap<DeclarationName, StoredDeclsList> | 772K | 1.2M (1.94) | 143K | 0 | 9.0K | 64 KiB |
DenseMap<LazyCallGraph::Node *, LazyCallGraph::SCC *> | 1.3M | 98K (2.95) | 175K | 173K | 15 | 258 KiB |
DenseMap<AnalysisKey *, bool> | 2.8M | 2.0M (1.52) | 2.0M | 0 | 124K | 1 KiB |
<const void *, Pass *>는 평균 1.03으로 2550만 번의 조회를 수행합니다. 즉, 트래픽이 뭉쳐 있지 않습니다. <Value *, ValueHandleBase *>는 220만 번으로 단일 최대 erase 소비자이며, 바로 이 워크로드에서 Algorithm R의 relocating-erase 콜백이 제값을 합니다. 이 타입의 find-miss 열이 0인 이유는 llvm/lib/IR/Value.cpp에서의 모든 접근이 operator[] 또는 erase를 통해 이루어지기 때문입니다. find/lookup 호출 지점이 없어서, 빈 슬롯으로 향한 probe가 find-miss가 아니라 insert로 분류됩니다. 버킷의 값 슬롯 주소는 ValueHandleBase *&Entry = Handles[V]로 포착되어 연결 리스트의 역포인터(PrevPtr)로 저장되는데, 이것이 바로 Algorithm R이 이웃을 이동시킬 때 새로운 OnMoved 콜백이 갱신해 주는 대상입니다. StringMapEntry는 4 MiB에서 정점을 찍는데, 바로 이 구간에서 used-bit 배열의 바이트 오버헤드가 가장 중요해집니다. 구조적 키와 그래프 포인터 키(DeclarationName, LazyCallGraph::Node *)는 miss마다 여전히 probe가 몇 번 더 듭니다.
코드 크기도 중요합니다. SIMD 테이블은 잘 맞지 않을 수 있습니다.
선형 탐사에는 강한 포인터 해시가 필요합니다. 예전 DenseMapInfo<T*>::getHashValue는 bump allocation된 포인터, 즉 clang에서 지배적인 키 형태가 높은 비트를 공유하게 만들었고, 짧은 버킷 범위로 붕괴시켰습니다. 이차 탐사는 이것을 가려 주고 있었습니다. #197390은 더 강한 믹서를 도입했고, 그 결과 SmallPtrSet과 DenseMap 모두의 길이 열렸습니다.
#200595는 tombstone을 동반한 이차 탐사를 Algorithm R을 동반한 선형 탐사로 대체합니다. 버킷 상태는 두 개뿐이며, lazy marker는 없습니다. 이제 erase는 뒤따르는 엔트리를 재배치하여 빈 구멍을 메우므로, 엔트리 포인터가 무효화될 수 있습니다. 새로운 erase(Key, OnMoved) 및 erase(iterator, OnMoved) 오버로드는 이동된 버킷마다 한 번씩 콜백을 호출하며, ValueHandleBase::RemoveFromUseList는 이를 사용해 PrevPtr를 갱신합니다.
첫 시도에는 전설적인 이야깃거리가 있었습니다. 원래 변경은 #199615로 들어갔다가, SCEV 크래시 이후 #200421에서 되돌려졌습니다. 원인은 PoisoningVH가 Algorithm R 이후에는 재배치가 일어나는 연산을 가로질러 생 버킷 포인터를 캐시하고 있었기 때문입니다. 이 버그는 재배치를 하지 않는 tombstone 아래에서는 잠복해 있었고, 알고리즘이 바뀐 뒤에야 드러났습니다. #200540에서 수정된 뒤 #200595로 다시 들어갔습니다.
stage1-O3에서 이 변화는 명령어 수 **-1.34%**를 기록했고, CTMark의 열 개 벤치마크가 모두 -0.85%에서 -1.61% 사이로 개선되었습니다(compare). Clang wall은 -1.54%, stage1 바이너리는 **-1.40%**입니다. 버킷 상태가 줄어들수록 생성 코드도 줄어들기 때문입니다. 커밋 메시지는 _"the in-band sentinel value approach … is the best, or at least very difficult to beat."_라고 적고 있습니다. 아래의 used-bit 배열은 이 명제를 깨뜨릴 자격을 얻었습니다.
빈 슬롯 판정은 getEmptyKey()에서 비트 검사로 바뀌었습니다. 버킷과 하나의 할당을 공유하는 버킷당 1비트 uint32 배열이 있습니다.
이것은 트레이드오프입니다.
집계된 수치는 흥미롭습니다(compare). Stage1-O3 명령어 수는 **-0.99%**이지만, stage2-O3는 +0.13%, stage2-O0-g는 **+0.34%**로 실제로 명령어 수가 증가 합니다. Clang wall time은 **-1.37%**인데 명령어 수는 **-0.49%**에 불과하고, size-file은 비트 배열이 바이트를 차지하기 때문에 **+0.87%**입니다. 절감분이 캐시 로드에 있을 때 instructions:u는 잘못된 비용 모델입니다. 이 카운터는 새로운 비트 테스트 시퀀스는 보지만, 당신이 발행하지 않은 버킷 로드는 보지 못합니다.
이 패치 이후 DenseMap<int/unsigned/size_t, X>는 키 도메인의 모든 값을 받을 수 있습니다.
트리 전반에 걸친 trait 단순화가 리뷰 가능성을 위해 서브디렉터리별 PR 하나씩으로 진행되었습니다.
getTombstoneKey() 제거는 ADT #200959, IR+Analysis #200958, CodeGen+Transforms #200956, llvm-rest #200957, Target #200955, clang #200634로 나갔습니다.getEmptyKey() 제거(post-#201281)는 이어서 BOLT #201986, clang #201987, flang #201988, lld #201989, lldb #201990, mlir #201991, Polly #201992, Target #201993, CodeGen+Transforms #201994, llvm #201996, IR+Analysis #201997, ADT #201998에서 이어졌습니다.이 커밋들 중 몇몇은 트래커에서 작지만 일관된 개선을 보여 주었습니다. 특히 IR+Analysis 정리 작업, 즉 getTombstoneKey()에 대한 #200958와 getEmptyKey()에 대한 #201997는 각각 stage1-O3 명령어 수 약 -0.05%에서 -0.10%, clang wall time 약 -0.23%를 측정했습니다. 하지만 가장 큰 성과는 타이밍이 아니라 trait 자체에 있습니다. 정수 키가 이제 안전해졌고, MLIR #54908 크래시 계열은 사라졌으며, AssertingVH downcast UB도 더 이상 문제가 되지 않습니다. 설계 논의는 #200183에 있습니다.
TODO
프로토타입을 만들고, 측정하고, 기각했습니다. 먼저 SmallPtrSet에서, 그다음 다시 DenseMap에서요.
clang 자체 빌드에서는 집니다. 메타데이터와 체인 로직이 모든 호출 지점에 인라인되어 **바이너리 +4–10%**가 되기 때문입니다. 결합 할당, 인라인 SmallDenseMap, NOINLINE cold path, fragment 제거, NumTombstones 정리까지 모두 시도했지만, 최선이 약 +3% 명령어 / 약 +5% 크기였습니다.boost::unordered_flat_map. 합성 하니스에서는 더 빠르지만(Böther et al., PVLDB '23), 각 인스턴스화가 더 많은 코드를 끌어오고, clang에는 그런 인스턴스화가 597개 있습니다.메타데이터를 저장하는 방식은 코드 크기 대가를 치릅니다. 코드 크기가 중요한 곳이 바로 clang 빌드입니다. Algorithm R + 1비트 점유 추적은 저비용 메타데이터의 한 구석입니다.
포인터 키용 DenseMap은 인밴드 센티널 변형을 유지해야 하는지 고민했습니다(#200183). 그렇게 하면 used-bit 배열의 max-rss 오버헤드를 피할 수 있었을 것입니다. AMD Zen 4와 Apple M4에서 측정한 결과는 이를 기각했습니다. 메모리가 더 들어가더라도 used-bit 버전이 더 빨랐습니다.
SmallPtrSet은 DenseMap의 위험을 줄여 준 예행연습이었습니다. 같은 알고리즘, 더 작은 영향 범위, 그리고 기각된 대안들에 대해서도 같은 결론이 나왔습니다.