JavaScript DOM Iteration and Date Function Optimization #

Short Version

Instead of row[k], use nextSibling to iterate between table rows in Safari and Firefox. Firefox has slow date functions; cache values whenever possible. Setting node values by using a template node subtree that you cloneNode, modify and insert is faster in Firefox and MSIE whereas setting the innerHTML property is faster in Safari.

Long Version

For my primary ongoing proto-project, I needed to do some transformations on a table's contents, to make them more human-readable. Specifically, I was iterating over all of its rows, picking a cell out of each one, extracting its contents (a date in the form of seconds from the Epoch), converting the timestamp to a nice human-readable string form, and replacing the cell's contents with that.

This all sounds very simple (and it was indeed easy to code up), but the performance I was seeing was not all that impressive. Specifically, here are the runtimes (in milliseconds) on a table with 674 rows in the three browsers that I usually test with:

Safari:1649.9 Firefox:2578.6 MSIE:618.9

Safari refers to the 1.3 beta release with the faster JavaScript implementation while Firefox is the standard version 0.9.1 and IE is of course Microsoft Internet Explorer 6.01. The first two browsers are running on 1 GHz TiBook, while IE was tested on a 1 GHz Centrino laptop.

The hardware may not match exactly, but we are (hopefully) looking for performance differences on the order of tens of percents, not the 2-4x difference that we see in the above times. I decided to investigate further, by trying to see how much time was spent just doing the iteration. This was a very simple traversal of the following manner:

for (var i=0; i < itemsTable.rows.length; i++)
    for (var j=0; j < itemsTable.rows[i].cells.length; j++)

(I am paraphrasing a bit, but performance characteristics were similar even when caching the two length values). Taking out the call to the transformation function, but leaving in a dummy assignment like var k = itemsTable.rows[i].cells[j] to make sure that all relevant table cells were accessed resulted in the following runtimes (the iteration was repeated ten times to reduce issues with timer accuracy, times presented are still per run and thus directly comparable to those above):

Safari:893.9 Firefox:667.1 MSIE:37.1

As it can be seen, Safari spends half its time just iterating over the elements, while Firefox needs a fifth of its longer runtime for the same task. Only in MSIE's case does the iteration represent a negligible portion. This prompted me to evaluate a different iteration method, one that moves from row to row and from cell to cell using a node's nextSibling property, like this:

for (var row = itemsTable.rows[1]; row != null; row = row.nextSibling)
    if (row.nodeType == 1)
        for (var cell = row.firstChild, i = 0; cell != null; cell = cell.nextSibling)
            if (cell.nodeType == 1)

(The nodeType == 1 comparison is needed since whitespace between rows/cells may be included as text nodes, whose type is 3.) This code snippet (again with the call to the transform function suppressed) resulted in:

Safari:40.0 Firefox:170.0 MSIE:38.9

MSIE is barely affected, while Safari and Firefox see very significant improvements. I'm guessing that the IE JavaScript/DOM implementation is optimized for the row[k] access method as well (perhaps by pre-computing the array when the DOM tree was generated) whereas the other two browsers simply step along k times through the linked list of nodes, every time there's a index request. A bit more digging would reveal whether Firefox and Safari have an N2 behavior for various table sizes, confirming that this was the case. At any rate, this significantly sped up the overall processing time, and now the bottleneck was the actual transformation that the function was doing. To see where it was spending its time, we ran it so that it just did the timestamp to string computation, as compared to doing the DOM operations as well (getting the cell's contents and later replacing them):

Iteration and Computation

Safari:208.1 Firefox:941.6 MSIE:95.1

Iteration, Computation and DOM Operations

Safari:550.3 Firefox:2081.7 MSIE:620.7

It seems that Safari and IE spend more time with DOM operations, while in Firefox's case the split is more even. As a quick change to help with the DOM issue, I changed the way I obtained the cell's contents. Rather than getting its innerHTML property, which presumably requires the browser to reconstruct the text from the node hierarchy, we rely on the fact that we know the cell's contents are plain text, and thus we can get its value directly with cell.firstChild.nodeValue. Running with this code gets us:

Safari:522.7 Firefox:2041.0 MSIE:587.7

A small (and reproducible) improvement, but not significant perceptually. I next decided to focus on the date operations themselves. The string conversion is done in two parts, one for the date and one for the time. In my application's case, it is likely that the same date will appear several times, therefore it makes sense to cache the strings generated for that, and reuse them in later iterations instead of recomputing them. With this particular dataset, the hit rate of this cache was 86.7%. Running the entire thing, we get:

Safari:474.3 Firefox:1839.7 MSIE:571.0

Firefox is helped the most, confirming the previous observation that its date functions are slow. I then realized that once I created a date object, I kept making calls to its accessor functions (getMonth(), getFullYear(), etc.) The small tweak of making these calls only once and remembering their values for later comparisons resulted in:

Safari:463.3 Firefox:1548.3 MSIE:571.0

Firefox is significantly helped yet again, and now for it too, the DOM operations dominate the runtime. As a final attempt in tweaking them, I tried a different approach when changing the cell's contents. Normally, I don't just get the resulting date string and use it; rather the date and time portions are put into different <span>s, aligned on opposite sides of the cell. Rather than generating these spans by setting the innerHTML property of the cell and letting the browser parse out the DOM tree, I attempted to create the sub-tree directly. I first created a static "template" subtree at initialization time. Then, when it came time to set the cell's contents, I made a (deep) copy of this template subtree by using cloneNode and replaced the values of its two text nodes with the strings. Finally, I replaced the original text child of the cell with this new sub-tree. Timing this resulted in:

Safari:805.0 Firefox:1483.0 MSIE:433.7

For the first time we see an optimization that hurts one browser (Safari) while helping the two others (Firefox and MSIE), to significant degrees in both cases. In my case, I decided to simply revert back to the innerHTML method, but it may be worth it to actually support both methods and switch based on the user's browser.

Finally, here are the percentage speedups that all of the tweaks brought (using the fastest time for each browser):

Safari:256% Firefox:74% MSIE:43%

I must say, I'm quite impressed with IE's JavaScript implementation, especially considering how many (perceived) issues there are with its other components, like its CSS engine.

Post a Comment