This looks somewhat similar to Aaron Hsu’s array-based tree structures and algorithms; you may find them interesting.
He uses two arrays in parallel: one contains, for each element, that element’s parent; and the other contains a given element’s left sibling. Terminal elements can use a sentinel value or (more likely) point to themselves. The second can be elided if order is not important.
I believe these techniques had been described before, but were not in very common use; e.g. I don’t think anybody had ever written a compiler using such a structure before.
Thanks for the links! I was aware of this awesome work but did not realize the similarity of the approach - I find Aaron’s approach not very accessible, though I am skimming the relevant chapter of the PhD now.
There are some related interesting array based tree representations in Iverson’s A Programming Language book (section 1.23 on ordered trees, page 45 of pdf book here). Also Stevan Apter’s treetable paper has some interesting uses of these ideas trees-as-arrays [edits for clarity - sorry!].
Also interesting and relevant. Quickly skimming over these and Hsu’s work, it seems that many of them include sorting as a primitive operation, which I’d count as medium performance on GPU. It also seems like many of these use an intermediate representation which is n_elements * max_depth. That’s considerably easier than what I’ve done, which is strictly O(n). It’s entirely possible I’ve rediscovered something that already exists, but so far I haven’t found it, and in particular I’m pretty sure my adaptation to the decoupled look-back framework (for single pass processing) is new. In any case, thanks for these links.
include sorting as a primitive operation, which I’d count as medium performance on GPU
As far as I know, no one before hsu had really focused on performant or compact representations; adjacency matrices, for instance, had been known for a long time as a simple way to represent graphs in apl, and were obviously not performant.
But hsu’s algorithms all use linear space, and don’t really rely on sorting; I count only two sorts in the core co-dfns compiler.
I didn’t mean to imply that your work wasn’t original—it’s certainly new to me, at least—just thought this might be something interesting to look at, and maybe inspire further improvements to your own work :)
Many apologies for my ambiguous comment! I didn’t at all mean to suggest these had your algorithm in; I hope it’s OK I edited my comment for clarity. Thanks for your admirably graceful reply and helpful complexity comparison, and of course for your very interesting blog post :)
This looks somewhat similar to Aaron Hsu’s array-based tree structures and algorithms; you may find them interesting.
He uses two arrays in parallel: one contains, for each element, that element’s parent; and the other contains a given element’s left sibling. Terminal elements can use a sentinel value or (more likely) point to themselves. The second can be elided if order is not important.
I believe these techniques had been described before, but were not in very common use; e.g. I don’t think anybody had ever written a compiler using such a structure before.
That’s what I thought when reading the post! Two Aaron’s papers touching this:
Thanks for the links! I was aware of this awesome work but did not realize the similarity of the approach - I find Aaron’s approach not very accessible, though I am skimming the relevant chapter of the PhD now.
There are some
relatedinteresting array based tree representations in Iverson’s A Programming Language book (section 1.23 on ordered trees, page 45 of pdf book here). Also Stevan Apter’s treetable paper has some interesting uses ofthese ideastrees-as-arrays [edits for clarity - sorry!].Also interesting and relevant. Quickly skimming over these and Hsu’s work, it seems that many of them include sorting as a primitive operation, which I’d count as medium performance on GPU. It also seems like many of these use an intermediate representation which is n_elements * max_depth. That’s considerably easier than what I’ve done, which is strictly O(n). It’s entirely possible I’ve rediscovered something that already exists, but so far I haven’t found it, and in particular I’m pretty sure my adaptation to the decoupled look-back framework (for single pass processing) is new. In any case, thanks for these links.
As far as I know, no one before hsu had really focused on performant or compact representations; adjacency matrices, for instance, had been known for a long time as a simple way to represent graphs in apl, and were obviously not performant.
But hsu’s algorithms all use linear space, and don’t really rely on sorting; I count only two sorts in the core co-dfns compiler.
I didn’t mean to imply that your work wasn’t original—it’s certainly new to me, at least—just thought this might be something interesting to look at, and maybe inspire further improvements to your own work :)
Many apologies for my ambiguous comment! I didn’t at all mean to suggest these had your algorithm in; I hope it’s OK I edited my comment for clarity. Thanks for your admirably graceful reply and helpful complexity comparison, and of course for your very interesting blog post :)
All good. I’ve updated the blog post with a bit of clarification and adding these links, which I’m hopeful puts everything in a good context.