Re: [boost] Request for feedback on design of concurrent_unordered_map, plus notes on use of memory transactions

Subject: Re: [boost] Request for feedback on design of concurrent_unordered_map, plus notes on use of memory transactions
From: Bjorn Reese (breese_at_[hidden])
Date: 2014-07-30 11:19:59

On 07/27/2014 05:20 PM, Niall Douglas wrote:

> 1. Items in a bucket were kept via an atomic forward pointer to the
> next item and one used cmpxchg to insert and remove items. This had
> really great, even superb, performance for load factors near one, but
> became pathological for badly distributed hash functions (I'm looking
> at you libstdc++). Once you rehashed the hash function to make it
> better distributed, performance nose dived. I was tempted to override
> std::hash with a decent implementation ...

I would not rule out this solution. You can just tell users to supply
their own hash function to solve the distribution problem.

> Final proposed design (comments welcome):

> If value_type has a big sizeof(), a very good idea is to make the
> above a unique_ptr as otherwise you can't pack many item_type's into
> a cache line (AFIO's value_type is a std::pair<size_t,
> std::shared_ptr<>> which is 24 bytes, so item_type is 32 bytes which
> works well for my purposes).

You add storage traits so users can decide for themselves. This
trait would contain the stored type and to/from conversion functions.

> * To insert or find an item involves determining the bucket from the
> modulus of the hash by the number of buckets, locking the bucket and
> scanning the linear list for an empty item or the right item as
> appropriate. We know empty items from a magic hash value which is
> defined to some magic constant (advice on the best magic hash value
> least likely to turn up from std::hash is welcome). find() starts

std::hash already does a modulo operation, so you could simply do
another to free a number for the magic value. For example,

   auto magic = std::numeric_limit<Hash::result_type>::max();
   hash %= magic;

It will change the distribution, however, as as both 0 and max are
mapped to 0.