4 ms·

I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult tha

by kumagi 10y ago

I already wrote wait-free stack https://gist.github.com/kumagi/d259274270fdc1385f81 https://gist.github.com/kumagi/d259274270fdc1385f81 It is much difficult than lock-free stack. https://gist.github.com/kumagi/b9a4715b1ce0dd511922 https://gist.github.com/kumagi/b9a4715b1ce0dd511922 And published as book(in Japanese sorry) http://longgate.co.jp/books/grimoire-vol3.html http://longgate.co.jp/books/grimoire-vol3.html

kumagi 10y ago
This book is published in 2013. Earlier than this arxiv paper.
- lrem 10y ago
  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 :/
  - jsprogrammer 10y ago
    After the 3, in place of the period.
  - ktta 10y ago
    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.
  - numbsafari 10y ago
    I think you want to use commas to set off "in Western Europe". I think it's referred to as an "aside".
- xchip 10y ago
  you rock! So what do the threads do when they are idle? Don't you put them to sleep?
- zerr 10y ago
  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?
  - egwor 10y ago
    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
  - deleted 10y ago
    [deleted]
amaks 10y ago
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.
- _ij0r 10y ago
  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.
  - amaks 10y ago
    Not really. Lots of applications where lock free algorithms are justified usually implement their own memory allocators.
  - haberman 10y ago
    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.
- cjensen 10y ago
  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.
- arunmoezhi 10y ago
  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.

by kumagi 10y ago

kumagi 10y ago

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

lrem 10y ago
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 :/
- jsprogrammer 10y ago
  After the 3, in place of the period.
- ktta 10y ago
  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.
- numbsafari 10y ago
  I think you want to use commas to set off "in Western Europe". I think it's referred to as an "aside".
xchip 10y ago
you rock! So what do the threads do when they are idle? Don't you put them to sleep?
zerr 10y ago
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?
- egwor 10y ago
  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
- deleted 10y ago
  [deleted]

amaks 10y ago

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.

_ij0r 10y ago
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.
- amaks 10y ago
  Not really. Lots of applications where lock free algorithms are justified usually implement their own memory allocators.
- haberman 10y ago
  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.
cjensen 10y ago
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.
arunmoezhi 10y ago
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.