76209 - Style context caches removes elements from the middle of an array

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Daniel Bratell]

Another fallout of profiling the colour table stress case (the style people must 
begin to hate me. :-) ) is that there is a nsVoidArray that is emptied one 
element at a time which causes alot of memmoves which degrades performance when 
pulling down a big style system.

If I understand it correctly StyleContextImpl's destructor 
calls StyleSetImpl::RemoveStyleContext which removes the style from a cache with 
the following code.

  nsVoidArray *pResults = nsnull;
  if (NS_SUCCEEDED(GetContexts(aKey,&pResults)) && pResults) {
     PRUint32 nCountBefore = Count();
     if (nCountBefore > 0){
       if(pResults->RemoveElement(aContext)) {
...

RemoveElement is slow since it requires moving at average half the array in 
memory. When done with all elements we get a nice O(n^2) algorithm.

According to quantify (which I don't trust very much anymore btw) it is 
0.5 seconds when leaving the colour table stress case.

Comment 1

[Daniel Bratell]

rjesup, here is another array related bug.

Comment 2

[Pierre Saslawsky]

The cache is gone since the rule tree landing (bug 78695).
Marked fixed.