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

On 30 Jul 2014 at 17:19, Bjorn Reese wrote:

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.

There are additional problems: (i) a concurrent_unordered_map cannot rehash automatically because iterators would spontaneously invalidate and (ii) size(), needed for rehashing, is O(buckets) which is an obvious scalability problem. That means it must be much more tolerant to high load factors than normal. I am aiming for good performance at a load factor of up to 12. AFIO is going to push the problem of bucket sizing onto its user and do no rehashing at all :)

...

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> 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.

I couldn't make rehashing exception safe without bringing in malloc for all allocations, so this has gone away. I now always use malloc.

...

* 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_limitHash::result_type::max(); hash %= magic;

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

One useful side effect of always using malloc is we can now use a null pointer to indicate the slot is unusued. This avoids the need for special hash values. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/