4 ms·

So uhm the top 2 link of HN in the last 5 hours have been about this and while they are highly voted there is very little discussion going. Can someone give som

So uhm the top 2 link of HN in the last 5 hours have been about this and while they are highly voted there is very little discussion going. Can someone give some context as to why this is attracting so much (surely deserved) attention? How will this affect us? Is it likely to have a deep effect on general computing performances? In what ways will this be applied? I'm sorry if this are silly questions but I find interesting the lack of discussion going on.

the8472 10y ago
one is a stack, the other a queue, they are different things.
ktta 10y ago
I'm not the most informed person to explain this, so anyone else please feel free to correct me. This paper is dealing with the computing process to be used (proposed) in highly parallel and distributed computing. Specifically how it manages and updates output data. (warning: this is a not so great example of lock-free, wait free) If you have experience with linux, you can only apt-get or yum install only once at a time, because there is a 'lock' which prevents you from installing multiple packages to prevent collisions in the system data which they modify. In a similar vein, in parallel or distributed computing (read: many threads) computation, the threads required access to the same files in executing the algorithm. So the ''stack" is the memory that is in use during a computation. When there is a lock on a particular sector, any programs cannot access it and have to wait for the thread currently modifying it before it makes changes, so that they don't corrupt it (mess up the data). This really is disadvantageous since you are not having the max utilization of parallel threads and threads are kept waiting. So a lock-free stack means that any threads don't have to wait for the lock to be removed before they can modify anything. So how will this affect us? make parallel computing more efficient than it already is. See this for more info- https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm (It's called non-blocking since it is not 'blocking any other threads'. And I suggest you read this comment before you jump in the link- See this: https://news.ycombinator.com/item?id=12109439 https://news.ycombinator.com/item?id=12109439)
badestrand 10y ago
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.
zamalek 10y ago
Disclaimer: I haven't implemented this yet, this is based on skimming the paper and what I know about lock-free structures. Your run-of-the-mill lock-free code basically operates under the premise of "keep trying until something sticks." For example, with only CompareAndSwap you can implement lock-free bit-field operations as: do { oldValue = Read(variable); newValue = oldValue | 0x01; } while ((CAS(variable, oldValue, newValue) & 0x01) == 0); You can see that we have to keep looping until the new value (which includes the flag) "sticks." The race is allowed to occur between the Read() and the CAS(), where CAS() is used to determine if a race occurred. CAS will check the current value of the address and update it only if it matches (as an atomic operation on the CPU). The worst case here is O(∞) - if another thread always wins, this loop will never exit. The run-of-the-mill lock-free stack code looks quite similar to this (you're basically updating the head until it sticks). This means that in certain circumstances, lock-free code can actually be slower. I have run into this myself[1]: that code uses locks because I couldn't figure out a faster lock-free implementation (that code is 30x faster than my best lock-free effort). There are two operations on a stack: Push() and Pop(). Classically, these both compete to write the head (write-contention). The advantage with this algorithm is that only Push() competes to write the head so you're decreasing the probability of proving O(∞) with each Push(). Additionally, Pop() seems to be O(N) (where N = number of items in the stack) where-as classically that's also O(∞). TL;DR Unless I'm misunderstanding wait-free (having never heard of that technical term before), it means eliminating a theoretically unbounded loop. If you'd like to learn more I consider Jeff Preshing[2] as the authority figure on lock-free data structures. His articles are clear and could explain how these structures work to "ostensibly anyone." CPPCon also has at least one talk of his. [1]: https://github.com/jcdickinson/AzXmpp/blob/master/src/AzXmpp.Transport/Sockets/FastBufferManager.cs https://github.com/jcdickinson/AzXmpp/blob/master/src/AzXmpp... [2]: http://preshing.com/ http://preshing.com/

the8472 10y ago

one is a stack, the other a queue, they are different things.

ktta 10y ago

I'm not the most informed person to explain this, so anyone else please feel free to correct me. This paper is dealing with the computing process to be used (proposed) in highly parallel and distributed computing. Specifically how it manages and updates output data. (warning: this is a not so great example of lock-free, wait free) If you have experience with linux, you can only apt-get or yum install only once at a time, because there is a 'lock' which prevents you from installing multiple packages to prevent collisions in the system data which they modify. In a similar vein, in parallel or distributed computing (read: many threads) computation, the threads required access to the same files in executing the algorithm. So the ''stack" is the memory that is in use during a computation. When there is a lock on a particular sector, any programs cannot access it and have to wait for the thread currently modifying it before it makes changes, so that they don't corrupt it (mess up the data). This really is disadvantageous since you are not having the max utilization of parallel threads and threads are kept waiting. So a lock-free stack means that any threads don't have to wait for the lock to be removed before they can modify anything. So how will this affect us? make parallel computing more efficient than it already is. See this for more info- https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm (It's called non-blocking since it is not 'blocking any other threads'. And I suggest you read this comment before you jump in the link- See this: https://news.ycombinator.com/item?id=12109439 https://news.ycombinator.com/item?id=12109439)

badestrand 10y ago

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.

zamalek 10y ago

Disclaimer: I haven't implemented this yet, this is based on skimming the paper and what I know about lock-free structures. Your run-of-the-mill lock-free code basically operates under the premise of "keep trying until something sticks." For example, with only CompareAndSwap you can implement lock-free bit-field operations as: do { oldValue = Read(variable); newValue = oldValue | 0x01; } while ((CAS(variable, oldValue, newValue) & 0x01) == 0); You can see that we have to keep looping until the new value (which includes the flag) "sticks." The race is allowed to occur between the Read() and the CAS(), where CAS() is used to determine if a race occurred. CAS will check the current value of the address and update it only if it matches (as an atomic operation on the CPU). The worst case here is O(∞) - if another thread always wins, this loop will never exit. The run-of-the-mill lock-free stack code looks quite similar to this (you're basically updating the head until it sticks). This means that in certain circumstances, lock-free code can actually be slower. I have run into this myself[1]: that code uses locks because I couldn't figure out a faster lock-free implementation (that code is 30x faster than my best lock-free effort). There are two operations on a stack: Push() and Pop(). Classically, these both compete to write the head (write-contention). The advantage with this algorithm is that only Push() competes to write the head so you're decreasing the probability of proving O(∞) with each Push(). Additionally, Pop() seems to be O(N) (where N = number of items in the stack) where-as classically that's also O(∞). TL;DR Unless I'm misunderstanding wait-free (having never heard of that technical term before), it means eliminating a theoretically unbounded loop. If you'd like to learn more I consider Jeff Preshing[2] as the authority figure on lock-free data structures. His articles are clear and could explain how these structures work to "ostensibly anyone." CPPCon also has at least one talk of his. [1]: https://github.com/jcdickinson/AzXmpp/blob/master/src/AzXmpp.Transport/Sockets/FastBufferManager.cs https://github.com/jcdickinson/AzXmpp/blob/master/src/AzXmpp... [2]: http://preshing.com/ http://preshing.com/