4 ms·

I remember the topic of lock free data structures from my time working with C++ a few years ago. C++ is a lot about performance. To do things quicker you creat

I remember the topic of lock free data structures from my time working with C++ a few years ago. C++ is a lot about performance. To do things quicker you create threads which execute code in parallel physically. Since they mess up when working on the same data structure (e.g. a stack) at the same time locks were introduced. So when pushing a new element onto a stack you acquire the lock, perform the push and free the lock. Unfortunately, of that whole operation acquiring/freeing the lock takes 99% of the time. Thus lock-free data structures were developed which magically did not need locking and thus could operate blazingly fast. I understand the article now introduces a lock-free stack. As I understand these data structures have no effects on multi-system environments and can only be applied to a single system. This is because they rely on atomic CPU operations that are not available (natively) on distributed systems. How does that affect us? Not much I guess. I have never seen those data structures widely used. In my understanding almost no application benefits noticably(!) from the speed up. Maybe games, but I don't think so. Nonetheless it is always nice to see basic building blocks improved.

zzzcpan 10y ago
> almost no application benefits noticably(!) from the speed up A lot of applications could benefit from a significant speed up. But atomic operations cannot help with that, they are too slow, they still have to do all that nasty synchronization underneath.
- bluejekyll 10y ago
  Atomic operations on NUMA architectures are much more efficient than lock/unlock on the same memory. It's more expensive than no synchronization, but it's the cheapest (that I know of) method of syncing state across threads and multiple CPU architectures. The only thing cheaper is immutable structures, but those obviously limit your ability to change state across threads.
  - loeg 10y ago
    You can do some checks as non-atomic instructions too, with careful use of memory barriers.
amaks 10y ago
> Thus lock-free data structures were developed which magically did not need locking and thus could operate blazingly fast. This is wrong assumption. With lock-free data structures you don't skip waiting for your right to access data, you just avoid using lock. It may or may not be faster depending on conditions, and whole lot harder to get it right: http://blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms/ http://blog.memsql.com/common-pitfalls-in-writing-lock-free-...
banachtarski 10y ago
Lock free != wait free > As I understand these data structures have no effects on multi-system environments and can only be applied to a single system I have no idea where to even begin with this statement. By this logic, no optimizations should be made to operations in a single threaded or single process environment. Distributing computation helps you achieve scale and HURTS latency except for extremely long running tasks. And yes in games these sorts of things REALLY matter. Things are measured in tens to hundreds of microseconds and optimized accordingly. Not just games, but have you noticed how slow software has gotten of late? Deep learning, rendering, neural networks, AI, etc. Heck, even the browser that I'm typing this in is slow as shit and likely using far more memory than it is supposed to. What about compilers? Those things use trees, stacks, queues, etc and are getting slower all the time. It's the attitude that programmers don't need to care about this stuff that will permanently separate, in my opinion, engineers at the top of the curve from the rest.
- hueving 10y ago
  >that will permanently separate, in my opinion, engineers at the top of the curve from the rest. Precisely. The engineers at the top will understand cost benefit analysis and be okay with sub-optimal solutions while the rest sit and rant about how slow something is.
- badestrand 10y ago
  Sorry, but that optimization elitarism does not get anyone anywhere. Most software written today is quite high level, be it the >2 million apps or the >1 billion websites. In my household neither the smoke detector, toaster or washing mashine needs faster executed code. I understand where you are coming from but for optimizations such low level considerations should be among the last because they matter so little. Most of the time an additional caching structure or the like solves any performance issues.
  - banachtarski 10y ago
    I mention in my reply specific applications where performance really does matter. I don't understand why issuing the strawman of pointing to things that I also trivially acknowledge are not performance sensitive really helps any.

zzzcpan 10y ago

> almost no application benefits noticably(!) from the speed up A lot of applications could benefit from a significant speed up. But atomic operations cannot help with that, they are too slow, they still have to do all that nasty synchronization underneath.

bluejekyll 10y ago
Atomic operations on NUMA architectures are much more efficient than lock/unlock on the same memory. It's more expensive than no synchronization, but it's the cheapest (that I know of) method of syncing state across threads and multiple CPU architectures. The only thing cheaper is immutable structures, but those obviously limit your ability to change state across threads.
- loeg 10y ago
  You can do some checks as non-atomic instructions too, with careful use of memory barriers.

amaks 10y ago

> Thus lock-free data structures were developed which magically did not need locking and thus could operate blazingly fast. This is wrong assumption. With lock-free data structures you don't skip waiting for your right to access data, you just avoid using lock. It may or may not be faster depending on conditions, and whole lot harder to get it right: http://blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms/ http://blog.memsql.com/common-pitfalls-in-writing-lock-free-...

banachtarski 10y ago

Lock free != wait free > As I understand these data structures have no effects on multi-system environments and can only be applied to a single system I have no idea where to even begin with this statement. By this logic, no optimizations should be made to operations in a single threaded or single process environment. Distributing computation helps you achieve scale and HURTS latency except for extremely long running tasks. And yes in games these sorts of things REALLY matter. Things are measured in tens to hundreds of microseconds and optimized accordingly. Not just games, but have you noticed how slow software has gotten of late? Deep learning, rendering, neural networks, AI, etc. Heck, even the browser that I'm typing this in is slow as shit and likely using far more memory than it is supposed to. What about compilers? Those things use trees, stacks, queues, etc and are getting slower all the time. It's the attitude that programmers don't need to care about this stuff that will permanently separate, in my opinion, engineers at the top of the curve from the rest.

hueving 10y ago
>that will permanently separate, in my opinion, engineers at the top of the curve from the rest. Precisely. The engineers at the top will understand cost benefit analysis and be okay with sub-optimal solutions while the rest sit and rant about how slow something is.
badestrand 10y ago
Sorry, but that optimization elitarism does not get anyone anywhere. Most software written today is quite high level, be it the >2 million apps or the >1 billion websites. In my household neither the smoke detector, toaster or washing mashine needs faster executed code. I understand where you are coming from but for optimizations such low level considerations should be among the last because they matter so little. Most of the time an additional caching structure or the like solves any performance issues.
- banachtarski 10y ago
  I mention in my reply specific applications where performance really does matter. I don't understand why issuing the strawman of pointing to things that I also trivially acknowledge are not performance sensitive really helps any.