Branch Prediction And Array Processing Speed
August 24, 2019
As of August 24th, 2019, this article is officially the number one article on stack overflow for Java related questions.
To summarize, the asker of the question, user “GManNickG” started with a simple array of integers. He then performed a conditional operation on the code - if the value was greater than 128, it would add the number to a sum.
This is a very fair question, and the top response nailed it right on the head.
CPU branch prediction was the culprit…
Wiki article explaining branching
In all, this is a really great academic case, but don’t go out and add a sort method before all of the code that you’ve written.
First and foremost, you should not be working on this level of abstraction in your day to day job unless you’re working on high performance frameworks/libraries/applications. If you are a regular application developer and focus on performance too much, you’ll be spending all of your time optimizing and very little time actually writing code. The most costly machine for any company is not the CPU or server, it’s you as the developer! Cycles and storage are cheap, writing and maintaining applications is not. If you manage to effectively optimize your code, you’ve saved on CPU cycles, but adding your opitimizations has made your code less readable, more difficult to maintain, and buggier.
For example, applying the sorting optimization from the stack overflow article, you’d have to add sorting before all of your conditional array logic. That means this:
if(myArray[i] < 100) {
sum += i;
}Becomes
Arrays.sort(myArray);
if(myArray[i] < 100) {
sum += i;
}Or even worse, maybe we try to pick the sorting algorithm that our array chooses because we just learned about quick sort and we think it’s awesome and the best! On top of that, we implement our own quick sort method because the library methods don’t work as fast as our own implementation on our development machine.
MySortingMethod.quickSort(myArray);
if(myArray[i]) < 100){
sum += i;
}Stop right there! If you’ve actually done this, you’ve likely spent all of your day making this one algorithm optimized, when your real goal was to make a monthly budgeting application or something of that nature. Instead, you’ve sacrificed your time to make a performance improvement that most likely won’t be noticeable in the final application. You either won’t last long at your job, or will be working many hours of overtime if you get this sidetracked.
Only optimize your application for performance reasons if you notice performance issues - i.e. you’re API is breaching SLA agreements. Testing before and after implementing your solution to ensure that you’re ‘optimizations’ are actually making a difference in the speed of the application.
The second reason you shouldn’t start sorting all of your arrays is because how the CPU works is not the job of the software engineer. How your operating system works and executes your code is also not your job. Different machines have different CPU’s and optimizations like this will run differently depending on your CPU architecture (Intel/AMD, 64vs32 bit, processor family [i.e. 9th gen intel chips], cache, etc.).
Any “optimizations” may run better on your machine, but not on the server that runs your code. On top of that, Operating Systems also dictate how code will be executed against the CPU and how resources are allocated. When microsoft updates their OS, you can’t be sure that your code will be optimal anymore. Case in point the issue Intel had with Meltdown and Spectre vulnerabilities.
It’s this branch prediction that left pretty much all CPU’s exploitable.
So, Intel worked with Microsoft to put an OS level patch in place, but this reduced the computing power significantly of many intel CPU’s. You can technically control this level of abstraction with your own custom OS, but writing and maintaining that yourself is very expensive.