62895 - pseudo selectors should be processed more efficiently

Status: VERIFIED FIXED

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

Description

[Marc Attinasi]

pseudo selectors are inherently different than tag or attribute selectors. By
treating them differently we could potentially increase the performance of style
resolution, especially for hovering (:hover) and element activation (:active)
changes.

Comment 1

[Hixie (not reading bugmail)]

I have in the past proposed that pseudo-classes and pseudo-elements be hashed
separately. We _never_ need to check the pseudo-element rules unless we are
specifically looking for rules for that pesueo-element. We can *guarentee*, for
example, that a rule ending with the ::before pseudo-element will not match ANY
element. It will only EVER match a node created specifically for the ::before
generated content.

The CSS3 concept that the pseudo prefixes will be '::' and ':' for pseudo-
elements and -classes respectively will allow this classification to be done
automatically without any hardcoding except for before, after, first-line and 
first-letter.

Comment 2

[Hixie (not reading bugmail)]

(again, for the record, that proposal originated from Peter Linss ages ago)

Comment 3

[buster]

It would be nice if someone could quantify the potential savings here.  How much
time do we waste in style resolution trying to match pseudo's?

Comment 4

[Chris Waterson]

hyatt: do you remember where you were seeing this? If so, I'd be happy to be 
quantify bitch and reprofile.

Comment 5

[Marc Attinasi]

Setting target to Mozilla 0.9

Comment 6

[Hixie (not reading bugmail)]

Netscape's standard compliance QA team reorganised itself once again, so taking 
remaining non-tables style bugs. Sorry about the spam. I tried to get this done 
directly at the database level, but apparently that is "not easy because of the 
shadow db", "plus it screws up the audit trail", so no can do...

Comment 7

[chris hofmann]

is the potencial for big win still there???
lets get this marked topperf if someone can get someone can
get good data..

Comment 8

[Marc Attinasi]

Raising priority: major performance issue we need to solve asap.

Comment 9

[David Hyatt]

The problem here lies with pseudoclasses.

As I've mentioned before, rules are hashed into four categories:
universal
tag
class
id

A selector with a pseudoelement is treated (by our system) as a synthetic tag
linked by a child combinator.  In other words, you can think of a rule like:

outlinerbody::-moz-outliner-row

as being equivalent to

outlinerbody > ::-moz-outliner-row

as far as our style system is concerned.  That means that a pseudoelement rule
is *always* hashed into only the tag-based section.

Therefore a pseudoelement will only be examined for rules where no tag is specified.

The real problem is with pseudoclasses.  When matching, we walk the selectors
from right to left.  A pseudoclass is just an adornment of some existing
selector, e.g.,

[hidden="true"]:active

is an attribute selector with a pseudoclass adornment.  Our selector matches
function examines the pseudoclass *last* in all cases.  This is the part that I
think is incorrect.

Some of the pseudoclasses should instead be examined *first*... in particular
:hover, :active, :focus, and anything that is extremely cheap to test and
extremely likely to eliminate a majority of content nodes.

To illustrate my point, consider this rule:

[bah="true"][foopy~=baz]:hover {}

For the above rule, we'll examine both the bah and foopy attrs before testing
:hover.  Moreover, this rule will be walked by *every single element in our UI
or web page*, since it's universal.

If we'd checked for :hover up front, we would quickly have eliminated 99% of all
elements, and we'd never have wasted any time fetching the attributes.

I propose that we split pseudoclasses into two categories: those that are cheap
to match, and those that are more expensive to match.  The cheap pseudoclasses
should be checked at the top of SelectorMatches, and the expensive ones should
be checked at the bottom as before.

Even simply doing this for the event pseudos would probably take care of the
problem.  We already have a helper, IsEventPseudo(), that can be used to
identify only the event pseudos.

Comment 10

[David Hyatt]

Attachment: Whooah! The chrome gets zippier with this baby.

Comment 11

[David Hyatt]

This patch makes the pseudoclass check happen right after the tag check and
before the attribute, id, and class checks.  The chrome gets zippier with this
patch, since we have a lot of complex :hover, :active, and :focus rules in which
we waste time examining attributes, ids, and classes for rules that don't apply.

In effect, for widgets, we're examining 1/3 the rules we used to, since 2/3 are
being eliminated quickly based off the lack of a pseudo.

Comment 12

[Marc Attinasi]

Man, that patch file is evil (context is blown) but if it does what I think it
does, namely just move the pseudoclass checks up a bunch, then I think it is
pretty smart. I'm gonna apply it and check it out...

Comment 13

[Hixie (not reading bugmail)]

Two comments:
 1. Let's make sure we have ample comments in the source explaining that the 
    order of matching is important!
 2. Based on Hyatt's explanation, it seems to me we should examine all the
    matching stuff, and sort the order of the matching based on how long it
    takes to do each match. e.g. if attributes can be checked faster than
    elements, we should do attributes before elements.
How does that sound? After the pseudo-class check move, are we already there?

Comment 14

[David Hyatt]

Good idea.  We should shuffle the order even more.  Right now with my patch the 
order has become:

TAG
PSEUDO
ATTRIBUTE
CLASS
ID

The order should actually be IMO

TAG
PSEUDO
CLASS
ID
ATTRIBUTE

Attributes and IDs both involve a string compare of an attribute, so they are 
the slowest.  Pseudos are usually lightning fast, and so are tags and classes.  
All three of these involve pointer compares or bit tests.

Comment 15

[David Hyatt]

Attachment: Patch to reorder checks and to optimize the obtaining of the ID for a content element

Comment 16

[David Hyatt]

Disregard the second patch.  It isn't worth it.  You already only examine 
hashes on class and ID, so they're very likely to match your rule anyway.  This 
makes any further reordering somewhat pointless.  The first patch is good 
enough.

Comment 17

[Mike Shaver (:shaver emeritus)]

(Note to would-be testers: the patch that hyatt attached has windows line
endings, so Unix -- and maybe Mac -- users will have to remove them before
applying.  dbaron RU£3Z.)

Comment 18

[Daniel Glazman (:glazou) (not active in Mozilla any more)]

You could even use the following order, from most to less specific.
ID being extremely specific : IDs are unique in the document instance... So most 
of selectors containing an ID selector are false conditions, no need to go 
further.

ID
TAG
PSEUDO
CLASS
ATTRIBUTE

Comment 19

[Daniel Glazman (:glazou) (not active in Mozilla any more)]

I am unable to apply patch on a recent build due to conflicts.

Comment 20

[David Hyatt]

The first patch is fine.  Rules are hashed on id, tag, and class, so the rules
you end up walking are extremely likely to match in those categories.  As I
said, shuffling the order of anything other than pseudos had zero impact on
performance, and if it had zero impact on performance in chrome, it will have
zero impact on CSS in Web pages as well.

It's just the pseudo check that is a problem here.

Comment 21

[Brendan Eich [:brendan]]

There is interest in getting this bug's first patch into 0.8.1, but we are short
on time.  We need r=, sr=, and a driver's a=.  Please record reviewer stamps of
approval here, and soon!

/be

Comment 22

[Marc Attinasi]

Yea Baby! [s]r=attinasi (and double-plus-thanks to David)

BTW: this should land on the trunk too IMO...

Comment 23

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

r=dbaron on attachment 27915 [details] [diff] [review]

Comment 24

[Christopher Blizzard (:blizzard)]

a=blizzard for 0.8.1

Comment 25

[David Hyatt]

Taking bug

Comment 26

[Asa Dotzler [:asa]]

Looks like that first patch has not made it to the branch yet.  Can someone
chack that in. Thanks.

Comment 27

[Christopher Blizzard (:blizzard)]

I'm checking with hyatt just to be sure.  If he says it's set to go then I'll
check it in.

Comment 28

[Christopher Blizzard (:blizzard)]

Checked into the 0.8.1 branch.

Comment 29

[David Hyatt]

Fixed.

Comment 30

[Hixie (not reading bugmail)]

verified, this was checked in