Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables

On 10 Mar 2015 at 18:43, Amarnath V A wrote:

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:

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. This last skill - self confidence in C++ - is probably the biggest thing we try to instill in GSoC students during a summer. It is exactly why I chose this test, indeed I got into a little hot water six months ago on this list by explicitly not finishing concurrent_unordered_map precisely because I thought this test so worthwhile for a student. 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?

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

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.

Consider adding some printf()'s to your implementation and comparing the state they report to what you thought was going on. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/