www.webdeveloper.com
Results 1 to 9 of 9

Thread: Speeding loops: why is Duff's device not faster?

  1. #1
    Join Date
    May 2009
    Posts
    127

    Speeding loops: why is Duff's device not faster?

    In all the online examples, the duff's device is 5 times faster than a normal for(...) loop. (See: http://www.websiteoptimization.com/speed/10/10-3.html and look at Duff's Faster15)

    However, in all my tests it's either the same, slightly faster or slightly slower than a normal loop. What am i doing wrong?

    NOTE: This is a full HTML page that will show this issue (I usually get 110 for the normal loop and 98 for the Duff loop, but not always):
    Code:
    <html>
        <head>
            <script type="text/javascript">
            
            //Our test object
            function Something(name)
            {
                if ( name ) this.name = name;
            }
            
            Something.prototype =
            {
                doSomething : function(somethingObject)
                {
                    somethingObject.name = this.name;
                },
                
                callDoSomething : function(somethingObjects)
                {
                    for ( var i = 0; i < somethingObjects.length; i++ ) this.doSomething( somethingObjects[ i ] );
                },
                
                callDoSomethingDuff : function(somethingObjects)
                {
                    var numIterations = somethingObjects.length;
                    
                    //The currentIndex in our loop
                    var currentIteration = 0;
                    
                    //Current amount of the loop we're doing
                    var loopLength = numIterations % 15;
                    
                    //Do the remainder number of iterations
                    if( loopLength > 0 )
                    {
                        do
                        {
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                        }
                        while ( --loopLength );
                    }
                    
                    //The number of iterations that are multiples of 15
                    loopLength= parseInt(numIterations / 15);
                    
                    //Run all leftover iterations
                    if ( loopLength > 0 )
                    {
                        do
                        {
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                            this.doSomething( somethingObjects[ currentIteration++ ] );
                        }
                        while ( --loopLength );
                    }
                }
            };
            
            function TestNormal()
            {
                var newObject = new Something( "Don" );
                var somethings = [];
                for ( var i = 0; i < 100000; i++ ) somethings[ i ] = new Something();
                var start = new Date();        
                newObject.callDoSomething( somethings );
                var end = new Date();
                return ( ( end - start ) );
            }
            
            function TestDuff()
            {
                var newObject = new Something( "Don" );
                var somethings = [];
                for ( var i = 0; i < 100000; i++ ) somethings[ i ] = new Something();
                var start = new Date();
                newObject.callDoSomethingDuff( somethings );
                var end = new Date();
                return ( ( end - start ) );
            }
            </script>
        </head>
        <body>
            <script type="text/javascript">
                var str = TestNormal();
                str = str + "," + TestDuff();
                alert( str );
            </script>
        </body>
    </html>

  2. #2
    Join Date
    May 2009
    Posts
    150
    It's likely that all the code you're running in the loop is significantly slower that the performance gains from the alternate loop, making them almost unnoticeable.

  3. #3
    Join Date
    May 2009
    Posts
    127
    Quote Originally Posted by Y_Less View Post
    It's likely that all the code you're running in the loop is significantly slower that the performance gains from the alternate loop, making them almost unnoticeable.
    So is there anything that can speed up my loops? Or am I stuck with what I have now? I mean, the example you see above is pretty simple so if that negates any benefit of Duff's device then it's a useless "device".

  4. #4
    Join Date
    Jul 2008
    Location
    urbana, il
    Posts
    2,787
    your loop does nothing:
    the only thing looped is "somethings[ i ] = new Something();"

    your timing code never get reached, so it won't display much diff between any given test.

    in general, you need to balance the conditionals and the workload to best optimize loops. depending on the task, there is a runtime trough that appears between no folds and no loop.

    Just because it doesn't seem to work for you, don't assume Duff device is useless.
    Loop folding yields significant increases in IE's engine, though firefox is so optimized and early that it doesn't much matter.

  5. #5
    Join Date
    May 2009
    Posts
    127
    Quote Originally Posted by rnd me View Post
    your loop does nothing:
    the only thing looped is "somethings[ i ] = new Something();"

    your timing code never get reached, so it won't display much diff between any given test.
    What do you mean by this? How could it not be reached if I'm getting actual time diff's?

    Also, you have the code wrong. inside my loop is the following:

    1. A function call: this.doSomething( somethingObjects[ i ] );
    2. Two "dot-lookups" somethingObject.name and this.name
    3. An assignment: somethingObject.name = this.name;

    So I'm not sure what you mean.

    Quote Originally Posted by rnd me View Post
    ... though firefox is so optimized and early that it doesn't much matter.
    I tried it in firefox and opera, but mostly firefox.

  6. #6
    Join Date
    Jul 2003
    Location
    The City of Roses
    Posts
    2,503
    6tr6tr, you should look at the source for the WebSiteOptimization page and notice that the only thing they're doing in their loops is a simple increment. If you change your loops to do the same -- that is, replace "somethings[ i ] = new Something();" with "someVar++" or some such -- then you'll start seeing some significant time differences.

    What this means is exactly as Y_Less said, that while the performance is technically improved with Duff's device, the difference is too insignificant to be noticeable.
    for(split(//,'))*))91:+9.*4:1A1+9,1))2*:..)))2*:31.-1)4131)1))2*:3)"'))
    {for(ord){$i+=$_&7;grep(vec($s,$i++,1)=1,1..($_>>3)-4);}}print"$s\n";

  7. #7
    Join Date
    May 2009
    Posts
    127
    Quote Originally Posted by Jeff Mott View Post
    6tr6tr, you should look at the source for the WebSiteOptimization page and notice that the only thing they're doing in their loops is a simple increment. If you change your loops to do the same -- that is, replace "somethings[ i ] = new Something();" with "someVar++" or some such -- then you'll start seeing some significant time differences.

    What this means is exactly as Y_Less said, that while the performance is technically improved with Duff's device, the difference is too insignificant to be noticeable.
    I got that, which is why I said that duff's device is useless if that's the case.

  8. #8
    Join Date
    Jul 2003
    Location
    The City of Roses
    Posts
    2,503
    Sorry. It seemed like you found it hard to believe and were looking for additional confirmation. My mistake.
    for(split(//,'))*))91:+9.*4:1A1+9,1))2*:..)))2*:31.-1)4131)1))2*:3)"'))
    {for(ord){$i+=$_&7;grep(vec($s,$i++,1)=1,1..($_>>3)-4);}}print"$s\n";

  9. #9
    Join Date
    Mar 2005
    Location
    Sydney, Australia
    Posts
    7,974
    With the particular situation where Duff's Device was first used it made a significant difference - the difference between operating fast enough to work (using Duff's Device) and being so slow as to be useless. The difference in technology between then and now means that even without using Duff's device the loop operates millions of times faster than the original loop did using it. So while it might be useless now due to the improvements in computer technology it was an essential tool at the time it was first created.

    As a speed comparison consider the situation where 1 represents fast enough to be useful. Where it was first used the numbers would have been perhaps with = 1 and without = .8 while now it is with 1000000.2 and without 1000000.
    Last edited by felgall; 06-01-2009 at 10:21 PM.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles