4 ms·

I don't quite understand it. When you replace lock with CAS (Compare and Swap), aren't you just replacing one synchronization primitive with another? Is lock no

I don't quite understand it. When you replace lock with CAS (Compare and Swap), aren't you just replacing one synchronization primitive with another? Is lock not implemented in CPU as a primitive instruction and therefore less performant? What overhead does locking have compared to CAS?

pzh 10y ago
A spin-lock would be more like a CAS loop (and the CAS IS a primitive CPU instruction), where you retry until the CAS succeeds. The point of lock-free algos, though, is that you could usually do something different from just retrying. There is this concept/general approach in lock-free where if a CAS fails at a certain place, you could invoke helpers that would help some other part of the algorithm make progress. E.g. you may be inserting an element in some structure and your CAS fails at some level (usually because another thread is doing a delete). In that case, you would help the delete operation proceed by invoking some idempotent 'post_delete_cleanup' operation on the same node. The idea of lock-free isn't that one particular thread won't block, but rather that the whole system would be making progress (i.e. no deadlock). It doesn't necessarily mean there will be no locks either.
devbug 10y ago
Besides other benefits mentioned, a spinlock is a user-space construct; you don't incur the overhead switching to kernel mode at the loss of the benefits and guarantees those primitives provide. (I'm simplifying some.)
- netule 10y ago
  On Win32, this has been abstracted into the critical section API, which lives entirely in user-space and is a lightweight mutex. Many of the functionality implemented in the article are already part of the API (spin-aquire, etc.). Though from what I've read, on Linux, pthreads implements its mutexes in user-space (futex) as well and are fairly cheap to use.
  - gpderetta 10y ago
    Yes, the difference is that spin locks never enter the kernel, while a good mutex only does on contention. In practice most mutexes use an hibrid approach.
- siddcoder 10y ago
  I think spinlock is used when the critical section is relatively smaller where the threads are likely to perform small amount of work after acquiring locks. Thus locks are not expected to be held for longer duration. The other threads contending for the lock prefer to just spin and poll (and of course burn CPU) with the hope that lock will soon be relinquished by the owner thread. This way spinning threads avoid the overhead of context switching as well. Goes without saying, spinlocks are not useful on uniprocessor machines or single core machines.
deleted 10y ago
[deleted]
deleted 10y ago
[deleted]
deleted 10y ago
[deleted]
scott_s 10y ago
This post doesn't get into the why very much, which is what you're asking about. Yes, locks will eventually be implemented with a primitive instruction. But it's not so much the cost of the mechanism but what those mechanisms allow you to do. Generally, when you protect a data structure with a lock, that means that the thread which has the lock has mutually exclusive access to it. Other threads which want access must wait. When you have many threads which want access, you will tend to have serialized that part of your program. That will tend to hurt performance, if you gain performance from parallelism. Lock-free approaches tend to allow multiple threads to access and modify a structure without having to get mutually exclusive access. Yes, if two threads are trying to touch the exact same part of the structure, they will interfere: one will succeed and move on, and the other will fail and have to retry. That's not much of a win over locks (generally). But, if it's common for the threads to touch different places of your structure, then they can do so without interfering with each other. That tends to allow better performance through parallelism. I'm using a lot of weasel words ("tends to", "generally") because there are tradeoffs. If you have a shared structure which is accessed by multiple threads very rarely, then it may actually be better to use locks. Lock-free data structures tend to be more complicated (and hence, take a bit longer in the unconteded case) than simply protecting a data structure with a lock. So if you're almost always going to have uncontended access, it may actually yield better performance to use a lock. But, locks can also be problematic when they're held too long or indefinitely. What if a thread dies while holding a lock? Or does I/O? Or is rescheduled? Other threads which want the lock must wait. Lock-free approaches tend to be free of such issues.
- pzh 10y ago
  I see what you're saying, but it seems to me that your description can be misunderstood to mean that lock-free programming is simply more fine-grained locking, which it is very far from. You can use mutexes to do fine-grained locking and still get into a dead-lock. Your algorithm can use only CASs and still not be deadlock-free. The general idea of lock free is to holistically design a data structure that guarantees that when you I invoke its operations in any concurrent scenario, the overall system will make progress and won't get stuck.
  - 10y ago
siddcoder 10y ago
The point is that overhead of locking is too much when the contention on the shared structure is fairly less. The cost of locking/unlocking/blocking/waiting or any other work done as part of enforcing synchronization is something that can be optimized away if the contention on the data structure is less. By contention, I imply -- contention or conflicts on the same portions/pieces of structure. If the data structure is subject to high concurrent access but in fairly disjoint regions of the data structure, we should try to implement fine grained locking scheme to increase the degree of parallelism and thus the scalability of data structure. This is where CAS comes into picture. The article doesn't compare CAS to another locking primitive. Instead, CAS is just used as a mechanism to implement fine grained locking scheme where the methods operating on the data structure don't take global or coarse locks. If the contention on the entire data structure is unreasonably high for some reason, then CAS based approaches or any flavors of it don't buy us much.
bogomipz 10y ago
I've also had some trouble reading(and probably really understanding) the term "lock free algorithms", since things like CAS are always mentioned and a CAS instruction locks the memory bus like any memory access. Isn't it more like "mutex minimization" since you are trying to limit the critical section to a single a single atomic instruction(as opposed to more than one)?
- gpderetta 10y ago
  >CAS instruction locks the memory bus like any memory access. FYI, this hasn't been the case in at least 20 years, on any of the major architectures. Cache coherency guarantees a single writer for any cache line aligned chunk of memory without any sort of bus lock.
  - bogomipz 10y ago
    Sure, but even with MESI a CAS translates into an exclusive lock on the cache line by a single core no? I probably could have articulated my original question better, sorry.
    - gpderetta 10y ago
      I guess you could call holding a cacheline in the exclusive state the same as holding a lock. The difference, I think, is that there's an hard upper bound on response time on serving any remote request for sharing.

pzh 10y ago

A spin-lock would be more like a CAS loop (and the CAS IS a primitive CPU instruction), where you retry until the CAS succeeds. The point of lock-free algos, though, is that you could usually do something different from just retrying. There is this concept/general approach in lock-free where if a CAS fails at a certain place, you could invoke helpers that would help some other part of the algorithm make progress. E.g. you may be inserting an element in some structure and your CAS fails at some level (usually because another thread is doing a delete). In that case, you would help the delete operation proceed by invoking some idempotent 'post_delete_cleanup' operation on the same node. The idea of lock-free isn't that one particular thread won't block, but rather that the whole system would be making progress (i.e. no deadlock). It doesn't necessarily mean there will be no locks either.

devbug 10y ago

Besides other benefits mentioned, a spinlock is a user-space construct; you don't incur the overhead switching to kernel mode at the loss of the benefits and guarantees those primitives provide. (I'm simplifying some.)

netule 10y ago
On Win32, this has been abstracted into the critical section API, which lives entirely in user-space and is a lightweight mutex. Many of the functionality implemented in the article are already part of the API (spin-aquire, etc.). Though from what I've read, on Linux, pthreads implements its mutexes in user-space (futex) as well and are fairly cheap to use.
- gpderetta 10y ago
  Yes, the difference is that spin locks never enter the kernel, while a good mutex only does on contention. In practice most mutexes use an hibrid approach.
siddcoder 10y ago
I think spinlock is used when the critical section is relatively smaller where the threads are likely to perform small amount of work after acquiring locks. Thus locks are not expected to be held for longer duration. The other threads contending for the lock prefer to just spin and poll (and of course burn CPU) with the hope that lock will soon be relinquished by the owner thread. This way spinning threads avoid the overhead of context switching as well. Goes without saying, spinlocks are not useful on uniprocessor machines or single core machines.

deleted 10y ago

[deleted]

deleted 10y ago

[deleted]

deleted 10y ago

[deleted]

scott_s 10y ago

This post doesn't get into the why very much, which is what you're asking about. Yes, locks will eventually be implemented with a primitive instruction. But it's not so much the cost of the mechanism but what those mechanisms allow you to do. Generally, when you protect a data structure with a lock, that means that the thread which has the lock has mutually exclusive access to it. Other threads which want access must wait. When you have many threads which want access, you will tend to have serialized that part of your program. That will tend to hurt performance, if you gain performance from parallelism. Lock-free approaches tend to allow multiple threads to access and modify a structure without having to get mutually exclusive access. Yes, if two threads are trying to touch the exact same part of the structure, they will interfere: one will succeed and move on, and the other will fail and have to retry. That's not much of a win over locks (generally). But, if it's common for the threads to touch different places of your structure, then they can do so without interfering with each other. That tends to allow better performance through parallelism. I'm using a lot of weasel words ("tends to", "generally") because there are tradeoffs. If you have a shared structure which is accessed by multiple threads very rarely, then it may actually be better to use locks. Lock-free data structures tend to be more complicated (and hence, take a bit longer in the unconteded case) than simply protecting a data structure with a lock. So if you're almost always going to have uncontended access, it may actually yield better performance to use a lock. But, locks can also be problematic when they're held too long or indefinitely. What if a thread dies while holding a lock? Or does I/O? Or is rescheduled? Other threads which want the lock must wait. Lock-free approaches tend to be free of such issues.

pzh 10y ago
I see what you're saying, but it seems to me that your description can be misunderstood to mean that lock-free programming is simply more fine-grained locking, which it is very far from. You can use mutexes to do fine-grained locking and still get into a dead-lock. Your algorithm can use only CASs and still not be deadlock-free. The general idea of lock free is to holistically design a data structure that guarantees that when you I invoke its operations in any concurrent scenario, the overall system will make progress and won't get stuck.
- 10y ago

siddcoder 10y ago

The point is that overhead of locking is too much when the contention on the shared structure is fairly less. The cost of locking/unlocking/blocking/waiting or any other work done as part of enforcing synchronization is something that can be optimized away if the contention on the data structure is less. By contention, I imply -- contention or conflicts on the same portions/pieces of structure. If the data structure is subject to high concurrent access but in fairly disjoint regions of the data structure, we should try to implement fine grained locking scheme to increase the degree of parallelism and thus the scalability of data structure. This is where CAS comes into picture. The article doesn't compare CAS to another locking primitive. Instead, CAS is just used as a mechanism to implement fine grained locking scheme where the methods operating on the data structure don't take global or coarse locks. If the contention on the entire data structure is unreasonably high for some reason, then CAS based approaches or any flavors of it don't buy us much.

bogomipz 10y ago

I've also had some trouble reading(and probably really understanding) the term "lock free algorithms", since things like CAS are always mentioned and a CAS instruction locks the memory bus like any memory access. Isn't it more like "mutex minimization" since you are trying to limit the critical section to a single a single atomic instruction(as opposed to more than one)?

gpderetta 10y ago
>CAS instruction locks the memory bus like any memory access. FYI, this hasn't been the case in at least 20 years, on any of the major architectures. Cache coherency guarantees a single writer for any cache line aligned chunk of memory without any sort of bus lock.
- bogomipz 10y ago
  Sure, but even with MESI a CAS translates into an exclusive lock on the cache line by a single core no? I probably could have articulated my original question better, sorry.
  - gpderetta 10y ago
    I guess you could call holding a cacheline in the exclusive state the same as holding a lock. The difference, I think, is that there's an hard upper bound on response time on serving any remote request for sharing.