branch prediction

bench.cpp

#include <algorithm>
#include <ctime>
#include <iostream>

int main(int argc, char** argv)
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    if (argc > 1) {
        std::cout << "Sorting..." << std::endl;
        std::sort(data, data + arraySize);
    }

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

bench.py

import sys
import time
import random
import pypytools

def main():
    # generate data
    arraySize = 32768
    data = [random.randrange(256) for _ in range(arraySize)]

    if len(sys.argv) > 1:
        print "Sorting..."
        data.sort()

    start = time.clock()
    sum = 0
    for i in range(100000):
        for c in data:
            if c >= 128:
                sum += c
    end = time.clock()
    print end-start
    print 'sum =', sum, type(sum)

main()

results.txt

homer b68842fbd98c86453ec10ff2e0023050 $ g++ --version
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

homer b68842fbd98c86453ec10ff2e0023050 $ g++ -O2 bench.cpp 
homer b68842fbd98c86453ec10ff2e0023050 $ ./a.out 
18.5356
sum = 314931600000
homer b68842fbd98c86453ec10ff2e0023050 $ ./a.out 1
Sorting...
3.16222
sum = 314931600000

homer b68842fbd98c86453ec10ff2e0023050 $ g++ -O3 bench.cpp 
homer b68842fbd98c86453ec10ff2e0023050 $ ./a.out 
1.84999
sum = 314931600000
homer b68842fbd98c86453ec10ff2e0023050 $ ./a.out 1
Sorting...
2.02086
sum = 314931600000

homer b68842fbd98c86453ec10ff2e0023050 $ pypy --version
Python 2.7.12 (81d063af711f, Nov 10 2016, 23:10:31)
[PyPy 5.7.0-alpha0 with GCC 4.8.2]

homer b68842fbd98c86453ec10ff2e0023050 $ pypy bench.py 
36.632486715
sum = 312008300000 <type 'int'>
homer b68842fbd98c86453ec10ff2e0023050 $ pypy bench.py 1
Sorting...
20.654395006
sum = 314276300000 <type 'int'>