3 ms·

lol. i once interviewed with facebook and had some "senior" dev on the phone who was balking and grousing at my claim that iterative algorithms are faster than

by a-dub 2mo ago

lol. i once interviewed with facebook and had some "senior" dev on the phone who was balking and grousing at my claim that iterative algorithms are faster than recursive ones. the minute i mentioned spatial locality, he went quiet. more to the point, i feel like there should be a compiler switch or decorator style flag in modern languages that declare "this function is expected to optimize with tail recursion, throw a compiler or linter error at static analysis time if that doesn't work out."

senkora 2mo ago
This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]
winstonlee 2mo ago
Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.
dataflow 2mo ago
Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?
- vanviegen 2mo ago
  Yes, and a high-level scripting language can in some specific circumstances be made to run code faster than a low-level compiled language. Generally, it's the other way around though.
  - dataflow 2mo ago
    This feels like a strawman and doesn't really attempt to answer my question. These kinds of broad generalizations really need good evidence/citation.
    - vanviegen 2mo ago
      Both parts of your comment lean on a sufficiently smart compiler to make up for recursion's natural disadvantage in maintaining locality of reference and performance. Sure, some compilers can bridge the gap in some cases (by transpiling your recursive code to an ittertive approach).
- a-dub 2mo ago
  maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries. the state spraying results in consumption and spilling down the memory hierarchy, from registers through caches. i think of this as the memory hierarchy being designed to best perform when spatial locality of memory usage is maintained, but it's slightly different from what most people mean when they discuss spatial locality... maybe "cache efficiency" is the better term?
  - dataflow 2mo ago
    > maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries If that's what you mean then I'm afraid it sounds like you're mixing a few things up. For example, imagine depth-first search: you're going to need a stack somewhere, whether it's the CPU stack which you use via recursion, or an explicit stack you use via iteration. Iterating doesn't magically remove your need for that space and somehow collapse everything down to one stack frame. And you can reuse temporaries from the heap too, etc. Fundamentally, there is the question of how much space you need for given algorithm, the question of what algorithm you should use in the first place, the question of whether that particular algorithm should be implemented recursively or iteratively, and the question of what is more maintainable and easier to evolve in practice. These are all separate questions, but you're conflating them. If your iteration uses constant space but your recursion doesn't, that's because you're not implementing the same algorithm. You're implementing a different algorithm that achieves the same original goal you had. Of course one algorithm might beat the other, that's no surprise.
    - a-dub 2mo ago
      let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. the stack grows with O(depth) and therefore memory usage does as well. a consequence of this is that the finite storage lru caches and registers are polluted with one-time-use variables which reduces their availability for actually useful caching. it IS possible for a loop to use constant space. pre-allocate temporaries and inline any function calls. everything lives in one stack frame. simply iterating the loop itself does not come with fixed space overheads from allocating new stack frames. i suppose one thing i should mention, i am thinking of extreme optimization use cases where the entire data structure fits in cache (or close to it). think like in-cache tries or similar. if you're hitting main memory with each iteration anyway, it doesn't really matter.
palata 2mo ago
> more to the point, i feel like there should be a compiler switch or decorator style flag in modern languages that declare "this function is expected to optimize with tail recursion, throw a compiler or linter error at static analysis time if that doesn't work out." Scala and Kotlin have that. Other modern languages probably do as well.

by a-dub 2mo ago

senkora 2mo ago

This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]

winstonlee 2mo ago

Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.

dataflow 2mo ago

Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?

vanviegen 2mo ago
Yes, and a high-level scripting language can in some specific circumstances be made to run code faster than a low-level compiled language. Generally, it's the other way around though.
- dataflow 2mo ago
  This feels like a strawman and doesn't really attempt to answer my question. These kinds of broad generalizations really need good evidence/citation.
  - vanviegen 2mo ago
    Both parts of your comment lean on a sufficiently smart compiler to make up for recursion's natural disadvantage in maintaining locality of reference and performance. Sure, some compilers can bridge the gap in some cases (by transpiling your recursive code to an ittertive approach).
a-dub 2mo ago
maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries. the state spraying results in consumption and spilling down the memory hierarchy, from registers through caches. i think of this as the memory hierarchy being designed to best perform when spatial locality of memory usage is maintained, but it's slightly different from what most people mean when they discuss spatial locality... maybe "cache efficiency" is the better term?
- dataflow 2mo ago
  > maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries If that's what you mean then I'm afraid it sounds like you're mixing a few things up. For example, imagine depth-first search: you're going to need a stack somewhere, whether it's the CPU stack which you use via recursion, or an explicit stack you use via iteration. Iterating doesn't magically remove your need for that space and somehow collapse everything down to one stack frame. And you can reuse temporaries from the heap too, etc. Fundamentally, there is the question of how much space you need for given algorithm, the question of what algorithm you should use in the first place, the question of whether that particular algorithm should be implemented recursively or iteratively, and the question of what is more maintainable and easier to evolve in practice. These are all separate questions, but you're conflating them. If your iteration uses constant space but your recursion doesn't, that's because you're not implementing the same algorithm. You're implementing a different algorithm that achieves the same original goal you had. Of course one algorithm might beat the other, that's no surprise.
  - a-dub 2mo ago
    let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. the stack grows with O(depth) and therefore memory usage does as well. a consequence of this is that the finite storage lru caches and registers are polluted with one-time-use variables which reduces their availability for actually useful caching. it IS possible for a loop to use constant space. pre-allocate temporaries and inline any function calls. everything lives in one stack frame. simply iterating the loop itself does not come with fixed space overheads from allocating new stack frames. i suppose one thing i should mention, i am thinking of extreme optimization use cases where the entire data structure fits in cache (or close to it). think like in-cache tries or similar. if you're hitting main memory with each iteration anyway, it doesn't really matter.

palata 2mo ago

> more to the point, i feel like there should be a compiler switch or decorator style flag in modern languages that declare "this function is expected to optimize with tail recursion, throw a compiler or linter error at static analysis time if that doesn't work out." Scala and Kotlin have that. Other modern languages probably do as well.