[RFC] Faster Sample Profile Loading

IR & Optimizations
8

RFC Amendment: Eytzinger Name Table and Parallel Function Offsets

Problem Statement

The compiler spends a significant amount of time loading and parsing
SecFuncOffsetTable in large AutoFDO profiles. The problem lies in the
encoding of the section where we use pairs of variable-length ULEB128 integers.
Since we cannot perform random access on the mmap memory, we must eagerly load
the entire section regardless of how many entries the current module is
interested in retrieving.

Background

Here is how we use SecFuncOffsetTable:

  • The compiler invokes getSamplesFor.

  • We look up its GUID in SecFuncOffsetTable (or its in-memory equivalent).

  • We find the corresponding file offset in SecLBRProfile (relative to the
    beginning of the section).

  • We retrieve FunctionSamples

In other words, we are essentially operating a hash map, where
SecFuncOffsetTable acts as key-value pairs, with the value being a file
offset.

Solution

The solution below applies to those cases where the user wishes to generate a
MD5 profile. The raw string-based AutoFDO profile is out of scope.

We propose a space-efficient profile format that does not require eager loading.
The basic setup is parallel arrays:

  • SecNameTable (or SecCSNameTable): Continues to be an array of MD5 values
    in fixed length uint64_t.

  • SecFuncOffsetTable: This section will hold an array of file offsets in
    uint32_t to FunctionSamples in SecLBRProfile only. It will no longer
    hold any keys (GUIDs).

SecNameTable

Now, we have three mutually exclusive sets of GUIDs:

  • CSKeys: Those GUIDs used as keys in Context-Sensitive SecLBRProfile
  • FlatKeys: Those GUIDs used as keys in Flat SecLBRProfile
  • Inlinees: Those GUIDs mentioned in SecLBRProfile but not as keys

The new SecNameTable will consist of:

  • Metadata
    • the number of CSKeys
    • the number of FlatKeys
    • the number of Inlinees
  • Payload
    • CSKeys in Eytzinger layout
    • FlatKeys in Eytzinger layout
    • Inlinees in Eytzinger layout

Notice that we have exactly the same number of keys as before, but they are
arranged differently into three groups, each of which can be easily searched
with a binary search.

SecFuncOffsetTable

The SecFuncOffsetTable for the Context-Sensitive SecLBRProfile has as many
entries as CSKeys, each being fixed-length uint32_t. We form key-value pairs
as follows:

  • Key (GUID): The k-th entry of CSKeys in SecNameTable

  • Value (File offset): The k-th entry of SecFuncOffsetTable for
    Context-Sensitive SecLBRProfile. This file offset is within
    SecLBRProfile just as before.

The same setup applies to SecFuncOffsetTable for Flat SecLBRProfile.

SecLBRProfile

This section encodes GUIDs as indexes into the name table as ULEB128. The
encoding scheme stays the same as before, but since the name table is in a new
order, actual encodings of ULEB128 will change.

Preliminary Results

Compilation Performance

Benchmarking on internal AutoFDO application using a large MD5-based profile
shows the following speed up with the new format:

Compilation Step Speedup Improvement
ThinLTO Pre-link Compilation 34.5% speedup
ThinLTO Post-link Backend 79.0% speedup

Profile Size on Disk

The same XFDO application above has 794,393 top-level function symbols across
its split hot and cold SecFuncOffsetTable sections. Replacing ULEB128 pairs
with a parallel 4-byte (uint32_t) array reduces the section size on disk
by 53%:

  • Before (ULEB128 Pairs): 6.73 MB across both sections.
  • After (Parallel uint32_t Array): 3.18 MB across both sections.

Impact on Heap Allocation

  • Before (SecFuncOffsetTable): 17.8 MB for DenseMap to store
    622,380 top-level entries from the larger hot/CS section after eagerly
    decoding ULEB128 pairs.
  • After (Parallel uint32_t Array): 80 bytes for various metadata.
    The reader operates directly over memory-mapped disk slices.

Auxiliary Benefits

Fast Global Membership Queries

The three Eytzinger spans in SampleProfileNameTable let
SampleProfileLoader::runOnFunction check symbol membership instantly on
demand, eliminating upfront DenseSet (GUIDsInProfile) construction.

Synergy with Profile Symbol List

As shown in:

I’m planning to encode Profile Symbol List in Eytzinger layout. We can use the
same encoder and decoder (binary search).

On-Disk Hash Table

Earlier, I was planning to use OnDiskChainedHashTable in SecFuncOffsetTable:

I have since shelved the idea for the following reasons:

  • OnDiskChainedHashTable uses about 6 times as much disk space for
    SecFuncOffsetTable.

  • OnDiskChainedHashTable is an one-off solution with no synergy with Profile
    Symbol List in Eytzinger layout.

Upstreaming

  • Finish upstreaming Eytzinger encoder. (The decoder has already landed.)

  • Support Eytzinger layout in SecNameTable (while leaving SecFuncOffsetTable
    as is in terms of the encoding scheme).

  • Use a uint32_t array in SecFuncOffsetTable.

@davidxl