[kudu-CR] WIP: interval tree: allow bulk queries

2017-03-24 Thread Todd Lipcon (Code Review) 
Hello David Ribeiro Alves,

I'd like you to do a code review.  Please visit

http://gerrit.cloudera.org:8080/6481

to review the following change.

Change subject: WIP: interval_tree: allow bulk queries
..

WIP: interval_tree: allow bulk queries

This adds an API to interval_tree to allow it to be queried in "bulk".
The caller passes a set of query points and a callback, and the tree
calls the callback once per  pair.

This has much better CPU cache efficiency than a lot of separate
queries. And more importantly, this will allow rowset-wise processing of
batches of writes, which opens up big perf wins in later patches in this
series.

Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
---
M src/kudu/util/interval_tree-inl.h
M src/kudu/util/interval_tree-test.cc
M src/kudu/util/interval_tree.h
3 files changed, 210 insertions(+), 27 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/81/6481/1
-- 
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon 
Gerrit-Reviewer: David Ribeiro Alves

[kudu-CR] WIP: interval tree: allow bulk queries

2017-03-27 Thread Todd Lipcon (Code Review) 
Hello Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

http://gerrit.cloudera.org:8080/6481

to look at the new patch set (#3).

Change subject: WIP: interval_tree: allow bulk queries
..

WIP: interval_tree: allow bulk queries

This adds an API to interval_tree to allow it to be queried in "bulk".
The caller passes a set of query points and a callback, and the tree
calls the callback once per  pair.

This has much better CPU cache efficiency than a lot of separate
queries. Additionally, doing 'Q' queries in bulk against N intervals
returning M results is O(log(Q) * log(N) + M) vs O(Q * log(N) + M)
doing them one-by-one. Performance results follow in the RowSetTree patch.

Perhaps more importantly, this will allow rowset-wise processing of
batches of writes, which opens up big perf wins in later patches in this
series.

Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
---
M src/kudu/util/interval_tree-inl.h
M src/kudu/util/interval_tree-test.cc
M src/kudu/util/interval_tree.h
3 files changed, 216 insertions(+), 27 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/81/6481/3
-- 
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot