Finally adding recursive functions to Futhark
16 points by fanf
16 points by fanf
Nice, now I can add BSP tree traversal to my futhark raytracer :)
You can do that anyway! You probably don't ever want to use recursive functions in anything that is even remotely performance-sensitive. The trick to efficiently traverse trees in a stack-free manner is to keep track of the previous node visited when returning to a parent, so you know which one to visit next.
Keep track of the previous node visited... Using a stack! ;-) ...a very, very short stack. If I'm reading the code correctly.
Sorry, couldn't resist. Certainly sounds like Futhark's recursion isn't suitable for hot loops still, yeah. But I've occasionally wished for Rust to have the ability to warn/error when a recursive function can't be optimized into a loop...
Keep track of the previous node visited... Using a stack! ;-)
It goes the other way, though! The normal recursion stack stores history towards the root of the tree; here you store the last visited child instead. Not only an asymptotic reduction in required stack space, also a momentous directional inversion!