Hacker News Reader

Comment by corey_moncure | Hacker News Reader

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?

View on HN

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.

In that case, loop fusion may be even more efficient - makes better use of CPU caches. Depends on the logic I suppose.

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.

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.

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.

> 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.

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...

This example isn't about branch prediction (not exactly), but it might still be interesting:

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

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.

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.

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.)

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

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++.

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.

> 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.

Did you try with an actual array or a Python list? 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.

I'm surprised you got such a high (11%) boost. I would not expect branch prediction issues from your code to have much of an effect in Python because the Python interpreter itself naturally introduces 10x as many branches under the hood as the code it interprets.

guess: the branches in the python VM are more accurately predicted than branch on the data. The data is going to be random and thus unpredictable, but the branches in the VM are probably pretty predictable.

Python if statements will branch on very few processor instructions in the VM; so I don't think branch prediction of the processor is able to predict different Python if's — they're all the same to it.

Well, that... and even simple Python VM instructions tend to take dozens of insns to execute.

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!

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.

Reply on news.ycombinator.com