search

wvwwvwwv / scalable-concurrent-containers

High performance containers and utilities for concurrent and asynchronous programming
Apache License 2.0
329 stars 16 forks source link

feat(tree_index, #157): implement TreeIndex::peek_entry #160

Closed qthree closed 3 weeks ago

qthree commented 3 weeks ago

Naive implementation of #157 Tests are passing, but idk about performance impact and lifetime rules in LeafNode::search and InternalNode::search - is it even allowed to pass key reference to outside?

wvwwvwwv commented 3 weeks ago

The compiler is very good at dead code elimination, so there should be no problem in terms of performance (all are inlined). Just briefly looked into it, this seems OK, but I’ll do a thorough code review on the weekend.

wvwwvwwv commented 3 weeks ago

@qthree can you possibly run cargo bench with/without the change? + mark this PR as ready when you think it's ready.

qthree commented 3 weeks ago

main:

TreeIndex: peek         time:   [55.716 ns 56.343 ns 56.837 ns]
                        change: [-3.6546% -0.7751% +2.3509%] (p = 0.62 > 0.05)
                        No change in performance detected.

tree-peek-with:

TreeIndex: peek         time:   [61.050 ns 61.810 ns 62.458 ns]
                        change: [+6.8138% +10.045% +13.459%] (p = 0.00 < 0.05)
                        Performance has regressed.
wvwwvwwv commented 3 weeks ago

I tested similar code in godbolt, but the compiler was able to eliminate the additional key field if inlined. I guess the code is relatively big, so the whole call stack cannot fit into a single compilation unit. I think, you can copy-and-paste the search methods only for peek_entry (search_entry); though most code will be duplicated… performance vs code quality -> performance in this case.