Niall, Thanks for the reply. Sorry for late replay as I am caught up with some assignments and examinations right now. I have coded the move constructor and move assignment operator. I am not sure how good the code is. (Again, let me reiterate I am new to C++11). Will have some time to look at that? Should I share it here in the lists or should I send you a private mail? On Sun, Feb 15, 2015 at 9:35 PM, Niall Douglas wrote:

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/

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thanks for the frank reply Niall. Firstly, I am interested in working with this project regardless of whether I get selected for GSoC. I am willing to learn C++11 and try to contribute high quality code to Boost. Secondly, I don't mind other candidates leveraging on the code I have written. I believe that's the whole point of open source. Yeah, I understand GSoC is competitive but I am a firm believer that we should keep the best interests of the community over individuals. I have decided to share the piece of code I have written. From what I understand, the code is serving the basic needs of move constructor and move assignment. As I have not extensively used C++11, I am quite unsure of anything else that I have to add to these to make the code more efficient and maintainable. I am just sharing the diff of the source code. I have skipped the diff of unittests here. Please point out any issues or improvements I can work on. Thanks in advance. - concurrent_unordered_map(const concurrent_unordered_map &); - concurrent_unordered_map(concurrent_unordered_map &&) BOOST_NOEXCEPT; + concurrent_unordered_map(const concurrent_unordered_map &); concurrent_unordered_map &operator=(const concurrent_unordered_map &); - concurrent_unordered_map &operator=(concurrent_unordered_map &&) BOOST_NOEXCEPT; public: + concurrent_unordered_map(concurrent_unordered_map &&old_map) BOOST_NOEXCEPT : _hasher(std::move(old_map._hasher)), _key_equal(std::move(old_map._key_eq + { + //Hold the rehash lock + typedef decltype(_rehash_lock) rehash_lock_t; + typedef decltype(old_map._rehash_lock) old_rehash_lock_t; + lock_guard guard(_rehash_lock, adopt_lock_t()); + lock_guard old_guard(old_map._rehash_lock, adopt_lock_t()); + _buckets.exchange(old_map._buckets.load(memory_order_consume), memory_order_release); + old_map._buckets.exchange(nullptr, memory_order_acq_rel); + old_map._buckets = new buckets_type(13); + old_map._oldbucketit = old_map._oldbuckets.begin(); + old_map._oldbuckets.fill(nullptr); + } + + concurrent_unordered_map &operator=(concurrent_unordered_map &&old_map) BOOST_NOEXCEPT + { + if (this != &old_map) { + //Hold the rehash lock + typedef decltype(_rehash_lock) rehash_lock_t; + typedef decltype(old_map._rehash_lock) old_rehash_lock_t; + lock_guard guard(_rehash_lock, adopt_lock_t()); + lock_guard old_guard(old_map._rehash_lock, adopt_lock_t()); + _buckets.exchange(old_map._buckets.load(memory_order_consume), memory_order_release); + _hasher = std::move(old_map._hasher); + _key_equal = std::move(old_map._key_equal); + _max_load_factor = std::move(old_map._max_load_factor); + _min_bucket_capacity = std::move(old_map._min_bucket_capacity); + old_map._buckets.exchange(nullptr, memory_order_acq_rel); + old_map._buckets = new buckets_type(13); + old_map._oldbucketit = old_map._oldbuckets.begin(); + old_map._oldbuckets.fill(nullptr); + } + return *this; + } Thanks, Amarnath On Tue, Feb 24, 2015 at 8:40 PM, Niall Douglas wrote:

On 24 Feb 2015 at 17:30, Amarnath V A wrote:

...

I have coded the move constructor and move assignment operator. I am not sure how good the code is. (Again, let me reiterate I am new to C++11). Will have some time to look at that? Should I share it here in the lists or should I send you a private mail?

It wouldn't be appropriate for me as the likely mentor to comment on anything specifically until GSoC student applications have closed, and then I can treat all submissions equally and fairly. So someone else here will have to comment on your work specifically, as I can only comment in very general and non-specific terms.

Regarding whether to post here with your effort for the community to inspect your work ... well, other candidates you might be competing against will see it as well. They may be able to leverage the discussion here to submit a better application than you. You may find no one here answers, and posting your answer here hasn't benefited you at all.

That said, and assuming anyone bothers to review your work, the fact you were here so early and asked for help in the right kind of way looks very positive, even if your written application compares poorly to another. There is also a valid point that if more of the community who rank GSoC applications have seen your coding skills now AND your coding skills are above average, then the chances are they will rank you more favourably.

Similarly, if your coding skills are below average, the community may well remember that and penalise you for it. If, however, you react really well to critique and show a rapid and marked improvement, then that might favour you.

I do apologise for the equivocal answer. I just wanted you to be aware that there are risks in either route, but there are also benefits. I would say that Boost is an open source software community, and its culture and how it judges others reflects that. Past that, the decision must be yours alone.

Niall --- Boost C++ Libraries Google Summer of Code 2015 admin https://svn.boost.org/trac/boost/wiki/SoC2015

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 25 Feb 2015 at 4:57, Rob Stewart wrote:

Why allocate? Just ensure old_map is destructible or assignable. Also note that new can throw which would violate your noexcept declaration.

Firstly Rob thanks for commenting in such detail. Anyone interested may be curious as to the concurrent_unordered_map algorithm, so I'll describe that here as it should completely transform what would be a correct vs an incorrect move and copy implementation. concurrent_unordered_map keeps an array of bucket_type in an atomic pointer _buckets. Each bucket_type has its own tristate spin lock where 0 is unlocked, 1 is locked, 2 is "this bucket is invalid and has been replaced, please go reload the _buckets pointer". Inserting an item looks up the bucket and locks its spin lock. It does a linear scan of the array of items in the bucket, looking for empty slots. If it finds an empty slot, it fills it. If it does not find an empty slot, it extends the array in the buckets. Erasure is very similar. Note that inserting and erasing does NOT hold the rehash lock. Rehashing is pretty much the only operation which can't run concurrently to any other, so it gets a rehash lock to enforce rehash serialisation as doing two rehashes at once could not work well. Rehashing involves creating a new bucket_type array and marking each of its buckets as locked. We replace the base _buckets pointer with the new array. We now mark all the buckets in the old bucket_type array as having state 2 (reload buckets list). We now copy the hash and pointer to every item in the old buckets array into the new buckets array. If an exception is thrown at any point, we can always restore the previous buckets list, which is untouched. If we succeed in completely transferring all the items, we remove all items from the old buckets array to reduce its memory consumption to minimum, and append the old buckets array to a ring buffer so that it hangs around for a while in memory. This is because other threads may still be inbetween the load of the buckets array and the first inspection of the bucket lock, and therefore deleting the buckets array immediately would delete the storage out from underneath them. As Rob mentioned, swap(), operator=(&&) and the move constructor are all closely related, and in many C++ classes one implements operator=(&&) entirely in terms of swap() and the move constructor. Some C++ classes can additionally implement swap() entirely in terms of move constructors, so in fact one can reduce everything to just a move constructor implementation. However, under concurrency this may or may not be ideal. I know how I'd do it, but the test here for the student is to demonstrate just how well they understand concurrent C++ programming. I would say Amarnath that I would be surprised if your posted solution would pass when tested with valgrind, and I would doubt it would pass with the thread sanitiser. I'd urge you to think about test code which when combined with valgrind and the thread sanitiser really demonstrates the correctness of your implementation under any CPU load situation. Think in terms of threads taking _seconds_ to realise that a bucket list is out of date, and you're going the right way. And keep going, you're doing well! Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

Hello Niall, I am just writing my proposal for the Concurrent Hash Tables and I had a query regarding the same. Do you expect the student to complete the implementation of unordered_set, unordered_multiset and unordered_multimap in the time frame of the programme? I see that the student might just get about 2 weeks for each of these datastructures. Is this the expectation from the student? I am not expert in this field and just wanted to confirm with you about this. Thanks, Amarnath

Hello, I have spent last few days trying to implement the move and copy constructors. But all my trials have ended up in failures. To be frank, right now I understand that I lack the basics of how to write concurrent data structures. I will like to have some pointers on where should I invest time to learn to how these are done elegantly. In particular, I would like to read upon how the constructors are written with thread safety and concurrency. Niall, any suggestions? Thanks, Amarnath

On Thu, Mar 5, 2015 at 9:34 PM, Niall Douglas wrote:

On 5 Mar 2015 at 19:34, Amarnath V A wrote:

...

I have spent last few days trying to implement the move and copy constructors. But all my trials have ended up in failures.

The fact of failure isn't anything like as important as how you failed. Can you tell us some more about exactly what failed and your best guesses as to why?

When making changes to move constructor after Rob's and Niall's review, I ended up several issues. I am not sure if these are due to my misunderstanding of the data structure or if it's because of my incorrect implementation. Nevertheless, I am sharing those here. 1. After the discussion with Niall and Rob on the piece of code I have shared here before, what I understood is that I was not marking the old map to be reloaded by the threads which are making use of it. Say, I performed a move construction of old_map and it was being used by few threads, shouldn't I mark it for reloading by those threads. From the explanation Niall had provided here, I came to the conclusion that I have to mark the newly created buckets of old_map as lock state 2. But this did not work out as expected. I ended up in a infinite loop I guess when I ran a simple unit test testing the move construction. Niall, after marking the buckets to be reloaded, how is the actual reload of the buckets performed? Do I have to some how let the threads know that you have to do a reload of the buckets? How is this achieved? I see that the lock stays in state 2 after I set it and is not switching back to 0 value. 2. For copy construction, should I do similar logic as in _rehash() method or can I just perform an atomic load and store from the old_map's buckets? I believe this is not the right way and should do something similar to the _rehash(). 3. How do I handle exceptions in move construction? On an exception, what is the move construction expected to do? Just abort whatever it was doing and restore the old_map? 4. And how about copy constructor? Are copy constructors allowed to throw exceptions? 5. Niall, one more question. I see that the thread_sanitizer unit test is not building. Please see the build #228's console output. https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.Spinloc... I see that there is an unrecognized flag "-fsanitize=undefined" and compiler is throwing the following error. g++: error: unrecognized command line option '-fsanitize=undefined' I removed the particular flag from the build script and compiled. This time it worked out and but when I ran, I see so many warnings thrown. Is this expected or is it that something needs to be fixed?

The only introductory resource I am aware of - and please, if anyone else reading can help here please chime in - is Anthony William's book "C++ Concurrency in Action: Practical Multithreading". I've never read it, but Anthony was one of the main designers of Boost.Thread, so I am taking it entirely on trust that his book is solid.

Yes, I have already come across this book. I will try to find time and read it.

I had been thinking this topic would be a standard course in Computer Science by now, but a quick search of google shows it is an optional final year module if present at all in most courses. This is a good example of how universities produce students not useful to the workplace. That said, MIT appear to have an electable web course on shared memory concurrency at http://web.mit.edu/6.005/www/fa14/classes/17-concurrency/, this might be useful.

I will go through this and see if I am able to do better. Yes, like you rightly commented, none of the universities have this as even an elective. What I know about concurrency is just what I have read online and some from my basic experience writing multi threaded applications. So, I am at an amateur level. And I will post any other problems faced from now on. I was under the impression that as this is part of competency test, the students are supposed to figure out how to do themselves. Thanks for helping out. Thanks, Amarnath

On Fri, Mar 6, 2015 at 9:49 AM, Niall Douglas wrote:

You had the situation inverted. New buckets are normally locked (1) until the copy/move is complete. Old buckets, shortly to be emptied, are locked to mark death (2) and stay that way forever.

Yeah I get that. But when I perform a move construction, should I need to create new buckets and copy items from the old map? What I was trying to achieve was different. I was trying to get the reference of _buckets of the old map and give this to the new map. After this was done, I was just creating few empty buckets and giving it to the old map. This means that I was hijacking the reference of the buckets that were being used by some threads and moved it to new map. Looks like this way of implementation is not right.

From your reply, I understand what I was trying to is not the correct way to implement move construction. Ideally, should I create new buckets and pick items one by one from the old map's buckets and copy it? And while doing it, like you said, I will be marking the new map's buckets as locked (1) and after this process is complete, I just go ahead and mark all buckets of old map as dead (2)? Is that right?

2 = this bucket is dead.

Okay. So who takes care of getting rid of the dead buckets?

That was my sloppiness on the CI config, sorry, I was running the wrong version of GCC. Fixed now.

So, if "-fsanitize=undefined" a correct flag? I am also getting the same compiler error. Could you let me know which version of gcc should I use?

You need to set the TSAN_OPTIONS environment variable to the suppressions file like this:

export TSAN_OPTIONS="suppressions=tsan.supp history_size=7"

Obviously adjusting the path appropriately. You then run the unittests_sanitise binary. The unit tests should execute very slowly, but hopefully no errors appear.

I will try this out and let you know later. Thanks, Amarnath

On Fri, Mar 6, 2015 at 7:00 PM, Niall Douglas wrote:

Move construction of the map != move construction of the buckets.

Okay. I am trying to achieve move construction in the same spirit. And I am piggybacking on Niall's implementation of _rehash(). concurrent_unordered_map(concurrent_unordered_map &&old_map) BOOST_NOEXCEPT : _hasher(std::move(old_map._hasher)), _key_equal(std::move(old_map._key_equal)), _allocator(std::move(old_map._allocator)), _max_load_factor(std::move(old_map._max_load_factor)), _min_bucket_capacity(std::move(old_map._min_bucket_capacity)) { typedef decltype(_rehash_lock) rehash_lock_t; lock_guard guard(old_map._rehash_lock, adopt_lock_t()); buckets_type &old_buckets=*(old_map._buckets.load(memory_order_consume)); size_t n = old_buckets.size(); if(n) { // Lock all existing buckets for(auto &b : old_buckets) b.lock.lock(); } buckets_type *tempbuckets=new buckets_type(13); auto untempbuckets=undoer([&tempbuckets]{ delete tempbuckets; }); buckets_type *buckets=new buckets_type(n); // Swap old buckets with new buckets tempbuckets=old_map._buckets.exchange(tempbuckets, memory_order_acq_rel); // Tell all threads using old buckets to start reloading the bucket list for(auto &b : *tempbuckets) b.lock.store(2); // Simply move the old buckets into new buckets as-is for(auto obit=tempbuckets->begin(), bit=buckets->begin(); obit!=tempbuckets->end(); ++obit, ++bit) { auto &ob=*obit; auto &b=*bit; if(ob.count.load(memory_order_relaxed)) { b.items=std::move(ob.items); b.count.store(ob.count.load(memory_order_consume), memory_order_release); ob.count.store(0, memory_order_release); } } Is this the right direction?

Old buckets go into a fixed size ring buffer, and get deleted eventually.

I couldn't really figure out where the ring buffer is which you are mentioning here. What am I missing? And another question, when I use the above implementation of move constructor and later call empty() on the newly created object, I land in a segfault. I see that the empy() checks on if the lock state is 2 and continues to check the next bucket. But, I think here I have all buckets set to lock state 2. Why did the swap I performed with the tempbuckets and oldmap._buckets not help me? Any pointers will be really helpful. Thanks, Amarnath

Hello, I have made some changes to the move constructor and also tried writing the copy constructor. Please comment on the implementation of the constructors. Does these meet the requirements and please point out if I have missed some crucial steps. concurrent_unordered_map(const concurrent_unordered_map &old_map) : _hasher(old_map._hasher), _key_equal(old_map._key_equal), _allocator(old_map._allocator), _max_load_factor(old_map._max_load_factor), _min_bucket_capacity(old_map._min_bucket_capacity), _oldbucketit(_oldbuckets.begin()) { _oldbuckets.fill(nullptr); buckets_type *tempbuckets=old_map._buckets.load(memory_order_consume); size_t n = tempbuckets->size(); buckets_type *buckets=new buckets_type(n); buckets=_buckets.exchange(buckets, memory_order_acq_rel); for(const auto &ob : *tempbuckets) { if(ob.count.load(memory_order_relaxed)) { for(auto &i : ob.items) { if(i.p) { size_t hash=_hasher(i.p->first); auto itb=_get_bucket(hash); bucket_type &b=*itb; if(b.items.size()==b.items.capacity()) { size_t newcapacity=b.items.capacity()*2; b.items.reserve(newcapacity ? newcapacity : 1); } b.items.push_back(item_type(hash, i.p)); b.count.fetch_add(1, memory_order_relaxed); } } } } } concurrent_unordered_map(concurrent_unordered_map &&old_map) BOOST_NOEXCEPT : _hasher(std::move(old_map._hasher)), _key_equal(std::move(old_map._key_equal)), _allocator(std::move(old_map._allocator)), _max_load_factor(std::move(old_map._max_load_factor)), _min_bucket_capacity(std::move(old_map._min_bucket_capacity)), _oldbucketit(_oldbuckets.begin()) { _oldbuckets.fill(nullptr); typedef decltype(_rehash_lock) rehash_lock_t; lock_guard guard(old_map._rehash_lock, adopt_lock_t()); size_t n = old_map._buckets.load(memory_order_relaxed)->size(); buckets_type *tempbuckets=new buckets_type(13); auto untempbuckets=undoer([&tempbuckets]{ delete tempbuckets; }); buckets_type *buckets=new buckets_type(n); // Swap old buckets with new buckets tempbuckets=old_map._buckets.exchange(tempbuckets, memory_order_acq_rel); buckets=_buckets.exchange(buckets, memory_order_acq_rel); // Tell all threads using old buckets to start reloading the bucket list for(auto &b : *tempbuckets) b.lock.store(2); // If it's a simple buckets cycle, simply move over all items as it's noexcept if(_buckets.load(memory_order_relaxed)->size()==tempbuckets->size()) { // Simply move the old buckets into new buckets as-is for(auto obit=tempbuckets->begin(), bit=_buckets.load(memory_order_relaxed)->begin(); obit!=tempbuckets->end(); ++obit, ++bit) { auto &ob=*obit; auto &b=*bit; if(ob.count.load(memory_order_relaxed)) { b.items=std::move(ob.items); b.count.store(ob.count.load(memory_order_consume), memory_order_release); ob.count.store(0, memory_order_release); } } } // Stop old buckets deleting stuff _reset_buckets(*tempbuckets); // Hold onto old buckets for a while typename old_buckets_type::iterator myoldbucket=old_map._oldbucketit++; if(old_map._oldbucketit==old_map._oldbuckets.end()) old_map._oldbucketit=old_map._oldbuckets.begin(); delete *myoldbucket; *myoldbucket=tempbuckets; tempbuckets=nullptr; untempbuckets.dismissed=true; } But I have peculiar issue. When I run basic unit test for the copy constructor, it fails saying it encountered a SIGABRT to memory corruption. The unit test is pretty basic and is as follows: BOOST_AUTO_TEST_CASE(works/concurrent_unordered_map/copyconstructor/basic, "Tests that concurrent_unordered_map works as expected") { printf("\n=== concurrent_unordered_map basic copy constructor ===\n"); boost::spinlock::concurrent_unordered_map map1; map1.reserve(100); // test dense map BOOST_CHECK(map1.empty()); BOOST_CHECK(map1.size()==0); for(int n=-200; n<=200; n+=2) { map1.emplace(n, n); } BOOST_CHECK(!map1.empty()); BOOST_CHECK(map1.size()==201); printf("Load factor for map1 is %f\n", map1.load_factor()); boost::spinlock::concurrent_unordered_map map2(map1); BOOST_CHECK(!map2.empty()); BOOST_CHECK(!map1.empty()); BOOST_CHECK(map2.size()==201); BOOST_CHECK(map1.size()==201); printf("Load factor for map1 is %f\n", map1.load_factor()); printf("Load factor for map2 is %f\n", map2.load_factor()); map1.clear(); map2.clear(); BOOST_CHECK(map1.empty()); BOOST_CHECK(map2.empty()); BOOST_CHECK(map1.size()==0); BOOST_CHECK(map2.size()==0); } The second last BOOST_CHECK is were I hit on this issue. And the error is Error in `/home/amarnath/work/boost.spinlock/test/unittests_1': corrupted double-linked list: 0x0000000000689200 *** But, when I remove the BOOST_CHECK and just run map1.size() and map2.size() calls, I have no issues.I tried to understand the problem but could not make out why it is failing? Any help is welcome. Thanks, Amarnath

On Tue, Mar 10, 2015 at 8:28 PM, Niall Douglas wrote:

I think you may still be trying to copy and paste parts of the existing implementation into something which works rather than creating your own implementation based on a sufficient understanding of how the algorithm works.

Yes, I was heavily relying on the existing implementation. I will rework and see if I can come up with better implementation myself.

Here's what I would suggest: get a whiteboard or equivalent and try drawing out the sequence of an insert operation on the left and an extract operation on the right. If you move the left up and down relative to the right, you can see how the concurrency can create problems if the sequence is not exactly in the right order.

From there, try to write out what a whole container copy operation must do, again with an insert and extract operation on the other side and you moving it up and down to see concurrency problems. It will yield several design choices: Should the copy be a snapshot i.e. no concurrency at all? Should the copy allow concurrency with rehashing?

Sure, I will sit down and think about the concurrency issues that will be faced when insert and extract operations are happening simultaneously.

BTW you might want to pull updates from the Boost.Spinlock git repo. I tried to get the thread sanitiser to not crash out during the unit testing over the weekend by trying to workaround a false positive it finds in _rehash() which is currently suppressed. The suppression means the sanitiser uses a lot of RAM, and it dies. Unfortunately I failed to achieve a workaround, but maybe the commented out printf's might be a hint to you as to how to go about debugging your implementation.

I will pull the latest code from the repo. Thanks, Amarnath

On 11 Mar 2015 at 7:02, Amarnath V A wrote:

...

Regarding the move constructor, I am surprised you haven't noticed it can be written in two lines yet. It wouldn't be particularly efficient, but then I didn't ask for the most efficient solution - I asked for a solution which works and is correct. This programming competency test is actually much smaller than it looks as soon as you mentally grok it, and remember that correctness is far more important than efficiency.

Niall, I was pretty confused about the move constructor. Sorry that I could not achieve what is expected.

Are these the approaches or is there a better way to get this done. Once again, I apologize if I couldn't meet the expectations of boost community out of a prospective GSoC student.

You're not doing too badly in fact. But in common with most students who get rewarded for the *volume* of code you write for coursework, you're thinking you need to write the implementation yourself to get maximum points instead of reusing existing functionality. Professional programmers shouldn't be judged by lines of code written (sadly, often they are), but by how bug free and maintainable their solution to a problem is (sadly many managers and employers don't understand how to correctly judge this). Usually, but not always, reusing already tested and debugged preexisting parts to build a solution is a superior approach to writing anything yourself. The move constructor can be written in two lines I believe. Think in terms of what other functions already present could be called to implement the move constructor for you. You should find the move constructor becomes quite trivial to implement, maybe two calls into other routines. I don't believe the copy constructor is as easy though. That you will have to implement yourself. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 14 Mar 2015 at 15:24, Amarnath V A wrote:

...

The move constructor can be written in two lines I believe. Think in terms of what other functions already present could be called to implement the move constructor for you. You should find the move constructor becomes quite trivial to implement, maybe two calls into other routines.

Taking hints from Niall's suggestions, I have re-implemented the move constructor using the member functions. Now, I extract the items first and then insert them into the new map.

concurrent_unordered_map(concurrent_unordered_map &&old_map) BOOST_NOEXCEPT : _hasher(std::move(old_map._hasher)), _key_equal(std::move(old_map._key_equal)), _allocator(std::move(old_map._allocator)), _max_load_factor(std::move(old_map._max_load_factor)), _min_bucket_capacity(std::move(old_map._min_bucket_capacity)), _oldbucketit(_oldbuckets.begin()) { _oldbuckets.fill(nullptr); auto items=old_map.extract(old_map.begin(), old_map.end()); buckets_type *buckets=new buckets_type(items.size()); buckets=_buckets.exchange(buckets, memory_order_acq_rel); insert(std::make_move_iterator(items.begin()), std::make_move_iterator(items.end())); }

Much better. Though in fact you can do better again. As I mentioned, I think maybe two lines. Remember in C++ 11 constructors can call other constructors.

...

I don't believe the copy constructor is as easy though. That you will have to implement yourself.

I am copying the snapshot of the original map when the call to the constructor was made.

concurrent_unordered_map(const concurrent_unordered_map &old_map) : _hasher(old_map._hasher), _key_equal(old_map._key_equal), _allocator(old_map._allocator), _max_load_factor(old_map._max_load_factor), _min_bucket_capacity(old_map._min_bucket_capacity), _oldbucketit(_oldbuckets.begin()) { _oldbuckets.fill(nullptr); buckets_type *tempbuckets=old_map._buckets.load(memory_order_consume); buckets_type *buckets=new buckets_type(tempbuckets->size()); buckets=_buckets.exchange(buckets, memory_order_acq_rel); for(const auto &ob : *tempbuckets) { if(ob.count.load(memory_order_relaxed)) { for(auto &i : ob.items) { if(i.p) { insert(*(i.p)); } } } } }

Now you're beginning to think more like an engineer. Good. The above is closer to working properly, but you've got a while to go yet.

Please let me know if I have got it completely wrong again. If that is the case, I don't think I should apply for GSoC this year. I have to take a step back and learn more about concurrent data structures to gain more knowledge.

"completely wrong" is too strong. Lack of experience that's all, same as any GSoC student. I'd aim for solid unit testing next. Really the competency test is testing whether students know how to test whether their solution is correct or not. I think the community ranking would favour a solid unit testing of an incorrect solution more than poor unit testing of a correct solution. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 6 Mar 2015 at 5:01, Rob Stewart wrote:

...

...

Say, I performed a move construction of old_map and it was being used by few threads, shouldn't I mark it for reloading by those threads.

This doesn't seem reasonable to me. Move semantics apply to temporaries, not to objects still in use. That applies to concurrent data structures, too. Otherwise, you have to copy the container so the container and its data are not yanked out from under other threads. Obviously, the onus is on the owner of the container to apply move semantics only when safe.

...

...

3. How do I handle exceptions in move construction? On an exception, what is the move construction expected to do? Just abort whatever it was doing and restore the old_map?

Exception safety means restoring the map to as if no change had happened with no resources leaked or data changed.

That's only true if you provide the strong guarantee.

concurrent_unordered_map is defined to be a STL drop in equivalent, so everything that unordered_map guarantees is guaranteed by concurrent_unordered_map [1]. Obviously it isn't quite as easy as that - in practice as you remove the locks around your unordered_map usage you will probably find some refactoring will be needed as just because concurrent_unordered_map is threadsafe doesn't mean the code using it is. The big aim was that a single code base with very little #ifdefing could have a macro selectable dual implementation as concurrent_unordered_map isn't as fast as a spinlocked unordered_map on average, but has much lower worst case latencies. And that's a tradeoff, with pros and cons. [1]: There is a slight issue with emplace() in that it doesn't preserve inputs on exception throw. The same problem afflicts some unordered_map implementations too. I think there was a defect before the LEWG about that. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/