[RFC] Faster Sample Profile Loading

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 SecProfileSymbolList string 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 for DenseSet<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 the mmap disk 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 to llvm/include/llvm/ADT/Eytzinger.h.
  • Section Flag Definition: Add SecProfileSymbolListFlags::SecFlagEytzinger
    to uniquely identify Eytzinger-formatted cold symbol sections.
  • Writer & Reader Integration: Update SampleProfileWriterExtBinaryBase to
    emit 64-bit MD5 arrays in Eytzinger layout when SecFlagEytzinger is
    requested, and update SampleProfileReaderExtBinaryBase to query
    EytzingerTableSpan directly on the underlying memory buffer.

@davidxl