News for hackers. Stuff that matters.
Re:Tree traversal without recursion: the tree as a state mac... by alkonaut on Tuesday September 03, 2019 @05:19AM (#20864872)
It seems like by adding parent pointer one is shifting complexity from the traversal into the data structure, in order to avoid a stack. I know there are places where avoiding an explicit stack can be nice (perhaps a BVH tree in a shader or other places where constant space is required?) but are there more good reasons for it? A DAG (such as a singly linked tree) has so many benefits for memory safety, GC performance, ability to extend it from a binary tree to N children etc., that it seems like an odd tradeoff in most scenarios.
Re:Tree traversal without recursion: the tree as a state mac... by HelloNurse on Tuesday September 03, 2019 @08:55AM (#20866002)
Obviously, adding read-only data in the tree and to save mutable data in the traversal state can be amortized if we have many ongoing traversals rather than one. For example, in a massively parallel GPU computation running an arbitrary number of tree searches simultaneously in a fixed memory amount.
Re:Tree traversal without recursion: the tree as a state mac... by amelius on Tuesday September 03, 2019 @06:42AM (#20865263)
Also you can use structural sharing if there are no parent pointers.