<p>I think that "COLLECTIONS" stands for "queues, stacks, linked lists, trees, ..."</p>

<p>From <a href="http://www.cl.cam.ac.uk/research/srg/netos/lock-free/" rel="nofollow">http://www.cl.cam.ac.uk/research/srg/netos/lock-free/</a></p>

<p><em>Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failures in distributed systems.</em></p>

<p><em>The best overall introduction to our non-blocking algorithms is the paper Concurrent programming without locks, currently under submission, which covers our designs for multi-word compare-and-swap, word-based software transactional memory and object-based software transactional memory.</em> </p>

<p><strong>If "lock-free" means "do not use operarting system's semaphores, mutex, monitors, ..."</strong> then I think (but I'm not an expert) that every collection can be made lock-free using atomic read-write-modify primitives that must be supported by the hardware.</p>

<p>A computational overhead is needed, but I think that for simple structures like lists, trees, hash tables ... the overall computational complexity of searches/insertions/deletions $O(\cdot)$ does not change.</p>

<p>Exhaustive documentation on the subject can be found online:</p>

<p><a href="http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf" rel="nofollow">http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf</a></p>

<p>(... and further references at the end of each document)</p>

CC BY-SA 2.5
2011-01-27T12:11:24.040Z
2011-01-27T12:11:24.040Z
Marzio De Biasi
<p>Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.</p>

<p><em>Collection</em>. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some <em>operations</em> that may access that memory and that may be invoked by <em>users</em>. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.</p>

<p><em>Lock-free</em>. <a href="http://scholar.google.co.uk/scholar?cluster=14359385420878719513">Herlihy and Boss</a> say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (<em>Edit:</em> According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is <em>not</em> the case that if a data structure does not use locks then it is lock-free.)</p>

<p>With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.</p>

<p>But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider <code>push(x) { lock(); stack[size++] = x; unlock(); }</code>. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether <em>push</em> will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that <em>push</em> will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that <em>push</em> <strong>is</strong> a constant time operation.</p>

<p>In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.</p>

CC BY-SA 2.5
2011-01-29T23:27:46.697Z
I am not too sure on whether you can actually consider that the `push` operation as stated above is not a constant time operation. For a fixed number of processors, and a common implementation of `lock` that guarantees no starvation, the above operation (in the worst case, for any given processor takes N_proc * O(1), which can naïvely be assumed to be O(1) (number of processors being factored into the hidden constant).
David Rodríguez - dribeas
CC BY-SA 2.5
2011-01-30T08:02:30.997Z
It is a surprisingly common error to fix $n$ in $f(n)$ and then claim that $f$ is constant. The other day I asked some colleagues if they can come up with a constant time algorithm for the [ruler function](http://oeis.org/A001511), and some objected that the number of bits in a computer word is constant. (Hence, I presume was implied, all algorithms for computing the ruler function are constant time.) To address your comment directly, yes, that's what I meant by `ignoring other users', that we treat that variable as a constant.
Radu GRIGore
CC BY-SA 2.5
2011-01-31T11:25:35.883Z
Well, memory access is a common case of that. Most algorithm analysis assumes that memory access is O(1) independent of memory used; real memory architectures (with caches etc) are better approximate by O(log N) where N is memory used.
MSalters
CC BY-SA 2.5
2011-02-01T22:58:39.057Z
While the assumption that the number of processors is a constant is quite practical, I will avoid it. Then the issue is that the complexity cannot be analyzed in a unidimensional fashion, as the size of the problem is bound to grow both in the size of the input and the number of processors, both of which are orthogonal dimensions. Assuming a particular container in the C++ standard library (I'm obviously picking a hard one) one of the requirements is that all elements are held in a contiguous block of memory.
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:02:57.260Z
Now, appending an element to the vector is an amortized constant time operation (if it does not fit in the previously allocated block, the call will take a linear time on the number of elements in the container, but if the reserved block of memory is acquired following an exponential sequence the amortized cost is constant). If you implement a thread safe container, you would lock and then perform the change, the cost of the operation is proportional to the cost of locking --which I don't really know... but in a first approximation you can consider mostly constant
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:06:25.820Z
My approximation assumes that you need an atomic operation (test_and_set, for example) whose cost is independent on the number of threads, and addition to the end of a queue if the resource is already locked. Digging into more details, and including not just the cost of the call to lock, but the time that the object is being locked, that can be approximated by `O(N * M)` where `N` is the number of threads and `M` the cost of the operations being performed on the container. So with this second approximation, the cost of a locking implementation would be proportional to the number of threads
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:12:34.910Z
**in the worst case**, since the implementations of locks guarantee that no particular thread will starve. Now if we go to a lock-less implementation, the thread that needs to grow the container would have to create a copy of the container that is slightly bigger, copy the elements, and then with an atomic operation interchange the old and new buffers. If the old buffer has been modified between the time that the thread started copying the data until it has finished, the whole operation has to be rolled back and restarted.
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:16:48.930Z
I cannot really formulate the cost of the operation, but while we can use amortized cost analysis to determine that appending to the vector is constant time, the problem is that because the buffer grow operation might have to be retried I don't think that amortized analysis holds any more. As the container grows in size, the probability of other threads actually modifying the contents also grows, since the copy operation is a longer process and other threads have more time to complete the extra tasks and go back to the container. As the number of threads increases, this gets even worse.
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:19:08.540Z
With this naïve approach, in the worst case a single thread trying to grow the buffer could get stalled with the modifications from other threads, breaking the *progress* guarantee and breaking the overall system.
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:22:58.537Z
Of course this is only a single approach... it might be the case that someone much smarter than me will come up with a solution for this. There are implementations of lock-less queues, and even a lock-less (I think or at least minimal lock) hashmap implementation where all threads share the load of copying the contents from one buffer to the next, but the reason that works is because at any given point in time, when the hashmap is being accessed the *up-to-date* value for each entry can be retrieved from any of the buffers, and the whole container is the union of all buffers.
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-01T23:23:31.453Z
Contiguity is not a requirement of a hashmap, but it is a requirement for a vector. Darn, comments are not meant for long theoretical discussions!
David Rodríguez - dribeas
CC BY-SA 2.5
2011-02-02T12:00:12.973Z
"comments are not meant for long theoretical discussions" More to the point, this website is not meant for long theoretical discussions. It is optimized for Q&A.
Radu GRIGore
CC BY-SA 2.5
2011-01-27T16:28:39.240Z
2011-01-27T20:04:22.177Z
2011-01-27T20:04:22.177Z
Radu GRIGore
<p>David Rodríguez - dribeas wrote in <a href="https://stackoverflow.com/questions/4813327/c-library-that-has-nonblocking-collections">a comment on StackOverflow</a> that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.</p>

<p>This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: <i>For every collection type <code>C</code>, there exists a lock-free collection type <code>C</code><sub>LF</sub> that offers the same set of operations, and where each operation on <code>C</code><sub>LF</sub> has the same big-O complexity as the corresponding operation on <code>C</code>.</i></p>

<p>I don't expect a transformation, by the way.</p>

CC BY-SA 2.5
2011-01-27T10:19:31.047Z
But you want it to be concurrent (thread safe)? And surely you are considering mutable collections?
Raphael
CC BY-SA 2.5
2011-01-27T10:23:59.963Z
Hadn't made it explicit, but yes, I'd expect the lock-free collection to be thread safe. And a non-mutable collection can always be made lock-free thread safe by creating (internal) copies.
MSalters
CC BY-SA 2.5
2011-01-27T10:31:21.227Z
As a non-expert, I wonder if “lock-free” can be rigorously defined.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T10:37:54.710Z
What's a collection ?
Suresh Venkat
CC BY-SA 2.5
2011-01-27T10:42:27.467Z
@Suresh: Maybe a synonym for “data structure”?
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T11:12:04.933Z
What if you just take a lock-free implementation of STM (software transactional memory), and implement any data structures on top of that?
Jukka Suomela
CC BY-SA 2.5
2011-01-27T11:32:21.173Z
@Tsuyoshi: I think there is no formal definition of lock-free. Informally, it means you don't use the LOCK instruction of the CPU, which is slow, and stick to the faster compare-and-swap. Since a LOCK can be simulated with compare-and-swap it's difficult to put a hard boundary between "you essentially use compare-and-swap here to simulate a lock (or a transaction for that matter)" and "oh, this is a really clever use of compare-and-swap, and doesn't look at all as if it simulates some higher level operation that we know of."
Radu GRIGore
CC BY-SA 2.5
2011-01-27T11:52:04.423Z
@Radu: That describes exactly what I wondered, except that I did not think about it that concretely.  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T14:49:57.263Z
As far as I understand it, lock-free is here understood to be synonymous with non-blocking. This doesn't involve the CPU's `LOCK` instruction but the thread scheduler, via mutexes/semaphores/etc.
MSalters
CC BY-SA 2.5
2011-01-27T16:30:05.447Z
@MSalters, you are right. I have a bigger comment posted as an answer below. Not sure if it will help you, but it helped me understand your question.
Radu GRIGore
<ds.data-structures><pl.programming-languages><dc.distributed-comp><concurrency>
Limits on lock-free collections?
MSalters
# Limits on lock-free collections?

(Asked by: username_0 on 2011-01-27)

David Rodríguez - dribeas wrote in [a comment on StackOverflow](https://stackoverflow.com/questions/4813327/c-library-that-has-nonblocking-collections) that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.

This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: *For every collection type `C`, there exists a lock-free collection type `C`LF that offers the same set of operations, and where each operation on `C`LF has the same big-O complexity as the corresponding operation on `C`.*

I don't expect a transformation, by the way.

**Tags:** ds.data-structures, pl.programming-languages, dc.distributed-comp, concurrency
> **Comments:**
> **username_1**: But you want it to be concurrent (thread safe)? And surely you are considering mutable collections?  
> **username_0**: Hadn't made it explicit, but yes, I'd expect the lock-free collection to be thread safe. And a non-mutable collection can always be made lock-free thread safe by creating (internal) copies.  
> **username_2**: As a non-expert, I wonder if “lock-free” can be rigorously defined.  
> **username_3**: What's a collection ?  
> **username_2**: @Suresh: Maybe a synonym for “data structure”?  
> **username_4**: What if you just take a lock-free implementation of STM (software transactional memory), and implement any data structures on top of that?  
> **username_5**: @Tsuyoshi: I think there is no formal definition of lock-free. Informally, it means you don't use the LOCK instruction of the CPU, which is slow, and stick to the faster compare-and-swap. Since a LOCK can be simulated with compare-and-swap it's difficult to put a hard boundary between "you essentially use compare-and-swap here to simulate a lock (or a transaction for that matter)" and "oh, this is a really clever use of compare-and-swap, and doesn't look at all as if it simulates some higher level operation that we know of."  
> **username_2**: @Radu: That describes exactly what I wondered, except that I did not think about it that concretely.  Thanks!  
> **username_0**: As far as I understand it, lock-free is here understood to be synonymous with non-blocking. This doesn't involve the CPU's `LOCK` instruction but the thread scheduler, via mutexes/semaphores/etc.  
> **username_5**: @MSalters, you are right. I have a bigger comment posted as an answer below. Not sure if it will help you, but it helped me understand your question.  

---

## 2 answers

### Answer by username_5 on 2011-01-27. Score: 11 | Accepted answer

Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.

*Collection*. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some *operations* that may access that memory and that may be invoked by *users*. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.

*Lock-free*. [Herlihy and Boss](http://scholar.google.co.uk/scholar?cluster=14359385420878719513) say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (*Edit:* According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is *not* the case that if a data structure does not use locks then it is lock-free.)

With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.

But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider `push(x) { lock(); stack[size++] = x; unlock(); }`. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether *push* will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that *push* will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that *push* **is** a constant time operation.

In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.

> **Comments:**
> **username_7**: I am not too sure on whether you can actually consider that the `push` operation as stated above is not a constant time operation. For a fixed number of processors, and a common implementation of `lock` that guarantees no starvation, the above operation (in the worst case, for any given processor takes N_proc * O(1), which can naïvely be assumed to be O(1) (number of processors being factored into the hidden constant).  
> **username_5**: It is a surprisingly common error to fix $n$ in $f(n)$ and then claim that $f$ is constant. The other day I asked some colleagues if they can come up with a constant time algorithm for the [ruler function](http://oeis.org/A001511), and some objected that the number of bits in a computer word is constant. (Hence, I presume was implied, all algorithms for computing the ruler function are constant time.) To address your comment directly, yes, that's what I meant by `ignoring other users', that we treat that variable as a constant.  
> **username_0**: Well, memory access is a common case of that. Most algorithm analysis assumes that memory access is O(1) independent of memory used; real memory architectures (with caches etc) are better approximate by O(log N) where N is memory used.  
> **username_7**: While the assumption that the number of processors is a constant is quite practical, I will avoid it. Then the issue is that the complexity cannot be analyzed in a unidimensional fashion, as the size of the problem is bound to grow both in the size of the input and the number of processors, both of which are orthogonal dimensions. Assuming a particular container in the C++ standard library (I'm obviously picking a hard one) one of the requirements is that all elements are held in a contiguous block of memory.  
> **username_7**: Now, appending an element to the vector is an amortized constant time operation (if it does not fit in the previously allocated block, the call will take a linear time on the number of elements in the container, but if the reserved block of memory is acquired following an exponential sequence the amortized cost is constant). If you implement a thread safe container, you would lock and then perform the change, the cost of the operation is proportional to the cost of locking --which I don't really know... but in a first approximation you can consider mostly constant  
> **username_7**: My approximation assumes that you need an atomic operation (test_and_set, for example) whose cost is independent on the number of threads, and addition to the end of a queue if the resource is already locked. Digging into more details, and including not just the cost of the call to lock, but the time that the object is being locked, that can be approximated by `O(N * M)` where `N` is the number of threads and `M` the cost of the operations being performed on the container. So with this second approximation, the cost of a locking implementation would be proportional to the number of threads  
> **username_7**: **in the worst case**, since the implementations of locks guarantee that no particular thread will starve. Now if we go to a lock-less implementation, the thread that needs to grow the container would have to create a copy of the container that is slightly bigger, copy the elements, and then with an atomic operation interchange the old and new buffers. If the old buffer has been modified between the time that the thread started copying the data until it has finished, the whole operation has to be rolled back and restarted.  
> **username_7**: I cannot really formulate the cost of the operation, but while we can use amortized cost analysis to determine that appending to the vector is constant time, the problem is that because the buffer grow operation might have to be retried I don't think that amortized analysis holds any more. As the container grows in size, the probability of other threads actually modifying the contents also grows, since the copy operation is a longer process and other threads have more time to complete the extra tasks and go back to the container. As the number of threads increases, this gets even worse.  
> **username_7**: With this naïve approach, in the worst case a single thread trying to grow the buffer could get stalled with the modifications from other threads, breaking the *progress* guarantee and breaking the overall system.  
> **username_7**: Of course this is only a single approach... it might be the case that someone much smarter than me will come up with a solution for this. There are implementations of lock-less queues, and even a lock-less (I think or at least minimal lock) hashmap implementation where all threads share the load of copying the contents from one buffer to the next, but the reason that works is because at any given point in time, when the hashmap is being accessed the *up-to-date* value for each entry can be retrieved from any of the buffers, and the whole container is the union of all buffers.  
> **username_7**: Contiguity is not a requirement of a hashmap, but it is a requirement for a vector. Darn, comments are not meant for long theoretical discussions!  
> **username_5**: "comments are not meant for long theoretical discussions" More to the point, this website is not meant for long theoretical discussions. It is optimized for Q&A.  

---

### Answer by username_6 on 2011-01-27. Score: 3

I think that "COLLECTIONS" stands for "queues, stacks, linked lists, trees, ..."

From <http://www.cl.cam.ac.uk/research/srg/netos/lock-free/>

*Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failures in distributed systems.*

*The best overall introduction to our non-blocking algorithms is the paper Concurrent programming without locks, currently under submission, which covers our designs for multi-word compare-and-swap, word-based software transactional memory and object-based software transactional memory.*

**If "lock-free" means "do not use operarting system's semaphores, mutex, monitors, ..."** then I think (but I'm not an expert) that every collection can be made lock-free using atomic read-write-modify primitives that must be supported by the hardware.

A computational overhead is needed, but I think that for simple structures like lists, trees, hash tables ... the overall computational complexity of searches/insertions/deletions $O(\cdot)$ does not change.

Exhaustive documentation on the subject can be found online:

<http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf>

(... and further references at the end of each document)


---

