More discussion on pdf link https://news.ycombinator.com/item?id=12109219
Different paper - queue vs stack. Confused me as well.
A Wait-Free Stack
11–20 of 71 posts
Re: A Wait-Free Stack
#12I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81
It is much difficult than lock-free stack.
https://gist.github.com/kumagi/b9a4715b1ce0dd511922
And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html
Re: A Wait-Free Stack
#13I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html
This book is published in 2013.
Earlier than this arxiv paper.
Re: A Wait-Free Stack
#14So 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 inter…
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 (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)
Re: A Wait-Free Stack
#15I'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?
Re: A Wait-Free Stack
#16I'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, mo…
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.
Re: A Wait-Free Stack
#17I'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, mo…
[deleted]
Re: A Wait-Free Stack
#18I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html
This book is published in 2013. Earlier than this arxiv paper.
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 :/
Re: A Wait-Free Stack
#19I'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, mo…
Lock contention? Why do you think they're using locks?
Re: A Wait-Free Stack
#20Earlier quoted context omitted.
This book is published in 2013. Earlier than this arxiv paper.
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 :/
After the 3, in place of the period.