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.
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/...
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.