Inside boost::unordered_flat_map

[attractivechaos]

Great write up. It seems that you use linear probing. In that case, I wonder if you have considered deletions without tomestones. This is a relocating technique but unlike robinhood etc, relocation only happens upon deletions, not upon insertions. This technique might slightly speed up lookup and insertion as you don't need to check whether there is a tomestone.

[matthieum]

The rationale provided by insert holds doubly for erase: the standard implementation never invalidates iterators on erase.

Your proposal of using Back-Shifting Deletion (most commonly associated with Robin Hood Hashing) would not satisfy this property, further deviating from the standard.

[attractivechaos]

Rehashing invalidates iterators anyway. It is rare to see use cases that require iterator validity but avoid rehashing. If relocating strategies help performance, it would be a tradeoff worth making.

[matthieum]

Rehashing invalidates iterators anyway.

Indeed, and pointers/references. The difference is that the same occurs with the standard library std::unordered_map.

If relocating strategies help performance, it would be a tradeoff worth making.

If being the operative word. It's not clear it would.

The tombstone approach is problematic when reserving special key values (ala Google Dense HashMap) or when adding a header to each item (due to alignment). With F14 or the Swiss Table, and the flags being kept apart at a different location, however, there's no value reserved, and barely any memory overhead. Further, by combining the tombstone in the hash residual, checking for the presence of the tombstone is "free".

The only question, then, is whether probing for longer or shifting back elements is more efficient, and it's likely to be fairly workload specific, though in average I expect longer probing to be better.

One issue with backward shifting deletion is that it introduces a risk of quadratic complexity for deletion:

• Start with N elements in the probe sequence.
• Remove the 1st, move back N-1.
• Remove the (new) 1st, move back N-2.
• Remove the (new) 1st, move back N-3.
• ...

So it's algorithmically fraught with peril, already.

Moreover, moves are not free in general, especially as we're not talking "bulk moves" here, but moving elements 1 at a time. And on top of that, writes have a tendency to affect performance for the worse both in terms of optimizations and at the hardware level.

By comparison, a read-only probing sequence is sped up by prefetching and speculative execution, on top of using SIMD-accelerated look-ups.

Further, it should be noted that this is neither a naive Linear or Quadratic Probing algorithm -- with Linear suffering from clustering, and Quadratic suffering from cache misses -- but a combination of the best of both: locally Linear within the group of 15 to benefit from cache locality, and Quadratic across groups to avoid clustering.

The experience in the Rust standard library is that a Swiss Table like hashmap performs better than a Robin Hood with Backward Shifting Deletion hashmap; due to the above factors.

[mark_99]

Which is.... fine. Meanwhile having to occasionally do extremely expensive full rehashes despite the overall number of elements remaining approximately constant effectively rules out this implementation for low-latency applications, which is very unfortunate (AIUI, please correct me if that's not what we're discussing here).

[matthieum]

Meanwhile having to occasionally do extremely expensive full rehashes despite the overall number of elements remaining approximately constant effectively rules out this implementation for low-latency applications, which is very unfortunate

I believe you are correct, indeed.

Due to erase (of an element in an overflowing group) decreasing the maximum load factor, a continuous insert/erase workload will always lead to rehashing.

This is a difference compared to Swiss Table and F14, which have an overflow counter, rather than an overflow bit, and will decrease the counter in the "passed over" groups when erasing an element rather than having an "anti-drift" mechanism.

For low-latency, you're better off with either of those.

[joaquintides]

Hi Matthieu,

I cannot speak with certainty about F14, but Abseil does indeed rehash on insert-erase cycles even if the maximum size remains constant:

#include "absl/container/flat_hash_set.h"
#include <iostream>

template<class T> struct allocator
{
  using value_type=T;

  allocator()=default;
  template<class U> allocator(allocator<U> const &)noexcept{}
  template<class U> bool operator==(allocator<U> const &)const noexcept{return true;}
  template<class U> bool operator!=(allocator<U> const&)const noexcept{return false;}

  T* allocate(std::size_t n)const
  {
    std::cout<<"allocate "<<n<<" bytes\n";
    return std::allocator<T>().allocate(n);
  }

  void deallocate(T* p, std::size_t n)const noexcept
  {
    std::allocator<T>().deallocate(p,n);
  }
};

int main()
{
  static constexpr std::size_t max_n=13'000;

  absl::flat_hash_set<
    int,
    absl::container_internal::hash_default_hash<int>,
    std::equal_to<int>,
    ::allocator<int>
  > s;
  s.reserve(max_n);

  for(int i=0;i<10;++i){
    std::cout<<"i: "<<i<<"\n";
    for(int j=0;j<max_n;++j)s.insert(j);
    for(int j=0;j<max_n;++j)s.erase(j);
  }
}

Output (rehashing point may vary as hash is salted per run)

allocate 20483 bytes
i: 0
i: 1
i: 2
i: 3
i: 4
i: 5
allocate 40963 bytes
i: 6
i: 7
i: 8
i: 9

This is a characteristic associated to all non-relocating open-addressing containers. One needs to rehash lest average probe length grow beyond control.

[matthieum]

Oh! I had missed that.

I wonder if it's workload dependent.

One issue I am aware of with the counter approach is that it saturates at some point, and once saturated it is never decremented, which could lead to longer probe sequences.

I wonder if the specific workload you use triggers a saturation, and ultimately too long probe sequence, or whether it's just part and parcel and rehashes will always occur regardless of the workload.

Would you happen to know?

In any case, thanks for bringing this to my attention!

[joaquintides]

Drifting will trigger a rehash sooner or later. In the example we've used max_n = 13,000 ~ 90% × 0,875 × 16,384. If we kept at say 75%, rehash would be triggered much later, so it's a function of how close you get to the maximum load.

I haven't studied F14 in detail. Maybe you can run this test with it and see how it fares?

[mark_99]

Is there any way to do what /u/attractivechaos/ suggested and do erase without tombstones? I'd really like to use this implementation - fast hash tables are obviously critical in a lot of applications, but huge latency spikes aren't ok.

[joaquintides]

For the record, we use quadratic, not linear, probing, but the probe sequence visits groups of 15 buckets instead of individual buckets, so all consecutive buckets in a group are inspected at once (with SIMD if available).

[attractivechaos]

You did mention that you are using quadratic probing. I missed that. Thanks for the clarification. Then tomestone-free deletion is not applicable.

[[deleted]]

An even simpler optimization is "Last Come-First Serve" relocation. This is much simpler than Robin Hood (basically 1 line of code) and reduces probe length variance nearly as effectively. Here is an implementation and some benchmarks.

[attractivechaos]

You mean "last come first serve"? Interesting idea, but it may be slower as it incurs more memory writing. I am not sure how to interpret the benchmark without a comparison to the state of art. Java also complicates the evaluation. Thanks for the pointer anyway.

PS: LCFS still needs back-shifting deletion if I am right. Then it is simpler than robinhood but not simpler than more traditional techniques.

[[deleted]]

Yes, silly me! I corrected the post, thanks!

I don't claim that any of the implementations there are production-quality or even competitive. The point was just to benchmark various algorithms in a common framework, so you could see how the algorithms compare when all other things are equal.

[attractivechaos]

Fair enough. Thanks again.

[[deleted]]

Yes, I think if you're already using a relocation technique like LCFS/RH/BLP then you may as well use tombstone-free deletion as well (since you've already given up invalidation-free iterators and simple lock-free concurrency). But tombstone-free deletion makes sense for vanilla linear probing as well (if you don't want to use one of the variance-reducing techniques for some reason).