Earlier quoted context omitted.
We've banned this account for violating the HN guidelines.
Curious, why did you ban this account? The comments seem legitimate.
Could be non-visible behavior. Perhaps vote manipulation.
A Wait-Free Stack
41–50 of 71 posts
Re: A Wait-Free Stack
#42> Subsequently, it is lazily deleted by a cleanup operation. So, it's wait free until this happens?
No, the cleanup operation is also wait free, which they claim is what makes this novel.
Ah, they should really have put that in the description because otherwise this doesn't seem like that great of an achievement.
Re: A Wait-Free Stack
#43Earlier quoted context omitted.
We've banned this account for violating the HN guidelines.
Curious, why did you ban this account? The comments seem legitimate.
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
Can't say anything about Muslims anywhere online or you get censored. Facebook, Reddit, now HN.
Re: A Wait-Free Stack
#44Earlier 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.
Yes, it is a real distinction. In lock-free algorithms, progress is guaranteed. If they are not wait-free, then they tend to update some values, then try to commit those values with CAS. If the CAS fails, they try again. Wait-free algorithms do the first part, but on the failure, they don't try again, they go off and do something different. All threads can make progress, even if some thread is suspended or dies; no thread has exclusive access to modify the state.
In lock-based algorithms, that is not the case; the thread with the lock can be suspended, killed, or go off on a wild goose chase, and the progress of the algorithm cannot continue. Only that thread may modify the state, and the rest must wait.
Re: A Wait-Free Stack
#45Earlier quoted context omitted.
> 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 alg…
How useful is a lock-free (not wait-free) approach in a real-time context? The point is that any thread contending on lock-free data is liable to starve, so the worst-case behavior is still quite bad, no? The only benefit I see is freedom from priority inversion, and that's a fixable problem anyway. Are there other properties of the system that you somehow use to get real-time guarantees?
On the other hand, if you combine interrupt-disabling with a fair lock, then your lock wait time can be bounded in every thread. This is probably only an option inside the kernel, though.
In userspace, and with more threads than CPUs, the lock-free approach probably will save you a lot of context-switching time. It'll probably also be at least as fine-grained as the most fine-grained locking scheme you can come up with, probably with less overhead.
So I'd say that the lock-free approach is an optimistic strategy, and I don't see the benefit except for performance. I say this as someone who really likes lockfree programming.
Re: A Wait-Free Stack
#46Earlier quoted context omitted.
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 alg…
How useful is a lock-free (not wait-free) approach in a real-time context? The point is that any thread contending on lock-free data is liable to starve, so the worst-case behavior is still quite bad, no? The only benefit I see is freedom from priority inversion, and that's a fixable problem anyway. Are there other properties of the system that you somehow use to get real-time guarantees? On the other hand, if you co…
> The only benefit I see is freedom from priority inversion, and that's a fixable problem anyway. Are there other properties of the system that you somehow use to get real-time guarantees?
Priority inversion was what I was thinking of. When you say its a fixable problem, the common way to fix that is to have a real time scheduler deal with it. Lots of systems don't have real time schedulers available to them, so lock free algos make sense there and you deal with the starvation issue instead of the inversion issue.
That said, I'm no expert on real time systems and my use of lock free algos has fallen into the exact category you are talking about, which is wanting to avoid context switches in user land, but that is more a property of the OSes I use than the algorithms themselves.
Re: A Wait-Free Stack
#47Correct 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=...
No? It has a lock-free stack though.
Re: A Wait-Free Stack
#48Make 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.
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.
Re: A Wait-Free Stack
#49I 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.
Do you suggest that they've used your findings without referencing you? You can make an inquiry I believe. Other than that, if their method is completely different or they've arrived to the same solution independently - there is nothing wrong. It is not about the competition who was first, isn't it?
Re: A Wait-Free Stack
#50So 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…
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.