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 https://programmers.stackexchange.com/questions/49550/which-hashing-al 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 storage. 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. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/