News for hackers. Stuff that matters.
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.