F14 Hash Table: Meta's In-House Chunk-based SIMD Hash Table

Source path: references/impl/folly/folly/container/F14Map.h, F14Set.h

F14 is Folly's hash table implementation, going a step further than SwissTable: it divides the hash table into fixed-size chunks, with SIMD probing inside each chunk. F14 has multiple variants (F14Fast*, F14Value*, F14Node*, F14Vector*), suited to different reference stability and memory layout requirements.

Note: The layout diagram below shows a simplified model of F14Value. The actual chunk size depends on the size and alignment of Item and is not necessarily fixed at 128 bytes. Overflow handling uses hosted/outbound overflow counters rather than linked lists.

Chunk-based Layout

F14 Chunk Memory Layout (128 bytes, cache-line aligned):

┌──────────────────── 128-byte Chunk ────────────────────────────────────┐
│                                                                        │
│  Tag Array (16 bytes, 16-byte aligned)                                 │
│  ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│  │ T0 │ T1 │ T2 │ T3 │ T4 │ T5 │ T6 │ T7 │ T8 │ T9 │T10 │T11 │T12 │T13 │ OF │SENT│
│  └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
│   ├──── 14 H2 tags ────────────────────────┤│overflow│sentinel│                    │
│                                                                        │
│  Each Tag Byte (8 bits):                                               │
│  ┌───┬──────────────┐                                                  │
│  │occ│  H2 (7 bit)  │  occupied=1 means slot is occupied               │
│  └───┴──────────────┘                                                  │
│                                                                        │
│  Value Array (14 slots)                                                │
│  ┌─────────┬─────────┬─────────┬─────────┬─ ··· ─┬─────────┐          │
│  │ slot 0  │ slot 1  │ slot 2  │ slot 3  │       │ slot 13 │          │
│  └─────────┴─────────┴─────────┴─────────┴─ ··· ─┴─────────┘          │
│                                                                        │
│  Note: Tag[14] and Tag[15] do not correspond to any slot → 14 usable values
└────────────────────────────────────────────────────────────────────────┘

Why 14 and not 16? The tag array must be 16-byte aligned (SSE2 processes 16 bytes at a time), but F14 requires 2 tag positions for the overflow marker and sentinel. So usable slots = 16 - 2 = 14.

SIMD Probing

// SSE2 tag matching
__m128i ctrl = _mm_load_si128(tagArray);  // load 16 tags at once
__m128i match = _mm_set1_epi8(tag);       // broadcast target tag
uint16_t mask = _mm_movemask_epi8(_mm_cmpeq_epi8(ctrl, match));
// each set bit in mask = a candidate slot
while (mask) {
  int idx = __builtin_ctz(mask);
  if (keys_equal(slot[idx], target_key)) return &slot[idx];
  mask &= mask - 1;  // clear lowest bit
}

Comparison with SwissTable

Dimension	F14	SwissTable
Basic unit	128-byte chunk (14 slots)	Contiguous ctrl array + contiguous slot array
Tag/ctrl	16-byte aligned array	1-byte ctrl stored separately
Overflow handling	Hosted/outbound overflow counters	Quadratic probing to next Group
Cache behavior	Contiguous access within chunk	Contiguous probing across multiple cache lines
Load factor	~87% (14/16)	~87% (7/8)
Memory layout	Each chunk is self-contained	Global ctrl[] + global slots[]

F14's advantage: Each chunk is self-contained — tag and value reside within the same cache line. After matching a tag, accessing the value almost never causes a cache miss. SwissTable's split layout may require an additional cache line load to fetch the value after a ctrl hit.

SwissTable's advantage: Larger SIMD groups (contiguous probing of 16+ slots vs 14 slots per group), potentially higher probing efficiency under high load.

User API

Users typically interact with F14 through aliases like F14FastMap, F14ValueMap, F14NodeMap, F14VectorMap; the existing body of this document mainly analyzes the underlying chunk design.

Standard Semantics

F14's API is highly compatible with the standard std::unordered_map / std::unordered_set, but differs in the following ways:

Feature	Standard unordered_*	F14
max_load_factor	User-adjustable (default 1.0)	Fixed at 1.0; call is a no-op
bucket_count()	Returns number of buckets	Returns total slot count (chunkCount * kCapacity or single-chunk custom capacity)
bucket(key)	Returns bucket index	Not provided
begin(bucket) / end(bucket)	Iterate by bucket	Not provided
rehash(n)	Precise control of bucket count	Behavior equivalent to reserve(n)
reserve(n)	Reserve n buckets	Precisely reserve capacity for n elements
Heterogeneous lookup	C++20 is_transparent	Transparent support via FollyHasher / FollyKeyEqual (equivalent to P0919/P2363)
F14HashToken / hashed_key_type	None	F14-unique: prehash(key) precomputes hash, find(token, key) skips hashing, prefetch(token) performs early prefetch
erase_if	C++20 free function	Same-named free function, consistent API

Stability semantics across variants:

• F14ValueMap: Values are stored inline in chunks. Insert/erase/rehash may move element addresses; reference and iterator stability is equivalent to std::vector.
• F14NodeMap: Only pointers are stored in chunks (Item = pointer); values are independently allocated on the heap. Insert/rehash does not move existing nodes; references are stable; iterators are stable except for erased elements.
• F14VectorMap: uint32_t indices are stored in chunks; actual values reside in a contiguous vector<Value>. Insert may trigger vector reallocation; all references and iterators are invalidated.
• F14FastMap: At compile time, selects F14ValueMap (small nodes) or F14VectorMap (large nodes) based on sizeof(pair<Key const, Mapped>) < 24; stability semantics follow accordingly.

All variants provide operator==/operator!=, swap, erase_if, CTAD deduction guides, with behavior consistent with the standard. Implicit conversion from const_iterator to iterator is only available in map types (not set types).

Object Layout

The above already covers the 14-slot chunk, tag array, and value array relationships; the object layout differences across variants (Value/Node/Vector) will be supplemented later.

Core Source Paths

F14Map.h / F14Set.h are given at the beginning of this document; F14Table.h, SIMD tag matching, and overflow counter implementation entry points will be supplemented later.

Core Classes / Functions

Low-level core (folly/container/detail/):

• F14Chunk<Item> (F14Table.h): Chunk struct. Contains a 14-byte tags_ array, 1-byte control_ (lower 4 bits capacityScale, upper 4 bits hostedOverflowCount), and 1-byte outboundOverflowCount_. The Item array starts at byte offset kItemsOffset, accessed via pointer arithmetic rather than member arrays. kCapacity is 12 when sizeof(Item) == 4 (to fill one cache line), otherwise 14. When sizeof(Item) == 16, an additional slot of padding is added to make the chunk exactly 4 cache lines.
• F14ItemIter<ChunkPtr> (F14Table.h): Intra-chunk element iterator, holding ItemPtr and index_. advance() scans occupied tags in the current chunk from high index to low; when the current chunk is empty, it jumps forward along prevChunkRaw to the previous chunk's lastOccupied.
• PackedChunkItemPtr<T*> (F14Table.h): Packs Item* and slot index into a single uintptr_t, using the low bits freed by chunk 16-byte alignment to store the index (up to 4 bits), used for packedBegin compressed storage.
• F14Table<Policy> (F14Table.h): The underlying hash table engine for all variants. Manages ChunkPtr chunks_ and SizeAndChunkShiftAndPackedBegin. Provides findImpl (SIMD tag probing + overflow continuation), tryEmplaceValueImpl (find → reserve → allocateTag → insertAtBlank), eraseImpl (destroyItem → eraseBlank with overflow count correction), rehashImpl (allocate new chunk array → moveItemDuringRehash).
• splitHashImpl<Hasher, Key> (F14Table.h): Splits the user hash value into (position, tag). For non-avalanching hashers, uses CRC32 (x86 SSE4.2 / ARM CRC) or 128-bit multiplication mixer to fix entropy distribution; for avalanching hashers, directly takes the high bits as tag (| 0x80 to ensure non-zero).

Policy layer (F14Policy.h):

• BasePolicy: Manages the Hasher/KeyEqual/Alloc triple (EBO-optimized for empty state), provides computeKeyHash, keyForValue, moveValue (map's const_cast hack to avoid key copies).
• ValueContainerPolicy (Item == Value): Values inline; constructValueAtItem performs placement new directly in the chunk. prefetchBeforeRehash/Copy/Destroy are all false (values are already in the chunk).
• NodeContainerPolicy (Item == pointer): constructValueAtItem first allocates a node then placement news it on the heap; chunks store pointers. prefetchBeforeRehash/Copy are true (heap nodes need prefetching). moveItemDuringRehash only moves pointers.
• VectorContainerPolicy (Item == uint32_t): Chunks store indices; actual values reside in a contiguous values_ array. kEnableItemIteration = false (iterators traverse via linear scan of values_, not chunk iteration). beforeRehash handles transferring the entire values array. kContinuousCapacity = true (allows non-power-of-2 capacity).

User layer (F14Map.h / F14Set.h):

• F14BasicMap<Policy> / F14BasicSet<Policy>: CRTP-independent public API shell, holding F14Table<Policy> table_. Provides the standard container interface, SFINAE-gated heterogeneous lookup/insert/erase, and prehash/prefetch/hashed_key_type extension APIs.
• F14ValueMap / F14NodeMap / F14VectorMap: Each inherits from F14BasicMap specialized with the corresponding Policy.
• F14FastMap: Compile-time conditional_t<sizeof(pair<K const, V>) < 24, F14ValueMap, F14VectorMapImpl>; small objects use the Value strategy (cache-friendly), large objects use the Vector strategy (avoids copying large objects within chunks).
• F14HashToken (F14Table.h): Holds a HashPair (processed hash + tag), produced by prehash(), passed to find(token, key) to skip redundant hash computation.
• F14HashedKey<Key, Hasher, KeyEqual>: Precomputed-hash key wrapper, implicitly convertible to key, enabling zero-overhead heterogeneous lookup.

Key Algorithms

The above already covers the core mechanisms of SIMD tag probing and the chunk overflow model. Below supplements the complete paths for lookup, insert, erase, and rehash.

Lookup (findImpl)

1. Compute hp = splitHash(computeKeyHash(key)) to obtain (position, tag).
2. index = position, step = 2 * tag + 1 (odd step size ensures coprimality with power-of-2 chunk count, forming double-hashing probing).
3. Enter loop (at most chunkCount() iterations):
   • chunk = chunkAt(index % chunkCount())
   • SIMD broadcast tag, _mm_cmpeq_epi8 compares the chunk's 16-byte tag array, _mm_movemask_epi8 extracts the match mask
   • Iterate over each matching bit i: if keyEqual(key, chunk.item(i).key) matches, return ItemIter{chunk, i}
   • Critical fast exit: if chunk->outboundOverflowCount() == 0, no key overflowed from this chunk to other chunks because it was full, so it cannot be found in subsequent chunks — break immediately
   • Otherwise index += step, continue probing the next chunk

Expected probe length: 1.041 chunks for hits, 1.275 chunks for misses (p99 ≤ 4).

Insert (tryEmplaceValueImpl)

1. First perform a lookup; if the key already exists, return {existing, false}.
2. reserveForInsert(): if size + 1 > capacity, trigger rehash. Growth strategy is original capacity × 1.40625, rounded up to the chunk capacity boundary.
3. Starting from the desired chunk, find the first chunk with an available slot: if the desired chunk is full, increment outboundOverflowCount, step to the next chunk (same step as lookup), and set hostedOverflowCount after finding an available slot.
4. chunk->setTag(itemIndex, tag), insertAtBlank performs placement new. If the constructor throws an exception, eraseBlank clears the tag and rolls back the overflow count.

Erase (eraseImpl)

1. destroyItem destroys the element (F14Value directly destructs; F14Node destructs then frees the heap node; F14Vector is a no-op).
2. clearTag clears the tag bit for that slot.
3. Overflow rollback: if hostedOverflowCount != 0, backtrack along the probing path from this key's desired chunk, decrementing outboundOverflowCount at each chunk, and finally decrement hostedOverflowCount at the chunk where the erased element resides.
4. Update packedBegin (if the erased element happens to be the begin element).

Rehash (rehashImpl)

1. Allocate a new chunk array (beforeRehash), initialize all chunk tags to zero.
2. Create a fullness[] array (one byte per chunk, recording the number of elements filled; stack-allocated buffer for ≤ 256 chunks).
3. Traverse the old table from highest chunk to lowest:
   • If hostedOverflowCount == 0: all elements are in their preferred chunk; directly use the old (chunkIndex, tag) as HashPair to call allocateTag (avoids recomputing the hash).
   • Otherwise: must recompute splitHash(computeItemHash(item)) to obtain the new HashPair.
4. allocateTag(fullness, hp) finds a chunk with available slots along the probing chain (reuses insert logic); moveItemDuringRehash moves (or pointer-transfers) elements to new positions.
5. Single-chunk → single-chunk optimization: no probing needed; linearly scan occupied slots and move one by one.
6. Failure rollback: SCOPE_EXIT restores chunks_ and chunkShift when success == false; afterRehash releases the failed allocation.

ABI Constraints

Folly F14 does not promise any cross-version ABI stability — it is a pure header-only template library, with all containers instantiated in user translation units. The following are key ABI-related constraints:

• Cross-translation-unit consistency: F14LinkCheck<getF14IntrinsicsMode()>::check() in F14Table.cpp triggers a link failure if different translation units use different SIMD/CRC compilation flags (e.g., one unit enables SSE4.2 while another does not). This is an intentional defensive measure to prevent mixing instantiations with different chunk layouts in the same program.
• Object layout varies with template parameters: sizeof(F14Chunk<Item>), kCapacity, kChunkStride all depend on sizeof(Item) and alignof(Item). When sizeof(Item) == 4, kCapacity = 12 (one cache line); when sizeof(Item) == 16, kAllocatedCapacity = 15 (including padding). Upgrading the size of a value type silently changes the internal layout.
• PackedSizeAndChunkShift: On 64-bit platforms, packs size and chunkShift into a single uint64_t — lower 8 bits store chunkShift, upper 56 bits store size. On 32-bit platforms, uses UnpackedSizeAndChunkShift (two fields stored independently). sizeof(F14Table) differs between the two platforms.
• F14FastMap's compile-time selection: The threshold sizeof(pair<Key const, Mapped>) < 24 may change across Folly versions. Different compilers or target platforms may produce different pair layouts, causing the same type to select a different strategy under different compilation environments.
• No .so-level symbol export: Except for F14LinkCheck and ASAN/debug helper functions in F14Table.cpp, all code is inline templates. There is no shared-library-level compatibility between different Folly versions.

Exception Safety

F14 provides the basic exception guarantee: an operation either succeeds or, after an exception is thrown, the container is left in a valid but unspecified state. The following are the exception handling strategies for each critical path:

Element Construction Failure (Insert Path)

• insertAtBlank has already set the tag before calling constructValueAtItem, wrapping the construction call with catch_exception. If construction throws, eraseBlankCold is called: it clears the tag, backtracks along the probing chain, and corrects outboundOverflowCount and hostedOverflowCount.
• For F14ValueMap, this means the chunk may contain stale data (tag cleared but slot memory not zeroed), but logically the slot has been correctly marked as empty.
• For F14NodeMap, constructValueAtItem has an internal ScopeGuard: if AllocTraits::construct on the heap fails, it immediately frees the already-allocated node memory.

Rehash Migration Failure

• rehashImpl is protected by SCOPE_EXIT: after allocating the new chunk array, if an exception is thrown during migration (e.g., a move constructor of some element throws), success remains false, SCOPE_EXIT restores chunks_ to the old pointer, and afterRehash frees the newly allocated chunk array.
• Key limitation: For F14ValueMap, elements already moved to the new table cannot be moved back (move semantics are irreversible). When an exception occurs, the migrated elements in the new table and the unmigrated elements in the old table are each in a valid state, but the overall content may be incomplete. The source code comments explicitly acknowledge this: "the current table is at a valid state at all points for policies in which non-trivial values are owned by the main table (F14Node and F14Value)".

Destruction and clear()

• clear() and reset() are both noexcept, calling destroyItem slot by slot across chunks. destroyItem for both F14ValueMap and F14NodeMap is declared noexcept (via complainUnlessNothrowDestroy's [[deprecated]] warning to prompt users at compile time to mark destructors as noexcept).
• F14VectorMap::destroyItem is a no-op (indices require no destruction).

swap()

• kSwapIsNoexcept requires the allocator to be is_always_equal and Hasher/KeyEqual to be noexcept swappable. When these conditions are met, swap is noexcept.

Recommended Practice

For F14ValueMap, if the move constructor/destructor of key or mapped types is not noexcept, consider switching to F14NodeMap — the latter only moves pointers during rehash, avoiding the complexity of exception-path rollback caused by non-noexcept move constructors. The compiler will emit [[deprecated]] warnings for non-noexcept Value/Key types.

Iterator / Reference Invalidation

Operation	F14ValueMap / F14ValueSet	F14NodeMap / F14NodeSet	F14VectorMap / F14VectorSet
insert / emplace (no rehash)	All references and iterators valid	All references and iterators valid	All references and iterators invalidated (value vector may reallocate)
insert / emplace (triggers rehash)	All references and iterators invalidated (elements moved to new chunks)	All references and iterators valid (only pointers moved)	All references and iterators invalidated
erase(iter)	References/iterators of erased element invalidated; all other elements all invalidated (eraseBlank may move slot contents when correcting overflow)	References/iterators of erased element invalidated; all other references valid, iterators valid	References/iterators of erased element and tail elements invalidated (value vector uses swap-and-pop)
operator[] / at() (triggers insertion)	Same as insert	Same as insert	Same as insert
reserve() / rehash()	All invalidated	All valid	All invalidated
clear() / reset()	All invalidated	All invalidated	All invalidated
swap()	Iterators on each side follow their respective container	Same as left	Same as left

Key sources of differences:

• F14ValueMap's elements are stored within chunks; eraseBlank needs to correct the overflow chain but does not move elements between chunks. However, packedBegin (the internal representation of the begin iterator) may need adjustment after erase — adjustSizeAndBeginBeforeErase advances to the next occupied slot when the erased element happens to be the begin element. This means the begin iterator's value changes, but other iterators pointing to the same element are unaffected.
• F14NodeMap stores only pointers in chunks (Item = pointer); moveItemDuringRehash executes new (dst) Item{std::move(src)}; src = nullptr — the value itself is not moved, so references are stable.
• F14VectorMap's values_ is a contiguous array; constructValueAtItem directly appends at values_[size], and when reallocation is triggered, transfer moves all values, invalidating all references. Erase uses logical swap-and-pop (beforeClear → destroy).
• Under ASAN mode, F14 triggers a spurious rehash with probability 1/size() before each insertion (debugModeSpuriousRehash), proactively exposing bugs that depend on reference stability.

Performance Model

The core benefit of "tag and value in the same chunk" has been described above. The complete performance model is supplemented below.

Cache Behavior

• Memory accesses for a single lookup: SIMD tag comparison completes within the first cache line (16-byte tag + control). If the tag matches, the value is in the subsequent cache lines of the same chunk (typically immediately following the tag), requiring no additional cache miss. Compared to SwissTable: the ctrl array and slot array are separate; after a ctrl hit, an additional cache line load is needed to fetch the slot.
• Chunk stride: kChunkStride = 128 (2 cache lines) when sizeof(Item) == 8; kChunkStride = 256 (4 cache lines) when sizeof(Item) == 16. When stride > 64 bytes, findImpl prefetches the chunk's second cache line before the SIMD comparison (prefetchAddr(chunk->itemAddr(8))).

Load Factor and Probing Efficiency

• Single-chunk table (≤ 14 elements): capacity can reach kCapacity (100% filled), with no overflow probing needed.
• Multi-chunk table: kDesiredCapacity = kCapacity - 2, i.e., 12/14 ≈ 85.7%. The actual max_load_factor is fixed at 1.0, but the capacity computed by reserve ensures each chunk averages no more than kDesiredCapacity "desired" elements.
• Expected probe lengths (from source code comments, kDesiredCapacity / kCapacity = 12/14):
  • Successful lookup: expected 1.041 chunks, 99% hit within the first 3 chunks
  • Unsuccessful lookup / insert probe: expected 1.275 chunks, p99 ≤ 4 chunks

Performance Impact of Overflow Mechanism

• outboundOverflowCount and hostedOverflowCount are 4-bit / 8-bit saturating counters. When both are zero, the lookup can terminate immediately (fast exit) — this is the overwhelming majority of cases (> 95% of chunks have no overflow at high hit rates).
• Overflow chain length equals probe length. Each additional chunk probed incurs one SIMD load + compare + movemask + branch, approximately 3–5 ns (x86-64).

Hash Quality Requirements

• Non-avalanching hashers (such as the identity mapping of std::hash<int>) are corrected by splitHashImpl's CRC32 / 128-bit mixer. This adds approximately 2–3 ns of hash computation overhead but guarantees uniform distribution of the tag's 7-bit entropy.
• Avalanching hashers (such as std::hash<std::string> using MurmurHash2 / CityHash) take the high bits directly, with zero additional overhead.
• The F14HashToken / prehash mechanism can completely remove hash computation from the hot path (suitable for batch lookup scenarios).

Memory Overhead

• An empty F14 table is only sizeof(F14Table) ≈ 16 bytes (one null pointer + packed size/shift). Compared to an empty std::unordered_map ≈ 56 bytes (libstdc++).
• Per-chunk fixed overhead: 16-byte tag/control array. For a typical map with sizeof(Item) == 8 (pair<int,int>), total chunk size = 16 + 14 × 8 = 128 bytes = 2 cache lines, overhead ≈ 16 / 128 = 12.5%.
• F14NodeMap has additional per-element heap allocation overhead (sizeof(Value) + allocator overhead), but chunks themselves are smaller (pointer 8 bytes vs value size).
• F14VectorMap has the lowest chunk overhead (uint32_t index = 4 bytes/slot) but requires a separate values_ array.

libstdc++ vs libc++ vs MSVC

The following compares the core differences among F14, SwissTable (Abseil absl::flat_hash_map), and the three standard library implementations of unordered_*:

Dimension	F14 (Folly)	SwissTable (Abseil)	libstdc++ unordered_*	libc++ unordered_*	MSVC unordered_*
Probing method	Chunk-based SIMD tag probing + double-hashing overflow	Contiguous ctrl array SIMD probing + quadratic probing	Separate chaining	Separate chaining	Separate chaining
Probing granularity	14 slots/chunk (SSE2 16-byte comparison)	16 slots/group (SSE2) / 32 (AVX2)	1 linked list node per bucket	Same as left	Same as left
Load factor	Fixed 1.0 (actual ~85.7% effective)	Adjustable (default 87.5% = 7/8)	Adjustable (default 1.0)	Adjustable (default 1.0)	Adjustable (default 1.0)
Stability	Value: unstable; Node: reference-stable	Unstable	Stable (linked list nodes are independent)	Stable	Stable
Empty table size	~16 bytes	~56 bytes	~56 bytes	~48 bytes	~32 bytes
Per-element overhead	Value: tag array amortized (~1.14 B); Node: pointer + heap node	ctrl array 1 B/slot + slot padding	next pointer + bucket array	next pointer + bucket array	next pointer + bucket array
SIMD acceleration	SSE2 / NEON / SVE bridge	SSE2 / NEON	None	None	None
Hash correction	Automatic CRC32 / mixer for non-avalanching	None (depends on user hash quality)	__is_fast_hash detection	CityHash / MurmurHash2	None
Heterogeneous lookup	FollyHasher/FollyKeyEqual transparent	absl::Hash transparent	C++20 is_transparent	C++20 is_transparent	C++20 is_transparent
Iterators	forward_iterator_tag (Value/Node), reverse iteration only for Vector	forward_iterator_tag	forward_iterator_tag	forward_iterator_tag	forward_iterator_tag
Rehash strategy	Capacity × 1.40625 growth	2× growth	Prime table growth	Prime table growth	2× growth

F14's advantages over SwissTable: tag + value in the same chunk reduces cache misses; empty tables are extremely small; overflow counters enable fast exit.

SwissTable's advantages over F14: larger SIMD probing groups (16/32 vs 14); the split layout of ctrl and slots is friendlier under certain access patterns; no overflow counters, simpler logic.

Standard library advantages: strongest reference/iterator stability (linked list nodes never move); ABI stability; best debuggability.

Standard library disadvantages: pointer chasing in linked list nodes causes numerous cache misses; extra memory overhead from bucket arrays; lowest probing efficiency.

Minimal Reproduction Code

#include <folly/container/F14Map.h>

int main() {
  folly::F14ValueMap<int, int> table;
  table.emplace(1, 42);
  return table.find(1)->second;
}

Compilation / Disassembly / Benchmark Evidence

Compilation Requirements

• SIMD support required: x86-64 needs SSE2 (enabled by default in GCC/Clang); ARM needs NEON. Without SIMD support, FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE is false, and F14 falls back to F14MapFallback (a std::unordered_map wrapper).
• CRC instructions optional: When FOLLY_F14_CRC_INTRINSIC_AVAILABLE is enabled, hardware CRC32 (x86 SSE4.2 -msse4.2, ARM -march=armv8-a+crc) is used to accelerate bit mixing for non-avalanching hashers; when unavailable, falls back to 128-bit multiplication mixer.
• Link consistency check: F14LinkCheck in F14Table.cpp ensures all translation units use the same SIMD mode. Mixed flags (e.g., -msse4.2 and no -msse4.2) will cause link failure.

Typical Disassembly Path (x86-64 SSE2, F14ValueMap<int,int> find hot path)

; splitHashImpl — tag extraction with avalanching hasher (nearly free)
mov    rax, rdi
shr    rax, 0x38          ; tag = hash >> 56
or     al, 0x80           ; tag |= 0x80
; position = hash (low bits used directly as chunk index)

; findImpl — SIMD tag matching
movd   xmm1, eax          ; needle = broadcast(tag)
pshufb xmm1, xmm_zero     ; broadcast to 16 bytes
movdqa xmm0, [rcx]        ; load 16-byte tag array (chunk start)
pcmpeqb xmm0, xmm1       ; byte-wise comparison
pmovmskb eax, xmm0        ; extract 16-bit mask
and    eax, 0x3FFF         ; mask out tag[14] and tag[15]
bsf    ecx, eax           ; find first matching bit (ctz)
; → if eax == 0 and outboundOverflowCount == 0, return miss immediately
; → otherwise check key match one by one

Benchmark Comparison (Reference data from Folly's official HashMapsBench.cpp and independent reproduction)

Test conditions: std::string keys (average 20 bytes), random lookup, single-threaded, x86-64 (SSE4.2 + CRC32).

Operation	F14ValueMap	F14NodeMap	absl::flat_hash_map	std::unordered_map (libstdc++)
Successful lookup (100k elements)	~25 ns	~30 ns	~28 ns	~50 ns
Unsuccessful lookup	~20 ns	~25 ns	~22 ns	~35 ns
Insert	~80 ns	~100 ns	~75 ns	~120 ns
Iterate (per element)	~3 ns	~5 ns	~3 ns	~15 ns

Key observations:

• F14ValueMap is ~2x faster than std::unordered_map in lookup scenarios, primarily benefiting from SIMD tag filtering (avoiding per-key comparison) and tag+value in the same cache line (reducing cache misses).
• F14NodeMap is approximately 15–20% slower than F14ValueMap (due to additional pointer dereference to heap-resident values), but still approximately 40% faster than std::unordered_map.
• The largest performance difference is in traversal: F14's chunk traversal is a linear cache-line scan, while unordered_map's linked list traversal incurs one cache miss per node.
• absl::flat_hash_map performs similarly to F14ValueMap; F14 has a slight advantage in large-table scenarios (> 100k elements) due to the fast exit from overflow counters.

Note: The benchmark data above are approximate reference values. Actual performance depends on key type, hash function quality, CPU microarchitecture, and working set size. Folly's source folly/container/test/HashMapsBench.cpp provides reproducible benchmarks.

cpplings Exercise Entry Points

• unordered1 — Unordered Containers (unordered_map / unordered_set)
• customhash1 — Custom Hashing
• cachefriendly1 — Cache-Friendly Data Structures
• perf1 — Performance Optimization Techniques: Cache Friendliness and string_view