kuniga.me > NP-Incompleteness > Folly F14 Map

Folly F14 Map

07 Aug 2026

Folly Logo

F14Map is Folly’s alternative to std::unordered_map and in this post we’ll explore this data structure in detail.

We’ll start with std::unordered_map which implements a more textbook version of hash maps using linked lists to handle collisions and then cover F14FastMap which uses a chunked (14 entries / chunk) open addressing implementation and leverages SIMD instructions for efficiency.

STL’s Hash Map

Recall that std::unordered_map is a hash map which uses linked lists for dealing with collision. Let’s cover the three main operations that can be performed: insertion, lookup and removal.

Insertion

When we insert a key-value pair, we first compute a hash h for the key to obtain a size_t (the hash function is configurable). Then we determine which bucket this key falls into by doing h % bucket_count. If two keys fall into the same bucket, we add to the bucket’s list.

In practice std::unordered_map uses a single linked list, but each bucket knows where its own list starts, for example:

sentinel ──> A ──> C ──> B ──> null
   ▲               ▲
   │               │
bucket[0]      bucket[2]     bucket[1] = nullptr

If we were to insert a new node for bucket 2, we can insert it between A and C and have bucket[2] point to this new node. The nodes store the value for the item.

Duplicates. We can’t just insert the item at the head and call it a day because if the key exists in the hash table we must update it instead of inserting, so we must traverse all the elements in the bucket to make sure if that’s the case. Since this is effectively what Lookup does, we’ll leave the details to that section.

In practice these operations get fused to avoid redoing work, for example determining the right bucket to insert is only done once.

Growing. As we insert more and more items in the hash table, the list for each bucket will grow and in the worst case degenerate to $O(n)$ insertion / lookup. So when the number of elements crosses a threshold, it increases the number of buckets by ~2x.

There are two “tracks” of thresholds, the default being primes that are roughly 2x apart:

2  5  11  23  47  97  197  397  797  1597  3203  6421  12853  25717

The other is power of 2. Primes are slower to apply % of (we cannot use bit shifting as with powers of 2), but they tend to hash more uniformly. In any case, every time the number of buckets changes, we need to rehash.

With a new bucket_count, the nodes will be reshuffled to different buckets so it reconstructs a new linked list from scratch by updating the next pointer of the nodes. This operation is done in $O(n)$. Note that the nodes themselves are not changed, so if we hold a reference to this node, it will be valid after the growing.

One way to avoid or reduce this overhead is to use .reserve(), much like we do for std::vector.

Lookup

For searching a key q, we need to traverse the whole list of a given bucket. How do we know when we “crossed” into the next bucket list? Each node stores the key hash (before the modular arithmetic), so when searching for an item it checks:

Note that we can’t store h % bucket_count in the node, because as we’ve seen, bucket_count can change.

Removal

Removal is straightforward, we search for an element via Lookup and remove the node from the linked list, potentially updating pointers on the bucket array.

The bucket_count never shrinks, even if most of the entries are removed.

F14Map

There are a few variants of F14Map and F14FastMap in particular decides which implementation to use at compile time based on the size of the item (key + value) being stored. If smaller than a threshold, it uses F14ValueMap which stores the items inline. Otherwise it uses F14VectorMap which externalizes the items to a vector. We’ll cover F14ValueMap first, then the differences with F14VectorMap.

F14Map relies on a lot of SIMD instructions which are not standardized between x86 and ARM architectures. For the sake of brevity we’ll use the x86 instructions, more specifically the 128-bit family SSE2.

As we did with std::unordered_map we’ll cover the 3 main operations – insertion, lookup and removal – at a high level, but then dive into some of the optimizations it uses that cannot be performed with the STL implementation, due to node allocation being done independently and hence fragmented in memory.

Insertion

The way F14Map handles collision is very different: first, the number of entries in a given bucket is fixed to 12 or 14 depending on the type of the item. The family of structures F14* is named after the latter value! I’m assuming 12 came later, probably due to some fine tuning for specific types. In any case, we’ll assume 14 for the remainder of the post for simplicity.

A structure holding the 14 entries is called a chunk. To determine which chunk an item should go to, we do h % chunk_count, much like in std::unordered_map. Note that chunk_count is always a power of 2. If that chunk is full, we try another chunk.

Before we explain how we search for the next chunk, we define the tag, which is an 8-bit value with the most significant bit set to 1 (we’ll explain the reason later) and the other 7 bits are extracted from the hash h, but the exact method for extraction varies.

We then calculate the stride, which is essentially 2 * tag + 1, which is always an odd number. This is the amount we’ll keep adding to the current index until we find a non-full chunk, wrapping around when it exceeds chunk_count. Because stride an odd number and chunk_count is a power of 2, they’re always co-prime, so we guarantee that by iterating by stride steps, we’ll cover all chunks before we repeat a chunk.

This result is not obvious, so we can prove more formally: if $k$ and $M$ are coprimes, i.e. $\gcd(k, M) = 1$, then $ik \pmod M$ are unique for $i \in \curly{0, \dots, M - 1}$.

Let's prove by contradiction. Assume $i \ne j$ but that $ik \equiv jk \pmod M$ for some $i, j \in \curly{0, \dots, M - 1}$. Then $(ik - jk) = (i - j)k \equiv 0 \pmod M$ and since $k$ is coprime with $M$, $i - j \equiv 0 \pmod M$ or $i \equiv j \pmod M$. Since bot are smaller than $M$, their "remainder" with $M$ equals themselves, which implies $i = j$, a contradiction.

The fact that stride is dependent on the tag which has 7 bits of entropy should help make sure different keys have a different distribution of strides. In other words, the order in which chunks are visited for each item should be uniformly distributed, which should keep the expected number of chunks to visit until we find a valid chunk small.

First Free Position. It’s not enough to determine that a chunk is not full. We need to determine the position at which to insert the item in a chunk. This is the first optimization that leverages SIMD (Single-Instruction Multiple Data). The chunk structure has this shape:

struct F14Chunk<typename Item> {
    std::array<uint8_t, 14> tags_;
    uint8_t control_;
    uint8_t outboundOverflowCount_;
    std::array<Item, 14> rawItems_;
};

The variable control_ clubs 2 pieces of information, but for this post we only care about the highest 4 bits, hostedOverflowCount_, which counts “how many items currently living in this chunk don’t belong here?”. We increment it whenever we insert an item on a chunk that wasn’t its first choice.

The variable outboundOverflowCount_ counts “how many items wanted this chunk at any point in their search but it was full?”. We increment it whenever we try to insert an item in a chunk that was already full.

Note that these 2 variables pad the 14 bytes of tags_ into a 16-byte value which is the “unit” for the SIMD instructions it uses.

The data is stored in rawItems_. Each item in tags_ corresponds to an item in rawItems_ and it stores the tag we just discussed. If the position i is free, then tags_[i] = 0. Recall that tags have the most significant bit (MSB) set to 1. So if we want to find the first free position, we just need to find the first position that has MSB 0. This is done by this code:

uint16_t occupied = _mm_movemask_epi8(_mm_load_si128(&tags_[0])) & 0x3FFF;
uint16_t empty = occupied ^ 0x3FFF;
if (empty == 0) { /* chunk is full */ }
unsigned slot = __builtin_ctz(empty);

The function _mm_load_si128() loads 16 bytes into a 128-bit SIMD register. Since we’re passing the address of tags_[0] it will load the 14 bytes of tags_ and the 2-byte counters.

The function _mm_movemask_epi8() takes the MSB of each of the 16 bytes and packs that into a 16-bit integer. The mask & 0x3FFF clears the bits from control_ and outboundOverflowCount_ because we don’t care about them. Then ^ 0x3FFF flips the bits on the 14 LSB. So if all positions were occupied, we would have occupied = 0x3FFF and then empty = 0.

Finally __builtin_ctz() counts trailing zeros, so it returns the first bit of empty that is set, which was the bit in occupied that was 0 and thus the index of the first position that is free!

Growing. As in the std::unordered_map, once enough entries are inserted the structure must grow. Differently from the STL version though, the chunks and the entries they hold are not stable. They need to be moved to a different location of contiguous memory because the F14Chunk is stored as a contiguous array.

It always allocates a new array though because it can’t update the chunks in place. Note that this increases the memory temporarily, while both structures are live. Then it iterates over the existing chunks and items inside each to reinsert (std::move) them into the new chunks using the same strategy except that now chunk_count is twice the previous value.

This implies that the address of the items in the hash map changes during this process, so references are not stable, which is a semantic difference with std::unordered_map.

One optimization that can be used is that during this process tags_ is compact: there are no holes because there’s no removal until we finish the rehashing, so First Free Position can be found by keeping a counter of item count for the chunk.

Another optimization that can be done because we use tags_ as the check for the presence of an element, is that when we malloc a new array of F14Chunk we don’t need to memset() the array rawItems_, we can leave garbage there. We just need to clear the first 16 bytes:

std::memset(&tags_[0], '\0', 16);

which can be done with a single SIMD instruction.

Lookup

For lookup, first we compute the tag for the key and load into the SIMD register via _mm_set1_epi8(tag). This replicates the same byte 16 times into a register, for parallel comparison.

Then, for each chunk it visits, we load the tags into a register (like we do during insertion) then compare with the key’s tag using a single SIMD instruction and then find the position where the bit is set. The code is roughly:

// once per search
__m128i needleV = _mm_set1_epi8(tag);

// for each chunk
auto tagV = _mm_load_si128(&tags_[0]);
auto eqV  = _mm_cmpeq_epi8(tagV, needleV);
auto mask = _mm_movemask_epi8(eqV) & 0x3FFF;
if (!mask) {
    // tag not in chunk
}
unsigned slot = __builtin_ctz(mask);

The function _mm_cmpeq_epi8 returns a 16-byte register. A byte is set to 0xFF if the corresponding bytes of the input are equal or 0x00 otherwise. Recall that _mm_movemask_epi8() takes the MSB of each of the 16 bytes and packs that into a 16-bit integer. Again we need 0x3FFF to exclude the bits from control_ and outboundOverflowCount_.

This acts as an early filter (think of a simplified bloom filter), but we still need to check if the key corresponding to that tag matches the searched one, so we’d check rawItems_[slot]. Note that mask might have multiple bits set if different keys map to the same tag and are on the same chunk, so we need to iterate.

The outboundOverflowCount_ can be used to stop searching early: if it’s 0, then it means no entry tried to insert on this chunk and could not, including the item we’re looking for, so if we don’t find the key here, there’s no point in continuing the search. Without this check we’d always have to scan all $O(n)$ chunks to be sure a key doesn’t exist anywhere.

Removal

The first part of the removal consists of finding the location of the element and this is exactly like Lookup. The second part consists of the cleanup. First we clear the corresponding byte in tags_ and destroy the value in rawItems_.

Then we need to update outboundOverflowCount_. We do this by replaying the insertion of the key being removed. It will start at the initial chunk (which depends only on the hash of the key) and then we’ll move by strides until we reach the chunk we’re at. On every chunk we visit we subtract from outboundOverflowCount_. The chunks we visit during removal are the same we did during insertion, no matter if other items were inserted or removed in between!

Removal by Iterator. The flow described above is when we have the key and want to remove it. This involves a lookup to find the position before erasing.

Another case is when we already have the iterator, in which case we can go straight to the removal. This is useful to apply a “filter” over the hash table, for example:

for (auto it = m.begin(); it != m.end(); ) {
    if (pred(*it)) it = m.erase(it);
    else ++it;
}

Here .erase(it) returns an iterator to the next item. When we have the iterator we know the chunk and index to remove but we don’t have the hash nor the tag. To perform the loop to update outboundOverflowCount_ we’d need to compute the hash from the key we’re at.

This is where the variable hostedOverflowCount_ can help us if it’s 0. Recall it counts: “how many items currently living in this chunk don’t belong here?”. If it’s 0, it means this is the first chunk and we don’t need to look further and we’d not need to compute the hash!

Otherwise, we need to decrement hostedOverflowCount_ after removing the element.

F14VectorMap

We use F14ValueMap whenever sizeof(std::pair<Key, Value>) < 24. Otherwise we do F14VectorMap. The main difference is that the item is not stored in the chunk’s rawItems_, but instead stored in an array, roughly:

std::pair<const Key, Value>* values_{nullptr};

which is malloc()‘ed to have chunk_count entries, then rawItems_ only stores indices/offsets to values_.

Insertion. This is very similar to before, except that we now store the value in values_[size], store size in rawItems_ and then increment size. When we need to grow, we malloc() a new array of size chunk_count * 2, and move the old values there.

Removal. The values_ array is dense, meaning that the first size positions are always occupied and the remaining contain garbage. This invariant can be maintained when removing position i by moving the last element to there and decrementing size by one. Then the rawItems_ corresponding to the swapped item must be updated to point to i. The way it’s done is by taking the key from that item to find the chunk + index using the same process as the insertion/lookup.

Comparison

The major difference between std::unordered_map and F14FastMap is that the former allocates a node for each entry, whereas for F14 it stores them in contiguous chunks of memory (both for the F14Chunk and values_ array). The STL version performs one malloc() per entry while the F14 only does malloc() when growing.

The tag system from F14 allows leveraging SIMD instructions and because the chunk is aligned at 16 bytes:

template <typename ItemType>
struct alignas(16) F14Chunk {
    std::array<uint8_t, 14> tags_;
    ...
};

The tags_ fit in the cache line.

Conclusion

In this post we learned how std::unordered_map and folly::F14FastMap work behind the scenes! I’m sure I got a bunch of details wrong but I have a cohesive understanding of the overall implementation. I’ve been curious about the 14 since I started working with folly::F14FastMap and it now all makes sense!

It was a delight to study folly::F14FastMap: both the data structure and the low-level optimizations are very clever!

We mentioned the post CPU Cache for cache lines, but also that post describes the implementation of a cache line as a hash table!

In Velox: The Vector we discussed the dictionary-encoding in which we only store indices to the actual underlying data, similar to F14VectorMap.

The post HyperLogLog in Rust also uses a hash function to determine the bucket and a function first_non_zero_bit_position which is equivalent to __builtin_ctz().

References

Source code | RSS feed RSS Icon | Tags: c++