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 2020/03/23 22:37:00 UTC
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Hello Adar Dembo,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/15539
to review the following change.
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
bitmap: faster implementation of iteration over a bitmap
This new implementation iterates 64 bits at a time instead of 8,
and uses a templated callback function instead of using an "iterator"
approach. In an upcoming patch, I found this method to be measurably
faster than the previous TrueBitIterator code.
I compared the included benchmark using the old TrueBitIterator vs the
new implementation:
Old:
1,263.17 msec task-clock # 0.998 CPUs utilized
254 context-switches # 0.201 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.001 M/sec
3,561,984,981 cycles # 2.820 GHz
5,878,012,694 instructions # 1.65 insn per cycle
1,301,336,934 branches # 1030.218 M/sec
22,275,166 branch-misses # 1.71% of all branches
1.265635106 seconds time elapsed
1.255785000 seconds user
0.007992000 seconds sys
new:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
595.63 msec task-clock # 0.996 CPUs utilized
254 context-switches # 0.426 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.003 M/sec
1,662,752,028 cycles # 2.792 GHz
3,666,713,168 instructions # 2.21 insn per cycle
328,412,721 branches # 551.374 M/sec
2,267,098 branch-misses # 0.69% of all branches
0.598305718 seconds time elapsed
0.588236000 seconds user
0.007962000 seconds sys
Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
---
A src/kudu/util/bitmap-inl.h
M src/kudu/util/bitmap-test.cc
M src/kudu/util/bitmap.h
3 files changed, 159 insertions(+), 80 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/39/15539/1
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 1
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 3:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h@178
PS3, Line 178:
: // Iterate over the bits in 'bitmap' and call 'func' for each set bit.
: // 'func' should take a single argument which is the bit's index.
: template<class F>
: void ForEachSetBit(const uint8_t* __restrict__ bitmap,
: int n_bits,
: const F& func);
:
: // Iterate over the bits in 'bitmap' and call 'func' for each unset bit.
: // 'func' should take a single argument which is the bit's index.
: template<class F>
: void ForEachUnsetBit(const uint8_t* __restrict__ bitmap,
: int n_bits,
: const F& func);
Why not define these down below?
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h@223
PS3, Line 223: base_idx += 64;
Could we do:
int base_idx = n_bits - rem;
after the loop to avoid this addition?
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 3
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 24 Mar 2020 06:55:36 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 3:
(3 comments)
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h@178
PS3, Line 178:
: // Iterate over the bits in 'bitmap' and call 'func' for each set bit.
: // 'func' should take a single argument which is the bit's index.
: template<class F>
: void ForEachSetBit(const uint8_t* __restrict__ bitmap,
: int n_bits,
: const F& func);
:
: // Iterate over the bits in 'bitmap' and call 'func' for each unset bit.
: // 'func' should take a single argument which is the bit's index.
: template<class F>
: void ForEachUnsetBit(const uint8_t* __restrict__ bitmap,
: int n_bits,
: const F& func);
> Why not define these down below?
wanted to keep this part simple without implementation details for easy reading of the header
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h@223
PS3, Line 223: base_idx += 64;
> Could we do:
but base_idx is used on line 220
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h@181
PS1, Line 181: template<class F>
> Wow, that is a big difference.
I think using std::function is fine so long as it's not a perf-sensitive call site where inlining is important. The overhead should be similar to a virtual call. Not sure why no compilers seem to be able to inline it out such a simple case. It seems if I make the 'Foo' function in my godbolt example above not have any loop, it can do it
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 3
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 24 Mar 2020 16:57:46 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 1:
(8 comments)
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h
File src/kudu/util/bitmap-inl.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@17
PS1, Line 17: #pragma once
Curious why not implement these functions in existing bitmap.h?
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@30
PS1, Line 30: int64_t
Why not uint64_t here?
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@59
PS1, Line 59: break;
just return here instead?
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc
File src/kudu/util/bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@37
PS1, Line 37: &
Nit: Just capture result by reference.
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@87
PS1, Line 87: set
Is ordered set necessary?
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@109
PS1, Line 109: const
Nit: constexpr
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@110
PS1, Line 110: const
constexpr
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@118
PS1, Line 118: &
Only sum by reference
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 1
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Tue, 24 Mar 2020 00:43:32 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Adar Dembo (Code Review)" <ge...@cloudera.org>.
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 3:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h@181
PS1, Line 181: template<class F>
> The compiler isn't smart enough to inline the contents of a lambda through
Wow, that is a big difference.
Through commits like f37e7a6e0 and 7dd10ba35 I've been working to converge all of our functor-like interfaces on std::function, converting all callers to lambdas. I was under the impression that this combination would yield good inlining of the lambdas on the part of the compiler, but maybe it doesn't go far enough? Do we need to templatize these interfaces to yield real dividends?
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 3
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 24 Mar 2020 06:37:51 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Adar Dembo (Code Review)" <ge...@cloudera.org>.
Adar Dembo has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
bitmap: faster implementation of iteration over a bitmap
This new implementation iterates 64 bits at a time instead of 8,
and uses a templated callback function instead of using an "iterator"
approach. In an upcoming patch, I found this method to be measurably
faster than the previous TrueBitIterator code.
I compared the included benchmark using the old TrueBitIterator vs the
new implementation:
Old:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
1,263.17 msec task-clock # 0.998 CPUs utilized
254 context-switches # 0.201 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.001 M/sec
3,561,984,981 cycles # 2.820 GHz
5,878,012,694 instructions # 1.65 insn per cycle
1,301,336,934 branches # 1030.218 M/sec
22,275,166 branch-misses # 1.71% of all branches
1.265635106 seconds time elapsed
1.255785000 seconds user
0.007992000 seconds sys
new:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
595.63 msec task-clock # 0.996 CPUs utilized
254 context-switches # 0.426 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.003 M/sec
1,662,752,028 cycles # 2.792 GHz
3,666,713,168 instructions # 2.21 insn per cycle
328,412,721 branches # 551.374 M/sec
2,267,098 branch-misses # 0.69% of all branches
0.598305718 seconds time elapsed
0.588236000 seconds user
0.007962000 seconds sys
Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Reviewed-on: http://gerrit.cloudera.org:8080/15539
Tested-by: Kudu Jenkins
Reviewed-by: Andrew Wong <aw...@cloudera.com>
---
M src/kudu/util/bitmap-test.cc
M src/kudu/util/bitmap.h
2 files changed, 135 insertions(+), 76 deletions(-)
Approvals:
Kudu Jenkins: Verified
Andrew Wong: Looks good to me, approved
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 4
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Adar Dembo, Bankim Bhavsar,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/15539
to look at the new patch set (#2).
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
bitmap: faster implementation of iteration over a bitmap
This new implementation iterates 64 bits at a time instead of 8,
and uses a templated callback function instead of using an "iterator"
approach. In an upcoming patch, I found this method to be measurably
faster than the previous TrueBitIterator code.
I compared the included benchmark using the old TrueBitIterator vs the
new implementation:
Old:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
1,263.17 msec task-clock # 0.998 CPUs utilized
254 context-switches # 0.201 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.001 M/sec
3,561,984,981 cycles # 2.820 GHz
5,878,012,694 instructions # 1.65 insn per cycle
1,301,336,934 branches # 1030.218 M/sec
22,275,166 branch-misses # 1.71% of all branches
1.265635106 seconds time elapsed
1.255785000 seconds user
0.007992000 seconds sys
new:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
595.63 msec task-clock # 0.996 CPUs utilized
254 context-switches # 0.426 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.003 M/sec
1,662,752,028 cycles # 2.792 GHz
3,666,713,168 instructions # 2.21 insn per cycle
328,412,721 branches # 551.374 M/sec
2,267,098 branch-misses # 0.69% of all branches
0.598305718 seconds time elapsed
0.588236000 seconds user
0.007962000 seconds sys
Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
---
M src/kudu/util/bitmap-test.cc
M src/kudu/util/bitmap.h
2 files changed, 136 insertions(+), 76 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/39/15539/2
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 2
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Todd Lipcon has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 1:
(10 comments)
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h
File src/kudu/util/bitmap-inl.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@17
PS1, Line 17: #pragma once
> Curious why not implement these functions in existing bitmap.h?
it's a relatively common way to move long implmentation details ("noise") out of the header files. That said it seems the google style guide now recommends against it. I'll move them into bitmap.h
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@30
PS1, Line 30: int64_t
> Why not uint64_t here?
typo
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-inl.h@59
PS1, Line 59: break;
> just return here instead?
this breaks out of the inner loop but may still have more bytes to process in the outer loop
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc
File src/kudu/util/bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@37
PS1, Line 37: &
> Nit: Just capture result by reference.
The style guide https://google.github.io/styleguide/cppguide.html#Lambda_expressions suggests using default scope when the lifetime of the lambda capture is clearly within the current scope, and explicit captures only when something is moved out of scope
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@87
PS1, Line 87: set
> Is ordered set necessary?
nope but this isn't perf sensitive so why not?
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@92
PS1, Line 92: static const int kNumBits = 1 + r.Uniform(100);
> warning: narrowing conversion from 'unsigned int' to signed type 'int' is i
Done
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@109
PS1, Line 109: const
> Nit: constexpr
Done
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@110
PS1, Line 110: const
> constexpr
Done
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap-test.cc@118
PS1, Line 118: &
> Only sum by reference
see above
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h@181
PS1, Line 181: template<class F>
> Curious why you're templatizing func vs. just using something like std::fun
The compiler isn't smart enough to inline the contents of a lambda through a std::function. See the following for example:
https://godbolt.org/z/68im5N
Play with the #define USE_TEMPLATE at the top of the source and see the difference in assembly output. You can change the clang optimization to '-Os' to get it to stop doing vectorization and just do a really tight loop similar to GCC, if you want.
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 1
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 24 Mar 2020 04:33:21 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 3: Code-Review+2
(1 comment)
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/3/src/kudu/util/bitmap.h@223
PS3, Line 223: base_idx += 64;
> but base_idx is used on line 220
Ah right :)
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 3
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 24 Mar 2020 17:05:26 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Adar Dembo (Code Review)" <ge...@cloudera.org>.
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/15539 )
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
Patch Set 1:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h
File src/kudu/util/bitmap.h:
http://gerrit.cloudera.org:8080/#/c/15539/1/src/kudu/util/bitmap.h@181
PS1, Line 181: template<class F>
Curious why you're templatizing func vs. just using something like std::function?
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 1
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Tue, 24 Mar 2020 00:46:35 +0000
Gerrit-HasComments: Yes
[kudu-CR] bitmap: faster implementation of iteration over a bitmap
Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Adar Dembo, Bankim Bhavsar,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/15539
to look at the new patch set (#3).
Change subject: bitmap: faster implementation of iteration over a bitmap
......................................................................
bitmap: faster implementation of iteration over a bitmap
This new implementation iterates 64 bits at a time instead of 8,
and uses a templated callback function instead of using an "iterator"
approach. In an upcoming patch, I found this method to be measurably
faster than the previous TrueBitIterator code.
I compared the included benchmark using the old TrueBitIterator vs the
new implementation:
Old:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
1,263.17 msec task-clock # 0.998 CPUs utilized
254 context-switches # 0.201 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.001 M/sec
3,561,984,981 cycles # 2.820 GHz
5,878,012,694 instructions # 1.65 insn per cycle
1,301,336,934 branches # 1030.218 M/sec
22,275,166 branch-misses # 1.71% of all branches
1.265635106 seconds time elapsed
1.255785000 seconds user
0.007992000 seconds sys
new:
Performance counter stats for 'build/latest/bin/bitmap-test --gtest_filter=*Bench* --gtest_repeat=10':
595.63 msec task-clock # 0.996 CPUs utilized
254 context-switches # 0.426 K/sec
0 cpu-migrations # 0.000 K/sec
1,808 page-faults # 0.003 M/sec
1,662,752,028 cycles # 2.792 GHz
3,666,713,168 instructions # 2.21 insn per cycle
328,412,721 branches # 551.374 M/sec
2,267,098 branch-misses # 0.69% of all branches
0.598305718 seconds time elapsed
0.588236000 seconds user
0.007962000 seconds sys
Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
---
M src/kudu/util/bitmap-test.cc
M src/kudu/util/bitmap.h
2 files changed, 135 insertions(+), 76 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/39/15539/3
--
To view, visit http://gerrit.cloudera.org:8080/15539
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibe772a7dd92faf9f99115148ad4cc7df542d1c76
Gerrit-Change-Number: 15539
Gerrit-PatchSet: 3
Gerrit-Owner: Todd Lipcon <to...@apache.org>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>