[webkit-dev] Performance of NamedAttrMap

[Maciej Stachowiak]

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  
successful:

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.

Regards,
Maciej

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