Boost logo

Boost :

Subject: Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2015-03-10 10:58:58

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

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


ned Productions Limited Consulting

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