Japanese is definitely the smartest asian races. No wonder why Chinese aren't getting no Nobels.
We've banned this account for violating the HN guidelines.
Curious, why did you ban this account? The comments seem legitimate.
A Wait-Free Stack
31–40 of 71 posts
Re: A Wait-Free Stack
#32I'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 trou…
> 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.
Re: A Wait-Free Stack
#33Make 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.
Re: A Wait-Free Stack
#34Earlier quoted context omitted.
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 trou…
> 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.
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.
Re: A Wait-Free Stack
#35Earlier quoted context omitted.
> 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.
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.
You can do some checks as non-atomic instructions too, with careful use of memory barriers.
Re: A Wait-Free Stack
#36Correct 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=...
Re: A Wait-Free Stack
#37So 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 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…
> 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-...
Re: A Wait-Free Stack
#38Re: A Wait-Free Stack
#39I 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
You call malloc in your implementation -- you realize that memory allocation takes lock at some point, right? To make it truly lock or wait free you need to implement a corresponding memory allocator as well.
Re: A Wait-Free Stack
#40I'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…
res = last.nextDone.compareAndSet( (null,false), (myNode, false))
I fail to see how under contention the statement above is "wait-free". Having globalPhase is another contention point (although atomic adds are wait free on most hardware, nowadays).
Not ceratain if 'tid' is threadId but having AtomicReferenceArray (all notation appears to stem from java.util.concurrent) with an arbitrary length is certainly not a wait-free operation, hence the announce would fail to be wait free. Using CPU-id instead is a hard one as well unless all threads are core-bound. Morealso if the array (announce) is not fixed length the entire algorithm cannot finish in finite amount of steps.