Mystery : why would std BTreeMap be slower inserting in ascending order than reverse?

help
1

I am starting to compare the performance of my BTreeMap implementation with the std implementation, and I have this puzzle.

C:\Users\ano31\Rust\btree>cargo test std_insert_fwd --release
     Locking 1 package
    Updating btree_experiment v0.1.64 (C:\Users\ano31\Rust\btree) -> v0.1.65
   Compiling btree_experiment v0.1.65 (C:\Users\ano31\Rust\btree)
    Finished `release` profile [optimized] target(s) in 8.45s
     Running unittests src\lib.rs (target\release\deps\btree_experiment-64d4677be5c2d34a.exe)

running 1 test
test test_std_insert_fwd ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 50 filtered out; finished in 1.18s


C:\Users\ano31\Rust\btree>cargo test std_insert_rev --release
    Finished `release` profile [optimized] target(s) in 0.02s
     Running unittests src\lib.rs (target\release\deps\btree_experiment-64d4677be5c2d34a.exe)

running 1 test
test test_std_insert_rev ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 50 filtered out; finished in 0.88s

So inserting in ascending order took 1.18s, but descending order only took 0.88 ( these results are quite consistent ).

These are the tests:

#[test]
fn test_std_insert_fwd() {
    for _rep in 0..1000 {
        let mut t = std::collections::BTreeMap::<usize, usize>::default();
        let n = 10000;
        for i in 0..n {
            t.insert(i, i);
        }
    }
}

and

#[test]
fn test_std_insert_rev() {
    for _rep in 0..1000 {
        let mut t = std::collections::BTreeMap::<usize, usize>::default();
        let n = 10000;
        for i in (0..n).rev() {
            t.insert(i, i);
        }
    }
}

Now I would expect inserting in ascending order to be (slightly) faster, as when inserting into the underlying Vec, there is no need to move the existing elements up, and in my implementation this is indeed the case. So why is std slower?

[ Another thing I just realised (if I am not mistaken), the std implementation stores raw pointers to parent nodes, which is interesting. It means a lot of unsafe code. It is quite a lot of modules, and I only just started looking at the code, here:

]

2

Flamegraphs[1][2] suggest the difference is in the implementation of NodeRef::find_key_index() but I'm not sure why.

1 Like
3

I have a feeling this helps when re-balancing larger trees or using the Entry API. If you have a parent pointer, it means you can rebalance starting from whatever was modified, rather than needing to start at the root of the tree and traversing nodes again.

Less pointer chasing probably means better performance.

1 Like
4

The function does a linear search starting with the smallest element. If you insert in reverse order the first is always a hit so you get fewer comparisons and probably more important a very good branch prediction.

7 Likes
5

Ah, I guess that might be because it searches for where to insert starting at position zero.

When inserting in descending order, the insertion position will always be zero, so the search is quick. That might explain it.

The function named

ascending::btree_insert_ascending::{{closure}}

looks a bit mysterious. Why would there be a specialised function (or closure) named that? Seems odd to me.

6

The reason I found the parent pointers interesting, even surprising is this:

" Unlike some BSTs, B-Trees absolutely do not store a "parent" pointer. This is because we do a lot of bulk shifting of nodes, and having to update visit all the children to update their parent pointers would completely trash the whole "cache-friendly" thing."

from Rust Collections Case Study: BTreeMap

1 Like
7

Yes, I think that's likely it. I am doing a binary search, but I think I read the std implementation does linear search.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.