google / btree

BTree provides a simple, ordered, in-memory data structure for Go programs.
Apache License 2.0
3.97k stars 420 forks source link

Try to call Less() fewer times when iterating #49

Open a180285 opened 1 year ago

a180285 commented 1 year ago

Base on issue #42

Cached stop index when iterating. And following is some benchmark compare result on my PC.

Benchmarck

  goos: windows
  pkg: github.com/google/btree
  cpu: Intel(R) Core(TM) i5-6600 CPU @ 3.30GHz

- without cache
+ after cache stopIndex

  goarch: amd64 go1.18
- BenchmarkAscendRangeG-4            14937             74071 ns/op
+ BenchmarkAscendRangeG-4            22119             55385 ns/op

- BenchmarkDescendRangeG-4           12909             92070 ns/op
+ BenchmarkDescendRangeG-4           15200             78136 ns/op

- BenchmarkAscendRange-4              9895            122200 ns/op
+ BenchmarkAscendRange-4             14628             81924 ns/op

  goarch: amd64 go1.17
- BenchmarkAscendRange-4             12496             94311 ns/op
+ BenchmarkAscendRange-4             17521             68965 ns/op
google-cla[bot] commented 1 year ago

Thanks for your pull request! It looks like this may be your first contribution to a Google open source project. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

View this failed invocation of the CLA check for more information.

For the most up to date status, view the checks section at the bottom of the pull request.

a180285 commented 1 year ago

CLA check has passed: https://github.com/google/btree/pull/49/checks?check_run_id=10372524044

a180285 commented 1 year ago

Hi @gconnell , could you help reviewing this merge request?

a180285 commented 1 year ago

@gconnell @gauntface can you help review this? thank you.