Avoid if/ else within loop

Yes, this post is about the most basic concept that using if/ else should be avoided within loop as much as possible. Optimizing code is always important and when it’s about performance then the basic efficiency rules should be followed at first. Practically there are many situations when a loop iterates over large data set e.g. 1m; there may be different required computation in the same loop- but if possible the loop should maintain branch prediction; avoid unnecessary if/ else.

Following simple rules lead to performance advantage certainly. Branch prediction is a simple concept to optimize a loop-

Branch predication– the very basic reason of processing a sorted array is faster than an unsorted array. There are many good references already available about it, that’s why I’m not elaborating about the same. A good read- processing a sorted array is faster than an unsorted array

Avoiding if/ else in loop leads to performance benefit. If possible, avoid that, consider loop-invariant code motion. But when if/ else is unavoidable in the loop, alternatives may be applied- like splitting the same loop or using bitwise operator etc. There are different possible scenarios when dividing a loop in multiple blocks is beneficial than keeping if and computing the logic in a single loop.

Have a look at this most simple code block to realize the difference and advantages I’m talking about-

<?php
$sortedSet = range(1, 1000000);
$randomSet = $sortedSet;
shuffle($randomSet);

$cnt = count($sortedSet);
$filter = $cnt / 2;

//sorted set processing
$startTimeSortedSet = microtime(true);
for ($i = 0, $sum = 0, $sum1 = 0; $i < $cnt; $i++) {
    if ($i >= $filter) {
        $sum += $sortedSet[$i];
    } else {
        $sum1 += $sortedSet[$i];
    }
}
$endTimeSortedSet = microtime(true);

//removed if/else from sorted set
$startTimeSplitSortedSet = microtime(true);
for ($i = ($cnt - 1), $sum = 0; $i >= $filter; $i--) {
    $sum += $sortedSet[$i];
}

for ($i = 0, $sum1 = 0; $i < $filter; $i++) {
    $sum1 += $sortedSet[$i];
}
$endTimeSplitSortedSet = microtime(true);

//random set processing
$startTimeRandomSet = microtime(true);
for ($i = 0, $sum = 0, $sum1 = 0; $i < $cnt; $i++) {
    if ($i >= $filter) {
        $sum += $randomSet[$i];
    } else {
        $sum1 += $randomSet[$i];
    }
}
$endTimeRandomSet = microtime(true);

//removed if/else from random set
$startTimeSplitRandomSet = microtime(true);
for ($i = ($cnt - 1), $sum = 0; $i >= $filter; $i--) {
    $sum += $randomSet[$i];
}

for ($i = 0, $sum1 = 0; $i < $filter; $i++) {
    $sum1 += $randomSet[$i];
}
$endTimeSplitRandomSet = microtime(true);

echo "\nsorted set processed in " . ($endTimeSortedSet - $startTimeSortedSet) . "s\n";
echo "\nsplit sorted set processed in " . ($endTimeSplitSortedSet - $startTimeSplitSortedSet) . "s\n";
echo "\nrandom set processed in " . ($endTimeRandomSet - $startTimeRandomSet) . "s\n";
echo "\nsplit random set processed in " . ($endTimeSplitRandomSet - $startTimeSplitRandomSet) . "s\n";

Results

sorted set processed in 0.1187698841095s

split sorted set processed in 0.085871934890747s

random set processed in 0.31727719306946s

split random set processed in 0.28484988212585s

So the conclusion is

i) Processing a sorted set is faster.
ii) When if/ else is removed by splitting 2 blocks, the same set processing speed gained over 28% approx.
ii) Random set is taking longer time due to branch prediction failing.
iv) The same random set can be processed faster, if the process is divided. Gain is almost 10% than the previous logic.

Simple but useful, right?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s