Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Wait-Free Stack

arxiv.org

Post reply on HN
Print view View original

51–60 of 71 posts

Re: A Wait-Free Stack

#51

Post by egwor »

zerr wrote: post #49
kumagi wrote: post #13

Earlier quoted context omitted.

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?

I think that in this day and age we ought to have a way to share knowledge so that we aren't repeating the same (completed) research unknowingly.

In maths it is thought to be beneficial to come up with a diferent proof of the same theorem though, so maybe in computing the similar idea that coming up with another implementation/demonstration/proof has value too

Re: A Wait-Free Stack

#52

Post by [deleted] »

zerr wrote: post #49
kumagi wrote: post #13

Earlier quoted context omitted.

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?

[deleted]

Re: A Wait-Free Stack

#53

Post by _ij0r »

amaks wrote: post #39
kumagi wrote: post #12

I 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.

With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right?

I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.

Re: A Wait-Free Stack

#54

Post by amaks »

_ij0r wrote: post #53
amaks wrote: post #39

Earlier quoted context omitted.

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.

With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right? I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.

Not really. Lots of applications where lock free algorithms are justified usually implement their own memory allocators.

Re: A Wait-Free Stack

#55

Post by amaks »

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.

Re: A Wait-Free Stack

#56

Post by aidenn0 »

chrisseaton wrote: post #48
bnjmn wrote: post #33

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.

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.

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.

Re: A Wait-Free Stack

#57

Post by haberman »

_ij0r wrote: post #53
amaks wrote: post #39

Earlier quoted context omitted.

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.

With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right? I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.

Lock-free algorithms don't usually depend on an OS being present. They could just as easily run in an environment that has no scheduler. But if the algorithm calls malloc, that is a hard dependency.

If an algorithm depends on malloc, it needs to prove that lock-free/wait-free malloc() exists before calling itself lock/wait-free.

Re: A Wait-Free Stack

#58

Post by cjensen »

amaks wrote: post #39
kumagi wrote: post #12

I 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.

Malloc can be lock free if you add a thread which wakes up periodically and ensures there is free memory available.

Also, any algorithm can be made mostly malloc free if you keep a freelist instead of freeing memory. Malloc will then only be called enough times to fill the max utilization.

Re: A Wait-Free Stack

#59

Post by mfukar »

gosu wrote: post #45
kasey_junk wrote: post #34

Earlier 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…

Both lock-free and wait-free algorithms/implementations offer the same advantage, as a corollary of their definition: latency guarantees. These are central to real-time systems.

PS. The difference is that lock-free algorithms improve throughput _at the expense of single-thread latency_, and thus are more useful for satisfying system-wide throughput requirements, e.g. for a DBMS. Wait-freedom additionally guarantees freedom from starvation.

Re: A Wait-Free Stack

#60

Post by arunmoezhi »

amaks wrote: post #39
kumagi wrote: post #12

I 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.

Most of the concurrent lock-free search trees published in literature do not even give a garbage collection strategy(assuming the implementation language has no automatic garbage collection). But they still claim lock-free or wait-free. They make assumption that memory can be reclaimed using recent techniques provided in the literature. I'm not sure sure if there is a lock-free Malloc. But that is not the problem the algorithm is trying to solve.

And almost all these algorithms use Compare-And-Exchange(CAS) instruction which internally uses locks.

Post reply on HN