62 ms·

Interesting. :-) I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think th

by afc 6y ago

Interesting. :-) I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simple implementation. And, if immutable (based on shared memory), allows trivial snapshotting, having multiple "concurrent" trees sharing most of their memory. Anyhow, it's here: https://github.com/alefore/weblog/blob/master/immutable-avl-trees.md https://github.com/alefore/weblog/blob/master/immutable-avl-... I have a small implementation here (which I use, among other things, to hold all lines in a file, in my text editor): https://github.com/alefore/edge/blob/master/src/const_tree.h https://github.com/alefore/edge/blob/master/src/const_tree.h

jiggawatts 6y ago
All node-based trees with a small branching factor of 2-3 have the same performance problems on modern hardware, irrespective of the theoretical big-O algorithmic complexity. They all have poor memory locality, high overheads, and high indirection. This is kryptonite for typical x86 or ARM CPUs. Unless you're only developing for some tiny embedded CPU with no cache, no branch predictor, and low frequency, such algorithms belong in the dustbin of history. Practically always, you get better actual performance when using array-based structures such as hashtables, B-Trees, or the like. Features like snapshotting can be implemented using virtual memory tricks, but is a gimmick rarely used outside of pure functional languages. You might find that simply copying an array when needed for a snapshot is faster than a fancy tree with sharing as a native capability. The exception would be certain dynamic programming scenarios where cloning is very common.
- afc 6y ago
  Thank you for your reply. Interesting points. I guess I'll implement an analogous immutable B-Tree structure and run some benchmarks. I suspect you're probably right. I'll probably experiment with different branching factors and tree sizes. I rely a lot on the trivial (i.e., zero cost) snapshotting for feeding work to background threads. For my workload, having to do deep copies constantly would be prohibitively expensive (and I'd rather not deal with the complexity of explicit locking). That said, I'm now curious to see whether using immutable B-Trees will yield significantly better performance. I suspect they likely will. Exciting. :-) Thanks again!
- magicalhippo 6y ago
  The traditional ZFS implementation(s) use AVL trees as the in-memory data structure for allocating space (ie finding free disk space). However the performance limitations of them have started to show, so there's been work done to switch to B-trees[1]. [1]: https://www.youtube.com/watch?v=LZpaTGNvalE https://www.youtube.com/watch?v=LZpaTGNvalE
kccqzy 6y ago
I don't know about you, but when I started learning data structures, my professor told me AVL trees lost the popularity battle with red-black trees, and people tended to use red-black trees more. He didn't mention AVL trees besides a footnote. Nowadays even red-black trees aren't favored due to practical concerns like caches, so I assume AVL trees are very niche.
- why-el 6y ago
  > Nowadays even red-black trees aren't favored due to practical concerns like caches Not sure if that's true. In addition to the main linux trunk using them, Java 8 included them also as an improvement to their HashMap (I found this by googling), so I don't they are not favored anymore. Edit: language.
  - revertts 6y ago
    There are cases where you need them, but it's relatively rare, they definitely shouldn't be your first choice. I'm fuzzy on all the current Linux use cases, but do remember one of the main users of rb trees was CFS. It's a neat scheduling algorithm. Java 8 specifically: HashMap is implemented with linked list chaining. This is already not very performant, but you can only do so much with Java being a reference heavy language. RB trees are used if the bucket chain grows excessively long - so it's addressing an edge case, speeding up some worst case scenarios. Dense hash tables based on open addressing outperform bucketed chaining. Look also at abseil's swiss table or folly's f14 if you want to see how they've further advanced to take advantage of the hardware. In general: flat, dense, linear structures are king for performance.
    - why-el 6y ago
      I was not commenting on whether one should use it or not, just that it is still used and picked as recently as Java 8. We are in agreement for the rest of your post. :+1:
      - revertts 6y ago
pseudoramble 6y ago
Thanks for sharing! I don’t remember C++ well at all anymore, but it’s cool to see an immutable AVL tree in it since it seems like it would be less common. I wrote one in F# a while back for fun/curiosity since I had no idea how it would be done at the time. Mine was purely key based though. The indexing idea is neat too!

by afc 6y ago

jiggawatts 6y ago

All node-based trees with a small branching factor of 2-3 have the same performance problems on modern hardware, irrespective of the theoretical big-O algorithmic complexity. They all have poor memory locality, high overheads, and high indirection. This is kryptonite for typical x86 or ARM CPUs. Unless you're only developing for some tiny embedded CPU with no cache, no branch predictor, and low frequency, such algorithms belong in the dustbin of history. Practically always, you get better actual performance when using array-based structures such as hashtables, B-Trees, or the like. Features like snapshotting can be implemented using virtual memory tricks, but is a gimmick rarely used outside of pure functional languages. You might find that simply copying an array when needed for a snapshot is faster than a fancy tree with sharing as a native capability. The exception would be certain dynamic programming scenarios where cloning is very common.

afc 6y ago
Thank you for your reply. Interesting points. I guess I'll implement an analogous immutable B-Tree structure and run some benchmarks. I suspect you're probably right. I'll probably experiment with different branching factors and tree sizes. I rely a lot on the trivial (i.e., zero cost) snapshotting for feeding work to background threads. For my workload, having to do deep copies constantly would be prohibitively expensive (and I'd rather not deal with the complexity of explicit locking). That said, I'm now curious to see whether using immutable B-Trees will yield significantly better performance. I suspect they likely will. Exciting. :-) Thanks again!
magicalhippo 6y ago
The traditional ZFS implementation(s) use AVL trees as the in-memory data structure for allocating space (ie finding free disk space). However the performance limitations of them have started to show, so there's been work done to switch to B-trees[1]. [1]: https://www.youtube.com/watch?v=LZpaTGNvalE https://www.youtube.com/watch?v=LZpaTGNvalE

kccqzy 6y ago

I don't know about you, but when I started learning data structures, my professor told me AVL trees lost the popularity battle with red-black trees, and people tended to use red-black trees more. He didn't mention AVL trees besides a footnote. Nowadays even red-black trees aren't favored due to practical concerns like caches, so I assume AVL trees are very niche.

why-el 6y ago
> Nowadays even red-black trees aren't favored due to practical concerns like caches Not sure if that's true. In addition to the main linux trunk using them, Java 8 included them also as an improvement to their HashMap (I found this by googling), so I don't they are not favored anymore. Edit: language.
- revertts 6y ago
  There are cases where you need them, but it's relatively rare, they definitely shouldn't be your first choice. I'm fuzzy on all the current Linux use cases, but do remember one of the main users of rb trees was CFS. It's a neat scheduling algorithm. Java 8 specifically: HashMap is implemented with linked list chaining. This is already not very performant, but you can only do so much with Java being a reference heavy language. RB trees are used if the bucket chain grows excessively long - so it's addressing an edge case, speeding up some worst case scenarios. Dense hash tables based on open addressing outperform bucketed chaining. Look also at abseil's swiss table or folly's f14 if you want to see how they've further advanced to take advantage of the hardware. In general: flat, dense, linear structures are king for performance.
  - why-el 6y ago
    I was not commenting on whether one should use it or not, just that it is still used and picked as recently as Java 8. We are in agreement for the rest of your post. :+1:
    - revertts 6y ago

pseudoramble 6y ago

Thanks for sharing! I don’t remember C++ well at all anymore, but it’s cool to see an immutable AVL tree in it since it seems like it would be less common. I wrote one in F# a while back for fun/curiosity since I had no idea how it would be done at the time. Mine was purely key based though. The indexing idea is neat too!