Optimizing AutoFDO Profile Symbol List Loading with Eytzinger Binary Search
The RFC above was more about those AutoFDO profiles that use MD5 values in SecNameTable. Since we already have this topic, let me add a closely related topic to the same thread – Profile Symbol List.
Problem Statement
The compiler spends a significant amount of time loading and querying
SecProfileSymbolList in AutoFDO sample profiles:
- Decompressing and parsing the
SecProfileSymbolListstring archive. - Constructing an in-memory
DenseSet<StringRef>to answer cold symbol
membership queries across C++ compilation and inlining passes.
Background
The compiler performs cold symbol membership queries via
ProfileSymbolList::contains(StringRef Name) to determine whether a function
symbol is recorded in the sample profile’s cold symbol table
(SecProfileSymbolList).
Solution
We format SecProfileSymbolList as a decompressed array of 64-bit MD5 hashes
arranged in Eytzinger (breadth-first) order so the reader can perform an
efficient binary search. The resulting array is written to
SecProfileSymbolList and tagged with a section flag:
SecProfileSymbolListFlags::SecFlagEytzinger.
For details on how to perform an Eytzinger binary search efficiently, see:
Current Status and Preliminary Results
Compilation Performance
Benchmarking an internal AutoFDO application with the Eytzinger Profile Symbol
List versus the compressed string list demonstrates compile-time speedups:
| Compilation Step | Speedup Improvement |
|---|---|
| ThinLTO Post-link Backend | 23.3% speedup |
| ThinLTO Pre-link Compilation | 6.7% speedup |
Profile Size on Disk
The same AutoFDO application above has 349,227 cold symbols in
SecProfileSymbolList. Replacing the compressed string list with an Eytzinger
array of 64-bit MD5 hashes saves 41% for the section:
- Before (Compressed String Archive): 4.8 MB zlib-compressed string
block (47 MB decompressed). - After (Eytzinger MD5 Array): 2.8 MB decompressed.
Impact on Heap Allocation
- Before (Compressed
SecProfileSymbolList): ~55 MB (47 MB string
buffer and 8 MB forDenseSet<StringRef>) to store 349,227 cold symbols
after decompressing 4.8 MB of zlib data. - After (Eytzinger
SecProfileSymbolList): Zero heap allocation for
the cold symbol table. The reader requires only 16 bytes of metadata to
access themmapdisk buffer.
Upstreaming Plan
We plan to upstream the Eytzinger Profile Symbol List in three patches:
- Core Data Structures (
EytzingerTableSpan): Introduce the non-owning
binary search span tollvm/include/llvm/ADT/Eytzinger.h. - Section Flag Definition: Add
SecProfileSymbolListFlags::SecFlagEytzinger
to uniquely identify Eytzinger-formatted cold symbol sections. - Writer & Reader Integration: Update
SampleProfileWriterExtBinaryBaseto
emit 64-bit MD5 arrays in Eytzinger layout whenSecFlagEytzingeris
requested, and updateSampleProfileReaderExtBinaryBaseto query
EytzingerTableSpandirectly on the underlying memory buffer.