You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@quickstep.apache.org by saketj <gi...@git.apache.org> on 2016/10/18 02:52:08 UTC
[GitHub] incubator-quickstep pull request #114: Convert setBitRegularVersion() to a b...
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 <ss...@cs.wisc.edu>
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by hbdeshmukh <gi...@git.apache.org>.
Github user hbdeshmukh commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
@saketj You may have to close this PR manually, as it was created from your personal fork of Quickstep.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by saketj <gi...@git.apache.org>.
Github user saketj commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
@pateljm Sure Jignesh, I have rebased this PR now with the master.
Thanks @hbdeshmukh for helping in re-running the performance numbers for this PR over the updated master after recent commits. Here are the updated numbers for the entire TPC-H suite of queries now:
| | Execution time w/o PR (in ms) | Execution time w/ PR (in ms) |
|--------------|-------------------------------|------------------------------|
| Query 01.sql | 16,405 | 14,901 |
| Query 02.sql | 5,603 | 5,582 |
| Query 03.sql | 8,267 | 6,018 |
| Query 04.sql | 4,823 | 2,741 |
| Query 05.sql | 5,210 | 4,592 |
| Query 06.sql | 396 | 402 |
| Query 07.sql | 23,907 | 23,154 |
| Query 08.sql | 3,324 | 3,268 |
| Query 09.sql | 9,641 | 15,749 |
| Query 10.sql | 15,215 | 14,823 |
| Query 11.sql | 2,141 | 2,160 |
| Query 12.sql | 2,479 | 2,121 |
| Query 13.sql | 34,369 | 34,159 |
| Query 14.sql | 795 | 822 |
| Query 15.sql | 4,696 | 5,109 |
| Query 16.sql | 9,442 | 9,040 |
| Query 17.sql | 149,132 | 142,230 |
| Query 18.sql | 81,042 | 76,434 |
| Query 19.sql | 1,453 | 1,564 |
| Query 20.sql | 53,268 | 59,553 |
| Query 21.sql | 119,326 | 124,905 |
| Query 22.sql | 6,812 | 7,187 |
| Total | 557745 | 556515 |
Overall, there is certainly some benefit to be gained by introducing a branchless codepath. Most queries seem to improve in general. However, the results for Query 09, 20, and 21 are definitely surprising. I will spend some time understanding why this is the case.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by saketj <gi...@git.apache.org>.
Github user saketj commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
It turns out that these queries have very few scan (selection) operations as compared to other queries and mostly involve joins where BitVectors might not be aggressively used. Also, if the selectivity is high, branch predictions will anyway be more-or-less accurate. (more so after the LIP filter optimization).
However, another interesting thing is that for these queries 09, 20, 21, the differences are actually not high across different trials. A cold cache may be playing some tricks, when we report our aggregate numbers.
| Query 9 | w/o PR (ms) | w/ PR (ms) |
|----------|-------------|------------|
| Trial 1 | 110251 | 42551 |
| Trial 2 | 13763 | 14386 |
| Trial 3 | 10302 | 10129 |
| Trial 4 | 11783 | 10616 |
| Trial 5 | 10070 | 9243 |
| | | |
| | | |
| Query 20 | w/o PR (ms) | w/ PR (ms) |
| Trial 1 | 85988 | 104532 |
| Trial 2 | 56639 | 58389 |
| Trial 3 | 50041 | 51712 |
| Trial 4 | 54269 | 50740 |
| Trial 5 | 49688 | 50723 |
| | | |
| | | |
| Query 21 | w/o PR (ms) | w/ PR (ms) |
| Trial 1 | 126323 | 142742 |
| Trial 2 | 120334 | 119632 |
| Trial 3 | 126304 | 115668 |
| Trial 4 | 115185 | 114618 |
| Trial 5 | 114663 | 113232 |
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by saketj <gi...@git.apache.org>.
Github user saketj commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
@cramja Quite correct. Yeah and it seems so from these benchmark runs. But, I guess that is happening for only 10% of all the times BitVector is being used. So, overall this PR gives us good improvements. I believe this is ready for merging.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep pull request #114: QUICKSTEP-59 Convert setBitRegularVer...
Posted by saketj <gi...@git.apache.org>.
Github user saketj closed the pull request at:
https://github.com/apache/incubator-quickstep/pull/114
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by cramja <gi...@git.apache.org>.
Github user cramja commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
+1 cool trick, and the comments were easy to follow!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by saketj <gi...@git.apache.org>.
Github user saketj commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
Merged in master
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by hbdeshmukh <gi...@git.apache.org>.
Github user hbdeshmukh commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
Looks good, merging.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by cramja <gi...@git.apache.org>.
Github user cramja commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
@saketj so what's the final analysis on why the branchless code takes longer on these queries? Is it because if the branch is predicted correctly, then the old code is slightly faster than the bit-fiddling code in the new method?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by saketj <gi...@git.apache.org>.
Github user saketj commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
@cramja Thanks Marc for reviewing this.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-quickstep issue #114: QUICKSTEP-59 Convert setBitRegularVersion() ...
Posted by pateljm <gi...@git.apache.org>.
Github user pateljm commented on the issue:
https://github.com/apache/incubator-quickstep/pull/114
Sweet @saketj. Can your rebase? I can merge this.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---