Todd Lipcon has submitted this change and it was merged.
Change subject: interval_tree: improve an O(n) loop to O(lg n)
......................................................................
interval_tree: improve an O(n) loop to O(lg n)
In the interval tree implementation, we were scanning forward through a
sorted list to find the first element for which a comparison predicate
returned false. Since we know that the list is sorted, we can use
std::partition_point instead for a logarithmic search instead of linear.
Before:
Performance counter stats for 'build/latest/bin/rowset_tree-test
--gtest_repeat=10 --gtest_filter=*Perf*':
4583.429978 task-clock (msec) # 0.999 CPUs utilized
133 context-switches # 0.029 K/sec
0 cpu-migrations # 0.000 K/sec
693 page-faults # 0.151 K/sec
14,480,814,146 cycles # 3.159 GHz
<not supported> stalled-cycles-frontend
<not supported> stalled-cycles-backend
36,542,995,670 instructions # 2.52 insns per cycle
6,044,686,478 branches # 1318.813 M/sec
63,527,970 branch-misses # 1.05% of all branches
4.585735270 seconds time elapsed
After:
Performance counter stats for 'build/latest/bin/rowset_tree-test
--gtest_repeat=10 --gtest_filter=*Perf*':
4044.192209 task-clock (msec) # 1.000 CPUs utilized
5 context-switches # 0.001 K/sec
0 cpu-migrations # 0.000 K/sec
509 page-faults # 0.126 K/sec
13,329,589,168 cycles # 3.296 GHz
<not supported> stalled-cycles-frontend
<not supported> stalled-cycles-backend
30,484,446,619 instructions # 2.29 insns per cycle
5,094,736,604 branches # 1259.766 M/sec
86,320,621 branch-misses # 1.69% of all branches
4.044156458 seconds time elapsed
Overall speeds up around 10%.
Change-Id: Ib8c9463fb901b7bf75d32b00cb528e96c119101e
Reviewed-on: http://gerrit.cloudera.org:8080/6496
Tested-by: Kudu Jenkins
Reviewed-by: David Ribeiro Alves <[email protected]>
---
M src/kudu/util/interval_tree-inl.h
1 file changed, 33 insertions(+), 31 deletions(-)
Approvals:
David Ribeiro Alves: Looks good to me, approved
Kudu Jenkins: Verified
--
To view, visit http://gerrit.cloudera.org:8080/6496
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: Ib8c9463fb901b7bf75d32b00cb528e96c119101e
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Todd Lipcon <[email protected]>
Gerrit-Reviewer: David Ribeiro Alves <[email protected]>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <[email protected]>
Gerrit-Reviewer: Will Berkeley <[email protected]>
