/* 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 #include #include 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; }