RE: Copying DOM NodeLists to genuine JS Arrays - Performance

My first thought whenever anyone wants to improve performance is to ensure
that everything you're touching the DOM as little as possible.  Judging by
what you've done here, though, it seems you've got that pretty well figured
out.

Not sure if this helps, but sometimes you can get a faster Duff's device by
converting your "while" decrement to a "do while" pre-decrement, sorta like
so:

Array.appendNodeList64(array, tags) {
    // Modified Duff's Device (Tom Duff, Kendra SG, Anon)
    var iterations = tags.length;
    var iTags = iterations - 1;
    var i = iTags + array.length;

    var n = iterations % 64;
    if (n>0) {
        do {
            array[i] = tags[iTags]; i--; iTags--;
        }
        while (--n); // n must be greater than 0 here
    }

    n = Math.floor(iterations / 64);
    do
    {
        array[i] = tags[iTags]; i--; iTags--;
       // 64 of the above line . . .
    }
    while (--n);
}

Note: this is from pp. 235-236 of Andrew B King's "Speed Up Your Site" book.

-ryan

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of
Chris
Sent: Tuesday, March 07, 2006 5:28 PM
To: [email protected]
Subject: [wdf-dom] Copying DOM NodeLists to genuine JS Arrays - Performance

Hi all,

I'm currently working on a script that executes over 7000 tags, in about 
7 seconds.

I analyzed it and determined that the slowest operation was this:

var length = tagsBase.length;
for(var i = 0; i < length; i++)
    tags.push(tagsBase[i]);

In other words, simply copying a DOM NodeList (fetched by 
.getElementsByTagName()) to a legit array.

It took over 4 seconds of the 7 second execution time. Another 2 seconds 
was spent performing a similar operation (with a filter applied).


The solution I applied to optimize it uses Duff's Device:
http://home.earthlink.net/~kendrasg/info/js_opt/jsOptMain.html
(bottom of that page)

I used a 64-wide version of the Modified version - here's a code snippet:

Array.appendNodeList64(array, tags) {
    // Modified Duff's Device (Tom Duff, Kendra SG, Anon)
    var iterations = tags.length;
    var iTags = iterations - 1;
    var i = iTags + array.length;

    var n = iterations % 64;
    while (n--)
    {
        array[i] = tags[iTags]; i--; iTags--;
    }
       
    n = Math.floor(iterations / 64);
    while (n--)
    {
        array[i] = tags[iTags]; i--; iTags--;
       // 64 of the above line . . .
    }
}


The Duff's Device improved performance as follows:

Firefox:
push of 7000 elements without: 4.28s
push of 7000 elements with: 2.08s

So that's pretty significant.

Of course, a simple Array.concat() of 7000 elements occurs in something 
like .2s, and I really wish I could hit a performance number closer to 
that - even 2s wasted on this trivial copy seems silly.

What performance tricks have others found to speed up this operation?

Thanks,
-Chris "SoopahMan" Moschini


Unsubscribe
[email protected]

List info
http://www.quirksmode.org/dom/list.html 
Yahoo! Groups Links



 





Unsubscribe
[email protected]

List info
http://www.quirksmode.org/dom/list.html 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/wdf-dom/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/