Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Concurrent Containers

Reply
Thread Tools

Concurrent Containers

 
 
Scott Meyers
Guest
Posts: n/a
 
      09-01-2010
Although C++0x includes support for concurrency, it offers no standard
containers that support simultaneous readers and writers. Java and .NET
developers have them as part of their standard libraries (e.g., Java's
Concurrent HashMap and ConcurrentLinkedQueue, .NET's ConcurrentQueue and
ConcurrentBag), but, from what I can tell, there don't even seem to be any de
facto standard concurrent containers for C++ developers. For example, Boost
doesn't seem to offer any.

The closest thing I can find to a portable cross-platform API for concurrent
containers are concurrent_vector and concurrent_queue offered independently by
Intel via TBB and Microsoft via PPL, but where both companies have pledged to
offer "identical concurrent STL container solutions" (per
http://tinyurl.com/2cgr22p). (That same page suggests that Intel and MS both
also offer concurrent_unordered_map, but that container is not listed at the PPL
web site (http://msdn.microsoft.com/en-us/library/dd504906.aspx)).

If I'm a cross-platform C++ developer who wants to take advantage of the work
others have done to develop, debug, and tune a concurrent container (i.e., I
don't want to write and maintain my own), what are my choices? Obviously, the
container I choose will depend on the problem I'm trying to solve, but what's on
the pre-built cross-platform concurrent container menu?

Thanks,

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
(http://cppandbeyond.com/)
* License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
personal use (http://tinyurl.com/yl5ka5p).
 
Reply With Quote
 
 
 
 
Chris M. Thomasson
Guest
Posts: n/a
 
      09-01-2010
"Scott Meyers" <(E-Mail Removed)> wrote in message
news:i5m4ee$ei9$(E-Mail Removed)...
> Although C++0x includes support for concurrency, it offers no standard
> containers that support simultaneous readers and writers.

[...]
> If I'm a cross-platform C++ developer who wants to take advantage of the
> work others have done to develop, debug, and tune a concurrent container
> (i.e., I don't want to write and maintain my own), what are my choices?
> Obviously, the container I choose will depend on the problem I'm trying to
> solve, but what's on the pre-built cross-platform concurrent container
> menu?


I am VERY sorry that I simply have no time to explain the details right now,
but FWIW C++0x actually does provide a perfect medium for creating fairly
efficient garbage collected concurrent containers. For instance, here is a
full blown example of a garbage collected lock-free node-based stack that is
based on one of my proxy collector algorithms:

http://groups.google.com/group/comp....3f24de178b419f
(please try to read entire thread...)

And here is a relevant discussion on the Boost threading mailing list:

http://thread.gmane.org/gmane.comp.l...0/focus=198747
(please try to read entire thread...)



Here is a brief description of what proxy garbage collection is "all about":

http://groups.google.com/group/comp....f29efe33e7f124




Here is recent implementation of one of my proxy garbage collector
algorithms in Relacy 2.3:

http://cpt.pastebin.com/f71480694




Here is where you can learn about and download a copy of Relacy 2.3:

http://groups.google.com/group/relacy

http://groups.google.com/group/relac...7ecceb5f1bf80b


IMHO, Relacy Race Detector is one of the _best_ synchronization verification
systems out there!



When I get more time I will explain how a proxy collector algorithm can
efficiently solve the reader/writer problem in _many_ diverse situations.



Here is some more info:

http://webpages.charter.net/appcore/vzoom/round-1.pdf

http://webpages.charter.net/appcore/vzoom/round-2.pdf

FWIW, those "papers" referred to my vZOOM algorithm entry in Sun
Microsystems CoolThreads contest:

https://coolthreads.dev.java.net

I was one of the finalists, and it got a brand new SunFire T2000. I was very
pleased!

;^)


 
Reply With Quote
 
 
 
 
Balog Pal
Guest
Posts: n/a
 
      09-01-2010
"Scott Meyers" <(E-Mail Removed)>
> Although C++0x includes support for concurrency, it offers no standard
> containers that support simultaneous readers and writers. Java and .NET
> developers have them as part of their standard libraries (e.g., Java's
> Concurrent HashMap and ConcurrentLinkedQueue, .NET's ConcurrentQueue and
> ConcurrentBag),


I'm light on java but what I picked up about 'concurrent' containers, (and
even more generally about using threads) is pretty sour. The early
collections with everything synchronizes did not solve any real life use
case but introduced slowdown. Later the programs were full of undefined
behavior due to race conditions. LAter people swithhed to the 'concurrent'
stuff thet converted UB to exceptions thrown here there and everywhere.

In sunmmary I saw only different flavors of broken software, and supposed
'architects' fighting to shuffle bugs around. Instead of looking at the
fundamental issue/root cause: lack of MT design and lack of even recognition
that one is needed. After all tha language is 'safe' and the tools have
all thet 'synchronized' or 'concurrent' names.
((

C/C++ was at least still put in some hurdles to infest a program with
threads, and left some sanity.

> but, from what I can tell, there don't even seem to be any de facto
> standard concurrent containers for C++ developers. For example, Boost
> doesn't seem to offer any.


Is there such thing at all? Now really.

I try to recall my own stuff: I used 'concurrent' queue, in fact many
flavors of it, to communicate between threads. Despite it being
ubiquitous as usage pattern I hardly have in in a stock library, but put
together one in the new arena. Tuned to the actual way of use, and
properties of payload.

And observed others do in a similar way.

As far as the standard: it failed miserably on the much simpler case to
give us a *string*...

On this topic I'd rather keep is conservative and teach people thinking MT,
and able to use the elements in combination. I see the chances to mess up
that way is lower than it would be from picking supposedly pre-assembled
elements.


 
Reply With Quote
 
Scott Meyers
Guest
Posts: n/a
 
      09-01-2010
On 9/1/2010 11:50 AM, Chris M. Thomasson wrote:
> "Scott Meyers"<(E-Mail Removed)> wrote in message
>> If I'm a cross-platform C++ developer who wants to take advantage of the
>> work others have done to develop, debug, and tune a concurrent container
>> (i.e., I don't want to write and maintain my own), what are my choices?

>
> I am VERY sorry that I simply have no time to explain the details right now,
> but FWIW C++0x actually does provide a perfect medium for creating fairly
> efficient garbage collected concurrent containers.


But that's not the question. C++ offers the capabilities to write anything I
want, but if I want to use a container that's already written and is likely
correct, I can use any of the containers in the standard library, as long as I
don't care about the ability to concurrently modify the container. Most of the
time, it's just not worth my trouble to write a container from scratch.

What I'm looking for now are portable, proven containers that do support
concurrent modification. Could I write one from scratch? Sure. But I'd rather
spend my time doing other things if at all possible.

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
(http://cppandbeyond.com/)
* License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
personal use (http://tinyurl.com/yl5ka5p).
 
Reply With Quote
 
Joshua Maurice
Guest
Posts: n/a
 
      09-01-2010
On Sep 1, 12:15*pm, "Balog Pal" <(E-Mail Removed)> wrote:
> "Scott Meyers" <(E-Mail Removed)>
>
> > Although C++0x includes support for concurrency, it offers no standard
> > containers that support simultaneous readers and writers. *Java and .NET
> > developers have them as part of their standard libraries (e.g., Java's
> > Concurrent HashMap and ConcurrentLinkedQueue, .NET's ConcurrentQueue and
> > ConcurrentBag),

>
> I'm light on java but what I picked up about 'concurrent' containers, (and
> even more generally about using threads) is pretty sour. The early
> collections with everything synchronizes did not solve any real life use
> case but introduced slowdown. Later the programs were full of undefined
> behavior due to race conditions. LAter people swithhed to the 'concurrent'
> stuff thet converted UB to exceptions thrown here there and everywhere.
>
> In sunmmary I saw only different flavors of broken software, and supposed
> 'architects' fighting to shuffle bugs around. Instead of looking at the
> fundamental issue/root cause: lack of MT design and lack of even recognition
> that one is needed. * *After all tha language is 'safe' and the tools have
> all thet 'synchronized' or 'concurrent' names.
> ((
>
> C/C++ was at least still put in some hurdles to infest a program with
> threads, and left some sanity.


Agreed that the original Java "thread-safe" containers were uselessly
slow from the synchronized methods which solved nothing. However, some
of the newer Java containers, which Scott mentions, such as
ConcurrentHashMap, do offer useful functionality, such as an atomic
"put entry in map if not present". I've made use of that function
several times.

A blocking queue for multiple consumers and multiple consumers would
be nice too. IIRC, Java has several flavors here, such as one with a
capped size based on an array - attempts to push to a full queue
blocked the producer, and another with a limitless size so that the
producer is never blocked.
 
Reply With Quote
 
Balog Pal
Guest
Posts: n/a
 
      09-01-2010

"Scott Meyers" <(E-Mail Removed)>

> But that's not the question. C++ offers the capabilities to write
> anything I want, but if I want to use a container that's already written
> and is likely correct, I can use any of the containers in the standard
> library, as long as I don't care about the ability to concurrently modify
> the container. Most of the time, it's just not worth my trouble to write
> a container from scratch.
>
> What I'm looking for now are portable, proven containers that do support
> concurrent modification.


Please define 'correct' for the scope of your discussion.

I recall a plenty of good articles on the topic of collection vs. MT -- or
rather on what is expected from the class to be called 'thread-safe' and
what is not. Not sure if it was Herb Sutter or someone else. With very
good examples on how a list or vector shall rptect its internal state on
some operations ((that the user can't ralisticly cover or even recognise as
a possible problem) -- while still leaving the obligation to lock around
for others -- where the collection can't really guess the intent.

In real life critical sections you protect a set of data -- and that set is
IMO too rarely match what we call 'container' in C++. It is mos likely a
class, a few members of a class, a few unrelated objects, or some existing
elements in a container.

As a transaction must involve them together, something a collection can
offer is more in the way than helps. Generally.

 
Reply With Quote
 
Balog Pal
Guest
Posts: n/a
 
      09-01-2010
"Joshua Maurice" <(E-Mail Removed)>

> However, some
>of the newer Java containers, which Scott mentions, such as
>ConcurrentHashMap, do offer useful functionality, such as an atomic
>"put entry in map if not present". I've made use of that function
>several times.


Sure, the progress with the collections is clear -- just they are still no
silver bullets (obviously) and can't replace the missing design elements.

>A blocking queue for multiple consumers and multiple consumers would
>be nice too.


This far it did not fit too well with the STL approach. As current STL is
full of copy operations -- and my queues were more likely holding pointers.
With allocation ownership issues placed to different parties. I was meny
times tempted to use some smart pointers there, especially shared_ptr, then
dropped it.

For other cases the payload supported swap, and that was used for good.

As move semantics enter, the picture may change here.


>IIRC, Java has several flavors here, such as one with a
>capped size based on an array - attempts to push to a full queue
>blocked the producer, and another with a limitless size so that the
>producer is never blocked.


See, the proliferation starts here. And in C++ you should add a policy for
move, a policy for allocation/destroy (that could be different that the
%$#@#%$ allocator<> we carry around). How far we got in practice with
customizable things in std this far? After all we can create a locale and
imbue it in a stream, can we? ;-o


 
Reply With Quote
 
Scott Meyers
Guest
Posts: n/a
 
      09-01-2010
On 9/1/2010 1:01 PM, Balog Pal wrote:
> Please define 'correct' for the scope of your discussion.


Correct means what it always means: the API does what it promises (e.g., all
invariants and postconditions are satisfied). For example, if I have a
ConcurrentSet that tells me I may concurrently perform multiple inserts, after
the concurrent inserts are done, I should find exactly one copy of each thing
that was inserted and zero copies of things that were not inserted.

> As a transaction must involve them together, something a collection can offer is
> more in the way than helps. Generally.


Concurrent containers don't claim to solve all concurrency problems, nor do they
promise that clients will never have to worry about concurrency issues
(including transactional issues such as you mention). They simply promise that
certain kinds of operations that would not normally be safe if performed
concurrently on a non-concurrent container are safe on the concurrent container.
So a concurrent queue (useful for producer/consumer systems) permits enqueue
and dequeue operations to proceed concurrently. A concurrent hash table
(potentially useful for, e.g., a cache shared across threads) might permit
concurrent insertions.

A *lot* of effort has gone into developing concurrent containers in Java and
..NET, as well as in C++ libraries such as TBB and PPL. To suggest that all that
effort has been misguided, because there are no common use cases for such
containers, is untenable.

Are there wrong ways to write concurrent containers? Sure. Did Java employ
them in its synchronized collections. It did. But neither of those
observations reflects on the fundamental utility of the idea of concurrent
containers. That question, IMO, has been settled for some time.

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
(http://cppandbeyond.com/)
* License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
personal use (http://tinyurl.com/yl5ka5p).
 
Reply With Quote
 
Balog Pal
Guest
Posts: n/a
 
      09-01-2010
"Scott Meyers" <(E-Mail Removed)>

>> Please define 'correct' for the scope of your discussion.

>
> Correct means what it always means: the API does what it promises (e.g.,
> all invariants and postconditions are satisfied). For example, if I have
> a ConcurrentSet that tells me I may concurrently perform multiple inserts,
> after the concurrent inserts are done, I should find exactly one copy of
> each thing that was inserted and zero copies of things that were not
> inserted.
>
>> As a transaction must involve them together, something a collection can
>> offer is
>> more in the way than helps. Generally.

>
> Concurrent containers don't claim to solve all concurrency problems, nor
> do they promise that clients will never have to worry about concurrency
> issues (including transactional issues such as you mention). They simply
> promise that certain kinds of operations that would not normally be safe
> if performed concurrently on a non-concurrent container are safe on the
> concurrent container. So a concurrent queue (useful for producer/consumer
> systems) permits enqueue and dequeue operations to proceed concurrently.
> A concurrent hash table (potentially useful for, e.g., a cache shared
> across threads) might permit concurrent insertions.
>
> A *lot* of effort has gone into developing concurrent containers in Java
> and .NET, as well as in C++ libraries such as TBB and PPL. To suggest
> that all that effort has been misguided, because there are no common use
> cases for such containers, is untenable.


Appears I compressed my thoughts too far, to lose essential elements.
And possibly captured the scopoe of your question incorrectly too.

I was thinking in the scope of a (possible) C++ standard. The problem is
exactly what you emphasice above. A *lot* of effort was put in that field.
And the results are not so bright even in their native environment. But
IMO (!_ even if the results were perfect in java/C#, poted to the C++
environment would not be good enough.

Especially compared to to effort of a creating them by hand.

IMO people who can pick java, will do so. Those who use C++ do that for
reasons like they need the control and performance.

Having some collection that can magically withstand all kinds of operations
from random threads looks really nice. Really. Having some time I'd jump
on it to analyse how it is done and applaud.

But I doubt I'd use such a generic solution in my app. Because having random
threads keep poking a shared collection sounds like a blasphemy. With MT
design we fight to limit sharing as much as possble, for good reasons.
Sharing objects, sharing operations, etc. And using a proper sync op
around what remains shared is not a problem, especially since RAII was
invented to guard the mutex lock.

And going back to the C++ standard, the people creating it (I guess) have
fragment of resources that owners of java and C# has at disposal.

That is why I don't expect to see it there anytime soon (read: in my
lifetime).
And I see the lack of 'de facto standard' going to similar causes.

The java way is to have everything and the pussycat in the lib. The lib is
written by Sun. Or was to yesteryear. And it is considered good enough.

C++ users have no such supplier, and on the other end are more picky. Both
in width and limits of expectations. After all the 'you don't pay for what
you don't use' is still in place. As I can visualize the implementtion of
a concurrent container, and its actual use in a real program -- I'm skeptic
whether it can hold.

To put it another way, in my view in the C++ environment the idea has a bad
tradeoff. But I do not claim my view to be some objective truth, neither
shall it be extrapolated outside its scope.

Boost covers so much stuff and has that fine selection of developers. And it
does have components for both threading and collections. But not for
concurrent collections. My explanations to "why" is that people there also
found it a poor tradeoff. I'm open to hear any other explanation.


And rereading the initial post, your question was what is the menu, not why
is it so thin -- sorry to kinda sidetrack it.


 
Reply With Quote
 
tni
Guest
Posts: n/a
 
      09-01-2010
On 2010-09-01 22:29, Scott Meyers wrote:
>
> A *lot* of effort has gone into developing concurrent containers in Java
> and .NET, as well as in C++ libraries such as TBB and PPL. To suggest
> that all that effort has been misguided, because there are no common use
> cases for such containers, is untenable.
>
> Are there wrong ways to write concurrent containers? Sure. Did Java
> employ them in its synchronized collections. It did. But neither of
> those observations reflects on the fundamental utility of the idea of
> concurrent containers. That question, IMO, has been settled for some time.


Really? There are a couple of useful concurrent containers: messaging
infrastructure (queues) and maybe maps for certain applications. Beyond
that, the value rapidly diminishes.

If the container interface doesn't allow you to perform the transactions
you need, it's useless. Very often, more than a single container is
going to be involved in a transaction.

What are those magic containers of general value that you are talking about?

\\

In general a mutex should be be cheap. I.e. if you look at Linux
Pthreads or Qt, a lock / unlock will be a single atomic operation in the
uncontested case. For most applications, a concurrent container won't do
better than just using a standard container with a mutex (even if it's
some fancy lock-free whatever). With RAII, exception safety for the
locking operation can be trivially had.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Are sequence containers not a subset of general containers? Sebastian Mach C++ 5 10-06-2012 07:54 PM
Containers of iterators vs. containers of references clark.coleman@att.net C++ 7 01-25-2008 01:37 PM
problems locating the concurrent EDU.oswego.cs.dl.util.concurrent package Pep Java 6 08-16-2005 07:26 AM
Concurrent ICS + wireless print server usage =?Utf-8?B?QW5keVM=?= Wireless Networking 3 04-21-2005 06:23 PM
Concurrent assignments to std_ulogic_vector slice is OK with ModelSim Nicolas Matringe VHDL 9 06-14-2004 10:10 PM



Advertisments