/*
dbm

3/19/2018 found at
https://stackoverflow.com/questions/11282938/gcc-branch-prediction

fills an array with 32768 elements having random values between 0 and 255
then plows through and accumulates all those among them equal or greater than 128
to do so it must visit and evaluate each element in order to decide whether or not
to branch to the code that accumulates ( sum += a[n]; )

prior to that it could sort the elements, or not (compile this both ways)

when the values it has to work with are sorted, summing takes about a third as much time
because upon reaching the 2nd half of the data where all elements are above 127 in value
the cpu notices the branch is consistently taken so goes ahead and "pre-accumulates"
while/before the evaluation (i.e., performs sum += accumulation before finishing  a[n] >= 128 evaluation)
by the time the evaluating is done, so also is the consequent summing
it's no longer truly "consequent" (i.e., "following")


The 32768 numbers it's adding on a pass through the array were chosen from the range 0 through 255. But since chosen
randomly, half of them will fall in the lower half of the range and half in the upper half. The former don't contribute
into the sum. The only contributers are those which are 128 or greater, and only half of them are. These, being randomly
distributed over the range 128 through 255, will have an average value in the middle of that range, or 191.5.
The sum of the array's elements therefore should prove to be 16384 times 191.5. Since the program does this
summation 20000 times, the final printed total should be 16384*191.5*20000 or 62750720000, which agrees with
observation.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int cmp(const void *d1, const void *d2)
{
    int a, b;

    a = *(int const *) d1;
    b = *(int const *) d2;

    if (a > b)
        return 1;
    else if (a == b)
        return 0;

    return -1;
}

int main()
{
    int seed = time(NULL);
    srandom(seed);

    int i, n, max = 32768, a[max];

    for (n=0; n < max; n++) {

        int r = random() % 256;
        a[n] = r;

    }

//  qsort(a, max, sizeof(int), cmp);

    clock_t beg = clock();

    long long int sum = 0;

    for (i=0; i < 20000; i++) 
    {
        for (n=0; n < max; n++) {
            if (a[n] >= 128)
                sum += a[n];
        }
    }

    clock_t end = clock();

    double sec = (end - beg) / CLOCKS_PER_SEC;

    printf("sec: %f\n", sec);
    printf("sum: %lld\n", sum);

    return 0;
}