210550 - avoid callback functions in GetStyleData

Status: RESOLVED FIXED

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

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

For bug 87229 we converted switch statements into jump tables.  However, jump
tables are also slow because of pipeline halts and cache misses.  So here's an
attempt to hand-write the code that a good compiler (I think) would optimize the
switch statement into -- a tree of tests.

We should test to see if this improves performance...

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 1.0

Comment 2

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 126393 [details] [diff] [review]
patch 1.0

r+sr=me; worth seeing how this does.

Comment 3

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

My own performance tests showed:

baseline:
    Test id: 3F0B784C35
    Avg. Median : 432 msec      Minimum     : 191 msec
    Average     : 431 msec      Maximum     : 1282 msec
                                                                                
    Test id: 3F0B7C5BE8
    Avg. Median : 430 msec      Minimum     : 179 msec
    Average     : 429 msec      Maximum     : 1252 msec
                                                                                
    Test id: 3F0B80D8CC
    Avg. Median : 428 msec      Minimum     : 184 msec
    Average     : 430 msec      Maximum     : 1235 msec
                                                                                
with 210550:
                                                                                
    Test id: 3F0B5DDDF0
    Avg. Median : 429 msec       Minimum     : 189 msec
    Average     : 434 msec       Maximum     : 1352 msec
                                                                                
    Test id: 3F0B7A2CC6
    Avg. Median : 425 msec      Minimum     : 176 msec
    Average     : 426 msec      Maximum     : 1258 msec
                                                                                
    Test id: 3F0B7F301C
    Avg. Median : 420 msec      Minimum     : 179 msec
    Average     : 423 msec      Maximum     : 1118 msec

Checked in to trunk, 2003-07-08 20:46 -0700.

Comment 4

[Aleksey Nogin]

This check-in have added a "might be used uninitialized" warning to brad TBox:

+content/base/src/nsRuleNode.cpp:1412
+ `const nsStyleStruct*res' might be used uninitialized in this function

Comment 5

[Boris Zbarsky [:bzbarsky]]

That's a bogus warning, since one of the branches of the if will always be
followed.... <sigh>.

Comment 6

[Brendan Eich [:brendan]]

Put pressure on gcc's keepers to fix its brain-damaged warnings.  If it can
compute data flow graphs in static single assignment form and do fancy-schmancy
graph algorithms to optimize the code, it can bloody well see that there is no
way that this variable could be used before set.

/be

Comment 7

[Aleksey Nogin]

OK, you seem _way_ too quick to blame gcc. The very last "if" is missing an else
- the case of > 19 does _not_ have an assignment!

I ran the code in question through preprocessor and indent. Here is what I got:

const nsStyleStruct *res;
if (aSID < 8) {
  if (aSID < 4) {
    if (aSID < 2) {
      if (aSID == 0) {
        res =...;
      } else {
        res =...;
      }
    } else {
      if (aSID == 2) {
        res =...;
      } else {
        res =...;
      }
    }
  } else {
    if (aSID < 6) {
      if (aSID == 4) {
        res =...;
      } else {
        res =...;
      }
    } else {
      if (aSID == 6) {
        res =...;
      } else {
        res =...;
      }
    }
  }
} else if (aSID < 16) {
  if (aSID < 12) {
    if (aSID < 10) {
      if (aSID == 8) {
        res =...;
      } else {
        res =...;
      }
    } else {
      if (aSID == 10) {
        res =...;
      } else {
        res =...;
      }
    }
  } else {
    if (aSID < 14) {
      if (aSID == 12) {
        res =...;
      } else {
        res =...;
      }
    } else {
      if (aSID == 14) {
        res =...;
      } else {
        res =...;
      }
    }
  }
} else {
  if (aSID < 18) {
    if (aSID == 16) {
      res =...;
    } else {
      res =...;
    }
  } else if (aSID == 18) {
    res =...;
  } else if (aSID == 19) {
    res =...;
  }
}

if (aRuleData->mPostResolveCallback)
  (*aRuleData->mPostResolveCallback) ((nsStyleStruct *) res, aRuleData);
return res;

Comment 8

[Boris Zbarsky [:bzbarsky]]

That's because the case > 19 cannot happen, as a matter of fact (which is why
the warning is bogus).  But it's kinda hard for gcc to know that, granted (note
that I did not imply it should have been able to determine that constraint).

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Well, gcc could be generous and assume, for these warnings, that a variable of
enumerated type can only have the values in the enumeration.

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Actually, though, that wouldn't work here, since we have a length at the end.

However, this is very performance-sensitive code, so we'll just live with the
warning.  After all, gcc says "might".

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: possible warning fix

Comment 12

[Brendan Eich [:brendan]]

Do you need the '} else if (aSID == 19) {' or could that just be '} else {'? 
What about aSID == 17?

I am harsh on gcc because it muffs simpler cases too; I've been living with the
resulting bogo-warnings for years.  Every once in a while someone wants to go
and "fix" them, which is a waste of time and performance penalty we don't want.
 Other compilers (MSVC) do better.  So should gcc.

/be

Comment 13

[Bradley Baetz (:bbaetz)]

brendan: I think that the tree-ssa branch (which also does some value range
propogation) does some of that. Currently gcc doesn't build a grpah with that
sort of detail.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 127379 [details] [diff] [review]
possible warning fix

Hmm.. I guess that works...

Comment 15

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 127379 [details] [diff] [review]
possible warning fix

Checked in to trunk, 2003-07-11 13:43 -0700.

Comment 16

[Aleksey Nogin]

The warning went away, thanks!

Comment 17

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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