It's not so obvious what the take-home lesson should be from this example. The code was obviously designed to test the loop speed. Surely in reality it would not be worth sorting the array just to optimize the branches in the loop. The branchless version somebody posted is effective, but it's hard to read and brittle. The Intel compiler seemed like the optimal solution if you have it.
I've found architecture effects fairly hard to predict in real situations, with my level of knowledge. I think it's hard to reduce these to straightforward lessons. It's useful to know that things like branch mispredictions and cache misses are important, but you should probably not try to optimize for them until you've timed the loop and built up a good case for what's occurring. Most of the time, when I think I can make something faster that way, I rewrite the code and it's no faster.
One case where something did get faster was in a case where I had two large arrays, one containing indexes into the other, which contained data, and I needed to permute the data by the indexes and write it out to a file. Initially, the indexes were arranged so that the output was sequential, but the array accesses were random. I switched out the array of indexes with its inverse, which would access the data sequentially, but produce output in random order, which I captured in a new array before writing out. The second version was measurably faster. The lesson seems to be that loads benefit more from locality than stores. In the end, though, it only saved a fraction of a second, even with 100 million elements in the array. Unoptimized, it was already pretty fast, taking slightly over a second. It was nice, but I'm glad I didn't spend too much time on it.
I think this kind of optimization is somewhat like saving money by doing your own plumbing. It's usually not worth it unless you know what you're doing, or you can afford to spend lots of time.
Edit: Reading more of the comments, I found something useful that I didn't know. The ternary ?: operator generates a conditional move rather than a branch. So that's a viable solution, although it came out a little slower than the predictable branch.
Comments
It's not so obvious what the take-home lesson should be from this example. The code was obviously designed to test the loop speed. Surely in reality it would not be worth sorting the array just to optimize the branches in the loop. The branchless version somebody posted is effective, but it's hard to read and brittle. The Intel compiler seemed like the optimal solution if you have it.
I've found architecture effects fairly hard to predict in real situations, with my level of knowledge. I think it's hard to reduce these to straightforward lessons. It's useful to know that things like branch mispredictions and cache misses are important, but you should probably not try to optimize for them until you've timed the loop and built up a good case for what's occurring. Most of the time, when I think I can make something faster that way, I rewrite the code and it's no faster.
One case where something did get faster was in a case where I had two large arrays, one containing indexes into the other, which contained data, and I needed to permute the data by the indexes and write it out to a file. Initially, the indexes were arranged so that the output was sequential, but the array accesses were random. I switched out the array of indexes with its inverse, which would access the data sequentially, but produce output in random order, which I captured in a new array before writing out. The second version was measurably faster. The lesson seems to be that loads benefit more from locality than stores. In the end, though, it only saved a fraction of a second, even with 100 million elements in the array. Unoptimized, it was already pretty fast, taking slightly over a second. It was nice, but I'm glad I didn't spend too much time on it.
I think this kind of optimization is somewhat like saving money by doing your own plumbing. It's usually not worth it unless you know what you're doing, or you can afford to spend lots of time.
Edit: Reading more of the comments, I found something useful that I didn't know. The ternary ?: operator generates a conditional move rather than a branch. So that's a viable solution, although it came out a little slower than the predictable branch.