|
»
Performance of NamedAttrMap
|
View:
New views
8 Messages
—
Rating Filter:
Alert me
|
 |
Performance of NamedAttrMap
by Jens Alfke-4
::
Rate this Message:
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.) —Jens _______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by Darin Adler
::
Rate this Message:
On Oct 29, 2009, at 2:30 PM, Jens Alfke wrote:
Memory consumption is much greater.
Would make lookups faster but parsing slower.
The DOM specification is not what matters here. Behavior of actual browsers is what determines website compatibility. So you will need to do more research on that. I think there could be some real room for improvement here, but also plenty of opportunity to unwittingly make things worse. -- Darin _______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by Darin Adler
::
Rate this Message:
On Oct 29, 2009, at 2:32 PM, Darin Adler wrote:
> On Oct 29, 2009, at 2:30 PM, Jens Alfke wrote: > >> Is there any reason this couldn't be optimized to use a HashMap > > Memory consumption is much greater. > >> or at least binary search? > > Would make lookups faster but parsing slower. I forgot to mention: I believe the common case for attributes is a very small number of attributes. Having one element with many attributes is quite uncommon. This is one consideration when making improvements and optimizations here. Making sure the pathological case is not terribly slow is good, but we also want the normal case to be super-fast. -- Darin _______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by Yaar Schnitman-2
::
Rate this Message:
I encountered a similar (potential) performance problem with style properties (see CSSMutableStyleDeclaration::findPropertyWithId), which are stored in an unordered vector too.
A potential solution would be to create a HashMap only for elements / style properties with more than K (5+?) attributes, and only when they are first accessed. Such a hashmap will not replace the vector, but just provide an index to it.
On Thu, Oct 29, 2009 at 2:33 PM, Darin Adler <darin@...> wrote:
_______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by David Hyatt
::
Rate this Message:
The order of the properties in both style declarations and in attribute maps is relevant for serialization that conforms to the original declared source order.
dave On Oct 29, 2009, at 4:57 PM, Yaar Schnitman wrote: I encountered a similar (potential) performance problem with style properties (see CSSMutableStyleDeclaration::findPropertyWithId), which are stored in an unordered vector too. _______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by David Hyatt
::
Rate this Message:
Experiment with .cssText and .innerHTML to see what I mean.
dave On Oct 29, 2009, at 5:03 PM, David Hyatt wrote:
_______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by Maciej Stachowiak
::
Rate this Message:
On Oct 29, 2009, at 2:30 PM, Jens Alfke wrote:
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 _______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
|
|
Re: Performance of NamedAttrMap
by Maciej Stachowiak
::
Rate this Message:
On Oct 29, 2009, at 3:03 PM, David Hyatt wrote:
I think this is a standards compliance issue for style declarations (besides serialization there is an API to traverse them in order) but for attributes I don't think it is a compatibility issue in practice to give the original declaration order. Could be wrong though. If that does turn out to be necessary then a data structure like ListHashMap could provide fast associative access but also preserve order. That's even more memory overhead than a regular HashMap though. Regards, Maciej
_______________________________________________ webkit-dev mailing list webkit-dev@... http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev |
| Free embeddable forum powered by Nabble | Forum Help |
