72217 - nsVoidArray::IndexOf called in StyleContextCache::AddContext is accounting for too much time in some cases

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect, P2)

Description

[Marc Attinasi]

In the code below, IndexOf is called to ensure that the item is not already in
the list, however it gets pretty expensive in cases where there are lots of
entires in the list, and since the assertion
  NS_ASSERTION(pList->IndexOf(aContext) == -1, "Context already in list");
is never triggered, it is probably best to remove the check in non-debug builds.

nsresult StyleContextCache::AddContext(scKey aKey, nsIStyleContext *aContext)
{
  // verify we have a list
  nsresult rv = VerifyList(aKey);
  if (NS_SUCCEEDED(rv)){
    nsVoidArray *pList = GetList(aKey);
    NS_ASSERTION(pList != nsnull, "VerifyList failed me!");
    NS_ASSERTION(pList->IndexOf(aContext) == -1, "Context already in list");
    if(pList->IndexOf(aContext) == -1){
              ^^^^^^^ - remove this check
      if (!(pList->AppendElement(aContext))) {
        rv = NS_ERROR_FAILURE;
      } else {
        mCount++;
      }
      DumpStats();
    } else {
#ifdef DEBUG
      printf( "Context already in list in StyleContextCache::AddContext\n");
#endif
      rv = NS_ERROR_FAILURE;
    }
  }
  return rv;
}


In a testcase with lots of unique style contexts (like one from bug 67692, to be
attached here) this IndexOf call accounts for almost 20% of the time in style
sharing.

Comment 1

[Marc Attinasi]

Attachment: Testcase from bug 67692: loads of table cells each with a different bgcolor causes a horrendous amount of style context instances

Comment 2

[Marc Attinasi]

Quantify shows that out of 8 seconds in style resolution on the attached
testcase, 1.4 is spent in nsVoidArray::IndexOf coming out of AddContext - seems
like a waste.

CC'ing some smart folks for opinions (or flames, or smelly fish).

Comment 3

[Chris Waterson]

Sounds good to me! What would happen if two ended up in the list after all?

Comment 4

[Marc Attinasi]

I'm not sure, but there is clearly an assumption that the entries in the list
are unique. I think that having multiple entries for a context in the list is
really just a symptom of something more heinous happening, like not being able
to find an entry in the first place. If there were two, then returning the
'wrong' one shouldn't really matter since they are, well, the same object instance.

I think this is a case of me over-protecting the preconditions of an internal
method... bad doggy. The assertion should definitely be enough to enforce the
contract here.

Comment 5

[Peter "jag" Annema]

r=jag if you want it :-)

Comment 6

[Marc Attinasi]

Attachment: Patch: -uw

Comment 7

[Marc Attinasi]

Patch is attached, needs sr=

Comment 8

[Brendan Eich [:brendan]]

sr=[e-mail] -- I'm curious to know the cause of the "duplicates",
even if benign (before I go klutzing around trying to squeeze out nsHashtable
and nsVoidArrays via pldhash here).

/be

Comment 9

[Marc Attinasi]

There are never any duplicates. The check was put in (along with an assertion
which is staying) to catch incorrect usage. Since it causes a performance
problem, I am removing the runtime check for duplicates and relying on the
assertion to cath them. However, I have never seen this assertion. 

Comment 10

[Marc Attinasi]

Fixed: nsStyleSet.cpp ver 3.85

Comment 11

[Daniel Bratell]

*** Bug 68030 has been marked as a duplicate of this bug. ***

Comment 12

[Madhur Bhatia]

verified as per comments