Boost logo

Boost :

Subject: Re: [boost] Request for feedback on design of concurrent_unordered_map, plus notes on use of memory transactions
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-07-28 06:08:26

On 28 Jul 2014 at 13:26, Gavin Lambert wrote:

> On 28/07/2014 03:20, Niall Douglas wrote:
> > * item_type is allocated via a rebind of the supplied allocator, and
> > looks like:
> >
> > struct item_type
> > {
> > value_type p;
> > size_t hash;
> > };
> I presume this will support partial construction to handle the case when
> value_type does not have a default constructor, or is movable-only, etc?

My partial implementation will only support move construction, as
that is all I need to store shared_ptr.

You're right that there is a small object vs large object
optimisation opportunity here.

> > * 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).
> Isn't it by definition (admittedly reality is less ideal) that all hash
> values have equal probability? What happens if a real item does end up
> with the magic "empty" hash value? I think it'd be safer to have a
> separate flag for this case.

Firstly, if the magic hash value ever turns up during insert the
program aborts :) It should, hopefully, be exceedingly rare on 64 bit
to the point that we don't care [1].

Secondly, a separate flag costs another 8 bytes, and it ruins the
cache line symmetry for AFIO where items size out to 32 bytes which
is a lovely multiple.

[1]: On libstdc++ a hash of a size_t is that size_t. As AFIO
increments a size_t from 1 onwards, any magic value with a top bit
set is safe. MSVC tries rather harder and for a size_t it uses the
FNV-1a hash function which is rated as second best overall (but best
for numbers) at
gorithm-is-best-for-uniqueness-and-speed. FNV-1a looks pretty random
to me.

> > * To erase an item is easy: iterators store an iterator to the bucket
> > and an offset into the linear table. Erasure involves constructing a
> > temporary value_type, locking the bucket and performing a *move*
> > construction out of the table into the temporary value_type,
> > resetting the hash to empty. Destruction can then occur without
> > holding the bucket lock. If the item just erased is the last in the
> > bucket, the bucket's size (not capacity) is reduced by one, and that
> > is repeated until the bucket size is the minimal possible.
> If the hash is reset to empty and the lock released before destruction
> occurs, doesn't that mean that something else could try to concurrently
> construct into the same storage? After all, the item slot will now look
> empty to insert().

We have to be careful here about "destruction of what?". The
assumption is that the value_type inside the item_type is left in a
low cost or default state after being moved out of it, so the lock is
held during the move, after which that slot will be available for use
by someone else who may claim the lock and move construct into that

If someone held a reference to that value, then it would suddenly
change contents in a racy way. But it would still point to an
unrelocated value of that type, and therefore I believe is safe for
most uses.

As destruction is generally slow (free() etc), that's why the bucket
lock isn't held for it. It makes an enormous difference to
concurrency anyway.

> Similarly the bucket size could be reduced by one
> just as insert() puts something into that bucket slot (thinking that it
> was still within the valid range, so not trying to increment it itself).

The lock is held during all resizes of the bucket.

> > * size() under this design becomes O(bucket count) as we sum the
> > count members of each bucket. empty() is worst case O(bucket count)
> > when the map is empty, best case O(1) when the first bucket is not
> > empty, average case O(bucket count/item count/2).
> You could use a relaxed count at the top level to improve this,
> possibly.

I didn't mention the atomic count in each bucket as I thought it
obvious, but it holds the number of valid entries in each bucket.
This saves size() or empty() having to iterate the bucket tables.

> size() and empty() become statistical rather than
> prescriptive in the presence of concurrent writes anyway, so a stale
> value is not harmful. Although I suppose conversely updating a shared
> counter will cause cache contention performance loss for insert/erase,
> which may not be worth it for the benefit of statistical functions that
> are less likely to even be called in a concurrent design.

Exactly. It's trivial to keep a top level atomic count, but the
concurrency consequences are dire. I do really wish I knew of a
better way for empty() to have constant time though :(

> > Thoughts on this design before I write a final implementation are
> > welcome. I don't plan to complete my implementation past the minimum
> > needed for proposed Boost.AFIO, so if someone else wishes to finish
> > it that and make it part of official Boost that would be great.
> I presume you've looked at other common implementations of this sort of
> thing? eg. libcds.

I did do quite a bit of prior art research, and was surprised that no
one seems to have had a crack at a STL compliant
concurrent_unordered_map apart from the Intel TBB and Microsoft PPL
implementations, both of which don't allow concurrent erase which is
a showstopper. I don't have the time to complete my implementation
past what I need now, but I was thinking it would make a great GSoC
for 2015 and Boost (and the STL) is in sore need of a decent
concurrent_unordered_map with a different set of design compromises
to the split ordered list designs.

The libcds implementations don't follow the STL API, and unless I
missed something they get their speed from some clever memory
allocation tricks which require threads to call init and cleanup
routines to initialise thread local state. I didn't look deeply here,
so if I am wrong please do correct.


ned Productions Limited Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at