5 ms·

Try it for yourself! Create an array with a million random bytes from 0 to 255, then count (in a for loop) with an "if" statement how many of them are less than

by OskarS 8y ago

Try it for yourself! Create an array with a million random bytes from 0 to 255, then count (in a for loop) with an "if" statement how many of them are less than 128. This branch will be essentially impossible to predict, and the branch predictor will fail roughly 50% of the time. Then try again, but sort the array before you begin (which will make the branch trivial to predict). Time the difference. I think you'll be surprised.

AceJohnny2 8y ago
Well, I took the bait. Time to go through an unsorted vs sorted array on an iMac17,1 with 4Ghz Core i7 (not sure which CPU exactly).: * 1MB: 6.52ms vs 2.16ms (3x speedup) * 1GB: 5.73s vs 2.25s (2.5x speedup) Tested with this C code, called as "bpredict-time [size] [sort]": #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <sys/time.h> #define SIZE (1024*1024) int cmp (const void *val1, const void *val2) { return *(uint8_t*)val1-*(uint8_t*)val2; } int main (int argc, char **argv) { uint8_t *array; size_t size = SIZE; struct timeval start, end; if (argc > 1) { size = atoi(argv[1]); } array = malloc(sizeof(*array) * size); if (array == NULL) { return -1;} for (size_t i=0; i<size; i++) { array[i] = random(); } if (argc > 2) { qsort(array, size, sizeof(*array), cmp); } (void)gettimeofday(&start, NULL); int cnt = 0; for (size_t i=0; i<size; i++) { if (array[i] < 128) { cnt++;} } (void)gettimeofday(&end, NULL); printf("N ints < 128: %d\n", cnt); printf("Time: %f\n", (float)(end.tv_sec-start.tv_sec)\ +(float)(end.tv_usec-start.tv_usec)/1000000); free(array); return 0; }
- Sohcahtoa82 8y ago
  Why do you use "(void)gettimeofday(&start, NULL);" instead of just "gettimeofday(&start, NULL);"?
  - AceJohnny2 8y ago
    To avoid the compiler complaining about the unused return value, by telling it I'm explicitly choosing to ignore the value. The complaint doesn't show up on the default warning levels. I think only with -W ? (fun fact: -Wall actually has fewer warnings enabled than -W, at least with Clang) Edit: actually, the warning is enabled by default, but only triggers for functions that have the attribute 'warn_unused_result' set, which is almost none of them, which is why this warning is not well-known. Indeed, in my example my (void) isn't necessary, and I couldn't get the warning to trigger even with -Wpedantic.
jandrese 8y ago
Looks like the 3x penalty is about right: There are 5001834 entries out of 10000000 less than 128 Exeuction took 65335182 nanoseconds There are 5001834 entries out of 10000000 less than 128 Exeuction took 26693952 nanoseconds Using the following code I hacked together: #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/types.h> #define DATASIZE 10000000 #define NSEC_PER_SEC 1000000000 int cmp(const void* a, const void* b) { return *(unsigned char*)a - *(unsigned char*)b; } int countsmall(unsigned char* data) { struct timespec start; struct timespec end; u_int64_t delta; int lcv; int numsmall; numsmall = 0; clock_gettime(CLOCK_MONOTONIC, &start); for ( lcv = 0; lcv < DATASIZE; lcv++ ) if ( data[lcv] < 128 ) numsmall++; clock_gettime(CLOCK_MONOTONIC, &end); delta = (end.tv_sec * NSEC_PER_SEC + end.tv_nsec) - (start.tv_sec * NSEC_PER_SEC + start.tv_nsec); printf("There are %d entries out of %d less than 128\n", numsmall, DATASIZE); printf("Exeuction took %ld nanoseconds\n", delta); return 0; } int main(int argc, char** argv) { unsigned char data[DATASIZE]; int lcv; srandom(time(NULL)); for ( lcv = 0; lcv < DATASIZE; lcv++ ) data[lcv] = random(); countsmall(data); qsort(data, DATASIZE, sizeof(unsigned char), cmp); countsmall(data); return 0; }
Sohcahtoa82 8y ago
A lot of people tested this on Stack Overflow a while back: https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-it-faste...

by OskarS 8y ago

AceJohnny2 8y ago

Well, I took the bait. Time to go through an unsorted vs sorted array on an iMac17,1 with 4Ghz Core i7 (not sure which CPU exactly).: * 1MB: 6.52ms vs 2.16ms (3x speedup) * 1GB: 5.73s vs 2.25s (2.5x speedup) Tested with this C code, called as "bpredict-time [size] [sort]": #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <sys/time.h> #define SIZE (1024*1024) int cmp (const void *val1, const void *val2) { return *(uint8_t*)val1-*(uint8_t*)val2; } int main (int argc, char **argv) { uint8_t *array; size_t size = SIZE; struct timeval start, end; if (argc > 1) { size = atoi(argv[1]); } array = malloc(sizeof(*array) * size); if (array == NULL) { return -1;} for (size_t i=0; i<size; i++) { array[i] = random(); } if (argc > 2) { qsort(array, size, sizeof(*array), cmp); } (void)gettimeofday(&start, NULL); int cnt = 0; for (size_t i=0; i<size; i++) { if (array[i] < 128) { cnt++;} } (void)gettimeofday(&end, NULL); printf("N ints < 128: %d\n", cnt); printf("Time: %f\n", (float)(end.tv_sec-start.tv_sec)\ +(float)(end.tv_usec-start.tv_usec)/1000000); free(array); return 0; }

Sohcahtoa82 8y ago
Why do you use "(void)gettimeofday(&start, NULL);" instead of just "gettimeofday(&start, NULL);"?
- AceJohnny2 8y ago
  To avoid the compiler complaining about the unused return value, by telling it I'm explicitly choosing to ignore the value. The complaint doesn't show up on the default warning levels. I think only with -W ? (fun fact: -Wall actually has fewer warnings enabled than -W, at least with Clang) Edit: actually, the warning is enabled by default, but only triggers for functions that have the attribute 'warn_unused_result' set, which is almost none of them, which is why this warning is not well-known. Indeed, in my example my (void) isn't necessary, and I couldn't get the warning to trigger even with -Wpedantic.

jandrese 8y ago

Looks like the 3x penalty is about right: There are 5001834 entries out of 10000000 less than 128 Exeuction took 65335182 nanoseconds There are 5001834 entries out of 10000000 less than 128 Exeuction took 26693952 nanoseconds Using the following code I hacked together: #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/types.h> #define DATASIZE 10000000 #define NSEC_PER_SEC 1000000000 int cmp(const void* a, const void* b) { return *(unsigned char*)a - *(unsigned char*)b; } int countsmall(unsigned char* data) { struct timespec start; struct timespec end; u_int64_t delta; int lcv; int numsmall; numsmall = 0; clock_gettime(CLOCK_MONOTONIC, &start); for ( lcv = 0; lcv < DATASIZE; lcv++ ) if ( data[lcv] < 128 ) numsmall++; clock_gettime(CLOCK_MONOTONIC, &end); delta = (end.tv_sec * NSEC_PER_SEC + end.tv_nsec) - (start.tv_sec * NSEC_PER_SEC + start.tv_nsec); printf("There are %d entries out of %d less than 128\n", numsmall, DATASIZE); printf("Exeuction took %ld nanoseconds\n", delta); return 0; } int main(int argc, char** argv) { unsigned char data[DATASIZE]; int lcv; srandom(time(NULL)); for ( lcv = 0; lcv < DATASIZE; lcv++ ) data[lcv] = random(); countsmall(data); qsort(data, DATASIZE, sizeof(unsigned char), cmp); countsmall(data); return 0; }

Sohcahtoa82 8y ago

A lot of people tested this on Stack Overflow a while back: https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-it-faste...