"John Torjo" wrote

...

As for more efficient lock-free impleentations (using CAS) Microsoft has (relatively recently) added singly linked lock-free list to Win32 API. There

could you post a link? thanks.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/bas... Exported from kernel32 but only on XP and Server 2003. Tony

"Holger Grund" <yahoo@ix-n.net> wrote

It's probably much harder for certain other architectures.

You are right. The rationale for providing API for singly-linked list is, I believe, based on typical library/reusability/avoid-boilerplate code mantra. There is a body of work for implementing Intel-like CAS (conditional store and swap) via LL/SC (load linked/store conditional) instructions on other architectures (notably Motorola). IMO, the issue boils down to usefulness of adding such functionality to the part of the library that deals with concurrency. Personally, I find it very useful, even if I would never claim that all concurrent data-access issues boil down to thread-safe access to standard containers. In my view, it is library functions like thread.join(0 that are trivial enough so that anybody can keep reimplementing them in his platform-specific programs, while thread-safe containers are nontrivial and error-prone enough to deserve resuable library implementation. Tony

"John Torjo" wrote:

...

I would argue that most of multi-threaded programs need thread-safe containers.

I tend not to agree with you (see above).

I am not sure I understand it well, so let's try with a concrete example of FIFO queue. Let's say you are asynchronously receiving message blocks (not necessarily of fixed size) and you implement that with two threads: - one is accumulating data until message end is found and puts the block in the queue - another reads and parses message blocks At this point the chunkiness of the data and the fact that data for message blocks arrive asynchronously is modelled via element membership in the queue container which must be accessed in a thread-safe manner. Thread-safe queue (whether lock-free or using 'ordinary' locks on all accessors) seems a way to implement this without programmer having to explicitly consider threading issues. One programmer puts the data block, another picks them and parses them. How woud you model this in your, right way? What is the guiding idea? Tony

John Torjo wrote:

Thus, to me, the benefit of having a thread-safe container is very small.

I see similar 'philosophy' in SGI STL. I wouldn't deny that thread-safety is, more often than not, more complex than thread-safe container access. However, at the same time, I see (and have seen) a large class of problems that require only container's thread-safety, plus, more complex scenarios typically require container's thread-safety for starters (as you wrote). Therefore, I see no harm, quite on the contrary, in having a separate class of robust, library-provided thread-safe containers. The existing research into wait-free and lock-free containers (to the point of processors implementing CAS and even DCAS) must have some basis in real requirements?! So 'my' philosophy' would be: while no library implementation can solve all thread-safety requirements that arise in everyday use, at certain basic, 'mechanical' level I would like to be able to work with the container and completely ignore threading issues, happy in the knowledge that library solved them for me in the most efficient way. IOW, I can say to a junior programmer, inexperienced with mutexes and threading: just use this container for your algorithm. Tony

Joel Salomon wrote:

...

Use mutexes. and In my experience, I hardly need just a container to be thead-safe. I usually need more data in addition to the container (which needs to be thread-safe). For instance, an extra latest_access_time, out_file, used_for_the_first_time, etc.

Thus, to me, the benefit of having a thread-safe container is very small. One thread-safe container that might be useful is a channel - a queue

John Torjo wrote: that one thread writes to and another reads to, the reader blocking when the channel is empty.

Right. This is the _only_ thread-safe(*) container (that I'm aware of) that is generally useful. Even here, there is a choice between non-blocking and blocking semantics (which preclude a lock-free implementation.) Having a max size implies blocking on push, of course. (*) For the implied definition of "thread safe" that we are using in this context ("strong" thread safety).

"Jeff Garland" wrote:

STLPort -- www.stlport.org implements them.

Well.. no, not really. At least not in the way Java library does it, which is closest to what I had in mind. According to the documentation only explicit locks are in allocators and there is this telling comment: "This decision is different from that made by the Java designers. There are two reasons for that. First, for security reasons Java must guarantee that even in the presence of unprotected concurrent accesses to a container, the integrity of the virtual machine cannot be violated. Such safety constraints were clearly not a driving force behind either C++ or STL. Secondly, performance was a more important design goal for STL than it was for the Java standard library." The following excerpt from STLPort _threads.h file shows that there is still work to be done: // This should be portable, but performance is expected // to be quite awful. This really needs platform specific // code. inline __stl_atomic_t _Atomic_swap(volatile __stl_atomic_t * __p, __stl_atomic_t __q) { _Swap_lock_struct<0>::_S_swap_lock._M_acquire_lock(); __stl_atomic_t __result = *__p; *__p = __q; _Swap_lock_struct<0>::_S_swap_lock._M_release_lock(); return __result; } All in all, IMO there is ample space for a small, even if quite ambitious project of implementing at least few cross-platform, fully thread-safe lock-free (to address performance concerns mentioned in the quote above) containers. Tony