5 ms·

The question I have, which I do not see answered after a quick glance of the top responses, is: What is the total time of sorting + good branch prediction loop,

The question I have, which I do not see answered after a quick glance of the top responses, is: What is the total time of sorting + good branch prediction loop, versus not sorting and bad branch prediction loop? Does the good branch prediction save more time than it cost to sort the array, on modern processors? What about old processors with shorter pipelines?

deleted 9y ago
[deleted]
petters 9y ago
Well, the code being measured does one pass through the array. Sorting can in general not be done in linear time, so asymptotically you won't gain anything by sorting first. Edit: Whoops, I misunderstood. Sorry!
- Iburinoc 9y ago
  Well sure, but from an asymptotic approach both unsorted and sorted are "linear", so asymptotics don't necessarily provide enough information to answer GP's question.
staticassertion 9y ago
I wouldn't expect the cost to offset the impact of having to sort first. But, if you need to process the same data many times, it may be a good idea to sort it up front.
- pletnes 9y ago
  In that case, loop fusion may be even more efficient - makes better use of CPU caches. Depends on the logic I suppose.
  - staticassertion 9y ago
    That's the thing, it's feels impossible to generalize since this can get pretty arbitrary. The size of the data, how sorted the data already is, what you're processing, etc.
    - redcalx 9y ago
      Yes heuristic logic can have a role here, e.g. if list has length M and number of passes through it M, do N*M and if the result is over some threshold then make the effort of sorting the list. But a good value for that threshold depends on many factors, hence a heuristic may make sense in some scenarios. It's the same sort of pattern used with SQL query optimizers, e.g. cardinality of a result set is one of the key factors that influence how some query on that result set will be executed, e.g. whether to scan versus use an index.
autokad 9y ago
I feel like branch prediction is only a small part of the performance boost. If I do the same in python 2500 times for an array of size 40k, I get 0.00183519964218 vs 0.00163079910278 or ~11% boost. I imagine the 6x factor probably is because the optimizer unfolds the array/loop structure. edit: sorting the array increases the time by about 4x if you include the sort time, so its not worth it
- hyperpape 9y ago
  You can't use the Python implementation to get insight into what's happening with a C++ implementation, because the overhead of operations in Python may mask a real effect that can be seen in C++.
  - autokad 9y ago
    not directly, but information is information. I am also more skeptical that branching alone would result in a 6x increase in run time. We know optimizes unfold loops as well as arrays. it doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did.
    - hyperpape 9y ago
      > information is information It's information, but not worthwhile information. > It doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did. Prove it. This article has had a ton of traffic. If you see the thing that everyone missed, a lot of people will be very impressed with you.
    - Ultimatt 9y ago
      Did you try with an actual array or a Python list? https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html or numpy you might be able to recover the same effect. Your average line of Python is miles away from low level and simple operations. Pretty much any dynamic language with a large runtime is. Especially when they default to lists not arrays. You should see your result as evidence of that. Not assume this discussion is flawed.
adrianN 9y ago
It might not matter for the simple case of searching through a list, but in general it makes a lot of sense to sort your data so that you improve cache locality on traversal. See for example how Frank McSherry uses Hilbert curves in graph processing: https://github.com/frankmcsherry/blog/blob/master/posts/2015-01-15.md https://github.com/frankmcsherry/blog/blob/master/posts/2015...
wyager 9y ago
Sorting is going to be more expensive than mis-predicting every item in the array (since sorting inherently involves multiple rounds of conditional swaps, getting it wrong a lot of the time on random data). The trick in the SO post is that they use the same sorted data tens of thousands of times.
- repsilat 9y ago
  You can partition the list with zero branches (aside from the loop test.) You don't need to sort it. (Though, of course, the original algorithm can be written in a one-pass branchless fashion anyway, so the point is kinda moot.)
xigency 9y ago
Modern processors have at least a dozen pipeline stages. In this case, every other instruction is a branch and they are completely unpredictable so it's possible to see a 12.0 x 0.50 x 0.50 or 3x slowdown. If you can sort or partition the data in effectively 2N time for the size, then you can beat the misprediction. The important thing is to be keenly aware that this is how a processor works. Branch predictors take up a big chunk of silicon on the CPU and keep very complicated histories, and in certain cases the compiler can outsmart some bad code, but in general it's way too easy to make this kind of mistake.
- Veedrac 9y ago
  > 12.0 x 0.50 x 0.50 I assume this means "12 cycles delay × 50% instructions can miss × 50% miss rate". But that's not really right; you're comparing against an IPC of 1 sans misprediction, with each instruction latency-1 and all of them dependent on the prior. Less importantly, you're assuming 50% of the instruction are branches, where it's really more like 25% since you have the load and add as well. Your mispredict penalty also seems a tad small. A not-horrific compiler and a fast CPU should do far better than that, with peak IPC of just under 4 (since theoretical peak is 4 and there's generally a little overhead). Mispredicts linearize the graph, reducing IPC to some fraction, which you can guess is a bit over 1/2, since you average ~2 loops of 4 instructions per mispredict. This means you've got a reduction of slightly less than 8x.
rayiner 9y ago
The second loop will do O(N) comparisons. If the array is unsorted, each will be poorly predicted. The best possible comparison sort will do O(N * log(N)) comparisons. If the array is unsorted, each of those will be poorly predicted. So regardless of the pipeline length, sorting first will be strictly slower than operating on the unsorted data. Sorting first might help if you subsequently need to do something that will do more than O(N * log(N)) comparisons.
frankmcsherry 9y ago
This example isn't about branch prediction (not exactly), but it might still be interesting: https://github.com/frankmcsherry/blog/blob/master/posts/2015-08-15.md https://github.com/frankmcsherry/blog/blob/master/posts/2015... It's about how sorting + random access can be faster than random access, because you introduce locality of reference. And in this case, it absolutely is faster to sort the data first and then do the work, even counting the sorting. Edit: Aw crap, adrianN beat me to this a few screenfuls down, sorry! But, it is a different post, so maybe this is still helpful. :D

deleted 9y ago

[deleted]

petters 9y ago

Well, the code being measured does one pass through the array. Sorting can in general not be done in linear time, so asymptotically you won't gain anything by sorting first. Edit: Whoops, I misunderstood. Sorry!

Iburinoc 9y ago
Well sure, but from an asymptotic approach both unsorted and sorted are "linear", so asymptotics don't necessarily provide enough information to answer GP's question.

staticassertion 9y ago

I wouldn't expect the cost to offset the impact of having to sort first. But, if you need to process the same data many times, it may be a good idea to sort it up front.

pletnes 9y ago
In that case, loop fusion may be even more efficient - makes better use of CPU caches. Depends on the logic I suppose.
- staticassertion 9y ago
  That's the thing, it's feels impossible to generalize since this can get pretty arbitrary. The size of the data, how sorted the data already is, what you're processing, etc.
  - redcalx 9y ago
    Yes heuristic logic can have a role here, e.g. if list has length M and number of passes through it M, do N*M and if the result is over some threshold then make the effort of sorting the list. But a good value for that threshold depends on many factors, hence a heuristic may make sense in some scenarios. It's the same sort of pattern used with SQL query optimizers, e.g. cardinality of a result set is one of the key factors that influence how some query on that result set will be executed, e.g. whether to scan versus use an index.

autokad 9y ago

I feel like branch prediction is only a small part of the performance boost. If I do the same in python 2500 times for an array of size 40k, I get 0.00183519964218 vs 0.00163079910278 or ~11% boost. I imagine the 6x factor probably is because the optimizer unfolds the array/loop structure. edit: sorting the array increases the time by about 4x if you include the sort time, so its not worth it

hyperpape 9y ago
You can't use the Python implementation to get insight into what's happening with a C++ implementation, because the overhead of operations in Python may mask a real effect that can be seen in C++.
- autokad 9y ago
  not directly, but information is information. I am also more skeptical that branching alone would result in a 6x increase in run time. We know optimizes unfold loops as well as arrays. it doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did.
  - hyperpape 9y ago
    > information is information It's information, but not worthwhile information. > It doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did. Prove it. This article has had a ton of traffic. If you see the thing that everyone missed, a lot of people will be very impressed with you.
  - Ultimatt 9y ago
    Did you try with an actual array or a Python list? https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html or numpy you might be able to recover the same effect. Your average line of Python is miles away from low level and simple operations. Pretty much any dynamic language with a large runtime is. Especially when they default to lists not arrays. You should see your result as evidence of that. Not assume this discussion is flawed.

adrianN 9y ago

It might not matter for the simple case of searching through a list, but in general it makes a lot of sense to sort your data so that you improve cache locality on traversal. See for example how Frank McSherry uses Hilbert curves in graph processing: https://github.com/frankmcsherry/blog/blob/master/posts/2015-01-15.md https://github.com/frankmcsherry/blog/blob/master/posts/2015...

wyager 9y ago

Sorting is going to be more expensive than mis-predicting every item in the array (since sorting inherently involves multiple rounds of conditional swaps, getting it wrong a lot of the time on random data). The trick in the SO post is that they use the same sorted data tens of thousands of times.

repsilat 9y ago
You can partition the list with zero branches (aside from the loop test.) You don't need to sort it. (Though, of course, the original algorithm can be written in a one-pass branchless fashion anyway, so the point is kinda moot.)

xigency 9y ago

Modern processors have at least a dozen pipeline stages. In this case, every other instruction is a branch and they are completely unpredictable so it's possible to see a 12.0 x 0.50 x 0.50 or 3x slowdown. If you can sort or partition the data in effectively 2N time for the size, then you can beat the misprediction. The important thing is to be keenly aware that this is how a processor works. Branch predictors take up a big chunk of silicon on the CPU and keep very complicated histories, and in certain cases the compiler can outsmart some bad code, but in general it's way too easy to make this kind of mistake.

Veedrac 9y ago
> 12.0 x 0.50 x 0.50 I assume this means "12 cycles delay × 50% instructions can miss × 50% miss rate". But that's not really right; you're comparing against an IPC of 1 sans misprediction, with each instruction latency-1 and all of them dependent on the prior. Less importantly, you're assuming 50% of the instruction are branches, where it's really more like 25% since you have the load and add as well. Your mispredict penalty also seems a tad small. A not-horrific compiler and a fast CPU should do far better than that, with peak IPC of just under 4 (since theoretical peak is 4 and there's generally a little overhead). Mispredicts linearize the graph, reducing IPC to some fraction, which you can guess is a bit over 1/2, since you average ~2 loops of 4 instructions per mispredict. This means you've got a reduction of slightly less than 8x.

rayiner 9y ago

The second loop will do O(N) comparisons. If the array is unsorted, each will be poorly predicted. The best possible comparison sort will do O(N * log(N)) comparisons. If the array is unsorted, each of those will be poorly predicted. So regardless of the pipeline length, sorting first will be strictly slower than operating on the unsorted data. Sorting first might help if you subsequently need to do something that will do more than O(N * log(N)) comparisons.

frankmcsherry 9y ago

This example isn't about branch prediction (not exactly), but it might still be interesting: https://github.com/frankmcsherry/blog/blob/master/posts/2015-08-15.md https://github.com/frankmcsherry/blog/blob/master/posts/2015... It's about how sorting + random access can be faster than random access, because you introduce locality of reference. And in this case, it absolutely is faster to sort the data first and then do the work, even counting the sorting. Edit: Aw crap, adrianN beat me to this a few screenfuls down, sorry! But, it is a different post, so maybe this is still helpful. :D