Hacker News Reader

Comment by nemoniac | Hacker News Reader

Fascinating blog post. Having said that, it may seem like nitpicking but I have to take issue with the point about recursion, which is often far too easily blamed for inefficiency.

The blog post mentions it as one of the reasons for the inefficiency of the conventional algorithm.

A glance at the algorithm shows that the recursion in question is a tail call. This means that any overhead can be readily eliminated using a technique known for nearly fifty years already.

Steele, Guy Lewis (1977). "Debunking the "expensive procedure call" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO". Proceedings of the 1977 annual conference on - ACM '77.

View on HN

A lot of modern programming languages do not do tail call optimization, often citing keeping accurate stack history for debugging as an excuse.

Regardless of how valid the excuse is, for such an obvious and old optimization, it’s very poorly supported.

The main problem with tail call optimization is that it's unreliable; small apparently unrelated changes elsewhere in the function, a difference in the compiler command line flags, or a different compiler version, could all make a tail call become a non-tail call. Some languages have proposed explicit markers to force a call to be a tail call (and generate a compilation error if it can't), but I don't think these proposals have been adopted yet.

Dumb question: does modern stack layout randomization affect the efficiency of recursion? On first glance I would be worried about cache misses.

Not specifically address space layout randomization in the way it's usually implemented; ASLR as applied in most modern production OSes randomizes each stack's base address, but each stack is still laid out and used in a normal way. There are some research projects towards actual stack layout randomization (involving stack rearrangement via static analysis, randomly sized stack padding frames, and other techniques) which would also definitely blow up cache, but none that are mainstream in a production system as far as I know.

However, for the naive case where the recursion is a full-blown function call, without some kind of optimization, other security mitigations than ASLR will significantly affect the efficiency of recursion by adding function call overhead (and possible cache side effects) - for example, the stack cookie will still be verified and control-flow guard checks and the shadow/return stack will still be in play, if present.

Isn't it true that if an algorithm can be tail-call optimized, it can be rewritten to not use recursion at all? (And conversely, if something can't be rewritten without recursion, it can't be tail-call optimized?)

Reply on news.ycombinator.com