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

21–30 of 71 posts

Re: A Wait-Free Stack

#21

Post by badestrand »

duiker101 wrote: post #8

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 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. Unfortunately, of that whole operation acquiring/freeing the lock takes 99% of the time. Thus lock-free data structures were developed which magically did not need locking and thus could operate blazingly fast. I understand the article now introduces a lock-free stack.

As I understand these data structures have no effects on multi-system environments and can only be applied to a single system. This is because they rely on atomic CPU operations that are not available (natively) on distributed systems.

How does that affect us? Not much I guess. I have never seen those data structures widely used. In my understanding almost no application benefits noticably(!) from the speed up. Maybe games, but I don't think so. Nonetheless it is always nice to see basic building blocks improved.

Re: A Wait-Free Stack

#22

Post by xchip »

kumagi wrote: post #13
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

This book is published in 2013. Earlier than this arxiv paper.

you rock! So what do the threads do when they are idle? Don't you put them to sleep?

Re: A Wait-Free Stack

#24

Post by zzzcpan »

badestrand wrote: post #21
duiker101 wrote: post #8

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

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

Re: A Wait-Free Stack

#26

Post by [deleted] »

zilchers wrote: post #15

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, mo…

[deleted]

Re: A Wait-Free Stack

#28

Post by bluejekyll »

zzzcpan wrote: post #24
badestrand wrote: post #21

Earlier quoted context omitted.

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…

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

Re: A Wait-Free Stack

#29

Post by ktta »

lrem wrote: post #18
kumagi wrote: post #13

Earlier 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 :/

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.

Post reply on HN