`B` is far too large

[orlp]

I think the choice of B = 1024 is far, far too large for an in-memory data structure. Such choices only make sense for disk applications.

The result of this is that indexset is ~28x slower than the stdlib BTreeMap for this simple benchmark:

use std::time::Instant;

fn main() {
    let mut bs = std::collections::BTreeSet::new();
    let start = Instant::now();
    for i in (0..100_000_000).rev() {
        bs.insert(i);
    }
    dbg!(start.elapsed());
    std::hint::black_box(bs);
    
    let mut bs = indexset::BTreeSet::new();
    let start = Instant::now();
    for i in (0..100_000_000).rev() {
        bs.insert(i);
    }
    dbg!(start.elapsed());
    std::hint::black_box(bs);
}

The standard library finishes in 2 seconds on my machine, indexset takes 56 seconds.

[brurucy]

Hello @orlp. Thank you so much for checking the library out. slotmap is dope.

I ran this on my machine:

use std::time::Instant;

fn main() {
    let mut bs = std::collections::BTreeSet::new();
    let n = 100_000_000;
    let start = Instant::now();
    for i in (0..n) {
        bs.insert(i);
    }
    dbg!(start.elapsed());
    assert_eq!(bs.len(), n);
    std::hint::black_box(bs);

    use std::time::Instant;

    let mut bs = indexset::BTreeSet::with_maximum_node_size(1024);
    let start = Instant::now();
    for i in (0..n) {
        bs.insert(i);
    }

    dbg!(start.elapsed());
    assert_eq!(bs.len(), n);
    std::hint::black_box(bs);
}

And I got the same result that you did:

[src/main.rs:10:5] start.elapsed() = 5.295904083s
[src/main.rs:22:5] start.elapsed() = 37.491929417s

When I switched to:

let mut bs = indexset::BTreeSet::with_maximum_node_size(8196);

I then got:

[src/main.rs:10:5] start.elapsed() = 5.440404542s
[src/main.rs:22:5] start.elapsed() = 2.681807167s

So, twice as fast as stdlib.

Also, I spotted a small bug with respect to using B's that are different than 1024. My bad. I have just fixed it.

[brurucy]

I have set 1024 as it seems to be optimal for ~ 1 million or so items. The higher you go above that, the higher B has to be (from my experience).

Could you confirm whether you got similar results when running with version 0.12.2 and B=8196?

[orlp]

I'm afraid that hasn't fixed it for me on 0.12.2 and B = 8196, still much slower:

[src/main.rs:9:5] start.elapsed() = 1.97546775s
[src/main.rs:17:5] start.elapsed() = 33.920779958s

In general I don't expect an insert/removal of one item to potentially shift thousands of elements for an in-memory tree data structure.

[orlp]

Also note that your example you posted is missing the .rev() from mine - that's what's highlighting what's so slow, by inserting in reverse order you constantly have to shift elements.

[brurucy]

Ok, I see that when using .rev I get:

[src/main.rs:10:5] start.elapsed() = 1.859180667s
[src/main.rs:22:5] start.elapsed() = 61.314583167s

While without:

[src/main.rs:10:5] start.elapsed() = 5.36481875s
[src/main.rs:22:5] start.elapsed() = 2.667113208s

It is true that when the data that you are inserting has no locality, it will perform much worse than a not-flat BTree.

However, I doubt that in practice anyone is inserting data with no locality 😀 If that's how one's workload looks like e.g strings, then I suppose a HashMap is an infinitely better choice.

It is also quite weird how Rust's stdlib BTree is 2.5x faster when inserting in reverse than otherwise.

===

In short, I see your point, and it is a fair assessment that this specialised B-Tree is not as general as the regular B+ Tree.