9 ms·

A Wait-Free Stack

281 points by EvgeniyZh 10y ago

deleted 10y ago
[deleted]
programmer_dude 10y ago
What is a wait-free stack?
- krig 10y ago
  From the introduction: > In this paper, we describe an algorithm to create a wait-free stack. A concurrent data structure is said to be wait-free if each operation is guaranteed to complete within a finite number of steps. In comparison, the data structure is said to be lock-free if at any point of time, at least one operation is guaranteed to complete in a finite number of steps. Lock-free programs will not have deadlocks but can have starvation, whereas wait-free programs are starvation free.
- wcrichton 10y ago
  Wait-freedom is described in the introduction. Quote: There are three levels of progress guarantees for non-blocking data structures. A concurrent object is: - obstruction-free if a thread can perform an arbitrary operation on the object in a finite number of steps when it executes in isolation, - lock-free if some thread performing an arbitrary operation on the object will complete in a finite number of steps, or - wait-free if every thread can perform an arbitrary operation on the object in a finite number of steps. Wait-freedom is the strongest progress guarantee; it rules out the possibility of starvation for all threads. Wait-free data structures are particularly desirable for mission critical applications that have real-time constraints, such as those used by cyber-physical systems.
xchip 10y ago
I love papers but I love it more when their code is in github :) thanks for sharing!
- EvgeniyZh 10y ago
  Yeah, I'd love to see implementation too. Even better - implementation in some lib with comparison of performance
appleflaxen 10y ago
More discussion on pdf link https://news.ycombinator.com/item?id=12109219 https://news.ycombinator.com/item?id=12109219
- bhouston 10y ago
  Different paper - queue vs stack. Confused me as well.
duiker101 10y ago
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
nemetroid 10y ago
The first few lines of pop() are: mytop <- top.get() curr <- mytop while curr != sentinel do mark <- curr.mark.getAndSet(true) ... What's keeping curr from becoming a dangling pointer if the size of the stack is bounded?
kumagi 10y ago
I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html http://longgate.co.jp/books/grimoire-vol3.html
- kumagi 10y ago
  This book is published in 2013. Earlier than this arxiv paper.
  - lrem 10y ago
    It's sad to be in "the other cultural circle", isn't it? Imagine that in western Europe a number of theorems by eastern European mathematicians is known by the name of the western professor who would propagate it... Also: I feel there should be a comma in the sentence above, but can't figure out where to put it :/
    - jsprogrammer 10y ago
      After the 3, in place of the period.
    - ktta 10y ago
      I understand what you're trying to convey and agree. I thought you might not have noticed the email address of the authors. Two of the authors' email addresses are of IIT Delhi, one of the universities managed by the Government of India. So these authors are in "the other cultural circle" too. One in which there's more than 10 times competition in the educational system for funding, compared to not only western and European counterparts but the Japanese one too, which the parent comment I think is/was a part of. Not just funding for cool projects. There is a very dire need for good universities but higher education in a good university is very difficult to have.
    - numbsafari 10y ago
zilchers 10y ago
I'm not sure I see what's novel about this - maybe it's a verbiage thing around "wait free," but if they're atomically updating the top pointer and linked list, there will be lock contention on writes, and similarly when marking an item popped, on reads. I suppose the contention is bounded by the number of readers or writers, but I wouldn't consider that wait free (again, that could just be a verbiage thing). But, more to the point, this is just a slight twist on how Kafka works (stack vs log / queue, but same with the pointer holding place and a cleanup operation), I don't really see it as particularly novel...perhaps I'm missing something?
- kasey_junk 10y ago
  A "wait free" data structure has a specific technical definition so yes, in some ways the novelty in this is that it meets that verbiage. Lock free stacks have been around since at least the 80s but I haven't seen a general wait free stack before (though I'm no expert). In neither this paper or the classic lock free stacks do you have lock contention on writes as you are using CAS operations. I'm having a little trouble parsing the algo in this paper, but what they seem to have added that is novel is their cleanup function will always complete in a finite number of steps, thus making the whole thing both wait free and bounded, which is pretty neat. In any case, with wait free structures generally implementation details matter a lot and stacks are pretty notoriously hard to handle because of the contention around the top node, as opposed to something like an append only log like Kafka uses, so that particular comparison is not fair.
  - jemfinch 10y ago
    > In neither this paper or the classic lock free stacks do you have lock contention on writes as you are using CAS operations. Given that real-world locks are most often implemented using CAS, is this distinction a valuable one? In either case you have contention on a memory location between multiple threads trying to modify that memory location.
    - kasey_junk 10y ago
      The answer is...it depends (on lots of things). In the case "real world performance" it has to do with the implementation of the lock and the architecture, but the CAS intrinsics on the architecture are almost certainly going to be the most performant way to do memory sync, so either the lock elides to those or it doesn't but if you are doing the CAS yourself you know what you are using. For the purposes of these algorithm discussions though it can matter a lot because of the semantics of the lock. To prove something is lock free you have to prove that a thread will complete in a finite number of steps and lots of lock semantics don't allow for that. For wait free all of the threads must complete and I don't know of any locking semantics that can allow for this property (but I'm definitely not an expert and usually poorly muddle through lock/algo papers). I think its important to recognize that lock-free/wait-free is more important for real time systems than it is for "performance" (in terms of latency of request). Real time systems are often practically slower than a non-real time version of the same thing, but they have a more consistent worst case. This is where lock-free/wait-free are especially useful.
cia48621793 10y ago
Japanese is definitely the smartest asian races. No wonder why Chinese aren't getting no Nobels.
- sctb 10y ago
  We've banned this account for violating the HN guidelines.
  - tarr11 10y ago
    Curious, why did you ban this account? The comments seem legitimate.
    - deleted 10y ago
      [deleted]
    - Natanael_L 10y ago
      Could be non-visible behavior. Perhaps vote manipulation.
    - EC1 10y ago
      This is an SJW site now. Can't say anything race related. I got banned for this comment: https://news.ycombinator.com/item?id=11377867 https://news.ycombinator.com/item?id=11377867 Can't say anything about Muslims anywhere online or you get censored. Facebook, Reddit, now HN.
snarfy 10y ago
> Subsequently, it is lazily deleted by a cleanup operation. So, it's wait free until this happens?
- kasey_junk 10y ago
  No, the cleanup operation is also wait free, which they claim is what makes this novel.
  - blaisio 10y ago
    Ah, they should really have put that in the description because otherwise this doesn't seem like that great of an achievement.
bnjmn 10y ago
Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time push/pop performance. This data structure is only a "stack" in the sense that it provides last-in-first-out access.
- chrisseaton 10y ago
  Is it possible for a contended concurrent stack accessed by an arbitrary number of threads to have guaranteed constant-time operations? I wouldn't think that was a realistic expectation.
  - aidenn0 10y ago
    A lock-based stack can be O(M) in number of threads accessing it. Judging by the abstract (haven't read the paper) this is O(N) in the size of the stack.
    - EvgeniyZh 10y ago
      "in terms of the number of concurrent threads in the system (N), the actual size of the stack(S) and the parameter W ... as soon as W consecutive nodes get marked ... the worst case time complexity of the pop operation is O(NWS)"
pzh 10y ago
Correct me if I'm wrong, but wasn't this already described in The Art of Multi Processor Programming? https://www.amazon.com/gp/aw/d/0123973376/ref=mp_s_a_1_1?ie=UTF8&qid=1468773145&sr=8-1&pi=SY200_QL40 https://www.amazon.com/gp/aw/d/0123973376/ref=mp_s_a_1_1?ie=...
- chrisseaton 10y ago
  No? It has a lock-free stack though.
amaks 10y ago
How often would you find a situation where lock free data queue or stack would bring huge performance gains? Usually bad performance comes from a poor choice of data structure(s), bad data locality or by locking is too coarse or too fine causing livelocks/convoys/excessive context switches etc. What I'm saying is that using lock free or wait free algorithm is not a panacea.

A Wait-Free Stack

281 points by EvgeniyZh 10y ago

deleted 10y ago

[deleted]

programmer_dude 10y ago

What is a wait-free stack?

krig 10y ago
From the introduction: > In this paper, we describe an algorithm to create a wait-free stack. A concurrent data structure is said to be wait-free if each operation is guaranteed to complete within a finite number of steps. In comparison, the data structure is said to be lock-free if at any point of time, at least one operation is guaranteed to complete in a finite number of steps. Lock-free programs will not have deadlocks but can have starvation, whereas wait-free programs are starvation free.
wcrichton 10y ago
Wait-freedom is described in the introduction. Quote: There are three levels of progress guarantees for non-blocking data structures. A concurrent object is: - obstruction-free if a thread can perform an arbitrary operation on the object in a finite number of steps when it executes in isolation, - lock-free if some thread performing an arbitrary operation on the object will complete in a finite number of steps, or - wait-free if every thread can perform an arbitrary operation on the object in a finite number of steps. Wait-freedom is the strongest progress guarantee; it rules out the possibility of starvation for all threads. Wait-free data structures are particularly desirable for mission critical applications that have real-time constraints, such as those used by cyber-physical systems.

xchip 10y ago

I love papers but I love it more when their code is in github :) thanks for sharing!

EvgeniyZh 10y ago
Yeah, I'd love to see implementation too. Even better - implementation in some lib with comparison of performance

appleflaxen 10y ago

More discussion on pdf link https://news.ycombinator.com/item?id=12109219 https://news.ycombinator.com/item?id=12109219

bhouston 10y ago
Different paper - queue vs stack. Confused me as well.

duiker101 10y ago

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

nemetroid 10y ago

The first few lines of pop() are: mytop <- top.get() curr <- mytop while curr != sentinel do mark <- curr.mark.getAndSet(true) ... What's keeping curr from becoming a dangling pointer if the size of the stack is bounded?

kumagi 10y ago

I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html http://longgate.co.jp/books/grimoire-vol3.html

kumagi 10y ago
This book is published in 2013. Earlier than this arxiv paper.
- lrem 10y ago
  It's sad to be in "the other cultural circle", isn't it? Imagine that in western Europe a number of theorems by eastern European mathematicians is known by the name of the western professor who would propagate it... Also: I feel there should be a comma in the sentence above, but can't figure out where to put it :/
  - jsprogrammer 10y ago
    After the 3, in place of the period.
  - ktta 10y ago
    I understand what you're trying to convey and agree. I thought you might not have noticed the email address of the authors. Two of the authors' email addresses are of IIT Delhi, one of the universities managed by the Government of India. So these authors are in "the other cultural circle" too. One in which there's more than 10 times competition in the educational system for funding, compared to not only western and European counterparts but the Japanese one too, which the parent comment I think is/was a part of. Not just funding for cool projects. There is a very dire need for good universities but higher education in a good university is very difficult to have.
  - numbsafari 10y ago

zilchers 10y ago

I'm not sure I see what's novel about this - maybe it's a verbiage thing around "wait free," but if they're atomically updating the top pointer and linked list, there will be lock contention on writes, and similarly when marking an item popped, on reads. I suppose the contention is bounded by the number of readers or writers, but I wouldn't consider that wait free (again, that could just be a verbiage thing). But, more to the point, this is just a slight twist on how Kafka works (stack vs log / queue, but same with the pointer holding place and a cleanup operation), I don't really see it as particularly novel...perhaps I'm missing something?

kasey_junk 10y ago
A "wait free" data structure has a specific technical definition so yes, in some ways the novelty in this is that it meets that verbiage. Lock free stacks have been around since at least the 80s but I haven't seen a general wait free stack before (though I'm no expert). In neither this paper or the classic lock free stacks do you have lock contention on writes as you are using CAS operations. I'm having a little trouble parsing the algo in this paper, but what they seem to have added that is novel is their cleanup function will always complete in a finite number of steps, thus making the whole thing both wait free and bounded, which is pretty neat. In any case, with wait free structures generally implementation details matter a lot and stacks are pretty notoriously hard to handle because of the contention around the top node, as opposed to something like an append only log like Kafka uses, so that particular comparison is not fair.
- jemfinch 10y ago
  > In neither this paper or the classic lock free stacks do you have lock contention on writes as you are using CAS operations. Given that real-world locks are most often implemented using CAS, is this distinction a valuable one? In either case you have contention on a memory location between multiple threads trying to modify that memory location.
  - kasey_junk 10y ago
    The answer is...it depends (on lots of things). In the case "real world performance" it has to do with the implementation of the lock and the architecture, but the CAS intrinsics on the architecture are almost certainly going to be the most performant way to do memory sync, so either the lock elides to those or it doesn't but if you are doing the CAS yourself you know what you are using. For the purposes of these algorithm discussions though it can matter a lot because of the semantics of the lock. To prove something is lock free you have to prove that a thread will complete in a finite number of steps and lots of lock semantics don't allow for that. For wait free all of the threads must complete and I don't know of any locking semantics that can allow for this property (but I'm definitely not an expert and usually poorly muddle through lock/algo papers). I think its important to recognize that lock-free/wait-free is more important for real time systems than it is for "performance" (in terms of latency of request). Real time systems are often practically slower than a non-real time version of the same thing, but they have a more consistent worst case. This is where lock-free/wait-free are especially useful.

cia48621793 10y ago

Japanese is definitely the smartest asian races. No wonder why Chinese aren't getting no Nobels.

sctb 10y ago
We've banned this account for violating the HN guidelines.
- tarr11 10y ago
  Curious, why did you ban this account? The comments seem legitimate.
  - deleted 10y ago
    [deleted]
  - Natanael_L 10y ago
    Could be non-visible behavior. Perhaps vote manipulation.
  - EC1 10y ago
    This is an SJW site now. Can't say anything race related. I got banned for this comment: https://news.ycombinator.com/item?id=11377867 https://news.ycombinator.com/item?id=11377867 Can't say anything about Muslims anywhere online or you get censored. Facebook, Reddit, now HN.

snarfy 10y ago

> Subsequently, it is lazily deleted by a cleanup operation. So, it's wait free until this happens?

kasey_junk 10y ago
No, the cleanup operation is also wait free, which they claim is what makes this novel.
- blaisio 10y ago
  Ah, they should really have put that in the description because otherwise this doesn't seem like that great of an achievement.

bnjmn 10y ago

Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time push/pop performance. This data structure is only a "stack" in the sense that it provides last-in-first-out access.

chrisseaton 10y ago
Is it possible for a contended concurrent stack accessed by an arbitrary number of threads to have guaranteed constant-time operations? I wouldn't think that was a realistic expectation.
- aidenn0 10y ago
  A lock-based stack can be O(M) in number of threads accessing it. Judging by the abstract (haven't read the paper) this is O(N) in the size of the stack.
  - EvgeniyZh 10y ago
    "in terms of the number of concurrent threads in the system (N), the actual size of the stack(S) and the parameter W ... as soon as W consecutive nodes get marked ... the worst case time complexity of the pop operation is O(NWS)"

pzh 10y ago

Correct me if I'm wrong, but wasn't this already described in The Art of Multi Processor Programming? https://www.amazon.com/gp/aw/d/0123973376/ref=mp_s_a_1_1?ie=UTF8&qid=1468773145&sr=8-1&pi=SY200_QL40 https://www.amazon.com/gp/aw/d/0123973376/ref=mp_s_a_1_1?ie=...

chrisseaton 10y ago
No? It has a lock-free stack though.

amaks 10y ago

How often would you find a situation where lock free data queue or stack would bring huge performance gains? Usually bad performance comes from a poor choice of data structure(s), bad data locality or by locking is too coarse or too fine causing livelocks/convoys/excessive context switches etc. What I'm saying is that using lock free or wait free algorithm is not a panacea.