Branch Prediction

This post is about hardware related optimization.

Let’s take an example. we will take two Lists (one sorted and other unsorted) and do same processing on it and see the benchmark.

as you can see branch method(one with sorted list) executed faster compared to normal method( one with unsorted list).

Reason?

Because array is sorted ? partially true.

The main reason is branch prediction. Modern hardware architecture has component called as branch predictor which predicts instructions pipeline. When it is processing IF statement with sorted list it is able to predict/anticipate next thing in pipeline but when working with unsorted list it has to flush things in pipeline.

I hope now when working with List and adding IF statement or any processing on array or collection , you will be little careful. ☺