An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 24, 2021 23:49 UTC (Wed) by NYKevin (subscriber, #129325)
In reply to: An introduction to lockless algorithms by Wol
Parent article: An introduction to lockless algorithms

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.

to post comments

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