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.
Chaman Singh Verma
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.
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?
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.