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 <ssaur...@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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

Reply via email to