6 ms·
I'm surprised how cheap a branch mispredict is. I had thought the relatively long pipelines in modern processors would have made that more painful. It seems w
by jandrese 8y ago
I'm surprised how cheap a branch mispredict is. I had thought the relatively long pipelines in modern processors would have made that more painful. It seems weird Intel devotes so much silicon to improving the branch predictor when the penalty is so light.
- mooman219 8y agoSpeculative execution probably plays a large role in that. I think this is more of an average that you can expect to see. Additionally, if eager execution is not at play, if a mispredict is triggered when data is finally fetched from main memory, the 5ns (handful of cycles) might just be the cost of unwinding, meaning the actual cost was 105ns.
- gpderetta 8y agoIt estimates 10 clock cycles penalty, which at 3GHz is ~3ns. I think that it is the correct order of magnitude, but 15-20 clocks is probay more accurate. The penalty is variable though and hard to characterize. For example recovering from the uop cache shaves 3-4 cycles.
- OskarS 8y agoTry 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 agoWell, 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 agoWhy do you use "(void)gettimeofday(&start, NULL);" instead of just "gettimeofday(&start, NULL);"?
- AceJohnny2 8y agoTo 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 agoLooks 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 agoA 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...
- glangdale 8y ago[ full disclosure: ex-Intel, although I did not work on h/w ] It is about 14 cycles on modern hardware, which is consistent with the 3ns if you have a very high-clocked machine. I think 3ns is rounding down otherwise. The penalty is not that light if you have heavily optimized code. Those 14 cycles will be spent with a completely empty pipeline and the code that follows the miss will be starting from scratch - that is, it will likely take time to spin up to filling the pipeline effectively. That is, you have a deep (~14) and wide (~4) pipeline and you're going to be progressively filling it with new work - maybe some of that work has data dependencies so it will be a while before you're filling most slots. Under enormously ideal conditions you can issue and retire 4 uops (not quite 1:1 with instructions) per cycle - so 14 cycles is passing up the opportunity to execute 56 uops (again, under ideal conditions). Very few codes will get anywhere near this. However, that is one of the prime reasons that having a really good branch predictor - and it is very good - is so important. It's not just the time spent waiting, it's the fact that you mostly wipe out your pipeline every time.