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

[bugzilla-daemon at webkit.org]

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





--- Comment #21 from Ryosuke Niwa <rniwa at webkit.org>  2011-12-20 11:41:06 PST ---
(In reply to comment #19)
> (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).

No, what I'm saying is that the number of lookup time appears to be increasing with respect to the number of nodes in the hashmap/hashset.

To give you more concrete idea, download https://bug-73737-attachments.webkit.org/attachment.cgi?id=117785 and open it on ToT WebKit. You get results like:

Shallow tree: 88 ms
Deep tree (20+): 93 ms
Deeper tree (50+): 143 ms

Now, reverse the order in which we run tests; e.g. replace lines 44-46 by:
document.getElementById('shallow').innerHTML = repeatTest(0);
document.getElementById('deep').innerHTML = repeatTest(20);
document.getElementById('deeper').innerHTML = repeatTest(50);

Then if you open it again in ToT WebKit, you get results like:

Shallow tree: 104 ms
Deep tree (20+): 84 ms
Deeper tree (50+): 86 ms

There might be some flakes but the overall, this is the trend I get if I repeat the experiment over and over.

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