selectors: Check the bloom filter at most once per complex selector. #15890

emilio · 2017-03-09T15:56:54Z

Fixes servo/rust-selectors#107

This change is

emilio · 2017-03-09T15:57:40Z

r? @SimonSapin

emilio · 2017-03-09T15:57:59Z

Also, cc @bholley

emilio · 2017-03-09T16:02:35Z

@bors-servo try

bors-servo · 2017-03-09T16:02:40Z

⌛ Trying commit 0a102d5 with merge 7c60e66...

selectors: Check the bloom filter at most once per complex selector. Fixes servo/rust-selectors#107  --- This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/15890)

bors-servo · 2017-03-09T17:01:11Z

💔 Test failed - linux-rel-css

emilio · 2017-03-09T18:27:50Z

That one is an intermittent it seems.

emilio · 2017-03-18T11:18:37Z

r? @heycam

Simon said he doesn't have the bloom filter paged in right now, and he's got a bunch to do for #15998.

emilio · 2017-03-18T11:20:39Z

(Though @bzbarsky could be a good reviewer for this one too, actually).

Which remembers we should probably limit the amount of selectors we test against the filter somehow, IIRC the gecko limit was four or something like that. Still I'd want to land this relatively soon.

stshine · 2017-03-19T13:17:35Z

components/selectors/matching.rs

+                 selector = &**cs;
+                 continue;
+             }
+         };


Still I haven't got all the details, but look like this prevents checking the first selector(the rightmost one) in the bloom filter. Maybe move this match to the end of the loop?

That's intended. The bloom filter contains only data from the ancestors, which are the expensive selectors to check. It's quite tricky, I admit.

heycam · 2017-03-20T06:39:45Z

components/selectors/matching.rs

@@ -466,7 +452,10 @@ fn matches_simple_selector<E>(
        }
        SimpleSelector::Negation(ref negated) => {
            !negated.iter().all(|s| {
-                matches_complex_selector(s, element, parent_bf, relations, flags)
+                match matches_complex_selector_internal(s, element, relations, flags) {


We might have descendant combinators inside the :not(...). Don't we want to be able to use the ancestor filter to quickly return false for them too?

I think it's not a super-clear win, and I wanted to prevent the filter from being misused, but I guess I can do that too.

(I meant that because :not is already quite expensive, but sure, will do that).

Fixes servo/rust-selectors#107

emilio · 2017-03-20T11:22:01Z

@bors-servo try

bors-servo · 2017-03-20T11:22:05Z

⌛ Trying commit ed6351c with merge f3c4ccd...

selectors: Check the bloom filter at most once per complex selector. Fixes servo/rust-selectors#107  --- This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/15890)

heycam · 2017-03-20T11:31:00Z

Hmm, I think I made a mistake. The selector inside :not(...) isn't allowed to take a selector with combinators. Is that the same in Servo? If so, then I guess we don't need to pass the Bloom filter through, sorry.

emilio · 2017-03-20T12:22:29Z

So, servo implements :not per the selectors 4 spec, which does allow combinators. I'll file a bug against the "don't ship new CSS features" bug we have for that, but I'd like to land this for now.

emilio · 2017-03-20T12:33:51Z

Filled https://bugzilla.mozilla.org/show_bug.cgi?id=1348802

heycam · 2017-03-20T12:33:58Z

OK, sounds good, thanks!

emilio · 2017-03-20T12:34:23Z

@bors-servo r=heycam

bors-servo · 2017-03-20T12:34:23Z

📌 Commit 2772419 has been approved by heycam

bors-servo · 2017-03-20T13:26:39Z

⌛ Testing commit 2772419 with merge 4fa40c7...

selectors: Check the bloom filter at most once per complex selector. Fixes servo/rust-selectors#107  --- This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/15890)

bors-servo · 2017-03-20T13:52:22Z

💔 Test failed - linux-rel-wpt

emilio · 2017-03-20T14:58:00Z

@bors-servo retry

#14323

bors-servo · 2017-03-20T14:58:03Z

⚡ Previous build results for android, arm32, arm64, linux-dev, linux-rel-css, mac-dev-unit, mac-rel-css, mac-rel-wpt1, mac-rel-wpt2, windows-msvc-dev are reusable. Rebuilding only linux-rel-wpt...

bors-servo · 2017-03-20T15:23:51Z

☀️ Test successful - android, arm32, arm64, linux-dev, linux-rel-css, linux-rel-wpt, mac-dev-unit, mac-rel-css, mac-rel-wpt1, mac-rel-wpt2, windows-msvc-dev
Approved by: heycam
Pushing 4fa40c7 to master...

bzbarsky · 2017-03-21T15:50:05Z

IIRC the gecko limit was four or something like that.

The Gecko limit is 4 because gecko does the following:

Precomputes hashes for the things it wants to test against the bloom filter, because hash functions are slow.
Stores those precomputed hashes in fixed-length allocations fused into another data structure, because malloc is slow.

Given that, we needed to have some fixed length we picked, and 4 was a compromise between bloating the data structure too much and having enough slots to cover common selectors reasonably.

bholley · 2017-03-21T22:43:15Z

Hm, does that setup predate the existing of precomputed hashes in nsIAtom?

bzbarsky · 2017-03-22T02:00:44Z

Hm, does that setup predate the existing of precomputed hashes in nsIAtom?

No. In fact, I implemented precomputed hashes in nsIAtom as a prereq for the Bloom filter in Gecko, precisely so we could build the cascade faster, instead of having to hash even then.

But even just getting to the atoms still involves a bunch of linked-list walking and whatnot in Gecko. I seem to recall that I tried measuring just looking for them every time, and it was slower than the precached approach, with lots of cache misses and whatnot.

It might be worth remeasuring various stuff around this, in general.

bholley · 2017-03-22T02:03:11Z

In Servo we have a Vec, so the only cache miss will be on the nsIAtoms themselves. Hopefully that's acceptable.

bzbarsky · 2017-03-22T02:28:38Z

In Servo we have a Vec

No, you have a linked list of Vecs.

Specifically, a ComplexSelector is a Vec of SimpleSelectors. But ComplexSelectors form a linked list. So given a selector like "#foo.bar > *" you have a linked list with two elements. The first element has probably an empty Vec or so, depending on default namespaces; the second element has a Vec with two items (one for the id selector, one for the class selector).

Any case in which the Bloom filter helps at all will involve a linked list of length more than 1, and hence pointer-chasing.

bzbarsky · 2017-03-22T02:29:09Z

Oh, and instead of hoping we should obviously measure. What the priority of that measurement should be is hard to say.

bholley · 2017-03-22T03:22:58Z

Oh interesting - is there a reason it actually needs to be a linked list rather than a Vec of Vecs? That would certainly make #16019 easier.

bzbarsky · 2017-03-22T03:33:10Z

I have no idea. I'm still in the "butterfly collecting" stage of understanding, slowly moving towards the "make predictions" stage. ;)

I should also note that even with Vec you can get cache misses on both the pointer to the buffer and the contents to the buffer, since I don't think Vec ever uses an inline buffer. Again, this is something that should be measured. I worry about it because profiles of Gecko's style system long ago showed L2/L3 misses being a significant part of the performance drag, as we walk around selectors, DOM nodes, etc, etc... But at least I had data then.

mbrubeck · 2017-03-23T23:39:55Z

I should also note that even with Vec you can get cache misses on both the pointer to the buffer and the contents to the buffer, since I don't think Vec ever uses an inline buffer.

We use https://crates.io/crates/smallvec in cases where we want a possibly-inline buffer.

SimonSapin · 2017-03-28T11:02:43Z

is there a reason it actually needs to be a linked list rather than a Vec of Vecs?

Each "link" also stores a combinator. With a Vec we’d need to have a dummy/unused combinator in the first or last item of the top-level vector, or have a separate vector of combinators whose length is 1 less than the other top-level vector.

bholley · 2017-03-28T17:25:38Z

Ok - a dummy combinator seems like a small price to pay for better cache locality. But we should measure.

highfive assigned KiChjang Mar 9, 2017

highfive added the S-awaiting-review There is new code that needs to be reviewed. label Mar 9, 2017

highfive assigned SimonSapin and unassigned KiChjang Mar 9, 2017

highfive added the S-tests-failed The changes caused existing tests to fail. label Mar 9, 2017

emilio mentioned this pull request Mar 15, 2017

Bug 1340683 - stylo: Implement the :-moz-any pseudo-class #15966

Merged

4 tasks

highfive assigned heycam and unassigned SimonSapin Mar 18, 2017

stshine reviewed Mar 19, 2017

View reviewed changes

heycam reviewed Mar 20, 2017

View reviewed changes

selectors: Check the bloom filter at most once per complex selector.

2772419

Fixes servo/rust-selectors#107

emilio force-pushed the bloom branch from 0a102d5 to ed6351c Compare March 20, 2017 11:19

highfive removed the S-tests-failed The changes caused existing tests to fail. label Mar 20, 2017

emilio force-pushed the bloom branch from ed6351c to 6e84e31 Compare March 20, 2017 11:23

emilio force-pushed the bloom branch from 6e84e31 to 2772419 Compare March 20, 2017 12:14

heycam approved these changes Mar 20, 2017

View reviewed changes

highfive added S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. and removed S-awaiting-review There is new code that needs to be reviewed. labels Mar 20, 2017

highfive added S-tests-failed The changes caused existing tests to fail. and removed S-awaiting-merge The PR is in the process of compiling and running tests on the automated CI. labels Mar 20, 2017

bors-servo merged commit 2772419 into servo:master Mar 20, 2017

emilio deleted the bloom branch March 21, 2017 16:19

selectors: Check the bloom filter at most once per complex selector. #15890

selectors: Check the bloom filter at most once per complex selector. #15890

Conversation

emilio commented Mar 9, 2017 • edited by larsbergstrom Loading

emilio commented Mar 9, 2017

emilio commented Mar 9, 2017

emilio commented Mar 9, 2017

bors-servo commented Mar 9, 2017

bors-servo commented Mar 9, 2017

emilio commented Mar 9, 2017

emilio commented Mar 18, 2017

emilio commented Mar 18, 2017

stshine Mar 19, 2017

Choose a reason for hiding this comment

emilio Mar 19, 2017

Choose a reason for hiding this comment

heycam Mar 20, 2017

Choose a reason for hiding this comment

emilio Mar 20, 2017

Choose a reason for hiding this comment

emilio Mar 20, 2017

Choose a reason for hiding this comment

emilio Mar 20, 2017

Choose a reason for hiding this comment

emilio commented Mar 20, 2017

bors-servo commented Mar 20, 2017

heycam commented Mar 20, 2017

emilio commented Mar 20, 2017

emilio commented Mar 20, 2017

heycam commented Mar 20, 2017

emilio commented Mar 20, 2017

bors-servo commented Mar 20, 2017

bors-servo commented Mar 20, 2017

bors-servo commented Mar 20, 2017

emilio commented Mar 20, 2017

bors-servo commented Mar 20, 2017

bors-servo commented Mar 20, 2017

bzbarsky commented Mar 21, 2017

bholley commented Mar 21, 2017

bzbarsky commented Mar 22, 2017

bholley commented Mar 22, 2017

bzbarsky commented Mar 22, 2017

bzbarsky commented Mar 22, 2017

bholley commented Mar 22, 2017

bzbarsky commented Mar 22, 2017

mbrubeck commented Mar 23, 2017

SimonSapin commented Mar 28, 2017

bholley commented Mar 28, 2017

emilio commented Mar 9, 2017 •

edited by larsbergstrom

Loading