Need to speed up loops - dramatically? Try Duff's Device

Raven · Posted: Mon Nov 24, 2003 7:26 am

In my journeys this week I came across a neat and nifty little routine known as Duff's Device. You can read about the origin

Only registered users can see links on this board!
Get registered or login to the forums!

.
I will provide a PHP equivalent here to demonstrate the dramatic performance gain. Here is the script I wrote to test 5,000,000 iterations

Code:

<?
function Bench(){
//set the number of iterations
$iterations = 5000000;
$testVal = 1;
for ( $n = 0; $n < $iterations; $n++) {
   $testVal++;
}
return($testVal);
}

function getmicrotime(){
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}

function DuffsDeviceBench(){
//set the number of iterations
$iterations = 5000000;
$testVal = 1;
$n = $iterations % 8;
while ($n--) $testVal++;
$n = (int) $iterations / 8;
while ($n--) {
   $testVal++;
   $testVal++;
   $testVal++;
   $testVal++;
   $testVal++;
   $testVal++;
   $testVal++;
   $testVal++;
}
return($testVal);
}

$time_start = getmicrotime();
$testVal = Bench();
$time_end = getmicrotime();
$time = $time_end - $time_start;
echo 'Standard Loop = '.$time.' -- '.$testVal;

$time_start = getmicrotime();
$testVal = DuffsDeviceBench();
$time_end = getmicrotime();
$time = $time_end - $time_start;
echo '<br /><br />In-Line Loop = '.$time.' -- '.$testVal;
?>

Here are the results

Code:

Standard Loop = 8.4020010232925 -- 5000001

In-Line Loop = 2.4259361028671 -- 5000001

A 6 second gain!

I then ran it for 50,000,000 iterations

Code:

Standard Loop = 84.608292937279 -- 50000001

In-Line Loop = 24.540007948875 -- 50000001

A 60 second gain! Obviously this is for large transaction handling/looping. But even on a smaller scale you still will see comparable results.

bugsTHoR · Worker Joined: Apr 05, 2006 Posts: 172

what is looping for in PHP , if ya don`t mind me asking, need to speed my site up

i put this code in ht.access

php_value memory_limit 50M

Both me and my members have noticed the difference , still need it quicker for some reason.

gregexp · Posted: Thu Jul 13, 2006 5:23 pm

Looping is when a script will run through a set of code until something is set to false or no further results can be gained.

For example

$x=15;

While($x>=1){
$x=$x-1;
echo $x;
}

this script will output
14
13
12
and so on till it reaches 1
and will stop there, then go onto the next code,

One other form of looping is to use list
Hope this helps you understand.

evaders99 · Moderator Joined: Apr 30, 2004 Posts: 2796

Looks like what its doing is essentially a form of loop unrolling. It is helpful in messy loops especially, where it is much easier to unroll the loop into seperate code lines. The assembly code will optimize it better.

In this specific case, I believe optimization is obtained because
$testVal++;
is detected to be used 8 times.
The compiler will see this and say hey, "that's just $testVal = $testVal + 8;" done once
So that's what it does Smile

I could be wrong, but that's my understanding of most compilers. I don't know if PHP works that way to do code optimizations.

bugsTHoR · Worker Joined: Apr 05, 2006 Posts: 172

is this added to raven distro 2.02.20 btw ?

and if not where would i put it ?

my site needs speeding up alot and the 50mb line in .htaccess works some but still
it`s slow still.

what could i use it for and a working example here would be muchly apreciated. thx

evaders99 · Moderator Joined: Apr 30, 2004 Posts: 2796

This is sample code and not something directly that can be used in RavenNuke

Really the code cannot be optimized much further. For significant performance gains, install a cache system or upgrade your web/database server