Concurrent Map, Set and SkipList ?

[csv610]

Hello,

I am looking for Concurrent Map, Set and SkipList implementation in TBB. Can someone provide me the link, if they already exist ? Otherwise, I will have to implement them for the community.

With regards.
Chaman Singh Verma
Poona, India

[Alexey-Kukanov]

No there is no such containers in TBB yet.

Designing a good semantics for concurrent methods and implementing it in such a way that provide better performance than globally-locked serial containers can provide would be an interesting exercise I suppose.

E.g. for the ordered map, which is usually implemented as a self-balancing tree (a red-black tree, for example),making this self-balancing part thread-safe and scalably concurrentshould be rather tricky, as itcan touch quite a few nodes tocompare key values or some internal fields there. Also guarantees that can be provided by concurrent map in presense of several actors (threads) that insert and remove elements at the same time are somewhat unclear. For example, what will happenif one thread looks for an element in the map, and at the same time another thread rebalances elements adjacent to the one that is searched? Would it be allowed to iterate over the map at the same time it is changed by a concurrent thread? And probably lot more of interesting designquestions will arise. I would start from looking for papers describing a possible design for concurrent map and etc.

[csv610]

Hello,

I think concurrent Map, Set and SkipList containers already exist in Java. Could you
provide me some link to some papers on this issue ?

Thanks.
csv

[Alexey-Kukanov]

I do not have links, sorry; you will need to search for it. Or might be someone else can suggest you some links or other info.

[robert-reed]

I searched the specification at the Sun J2SE 1.4.2 documentation site. There's no mention of SkipList and the concurrentMap and Set implementations are only available as the wrappers, synchronizedMap and synchronizedSet, which wrap the collections under a global lock to protect the unsafe code within. I don't think these serve as a motivating example for similar features within Intel TBB.

[RafSchietekat]

ConcurrentSkipListMap and ...Set are more recent additions (see package java.util.concurrent in Java SE 6), and their scalable implementation (lock-free!) seems well worth considering (I'm still trying to get my head around it, though, and even at Sun a group is proposing another implementation that should be simpler and provable, not lock-free yet with similar performance).

Now the question is what do we do... I've been playing around with this already (with my interest sparked by "Perhaps a tbb::concurrent_set?"), but now there's something like a race building up, and we don't like races, do we?

[Alexey-Kukanov]

Non-blocking implementations have good properties, but alsohave major drawbacks :
- such implementation is usually far from being trivial; developing and debugging takes more efforts;
- without garbage collection, non-blockingcontainers are almost nonviable - you never know if it is safe to delete an element or not;
- they usually require double-word compare-and-swap (DCAS) to prevent ABA problem, and DCAS is not available everywhere;
- as almost any container, they rely on memory allocation routines that usuallyblock anyway;
- comparing to fine-grained locking implementations, non-blocking ones usually required 3+ times more atomic (aka interlocked) operations for same actions, and thus its performance may suffer; "non-blocking" does not imply "scalable"!

We tried toimplement a few non-blocking containers and didn't achieve decent performance. So current position of us at Intel with regard to non-blocking containers is that we should better have a solid customer-driven case, i.e. it should be done with the requirements from a specific customer held in mind. Otherwise we might end up with something that noone would want to use.

But as the community people, you all are free to do your own experiments and make your own judgements, and contribute your implementations to TBB if you will. We will definitely appreciate such contributions and will make worthy implementations available to the community, though not necessarily as the part of TBB.

[Kostas_M_Intel]

Guys, I also need a concurrent set container with efficient insert/delete/find operations.

What about concurrent_hash_set? Trivially it can be implemented astbb::concurrent_hash_map< Key, T, HashCompare, Allocator > with T=Key or T=bool or whatever. Ideally i would like to havetbb::concurrent_hash_map< Key, void, HashCompare, Allocator > to save memory. Is it possible?

[RafSchietekat]

I'm afraid not, but there already is some essential overhead per element, so carrying a dummy byte should add little if anything to allocation size with TBB's scalable memory allocator.

[Andrey_Marochko]

TBB does have concurrent_hash_map and concurrent_unordered_map containers. Have you looked at them?

[Kostas_M_Intel]

Yes, I use concurrent_hash_map to implement concurrent_hash_set now. But it is desirable to have a simpler interface for a set and a more effective implementaiton (with no memory overhead for storing map values).

[Jeffrey_B_]

the problem you mention here has a bit to do with the impl of the concurrent hash map. it is bucket style impl which has advantages from a resize perspective, i.e. you don't have to 'copy' things when expandind the table. if one were to build a linear table then resize becomes an issue, i.e you have to copy objects when doing the resize. i built a lf hash map because i have lots of cases where this is the better impl. in most cases it performs better than the tbb concurrent_hash_map (2X better for most operations find, insert and erase however the test was only on workloads that I care about). the tbb impl is quite good for most cases esp where 'copy' is expensive (in my case, it is cheap).

[Andrey_Marochko]

I believe that the point of Kostas' remark is that he does not need a value attached to the key, and for him using any map implementation would mean wasting space. Honestly, I do not know why we do not provide a set counterpart of our concurrent maps. I'll ask the guys who work on concurrent containers if they have any plans in this regard.