An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 2:32 UTC (Sat) by Cyberax (✭ supporter ✭, #52523)
In reply to: An introduction to lockless algorithms by pebolle
Parent article: An introduction to lockless algorithms

It's a mathematical term (a "totally ordered set"). It means that for any two events you can tell which one came earlier.

This is opposed to a partially ordered set. A good example of a partially ordered set is a genealogical tree. From the information within the tree you can tell that some people are older than other (a father is always older than a son) but for some cases there's not enough information (e.g. you can be younger or older than your cousin).

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 9:34 UTC (Sat) by pebolle (guest, #35204) [Link] (21 responses)

> A good example of a partially ordered set is a genealogical tree.

That helps.

I'm mathematically challenged. So, for example, I found it very annoying in programming exercises that recursion would always be taught with Fibonacci numbers. Who cares about that? It wasn't until I once had to walk through directories and filenames that recursion started to make sense to me.

An introduction to lockless algorithms

Posted Feb 21, 2021 11:20 UTC (Sun) by ballombe (subscriber, #9523) [Link] (20 responses)

Maybe you missed the point of the exercise ?
The point is that recursion *does not* work for computing Fibonacci numbers...

An introduction to lockless algorithms

Posted Feb 21, 2021 12:13 UTC (Sun) by pebolle (guest, #35204) [Link] (9 responses)

> [...] recursion *does not* work for computing Fibonacci numbers...

I just double checked - I was afraid that my memory let me down again - but recursion does work for Fibonacci. At least, that's what the web and the only introductory programming book I have on my shelves tells me.

Perhaps we disagree on the meaning of "recursion" and "work"?

An introduction to lockless algorithms

Posted Feb 21, 2021 12:29 UTC (Sun) by Wol (subscriber, #4433) [Link] (6 responses)

int fibonacci( int f)
{
if (f <= 1)
return f;
else
return fibonacci( f-1) + fibonacci( f-2);
}

Which will blow your stack for large values of f :-)

I hope I've got it right ... :-)

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 21, 2021 13:08 UTC (Sun) by dtlin (subscriber, #36537) [Link]

With that implementation, there's a good chance you'll experience integer wraparound (and thus wrong results) before you blow the stack. fib(92) = 7540113804746346429, fib(93) = 12200160415121876738 which doesn't fit in a 64-bit signed integer.

The problem with the recursive solution is the exponential runtime; the stack usage is linear.

An introduction to lockless algorithms

Posted Feb 21, 2021 15:24 UTC (Sun) by Wol (subscriber, #4433) [Link] (1 responses)

I knew I should have checked it ...

The start of the conditional should be

if (f <= 2) return 1;

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 21, 2021 16:16 UTC (Sun) by yann.morin.1998 (guest, #54333) [Link]

> The start of the conditional should be
> if (f <= 2) return 1;

Not necessarily. The generalised Fibonacci sequence starts with F(0) = 0 and F(1) = 1 [0]. So your initial condition was (not in)correct.

[0] https://en.wikipedia.org/wiki/Fibonacci_number

An introduction to lockless algorithms

Posted Feb 21, 2021 17:10 UTC (Sun) by matthias (subscriber, #94967) [Link]

This will definitely not blow the stack. Even for quite small numbers of f, the runtime will be longer than the age of the universe.

An introduction to lockless algorithms

Posted Feb 21, 2021 23:41 UTC (Sun) by neilbrown (subscriber, #359) [Link]

> Which will blow your stack for large values of f :-)

Only if you try to implement it on a computer.
As a mathematical abstraction, this is perfectly fine and well defined for all f.

An introduction to lockless algorithms

Posted Mar 5, 2021 0:13 UTC (Fri) by qzPhUZ7af5M6kjJi3tDgMaVq (guest, #140267) [Link]

Recursive definitions work just fine in certain programming languages.

https://wiki.haskell.org/The_Fibonacci_sequence

In a Haskell interpreter:

Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude> fibs !! 100000

(20,899 digit number omitted... it took about 2 seconds to compute it)

An introduction to lockless algorithms

Posted Feb 22, 2021 9:49 UTC (Mon) by ballombe (subscriber, #9523) [Link] (1 responses)

To compute fibo(50) the naive sequential algorithm needs 50 additions, the naive recursive algorithm needs
12586269025 additions. That is what I call 'not working'.

An introduction to lockless algorithms

Posted Feb 22, 2021 10:04 UTC (Mon) by pebolle (guest, #35204) [Link]

I'll file this under 'Disagreeing what "work" means' too.

An introduction to lockless algorithms

Posted Feb 22, 2021 11:47 UTC (Mon) by jezuch (subscriber, #52988) [Link] (9 responses)

Actually I don't think I ever saw a programming tutorial which introduced recursion using Fibonacci sequences and said that this was a bad example. Which I too think is sad. But I guess this is the prototypical "recursive function" known from the math classes, so...

An introduction to lockless algorithms

Posted Feb 22, 2021 12:14 UTC (Mon) by Wol (subscriber, #4433) [Link] (8 responses)

Thing is, the *definition* of fibonacci is recursive. Doesn't mean it's the best way to calculate it ...

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 24, 2021 23:49 UTC (Wed) by NYKevin (subscriber, #129325) [Link] (7 responses)

The recursive definition is perfectly fine for computing it as long as you memoize appropriately. You don't even need all that much memo space, because you only ever need to keep the largest two values (which I believe will generally also be the two most recently computed values, so you can just bolt on a bog-standard LRU cache).

Of course, if you *really* want to motivate memoization, you probably want to talk about something more interesting, like Hashlife. I remember reading a lengthy series of articles on Eric Lippert's blog where he spends much of the series painstakingly squeezing out every ounce of performance from the iterative approach (vectorization, bit-twiddling, lookup tables, etc.), and then he switches to Hashlife ("Gosper's algorithm"), with hardly any weird optimizations at all beyond basic algorithm design and memoization, using *garbage collected objects* to represent everything, and suddenly the whole thing is orders of magnitude faster* for large-enough N. My conclusion: Using the right algorithm is far, far more effective than heavily optimizing the wrong algorithm.

* Strictly speaking, it is faster when solving the problem "Figure out what the board will look like at generation N." If the problem is instead "Figure out what the board will look like at every generation from 1 through N," then Hashlife is much less effective. So using it for an interactive UI that sequentially displays one generation at a time is probably not a great idea. But if you want to advance directly to generation 2^27 or something like that, Hashlife is basically the only game in town.

An introduction to lockless algorithms

Posted Mar 2, 2021 20:07 UTC (Tue) by jezuch (subscriber, #52988) [Link] (6 responses)

Well actually...

Fibonacci numbers are defined by a recursive function which has an exact solution, so you can calculate every number in O(1) time (assuming no bignums are needed). So it's doubly (or triply) a bad example to intoduce recursion to new programmers ;)

An introduction to lockless algorithms

Posted Mar 5, 2021 3:16 UTC (Fri) by dtlin (subscriber, #36537) [Link] (5 responses)

It has a closed-form solution but that does not make it O(1).

An introduction to lockless algorithms

Posted Mar 11, 2021 9:56 UTC (Thu) by anselm (subscriber, #2796) [Link] (4 responses)

It has a closed-form solution but that does not make it O(1).

If your platform only supports integers up to a certain maximum (say 2^64-1), it is O(1) because it is straightforward to create a lookup table for all n where F(n) < 2^64 and use that rather than the recursive definition.

An introduction to lockless algorithms

Posted Mar 11, 2021 19:28 UTC (Thu) by nybble41 (subscriber, #55106) [Link] (3 responses)

> … it is O(1) because it is straightforward to create a lookup table for all n where F(n) < 2^64 and use that rather than the recursive definition.

If you strict permissible inputs to a predetermined finite range then every algorithm becomes O(1). That's not a very useful definition, though. And while a 93-entry table suffices to represent all Fibonacci numbers less than 2^64, many languages have built-in arbitrary-precision integer types limited only by available memory.

An introduction to lockless algorithms

Posted Mar 12, 2021 10:49 UTC (Fri) by anselm (subscriber, #2796) [Link] (1 responses)

Obviously. I think the point here is that Fibonacci numbers are often used as a prime example for the use of recursion, but in practice, calculating Fibonacci numbers through a 1:1 implementation of their recursive definition is not what one would actually ever do. As such it gives people silly ideas. It would be better to come up with examples where there are more compelling arguments for using recursion in the first place, or at the very least put a big health warning on the Fibonacci example.

An introduction to lockless algorithms

Posted Mar 13, 2021 8:54 UTC (Sat) by neilbrown (subscriber, #359) [Link]

I recall in first year CompSci, recursion was introduced using the Towers of Hanoi game. I think that is an excellent vehicle, much better than Fibonacci.

An introduction to lockless algorithms

Posted Mar 16, 2021 20:49 UTC (Tue) by nix (subscriber, #2304) [Link]

The canonically crazy example of this is the wonderful Hutter search: https://arxiv.org/abs/cs/0206022. The title describes it well: it is, in fact, the fastest and shortest general algorithm possible if you want one single algorithm that can solve all well-defined problems -- but given that it involves searching for and then executing all possible programs until it finds the one that solves the problem you asked about, it is somewhat impractical. You might find it useful if you are looking for something for your hypercomputer to run when you are bored of having it work out all the busy beaver numbers up to 10^100...