pseudo selectors should be processed more efficiently

VERIFIED FIXED in mozilla0.9

Status

()

defect
P1
normal
VERIFIED FIXED
19 years ago
17 years ago

People

(Reporter: attinasi, Assigned: hyatt)

Tracking

({css1, helpwanted, perf})

Trunk
mozilla0.9
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [Hixie-P1] (potential for major speed improvements))

Attachments

(2 attachments)

(Reporter)

Description

19 years ago
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.
(Reporter)

Updated

19 years ago
Status: NEW → ASSIGNED
Keywords: perf
Summary: pseudo selectors shoudl be processed more efficiently → pseudo selectors should be processed more efficiently
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.
Keywords: css1, mozilla0.9
(again, for the record, that proposal originated from Peter Linss ages ago)
Keywords: nsbeta1
Whiteboard: [Hixie-P1] (potential for major speed improvements)
Blocks: 53796

Comment 3

19 years ago
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?
Keywords: helpwanted

Comment 4

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

Comment 5

18 years ago
Setting target to Mozilla 0.9
Target Milestone: --- → mozilla0.9
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...
QA Contact: chrisd → ian

Comment 7

18 years ago
is the potencial for big win still there???
lets get this marked topperf if someone can get someone can
get good data..
(Reporter)

Comment 8

18 years ago
Raising priority: major performance issue we need to solve asap.
Priority: P3 → P1

Updated

18 years ago
Blocks: 71874
No longer blocks: 53796

Updated

18 years ago
Blocks: 71668
No longer blocks: 71874
(Assignee)

Comment 9

18 years ago
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.

(Assignee)

Comment 11

18 years ago
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.
(Reporter)

Comment 12

18 years ago
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...
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?
(Assignee)

Comment 14

18 years ago
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.
(Assignee)

Comment 16

18 years ago
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.
(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.)
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
I am unable to apply patch on a recent build due to conflicts.

Updated

18 years ago
Keywords: nsCatFood
(Assignee)

Comment 20

18 years ago
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.
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
(Reporter)

Comment 22

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

BTW: this should land on the trunk too IMO...
a=blizzard for 0.8.1
(Assignee)

Comment 25

18 years ago
Taking bug
Assignee: attinasi → hyatt
Status: ASSIGNED → NEW
Looks like that first patch has not made it to the branch yet.  Can someone
chack that in. Thanks.
I'm checking with hyatt just to be sure.  If he says it's set to go then I'll
check it in.
Checked into the 0.8.1 branch.
(Assignee)

Comment 29

18 years ago
Fixed.
Status: NEW → RESOLVED
Last Resolved: 18 years ago
Resolution: --- → FIXED

Updated

18 years ago
Blocks: 49141
verified, this was checked in
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.