Re: thread safety of C++ standard library
Re: thread safety of C++ standard library
- Subject: Re: thread safety of C++ standard library
- From: Jonathan Prescott <email@hidden>
- Date: Tue, 1 Dec 2009 18:15:22 -0500
std::sort is a template function defined in /usr/include/c++/(4.0.1,4.2.1)/bits/stl_algo.h. If you look at the code, you'll see that it's not thread-safe, and it's actually platform-independent (I first saw these routines on SGI stuff way back when). They've been updated by the gcc folks to add in some gcc-specific conventions, but, the algorithms themselves are almost direct from SGI IRIX.
However, that may be all right. First thing you need to decide is what are you worried about when you are concerned about thread safety? I'm assuming that your concern is that 1) the collections you want to sort are global thread variables, and 2) that being the case, you don't want the collections being sorted to be changed underneath you while you are sorting. If that is the case, you will need to read-lock both collections using pthread mutexes or some other synchronization technique before sorting. If the iterators are declared as local to the thread doing the sorting, like:
std::vector<int> collect1;
std::vector<int>::iterator itor1=collect1.begin();
std::list<double> collect2;
std::list<double> itor2=collect2.begin();
std::sort(itor1, itor2, IntToRealLT);
then, as long as collect1 and collect2 are protected through a mutex lock or locks, you should not have a problem. However, if itor1 and/or itor2 are global variables themselves, then, they will need to be locked as well to protect against some other thread modifying the contents of the iterators while sort is doing its thing.
Unless someone has written a specialized version of the STL and included system-specific locking conventions (a lot of work for little return on the part of the vendor), most vanilla implementations are derived from the HP/SGI template code ( the "T" in STL). It's difficult to write thread-safe code at this low a level since its hard to define what "thread-safe" really means at this level and doesn't conflict with developer's requirements. Philosophy is that the STL provides standard implementations of standard algorithms, and, since the developer is in the best position to figure out the access requirements to containers, iterators, etc., it's better that the developer provide whatever access protections are deemed sufficient to the containers being used external to the container.
Jonathan
On Dec 1, 2009, at 5:30 PM, John Weeks wrote:
> Jens Alfke <email@hidden> replied:
>
>> On Dec 1, 2009, at 1:36 PM, John Weeks wrote:
>>
>>> In particular, is std::sort thread-safe when working with distinct
>>> containers? That is, std::sort(iterator, iterator, predicate) where
>>> the
>>> iterators point to different containers.
>>
>> I don't know for sure, but I would guess not. It's often (generally?)
>> considered inappropriate to design thread-safety into low-level
>> collection classes, as it adds overhead to the more common case where
>> an object is being used from only one thread.
>>
>> For instance, the original Java 1.0 collection classes were thread-
>> safe, but were soon deprecated in favor of the Java 1.2 collections
>> that are not, and performance was one reason for the change.
>> CoreFoundation's collections aren't thread-safe either.
>>
>> It's better to look at the concurrency of your larger scale object
>> model and add locks at appropriate places, than to assume things get
>> handled for you at a lower level. (In particular, in the case you
>> describe that works on two collections, I can imagine it would be very
>> hard for STL to avoid lock ordering problems; you'd need to decide on
>> a policy yourself.)
>
> Thank you, Jens.
>
> That's all fine, and I just re-read Scott Meyers on STL thread-safety. My
> problem is that I wouldn't know what to lock. Certainly not the containers;
> they are different containers. The iterators? Won't new ones be generated
> as sort runs? How do I lock an iterator so that std:sort respects my lock?
>
> Perhaps the answer is simply: No, std::sort is not thread-safe, and I need
> to roll my own sort.
>
>
>
> Rush Manbert <email@hidden> replied:
>
>>> In particular, is std::sort thread-safe when working with distinct
>>> containers? That is, std::sort(iterator, iterator, predicate) where the
>>> iterators point to different containers.
>>
>> I think that's your problem. The iterators need to point to the same
>> container. The sort algorithm operates in place.
>
> I wasn't careful with my wording. I have two threads, each calls std::sort.
> Each thread has a container (a vector) to be sorted. In each thread the
> iterators point to that thread's container. By "iterators point to
> different containers" I was referring to the fact that the different
> threads were working on different containers, not that a single call to
> std:sort used iterators pointing to different containers.
>
> Regards,
> John Weeks
>
> WaveMetrics, Inc.
> Phone (503) 620-3001
> Fax (503) 620-6754
> email email@hidden
>
> _______________________________________________
> Do not post admin requests to the list. They will be ignored.
> Xcode-users mailing list (email@hidden)
> Help/Unsubscribe/Update your Subscription:
>
> This email sent to email@hidden
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Xcode-users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden