sorted array faster than an unsorted array-Thatsjavainfo

Categories: Java // Tags: , .
Email this to someonePrint this pageShare on Google+0Share on Facebook0Tweet about this on TwitterShare on LinkedIn0Share on Reddit0Pin on Pinterest1Share on StumbleUpon0

why sorted array faster than an unsorted array?Here is a Java code which shows that sorting the stored array amazingly makes the code faster than the unsorted array. Let’s try out a below piece of JAVA code to find out the its better.


Output :

examine that time taken for processing a sorted array is less as  unsorted array. The reason for this optimisation for sorted array is branch prediction.

branch prediction ?
In computer architecture, branch prediction means determining whether a conditional branch(jump) in the instruction flow of a program is likely to be taken or not.
All the pipelined processors do branch prediction in some form, because they must guess the address of the next instruction to fetch before the current instruction has been executed.

How branch prediction in applicable on above case ?

The if condition checks that arr[i] < 5000, but if you observe in case of sorted array, after passing the number 5000 the condition is always false, and before that it is always true, compiler optimises the code here and skips the if condition which is referred as branch prediction.

Case 1 : Sorted array

We can observe that it is very easy to predict the branch in sorted array, as the sequence is TTTTTTTTTTTT………FFFFFFFFFFFFF

Case 2 : Unsorted array

It is very difficult to predict that if statement will be false or true, hence branch prediction don’t play any significant role here.

Branch prediction works on the pattern the algorithm is following or basically the history, how it got executed in previous steps. If the guess is correct, then CPU continue executing and if it goes wrong, then CPU need to flush the pipeline and roll back to the branch and restart from beginning.

In case compiler is not able to utilise branch prediction as a tool for improving performance, programmer can implement his own hacks to improve performance.

Email this to someonePrint this pageShare on Google+0Share on Facebook0Tweet about this on TwitterShare on LinkedIn0Share on Reddit0Pin on Pinterest1Share on StumbleUpon0

About Team

Browse Archived Articles by Team