[webkit-dev] Performance of NamedAttrMap

Maciej Stachowiak mjs at apple.com
Thu Oct 29 15:25:30 PDT 2009

On Oct 29, 2009, at 2:30 PM, Jens Alfke wrote:

> I was looking at the performance of Element.getAttribute(), and I  
> see that NamedAttrMap, which actually stores the attributes, is  
> implemented as an unsorted array. This makes looking up an attribute  
> an O(n) operation. Is there any reason this couldn't be optimized to  
> use a HashMap, or at least binary search?
> (I thought the answer might be that the order of attributes is  
> significant; but I just checked the DOM spec, and NamedNodeMap is  
> explicitly unordered.)

By far the most common case is that Elements have relatively few  
attributes (<6). This means that a hybrid strategy (unsorted array for  
a few attributes, HashMap for more than some threshold) might be  

a) With very few attributes, you minimize memory use, and the linear  
scan is not really slower than a hash lookup.
b) Because in practice very few elements have lots of attributes, the  
greater memory consumption of the HashMap will not be a significant  
cost on average.

The downside is that the likely inserts a branch into the common case,  
relative to what we have now, the benefit is that it's scalable to  
huge numbers of attribtues.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20091029/b31a5815/attachment.html>

More information about the webkit-dev mailing list