[Webkit-unassigned] [Bug 73853] Inserting nodes is slow due to Node::notifyNodeListsAttributeChanged (20%+)

Tue Dec 20 11:09:01 PST 2011

https://bugs.webkit.org/show_bug.cgi?id=73853

--- Comment #19 from Darin Adler <darin at apple.com>  2011-12-20 11:09:01 PST ---
(In reply to comment #17)
> The bad news is that new profile result indicates our hashmap/hashset may not be as efficient as it should be. In fact, we seem to spend 30-50% of time in hashmap/hashset at the moment. And the time we spend in them increase linearly with respect to the number of nodes inserted.

I’m not sure what performance you are expecting from the HashMap. I believe that reading from it should be somewhere between O(1) and O(log n). Thus reading from it n times should be between O(n) and O(n log n). So if you are saying that time in the HashMap function is linear, that’s exactly what’s expected: O(n).

We can achieve further speed by making a data structure that’s more specialized than a hash table for the operation in question. For example, for the HTML element factory, if we know the frequency of various types of tags, we can do a linear search in an array that is sorted by frequency instead of the hash map or as a first pass before falling back on it.

I find all that time spent in StringImpl::lower() alarming. And I’m quite interested in the WTF::AtomicString::addSlowCase time as well. There’s a lot of juicy interesting things that could possibly be sped up here.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.