GitHub user saketj opened a pull request:
https://github.com/apache/incubator-quickstep/pull/114
Convert setBitRegularVersion() to a branchless version using bitwise
arithmetic
The `setBitRegularVersion()` of `BitVector.hpp` is a critical function that
is called in various tight loop iterations over storage blocks throughout the
Quickstep code. This function has a simple purpose of setting a bit value in a
BitVector to true/false given a boolean argument. However, it has an expensive
if-else branch that can add a significant penalty at runtime due to branch
mis-predictions.
This short PR completely removes branching from the
`setBitRegularVersion()` by replacing the same functionality with a set of
bitwise arithmetic operations. Given that a branch mis-prediction costs about
10 cycles, the branchless code is expected to save those precious 10 cycles at
the slight expense of 4 additional bitwise operations (a cost of additional 2-4
cycles only, given hyper-threading).
Thanks @navsan for pointing out this optimization.
**Tests:**
The existing unit tests should already cover the changes introduced by this
PR. Correctness also verified by comparing TPC-H output results.
**Performance Results:**
Following demonstrates the performance improvement for TPC-H data at Scale
Factor 100 for compressed column stores (measured through query execution time
with and without changes of this PR; experiments done on Cloudlab instance). In
general, queries (01, 04, 10, 12, 13, 15) see a good reduction in execution
time. A difference of <= 100 ms can be attributed to noise, and may be
discounted.
| | w/o PR (in ms) | w/ PR (in ms) |
|--------------|----------------|---------------|
| Query 01.sql | 16847 | 16308 |
| Query 04.sql | 3669 | 2666 |
| Query 06.sql | 384 | 402 |
| Query 09.sql | 39615 | 39700 |
| Query 10.sql | 13987 | 12972 |
| Query 11.sql | 2229 | 2243 |
| Query 12.sql | 7097 | 4345 |
| Query 13.sql | 51979 | 49900 |
| Query 14.sql | 807 | 814 |
| Query 15.sql | 5236 | 4425 |
| Query 16.sql | 8230 | 8495 |
| Query 19.sql | 1564 | 1597 |
| Query 22.sql | 7223 | 7159 |
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/saketj/incubator-quickstep branchless-setbit
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-quickstep/pull/114.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #114
----
commit ee854fa40c603425bbc15171fe97e4efa504996c
Author: Saket Saurabh <[email protected]>
Date: 2016-10-17T22:50:40Z
Convert setBitRegularVersion to a branchless version using BitWise
Arithmetic
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
