[webkit-dev] Performance of NamedAttrMap
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...
More information about the webkit-dev