Boost logo

Boost :

Subject: Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2015-02-15 11:05:12


On 15 Feb 2015 at 19:24, Amarnath V A wrote:

> 1. I could not make out the use of _oldbuckets in the code. What purpose
> does it serve?

Implementing a thread safe rehash of a concurrent unordered map is
tricky without losing a lot of performance. The assumption is that
rehashing is infrequent, so to rehash we mark all old buckets as
being "dead and please go reload the bucket list" and push the old,
now emptied bucket list into a FIFO queue such that it hangs around
for a while to make sure all threads currently using it get a chance
to spot that it is now dead, and to reload the bucket list.

Purists wil remark this isn't 100% thread safe if you rehash
frequently enough. Correct, but it's good for 1000 rehashs per second
for a 24 hour soak test on ARMv7 and Intel. The unit testing tests
100 rehashs per second for a period as a quick smoke test.

In real world code, as rehashing is manual, simply don't rehash more
than once a second. This is mentioned in bold font in the class
documentation.

> 2. I see a swap() function which is not used anywhere in the codebase. Is
> it dead code?

Consider it untested inspirational code which may or may not be
correct.

> 3. And I have a generic question regarding std::atomic. I was trying to
> code the move constructor and finally ended up failing miserably to move
> the reference of _bucket. I could not figure out how to do it. Could you
> point me to some documentation which would help me to achieve the same.

You might have a hint now above about what to do with old buckets.

> To give a fair idea about my last question, let me elaborate what I was
> trying to do. I have got the reference of _buckets and have assigned it to
> new variable using store and load methods of atomic. But, I am not
> confident if that is the right way to go about. And secondly, I see that I
> am not able to reset the reference of original.

For thread safety to be present, you can never relocate a bucket in
memory after its construction, otherwise threads using it would see
memory vanish out from underneath them during use. That is what
oldbuckets is for.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/



Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk