quickstep-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From saketj <...@git.apache.org>
Subject [GitHub] incubator-quickstep pull request #114: Convert setBitRegularVersion() to a b...
Date Tue, 18 Oct 2016 02:52:08 GMT
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 <ssaurabh@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.
---

Mime
View raw message