10 ms·
Tree traversal without recursion: the tree as a state machine (2007)
- segmondy 7y agoLearn some Prolog, one of the best langauge for studying your algorithms and data structures. https://rosettacode.org/wiki/Tree_traversal#Prolog https://rosettacode.org/wiki/Tree_traversal#Prolog preorder(nil). preorder([Node, FG, FD]) :- format('~w ', [Node]), preorder(FG), preorder(FD). inorder(nil). inorder([Node, FG, FD]) :-inorder(FG), format('~w ', [Node]), inorder(FD). postorder(nil). postorder([Node, FG, FD]) :-postorder(FG), postorder(FD),format('~w ', [Node]).
- willvarfar 7y agoExcellent! Generally, trees are poor for performance as you zig-zag around memory and stall on cache misses. But in situations where you have to do tree traversal and you have to be as fast as possible, trading the memory for the parent pointer (which probably fits within the same cache line as the rest of the node anyhow, so in practice basically free) vs recursion or an explicit stack which stress memory in the tight loop, it is probably a winner! Definitely worth profiling in those situations.
- lmilcin 7y agoMan, hold your horses. Assume you have 64GB of memory devoted to binary tree (of just integers), assuming the tree is balanced. Your node is two pointers + integer (24 bytes). That gives 2666666667 nodes. Balanced tree will have 32 levels (log2(2666666667) ~= 31). When doing recursion you just need to keep pointer to the level, so this is 32 times pointer or just about 256 bytes of your cache. Also, even if we were storing data in memory (and not in cache) this still is orders of magnitude less effort than accessing the memory for the large data structure.
- codebje 7y agoL1 cache lines are typically 64 bytes long, and you're only reading 16 bytes of it per level of the tree. And a random pointer tree traversal is the worst case for CPU branch prediction, too. There are methods for optimising the use of various tiers of cache, trying to pack multiple nodes into one 64 byte line, arranging nodes such that left and right children are usually adjacent in memory so prediction losses are minimised, and other tricks.
- signa11 7y agowell, these are dynamic structures which are constructed over a period of time with pointers pointing all over the place...imagine creating a singly-linked-list of 20/30m integers, and then running a trivial sum/accumulate over the whole thing vs doing the same thing with a vector/array.
- wahern 7y ago> When doing recursion you just need to keep pointer to the level, so this is 32 times pointer or just about 256 bytes of your cache. What language do you use where a recursive function invocation only requires a call frame large enough to hold a single parameter? By what magic does the function know where to return? And what are you doing in that function that doesn't require any temporaries whatsoever? At best you're looking at a couple of kilobytes. For all but the most constrained environments (toaster, a 4Kb kernel thread stack, etc), this isn't really worth worrying about. And compared to the pointer chasing, all those pushes and pops aren't much of a problem, either. However, in a language like C without function closures, non-recursive traversal can keep code much more concise and clear. This is the real win, IMO.
- rrobukef 7y agoYou could simulate the recursion with an iteration, a depth byte and a stack-array of 32 pointers (64 for overkill). This removes the frame pointer and makes the temporaries clear too.
- wahern 7y agoBut that's not recursion, which pretty much by definition implies the use of repeated invocations of the same function(s). Explicitly building a stack is exactly what the article was discussing, though it's far more clever than the obvious approach. I've seen AVL implementations that use an explicit array for maintaining a stack in lieu of recursion or parent pointers. In any event, you always need a stack of some sort. Recursion is one way to accomplish that, but saying that you're simulating recursion by explicitly building a stack reverses the categories.
- jnordwick 7y agoCongratulations you've just recreated CS Intro Data Structures 61 tree iterators? Constant space is the normal way with a parent pointer.
- kazinator 7y ago> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. Effectively, this turns the tree into a (sort of) state machine. How can it be a state machine if you aren't mutating it? In fact, you can traverse a tree without recursion (or any equivalent stack-like structure) and without parent pointers. And then you actually use the tree as a state machine: you stash the reverse path pointer in the tree itself by overwriting the downward links temporarily and then putting them back. This is useful for garbage collection; you can have a garbage collector that is guaranteed never to blow the stack in the marking phase.
- normalhuman 7y ago> How can it be a state machine if you aren't mutating it? You are confusing a state machine (which is an abstract model of computation) with the behavior of a program implementing it. The set of possible states and the conditions of transition from one state to the next never change. These conditions can depend on mutable state, as is the case described by the author (in this case, mutable state is kept in the current and previous node pointers).
- vnorilo 7y agoIf you require the highest performance and your trees are write once, read often (and immutable), it's worth looking into if you should just sort the nodes in traversal order in one contiguous block of memory. Storing the edges as indices into the block is handy in this case. The article used parent pointers in node to avoid using a stack (native or custom made). One downside of a parent pointer is that your identical subtrees can no longer share structure.
- lmilcin 7y agoI agree. I would also point out that this doesn't have much advantage (if it has any) over simple recursion, performance wise. First, the depth (the amount of storage for traversal) typically is on the order of log2(n) and so this gets amortized very quickly when traversing nodes. What if the tree is unbalanced? If the tree is unbalanced you will have all sorts of other problems like problems with inserting or searching. Since trees are typically used for efficient searching and traversal is done more efficiently with just plain array (or list) it is really hard to find any real-world trees that are not kept balanced somehow.
- Axsuul 7y agoCould you expand more on what you mean by "Storing the edges as indices into the block is handy in this case."? This is super relevant to me right now, thanks!
- nosianu 7y agoYou add integer slots to each node and store the index of the child nodes in them. So you have, for a binary tree, [actualTreeNodeData1,child1Idx,child2Idx][actualTreeNodeData2,child1Idx,child2Idx][...] instead of just [actualTreeNodeData1][actualTreeNodeData2][...] Vary this to include whatever you actually need, could also be links to parents instead of or in addition to links to child nodes.
- rocqua 7y agoThat feels like it'll start hurting when you don't know the (maximum) degree of your nodes. As you won't have fixed-size object anymore.
- malisper 7y agoI've always found these kinds of tricks fascinating. There's all sorts of crazy things you can do to save some bytes here and there. One of my personal favorites is the XOR linked list[0]. It's a doubly linked list that uses as much memory as a singly linked list. It works by XORing the previous pointer with the next pointer. As you're doing a traversal you can compute the next pointer by making use of next = prev XOR (prev XOR next) giving you the address of the next node in the list. Anyways, I did some digging into TAOCP. In section 2.3.1 Knuth mentions threaded binary trees[1]. They are trees that you can traverse without a stack and do not use more memory than a regular binary tree. This is compared to the method used in the post which requires you to store the parent pointers. The trick is that in a binary tree, lots of pointers are going to be null. Instead of storing null there, you can store a special value that provides information on how to traverse the tree. Indicating the difference between a regular pointer and one of these special values requires only a single bit. You can often store that bit within the pointer itself, requiring no additional space over a regular binary tree. For a threaded binary tree, if the left child is null, you instead store the predecessor node. If the right child is null, you store the successor node. Finding the successor now becomes: 1) Check if the right child is null. If so the right child pointer points to the successor. We are done. 2) Follow the right child pointer. Then keep following the left child pointer until the left child is null. This gives us the smallest value greater than the current value. One small advantage of threaded binary trees is you traverse the tree slightly less. If the right child is null, instead of traversing back up the tree as in the post, you can jump straight to the successor node. [0] https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list [1] https://en.wikipedia.org/wiki/Threaded_binary_tree https://en.wikipedia.org/wiki/Threaded_binary_tree
- eps 7y ago> You can often store that bit within the pointer itself Yep, the lower 1-3 bits in many pointers will always be zero due to how C run-time allocators and structure alignment works out of the box.
- PeCaN 7y agoupper 16 bits are usually unused on x86_64 as well (since the x86_64 virtual address space is only 48-bit), though whether they're one or zero depends on bit 48
- nudpiedo 7y agoI thought everyone learns that in the university.
- inimino 7y agoNot everyone went to university.
- nudpiedo 7y agoJust an observation, for some reason people take as elitism the observation of having a complete well rounded curriculum has certain advantages. And this article has a good point to illustrate that there is value in taking an engineer rather than a boot camp code fighter. Data structures are a very specific subject of IT Engineering, every person studying subject should take the whole curriculum, including recursivity scanning data structures and how to transform these recursive procedures into iterative code (or FSM as the article says).
- inimino 7y agoI'd take an English major who is self-taught in computer science over a CS grad any day. And I'd take a bootcamp kid who went on to study the theory themselves over a Stanford kid who only knows this shit because he was tested on it. I'm honestly, at this point, not sure why we even teach software engineering in schools, as we so manifestly fail at imparting anything to the kids, and the ones that come out as decent engineers would have been so anyway. Oh right, it's signalling.
- stuxnet79 7y agoThe book "Elephant In The Brain" devotes an entire chapter to how the education system is effectively one large, expensive signaling mechanism. It was an interesting read that I'd recommend checking out. For the record I completely agree with you and I'm saying this as someone with a STEM degree. The "signaling" aspects of our education system completely break down in tech. I would personally need a lot more info than whether someone is an MIT or Stanford grad to want to work with them.
- huhtenberg 7y agoAsking to write a tree iterator was our "FizzBuzz" question when interviewing people for the kernel dev position. Worked exceptionally well.
- andreaorru 7y agoAre you still hiring?
- huhtenberg 7y agoNo. It was over 10 years ago, sorry.
- inimino 7y agoI missed the introductory part where you mentioned that these are binary trees only and not just trees. I think you should mention it more prominently.
- kragen 7y agoThere's an isomorphism between binary trees and general ordered trees, man. That's how we can have Lisp.
- inimino 7y agoYes, sure, there's an isomorphism. Using that fact, is it then so trivial to show how this FSM approach works out if you don't have a binary tree to start with? I think it would make an interesting follow-up blog post. But failing that, it would have been nice to call out at the top that these are binary trees.
- kragen 7y agoIt definitely doesn't work if you don't change your in-memory data representation, and it requires you to change it in a way that forecloses the possibility of FP-persistent tree structures or efficient DAGs. Compared to that, representing your ordered-tree nodes as cons chains is a barely-significant change. It does generalize, though, to ordered-tree nodes that aren't represented as cons chains. You just have to walk through the n child pointers when you're moving back up the tree to search for the one you're returning from, adding an extra runtime cost factor proportional to n but no extra memory. Moreover, if you devote three or four registers to an amnesic stack, you can avoid that cost for the bottom two or three levels of the tree, which will necessarily contain the vast majority of tree nodes.
- roddux 7y agoA complete aside: the site design on linked page is beautiful. Very minimalist and totally functional.
- ajuc 7y agoI don't know, maybe I get a different color scheme than everybody else? It's light gray on white for me and the text is almost invisible. https://i.imgur.com/YM3dIcG.png https://i.imgur.com/YM3dIcG.png Surely that's not considered a great design? EDIT: ok, was fault of a chrome extension "NightModePro" :)
- Hitton 7y agoHonestly I'm quite surprised that although this uses both Perl and goto it gets upvoted. Sometimes I'm pleasantly surprised by HN community.
- lioeters 7y agoThe goto's did get my nerves bristling a bit on first sight - but it's the right tool for the job (or at least gets the job done), so I was OK with it. I guess other languages may have better/cleaner ways to achieve it. I love the discussion that it sparked here too. It's wonderful and educational to see so many smart people breaking down the problem space, discussing de/merits of this particular technique, presenting alternative approaches with analysis on memory use, performance..
- alkonaut 7y agoIt 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.
- amelius 7y agoAlso you can use structural sharing if there are no parent pointers.
- HelloNurse 7y agoObviously, 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.
- enz 7y ago> then, when discussing how to turn recursive functions into iterators using an explicit stack (which permits breadth-first searching); How about a depth-first search?
- derriz 7y ago> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. You can actually in-order traverse a binary tree without any memory overhead at all (no parent pointer nor an implicit or explicit stack) using Joe Morris' traversal. I found that this can be done to be surprising but effectively it uses the NULL slots as temporary storage. Here's one explanation: https://yuyuan.org/MorrisAlgorithm/ https://yuyuan.org/MorrisAlgorithm/ - although there seem to be a few youtube videos on it also.
- DoctorOetker 7y agoBrilliant, I need something like this for one of my projects (attempt to decrypt Beale cipher)!
- ttctciyf 7y agoReminds me of Sean Parent's recounting[1] of how his son's beads and string toy could represent a tree data structure with stateless traversal and some other interesting properties, like: > ...to erase elements from some point in my model to some other point in my model, what I do is grab those two locations on the string, and I pick the whole thing up, and the beads that fall off are the ones that get erased ... (48:41) 1: https://youtu.be/sWgDk-o-6ZE?t=2721 https://youtu.be/sWgDk-o-6ZE?t=2721
- kofejnik 7y agoright, traverse a maze by always turning left
- FeepingCreature 7y agoNote that if your language has non-precise garbage collection, having parent pointers guarantees that any spurious pointer into any node on the tree will keep the entire tree alive.
- dragontamer 7y ago> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. Effectively, this turns the tree into a (sort of) state machine. While traversing, you need no memory other than the current and previous node/state. The traversal algorithm is very simple: While this sounds innocent, truly consider the ramifications of this decision. Your node has now grown to be +8 bytes (the size of a 64-bit pointer). If you have 1-million nodes in your binary tree, you are using +8MB of memory. ------- Lets consider the alternative: lets say you have 1-million nodes, and you have a red-black tree (imperfect balance: instead of a perfectly balanced 20-depth tree you have some branches which are 40-depth). Traversing to 40-depth requires 40x pointers on the stack, or 320 bytes. ---------- In effect, you're spending 8-bytes per node (which could be millions, or even billions of nodes), to save log2(depth) space off of your stack frame. While the state-machine is very "clean", it seems like a very bad tradeoff from an algorithmic / memory space point of view. I'd rather spend log2(depth) space on the stack, rather than O(+8 bytes * number nodes) in the heap. I think there's something to be said about the clarity and cleanliness of the state-machine design. Its quite possible that some algorithms are easier to write with this "parent pointer in node" methodology. However, anyone seeking the highest performance per unit-memory will have to see that the +8 bytes per node is a terrible, terrible tradeoff. ------------- > Update: Todd Lehman pointed out that given node-level locks, this algorithm allows concurrent traversal and update of the tree. Any atomic operation other than detaching a non-leaf node is safe. Hmm... the parallel-angle I haven't thought about. But it does seem to be a potential building block as maybe even a lock-free data-structure. Or just use locks, since locks are easier to think about. Insertion and deletion into the tree seems possible, but "rebalance" is very difficult for me to think about (since it possibly requires modifying many, many nodes). Locking all nodes involved would be a heavy approach and probably work. Red-black colors are kept track of for self-balancing purposes. Maybe more colors are needed to make the methodology "clean" for multi-threaded / lock free purposes.