Example<\/h1>\n\n\n\n
Let’s start with a simple code snippet.<\/p>\n\n\n\n
public class BranchMispredictionExecutor\n{\n private readonly List<int> _sortedCollection;\n private readonly List<int> _unsortedCollection;\n\n public BranchMispredictionExecutor(int count)\n {\n _sortedCollection = Enumerable.Range(0, count).ToList();\n _unsortedCollection = Enumerable.Range(0, count).ToList();\n _unsortedCollection.Shuffle();\n }\n\n public int SortedSumLessThan(int threshold)\n {\n var sum = 0;\n\n for (int i = 0; i < _sortedCollection.Count; i++)\n {\n var element = _sortedCollection[i];\n if (element < threshold)\n sum += element;\n }\n\n return sum;\n }\n\n public int UnsortedSumLessThan(int threshold)\n {\n var sum = 0;\n\n for (int i = 0; i < _unsortedCollection.Count; i++)\n {\n var element = _unsortedCollection[i];\n if (element < threshold)\n sum += element;\n }\n\n return sum;\n }\n}<\/code><\/pre>\n\n\n\nTo measure the branch misprediction slow down I’ve created BranchMispredictionExecutor<\/code> class. The class has sorted and unsorted collection: _sortedCollection<\/code> and _unsortedCollection<\/code>. There’re also two methods: SortedSumLessThan<\/code> and UnsortedSumLessThan<\/code>. First one sums elements from the sorted collection that are less than a passed argument. Second one does the some but against unsorted collection. The collections consist of the same elements. The only difference is the order, hence the methods’ returned value is always the same.<\/p>\n\n\n\nWARNING: In C#, at least at the time of writing this post, there’s not a method to shuffle a collection. The above Shuffle()<\/code> method is a custom implementation taken from this post<\/a>.<\/p>\n\n\n\nYou might ask what is the point of iterating through a sorted\/unsorted collection. Well, the key point is the if (element < threshold) <\/code>but let’s see the benchmark first and then go to the explanation.<\/p>\n\n\n\nBenchmark<\/h1>\n\n\n\n
The benchmark code looks like this:<\/p>\n\n\n\n
public BranchMispredictionExecutorBenchmarks()\n{\n _executor = new BranchMispredictionExecutor(_size);\n}\n\n[Benchmark]\npublic void SortedSumLessThan()\n{\n var sum = _executor.SortedSumLessThan(_size \/ 2);\n}\n\n[HardwareCounters(HardwareCounter.BranchMispredictions, HardwareCounter.BranchInstructions)]\npublic class BranchMispredictionExecutorBenchmarks\n{\n private readonly BranchMispredictionExecutor _executor;\n private readonly int _size = 100000;\n\n public BranchMispredictionExecutorBenchmarks()\n {\n _executor = new BranchMispredictionExecutor(_size);\n }\n\n [Benchmark]\n public void SortedSumLessThan()\n {\n var sum = _executor.SortedSumLessThan(_size \/ 2);\n }\n\n [Benchmark]\n public void UnsortedSumLessThan()\n {\n var sum = _executor.UnsortedSumLessThan(_size \/ 2);\n }\n}<\/code><\/pre>\n\n\n\nComparison of execution time of the aforementioned methods looks quite impressive:<\/p>\n\n\n\n
![\"\"](\"https:\/\/baldsolutions.com\/wp-content\/uploads\/2022\/03\/image-7.png\")
<\/figure><\/div>\n\n\n\nAs the results present, the sorted array turns out to be much faster (~6.3 times faster) than the unsorted one. What is more (as expected), the unsorted array caused great amount of branch mispredictions and therefore the execution time was so slow.<\/p>\n\n\n\n
Explanation<\/h1>\n\n\n\n
It is high time to go back to the if (element < threshold)<\/code>. You can think of the if<\/code> statement as of the branch instruction (but at processor level). When it comes to the sorted collection the _executor.SortedSumLessThan(_size \/ 2)<\/code> iterated through the collection of the consecutive elements, i.e. 0, 1, 2, … , 99999. The for<\/code> loop summed first 50000 elements because all of them were less than passed argument, i.e. 50000 (_size\/2<\/code>) So, first 50000 if<\/code> evaluations were the same (resulted true<\/code>), thus the processor were able to predict correctly the consecutive executions. On the other hand, unsorted collection didn’t have such a predictive flow. Due the unsorted array the processor weren’t able to correctly predict the consecutive executions as it happened for the sorted collection.<\/p>\n\n\n\nSummary<\/h1>\n\n\n\n
To sum up, branch misprediction is definitely low level stuff. Presented example was written in C# but of course it applies to other programming languages as well. It is processor-realted feature, which is definitely lower in the abstraction hierarchy. Benchmark results showed that the execution time might me much faster, even if the methods looks the same at first glance. If you are interested in performance counters in BenchmarkDotNet I recommend to read this post<\/a>.<\/p>\n\n\n\nAs always I’ve prepared an example and you can find it on my github<\/a>, project: branch-misprediction<\/a>, benchmark project: branch-misprediction-benchmark.<\/a> I encourage you to go through the code, debug it and try to test your own scenarios.<\/p>\n\n\n\nHave a nice day, bye!<\/p>\n","protected":false},"excerpt":{"rendered":"
Introduction Branch misprediction, as title suggests, might slow down program execution time. If you have never heard about the topic I recommend to read the…<\/p>\n