Always surprising to click through a link on HN and discover it is one's own work. For a time I was very interested in lightweight array-based implementations of common data structures and this one seemed particularly handy.
I am interested because I have some scientific software (astrodynamics - propagating orbits in space) that would really benefit from a cache-friendly tree, and this seemed promising.
Also, I write a lot of code that runs on a gpu, and the claim that this tree is somehow gpu friendly I find particularly dubious.
Big O isn't irrelevant, but it is not the full story either. There's a solid reason why hash tables are a thing in memory but aren't really a thing on disk.
The parent commenter writes a wonderful blog that covers their experience with building and optimizing a search engine, well worth a read.
When N is small, the asymptotic behavior is irrelevant and that's easy to show. Let's say we're comparing a O(N) algorithm to a O(N^2) algorithm, but each operation of the O(N) is 1000x more expensive. The O(N^2) algorithm is preferred as long as N < 1000. Choosing the O(N) algorithm will hurt performance in those situations. Real world examples like single-byte-writes causing full pages to be re-written on SSDs shows this isn't just a mathematical curiosity.
Without benchmarks, analysis of big-O behaviors, usage patterns, and known data size I'd (personally) avoid guessing the performance of Atree in an application.
Are you saying something different? It sounds like you have much more SIMD experience than I do and I'm always happy to learn something new.
How? Non-asymptotic N stays non-asymptotic no matter how you label it.
Big O tells you that there exists some number N such that for each number m larger than N, if O(f(m)) > O(g(m)) then f(m) > g(m). In practice, N may be 10, or it may be larger than the number of atoms in the universe. It's unrelated to the number of items in your collection, but a property of the algorithm itself.
The trick is that querying the children of N different nodes is usually still a single O(N) scan, so if you operate on it array-style (which APL heavily encourages anyway), it's amortized constant time. Of course that's not always viable, but APL programmers tend to be surprisingly good at making array operations out of things you wouldn't expect to use arrays for.
> cache hostile
If you additionally enforce that all parent indexes point to lower numbers, a preorder traversal is a linear scan forward, and a postorder traversal with child order reversed (which you can usually correct for one way or another) is a linear scan backward.
(This assumes you only need dependency ordering, ie the parent node uses or supplies data to/from its children; if you need a true sequential traversal, the array has to be sorted according to that traversal (but is still a valid Apter Tree).)
> the claim that this tree is somehow gpu friendly I find particularly dubious
Yeah, array programming is generally kind of hit-or-miss at that and this does look like a miss.
I mean, there are specific sizes that will fit in the L-(N) cache.
And consequently, sizes that don't suffer from the false-sharing problem in concurrent scenarios due to this.
https://en.cppreference.com/w/cpp/thread/hardware_destructiv...
There's an entire field of study devoted to cache-friendly/cache-oblivious data structures:
- https://www.microsoft.com/en-us/research/wp-content/uploads/...
But personally I’ve been working at higher levels of the stack the last few years, where these kinds of decisions seem less important.
And on another level, it seems like coders in general aren’t that interested in vector oriented languages and techniques which makes their study somewhat isolating.
I used a very similar setup, first time I needed to implement a tree. Now, I'm a fan of Eytzinger layout. (referenced in a previous comment in this thread)
Yeah, most coders in general don't seem to be as interested in this stuff, but it's still necessary. They'll want more performance.
I don't think programmers actually care about performance as much as they care for convenience. Every year the stack moves a bit higher, and everyone is okay with websites taking days to load on brand new phones with Gigabit wireless connections. There are companies that care about performance on the margin, like stock trading firms, but to get into one of them, you have to get pretty lucky, or come from a pretty special background. Even the banks are using Python more and more, these days.
People will always care about performance because they will always want more functionality.
I bet you care about the performance of your database or how fast your pages load. You want your streaming videos to be skip-free and your phone calls to sound lifelike. Performance will always matter. Because while people like me will be always trying to squeeze more, "the other side" will always be ready to use it for some new feature.
I'm not under the impression that people care at all, to be honest, outside of certain communities. If you're not in those communities talking about performance as a corner stone feels mostly like screaming into the void.
but then accumulated outcome of this is the slowness you see in web software!
I'm _also_ interested in scientific software, but that's more a hobby than a job. =)
For propagating a large number of orbits in space, I'm really curious what the Correct (tm) numerical algorithm is, mind sharing more? I love that space right at the intersection of lots of math + need to understand how computers really work. Once upon a time I implemented fast multipole method for the n-body problem, but I certainly don't claim to deeply understand it, anymore. :)
It does help (roughly ~5x vs. pointer-chasing trees, probably can be further optimized) for my workload, but at the same time quite some time was spent just making sure the tree is correct.