News for hackers. Stuff that matters.
Re:Tree traversal without recursion: the tree as a state mac... by Axsuul on Tuesday September 03, 2019 @01:58AM (#20864023)
Could 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!

Re:Tree traversal without recursion: the tree as a state mac... by vnorilo on Tuesday September 03, 2019 @02:08AM (#20864055)
Suppose your `Tree` is an array of `Nodes` sorted in whatever traversal order is expected to be good. Edges are fully defined as pairs of indices (Node[A] -> Node[B] means you need to know just A and B): Nodes can contain their own upstream indices.

If you need per-traversal state per node (such as visited status or intermediate dataflow), it's very handy to allocate another flat array for that and use the node indices.

I've looked into this in a compiler setting, transforming ASTs and intermediate representations.

Re:Tree traversal without recursion: the tree as a state mac... by usrusr on Tuesday September 03, 2019 @05:19AM (#20864874)
I was confused by that as well before reading the answers: the confusion stemmed from only thinking about the linear traversal or search use cases, where an ordered array plus binary search is all you'd ever need for reading. But when the tree shape itself is still needed, indices can be better than pointers, particularly when adding sidecar arrays for extension or as temporary scribble space (see sibling comment).
Re:Tree traversal without recursion: the tree as a state mac... by nosianu on Tuesday September 03, 2019 @02:04AM (#20864042)
You 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.
Re:Tree traversal without recursion: the tree as a state mac... by rocqua on Tuesday September 03, 2019 @03:49AM (#20864437)
That 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.
Re:Tree traversal without recursion: the tree as a state mac... by silasdavis on Tuesday September 03, 2019 @05:45AM (#20865011)
Hurting because of memory alignment or something else?

Given we have indices along the serialisation for child nodes I would have thought not having nodes start at the consistent intervals doesn't hurt us for traversal at least.

I'd quite like to use this idea for a file backed immutable tree. The array of children would have variable size with bit field to index then nth child in the sparse array.

Re:Tree traversal without recursion: the tree as a state mac... by rocqua on Tuesday September 03, 2019 @05:33PM (#20871413)
Constant time array indexing depends on a fixed array member size. So, the actual memory layout of storing the nodes with non-fixed size could not use an array of nodes.

I suppose you could (should) write your own allocator to ensure nodes are allocated in a contiguous piece of memory, and have a separate array of indexes / pointers that tells you where the n-th node starts. That is another array that'll have to be kept in cache though.

Re:Tree traversal without recursion: the tree as a state mac... by vnorilo on Tuesday September 03, 2019 @04:13AM (#20864561)
Typically you'd have a handful in-object and a heap allocated tail if needed. A bit like small string optimization.