3 ms·

Trees are a powerful and practical data structure, but even if it does not appear clearly when doing O(n) style complexity analysis, they are usually slow. Unf

Trees are a powerful and practical data structure, but even if it does not appear clearly when doing O(n) style complexity analysis, they are usually slow. Unfortunately, the difference between slow and fast can be several orders of magnitude, while the perception of the programmer doing a back of the envelope analysis seems to be a logarithmic scaling of the reality...

josephg 5y ago
Trees seemed to work pretty well for me here! The problem with trees is usually that people don't pack enough data into each node in the tree. I implemented a skip list in C a few years ago[1]. For a lark I benchmarked its performance against the C++ SGI rope class which was shipped in the C++ header directory somewhere. My skip list was 20x faster - which was suspicious. I looked into what the SGI rope does and it turns out it was only putting one character into each leaf node in the tree it constructed. Benchmarking showed the optimal number was ~120 or so characters per leaf. Memcpy is much much faster in practice than main memory lookups. In diamond-types (benchmarked here), the internal nodes in my B-tree store 16 pointers and leaf nodes store 32 entries. With run-length encoding, all 180,000 inserted characters in this data set end up in a tree with just 88 internal nodes and a depth of 3. It goes fast like this. But if you think an array based solution would work better, I'd love to see it! It would certainly need a lot less code. [1] https://github.com/josephg/librope https://github.com/josephg/librope
- masklinn 5y ago
  Isn't that also the insight which led to HAMT (and friends) being so fast compared to older persistent datastructures? Turns out for a while now copying more but denser memory has been way cheaper than chasing pointers. Brian Cantrill also noticed that in his comparison of his C and Rust versions of statemap[0]: Rust had a way, way better cache behaviour than C (96.9 L1 hit rate to 77.9%, and half the L2 misses although the better L1 behaviour also led to >90% less L2 interactions in the first place), and most of that was attributed to using a btreeset instead of an AVL BST. [0] http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

josephg 5y ago

Trees seemed to work pretty well for me here! The problem with trees is usually that people don't pack enough data into each node in the tree. I implemented a skip list in C a few years ago[1]. For a lark I benchmarked its performance against the C++ SGI rope class which was shipped in the C++ header directory somewhere. My skip list was 20x faster - which was suspicious. I looked into what the SGI rope does and it turns out it was only putting one character into each leaf node in the tree it constructed. Benchmarking showed the optimal number was ~120 or so characters per leaf. Memcpy is much much faster in practice than main memory lookups. In diamond-types (benchmarked here), the internal nodes in my B-tree store 16 pointers and leaf nodes store 32 entries. With run-length encoding, all 180,000 inserted characters in this data set end up in a tree with just 88 internal nodes and a depth of 3. It goes fast like this. But if you think an array based solution would work better, I'd love to see it! It would certainly need a lot less code. [1] https://github.com/josephg/librope https://github.com/josephg/librope

masklinn 5y ago
Isn't that also the insight which led to HAMT (and friends) being so fast compared to older persistent datastructures? Turns out for a while now copying more but denser memory has been way cheaper than chasing pointers. Brian Cantrill also noticed that in his comparison of his C and Rust versions of statemap[0]: Rust had a way, way better cache behaviour than C (96.9 L1 hit rate to 77.9%, and half the L2 misses although the better L1 behaviour also led to >90% less L2 interactions in the first place), and most of that was attributed to using a btreeset instead of an AVL BST. [0] http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...