You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@kudu.apache.org by "Todd Lipcon (Code Review)" <ge...@cloudera.org> on 2017/03/25 01:10:01 UTC
[kudu-CR] WIP: interval tree: allow bulk queries
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 <interval, point> 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 <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 5:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-test.cc
File src/kudu/util/interval_tree-test.cc:
PS4, Line 239: TEST_F(TestIntervalTree, TestBigO) {
> I was referring to that if we want to get benchmark numbers from this we us
oh, check out what I did in the rowset_tree test in the next patch, hopefully that covers it. The actual CPU consumption of the RowSetTree lookup isn't a huge consumer in the benchmarks I ran - most of the perf stuff in this patch is to ensure we don't regress. The CPU improvement is icing on the cake.
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree.h
File src/kudu/util/interval_tree.h:
PS4, Line 132: const QueryContainer& queries,
: const Callback& cb)
> still haven't addressed my naming concern. how about "queries_begin" and qu
you mean on ITNode? here in the public API I've changed it to just take the container.
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 5: Verified+1
Known flake (sorry, still need to review your fix for that one!)
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: No
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has submitted this change and it was merged.
Change subject: interval_tree: allow bulk queries
......................................................................
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 <interval, point> pair.
This has much better CPU cache efficiency than a lot of separate
queries. Additionally, doing 'Q' queries in bulk is logarithmic in Q
rather than linear.
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
Reviewed-on: http://gerrit.cloudera.org:8080/6481
Tested-by: Todd Lipcon <to...@apache.org>
Reviewed-by: David Ribeiro Alves <dr...@apache.org>
---
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, 347 insertions(+), 28 deletions(-)
Approvals:
David Ribeiro Alves: Looks good to me, approved
Todd Lipcon: Verified
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 6
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 4:
(6 comments)
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-inl.h
File src/kudu/util/interval_tree-inl.h:
PS4, Line 248: into
> into those
Done
PS4, Line 275: rem_queries
> explain what this is.
Done
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-test.cc
File src/kudu/util/interval_tree-test.cc:
Line 100: return -compare(b, a);
> warning: parameter 'b' is passed by value and only copied once; consider mo
changed to const refs
PS4, Line 239: TEST_F(TestIntervalTree, TestBigO) {
> can you make this parameterized and do (small ints, big qs) (big ints, big
hmm, not quite following what you mean. The for loops on line 247 and 250 don't cover this?
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree.h
File src/kudu/util/interval_tree.h:
PS4, Line 122: 1
> 3
Done
PS4, Line 132: ItType begin_queries,
: ItType end_queries,
> so the point is to not make this dependent on vector or something? feel lik
changed it to be a templated 'Container' type. You're right it's a typically but I think just saying it has to be an "STL Container" is clear enough.
The ITNode<>::ForEachIntervalContainingPoints() still takes a pair of iterators serving as an STL range because the range changes as we recurse down the tree
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
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 (#5).
Change subject: interval_tree: allow bulk queries
......................................................................
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 <interval, point> pair.
This has much better CPU cache efficiency than a lot of separate
queries. Additionally, doing 'Q' queries in bulk is logarithmic in Q
rather than linear.
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, 347 insertions(+), 28 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/81/6481/5
--
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: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] interval tree: allow bulk queries
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 4:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree.h
File src/kudu/util/interval_tree.h:
PS4, Line 132: ItType begin_queries,
: ItType end_queries,
> you mean on ITNode? here in the public API I've changed it to just take the
nah, my bad was commenting on an earlier rev
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes
[kudu-CR] interval tree: allow bulk queries
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 4:
(5 comments)
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-inl.h
File src/kudu/util/interval_tree-inl.h:
PS4, Line 248: into
into those
PS4, Line 275: rem_queries
explain what this is.
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-test.cc
File src/kudu/util/interval_tree-test.cc:
PS4, Line 239: TEST_F(TestIntervalTree, TestBigO) {
can you make this parameterized and do (small ints, big qs) (big ints, big qs) and (big ints small qs?) I'd be nice to see those results in the commit message
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree.h
File src/kudu/util/interval_tree.h:
PS4, Line 122: 1
3
PS4, Line 132: ItType begin_queries,
: ItType end_queries,
so the point is to not make this dependent on vector or something? feel like this is obfuscating the purpose and making it hard to read. might be worth considering simplifying.
Also "begin_queries" makes it read like its a "set of begins", which can't be derived from context because of templating. I had to go look in the test to be sure what this is taking.
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-HasComments: Yes
[kudu-CR] interval tree: allow bulk queries
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 5: Code-Review+2
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: No
[kudu-CR] WIP: interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
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 <interval, point> 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 <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] interval tree: allow bulk queries
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
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 (#4).
Change subject: interval_tree: allow bulk queries
......................................................................
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 <interval, point> pair.
This has much better CPU cache efficiency than a lot of separate
queries. Additionally, doing 'Q' queries in bulk is logarithmic in Q
rather than linear.
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, 341 insertions(+), 28 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/81/6481/4
--
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: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
[kudu-CR] interval tree: allow bulk queries
Posted by "David Ribeiro Alves (Code Review)" <ge...@cloudera.org>.
David Ribeiro Alves has posted comments on this change.
Change subject: interval_tree: allow bulk queries
......................................................................
Patch Set 5:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree-test.cc
File src/kudu/util/interval_tree-test.cc:
PS4, Line 239: TEST_F(TestIntervalTree, TestBigO) {
> hmm, not quite following what you mean. The for loops on line 247 and 250 d
I was referring to that if we want to get benchmark numbers from this we usually measure run times so using those params would allow us to start benching this (instead of having a single run that does everything). If you don't think it's worth it that's ok
http://gerrit.cloudera.org:8080/#/c/6481/4/src/kudu/util/interval_tree.h
File src/kudu/util/interval_tree.h:
PS4, Line 132: const QueryContainer& queries,
: const Callback& cb)
> changed it to be a templated 'Container' type. You're right it's a typicall
still haven't addressed my naming concern. how about "queries_begin" and queries_end"
--
To view, visit http://gerrit.cloudera.org:8080/6481
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: comment
Gerrit-Change-Id: Ifb4da25ca43413fbcae631a7b0f3f16062e4e408
Gerrit-PatchSet: 5
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: David Ribeiro Alves <dr...@apache.org>
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-HasComments: Yes