Proposal: Customizable prefetch strategy for absl::flat_hash_map to avoid cache bouncing on complex keys

[AlexABorisov]

Hi Abseil Team,

We are using absl::flat_hash_map in a performance-critical, highly concurrent in-memory caching system. We have observed a severe performance degradation directly caused by the mandatory PrefetchToLocalCache inside raw_hash_set::prefetch().

After disabling these prefetch hints, we saw a massive improvement in overall map throughput and a drastic reduction in CPU stalls.

Context & Key Layout
Our key type is non-trivial (a flat structure containing an unaligned string pointer or a composite structure):

struct Key {
    uint64_t hash_metadata;
    char* string_data;
    size_t size;
    // ... custom operator== and absl::Hash implementation
};

The Problem
When looking at perf profiling data under heavy workload, the CPU spends a significant amount of cycles stalled directly on the prefetch instructions inside raw_hash_set.h:

template <class K = key_type>
void prefetch(const key_arg<K>& key) const {
  if (capacity() == DefaultCapacity()) return;
  (void)key;
#ifdef ABSL_HAVE_PREFETCH
  prefetch_heap_block();
  auto seq = probe(common(), hash_of(key));
  
  // High CPU overhead and cache stalls observed here:
  PrefetchToLocalCache(control() + seq.offset());
  PrefetchToLocalCache(slot_array() + seq.offset());
#endif
}

Root Cause Analysis
Cache Bouncing & Invalidation: In high-concurrency environments (multiple threads reading/writing to partitioned maps), standard prefetch hints indiscriminately pull control bytes and slot arrays into the local core's L1/L2 cache. If another core is modifying adjacent slots, this triggers immediate line invalidation and heavy cache bouncing.

Speculative Overhead: For non-trivial key types, single explicit cache line reads are often less expensive than constant speculative L1D prefetches that pollute the cache with data that might not be evaluated immediately.

By completely commenting out:

PrefetchToLocalCache(control() + seq.offset());
PrefetchToLocalCache(slot_array() + seq.offset());

we observed a sharp decline in L1-dcache-load-misses and CYCLE_ACTIVITY.STALLS_L1D_MISS metrics, yielding a significant latency reduction.

Proposal: Customizable Prefetch Policy
Currently, ABSL_HAVE_PREFETCH is an all-or-nothing global macro switcher. We would like to propose a way to customize or completely disable prefetch behavior on a per-map or per-key level.

Option A: Policy template parameter (Preferred C++ way)
Introduce a PrefetchPolicy trait or tag to absl::flat_hash_map:

template <typename K, typename V, 
          typename Hash = absl::Hash<K>, 
          typename Eq = std::equal_to<K>,
          typename Allocator = std::allocator<std::pair<const K, V>>,
          typename PrefetchPolicy = absl::container_internal::default_prefetch_policy>
class flat_hash_map;

Where PrefetchPolicy could be absl::no_prefetch_policy to turn prefetch() into a clean no-op for specific high-contention or complex key scenarios.

Option B: Extensible PrefetchTraits based on Key Type
Allow the map to detect if a key type explicitly opts out of prefetch:

template <typename Key>
struct prefetch_traits {
  static constexpr bool enable_slot_prefetch = true;
};

I would be happy to share our raw perf / flamegraph data if needed.

What are your thoughts on introducing this flexibility into the container design?

[derekmauro]

It is pretty unlikely that we are going to add a prefetch policy.

ABSL_HAVE_PREFETCH is not a user-selectable global switch. It is for compile-time detection of the availability of a prefetch instruction.

As far as I know, absl::flat_hash_map doesn't call prefetch() directly. The client chooses to call it. So why call it if you observe that it is slowing you down?

[AlexABorisov]

This is peace of code

template <class K = key_type>
  iterator find(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    AssertOnFind(key);
    if (capacity() <= 1) return find_small(key);
    prefetch_heap_block();
    return find_large(key, hash_of(key));
  }

Also for some reasons
PrefetchToLocalCache(control() + seq.offset());
PrefetchToLocalCache(slot_array() + seq.offset());
Was called during find operations.

also

template <class K = key_type>
  iterator find_large(const key_arg<K>& key, size_t hash) {
    ABSL_SWISSTABLE_ASSERT(!is_small());
    auto seq = probe(common(), hash);
    const h2_t h2 = H2(hash);
    const ctrl_t* ctrl = control();
    while (true) {
#ifndef ABSL_HAVE_MEMORY_SANITIZER
      absl::PrefetchToLocalCache(slot_array() + seq.offset());
#endif
      Group g{ctrl + seq.offset()};
      for (uint32_t i : g.Match(h2)) {
        if (ABSL_PREDICT_TRUE(equal_to(key, slot_array() + seq.offset(i))))
          return iterator_at(seq.offset(i));
      }
      if (ABSL_PREDICT_TRUE(g.MaskEmpty())) return end();
      seq.next();
      ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!");
    }
  }

Thats why i proposed to define prefetch strategy
Also by default ABSL_HAVE_MEMORY_SANITIZER not defined.

by the way
absl::PrefetchToLocalCache(slot_array() + seq.offset());
will not be efficient. call for

if (ABSL_PREDICT_TRUE(equal_to(key, slot_array() + seq.offset(i))))

Occurs imminently. I can say it is good idea to prefetch but it happened too late. Even better to call it before calling find_large. From my pov better to remove this prefetch because perf shows quite big spikes here.

may be it will be better. But need to test it carefully

template <class K = key_type>
  iterator find_large(const key_arg<K>& key, size_t hash) {
    ABSL_SWISSTABLE_ASSERT(!is_small());
    auto seq = probe(common(), hash);
    const h2_t h2 = H2(hash);
    const ctrl_t* ctrl = control();
#ifndef ABSL_HAVE_MEMORY_SANITIZER
      absl::PrefetchToLocalCache(slot_array() + seq.offset());
#endif
    while (true) {
      Group g{ctrl + seq.offset()};
      for (uint32_t i : g.Match(h2)) {
        if (ABSL_PREDICT_TRUE(equal_to(key, slot_array() + seq.offset(i))))
          return iterator_at(seq.offset(i));
      }
      if (ABSL_PREDICT_TRUE(g.MaskEmpty())) return end();
      seq.next();
      ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!");
    }
  }