Closed Bug 1475197 Opened 6 years ago Closed 6 years ago

shrink selector storage some more

Categories

(Core :: CSS Parsing and Computation, enhancement, P3)

Product:
Core
Component:
CSS Parsing and Computation
Type:
enhancement

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla63
Tracking Flags:
Tracking Status
firefox63 --- fixed

People

(Reporter: heycam, Assigned: heycam)

References

Details

(Whiteboard: [overhead:37K])

Attachments

(3 files, 1 obsolete file)

Bug 1475197 - Part 1: Shrink selectors::Component to 24 bytes.
59 bytes, text/x-review-board-request
emilio
: review+
Details
Bug 1475197 - Part 2: Revendor Rust dependencies.
59 bytes, text/x-review-board-request
emilio
: review+
Details
microbenchmark
326 bytes, text/html
Details 
Selectors can take a fair amount of storage in our UA style sheets.  For the set of style sheets I mentioned in bug 1474793 comment 9, 175 KiB is used for selector storage.  Most of that will be Component values.

In bug 1364148 we shrank Component down to 32 bytes, but I think we can get it down to 24 bytes, and maybe save around 40 KiB.
Attached patch WIP (obsolete) — — Splinter Review 
This patch saves 37 KiB in selector storage for the UA style sheets.
Comment on attachment 8991799 [details] [diff] [review]
WIP

Emilio, interested in your thoughts on this.
Attachment #8991799 - Flags: feedback?(emilio)
Obviously I'd need to handle 32 bit builds in some way.  (Probably just by making ThinBoxedSlice a wrapper around Box<[T]>.)
Whiteboard: [overhead:37K]
Comment on attachment 8991799 [details] [diff] [review]
WIP

Review of attachment 8991799 [details] [diff] [review]:
-----------------------------------------------------------------

Over all looks reasonable, though I'm not sure the ThinkBoxedSlice code is correct (see comments below).

Also it's unfortunate to handle div and DIV differently, though probably it's ok as long as we test the serialization properly.

I wonder if there are easier wins to be had by shrinking the selector lists to fit and similar.

Also we should definitely add a test to avoid regressing this if we do it.

::: servo/components/selectors/matching.rs
@@ +713,5 @@
>              }
>              let is_html = element.is_html_element_in_html_document();
>              element.attr_matches(
>                  &NamespaceConstraint::Specific(&::parser::namespace_empty_string::<E::Impl>()),
> +                select_name(is_html, local_name, local_name/*_lower*/),

Probably debug_assert instead that local_name.is_ascii_lowercase or something like that?

::: servo/components/selectors/parser.rs
@@ +50,4 @@
>      if let Some(first_uppercase) = s.bytes().position(|byte| byte >= b'A' && byte <= b'Z') {
>          let mut string = s.to_owned();
>          string[first_uppercase..].make_ascii_lowercase();
> +        (string.into(), true)

Instead of this you could keep the function as-is with a doc comment and match on Cow::Owned / Cow::Borrowed instead.

@@ +1715,4 @@
>      let local_name = local_name.as_ref().into();
> +    if namespace.is_some() || unique_lower {
> +        let namespace = namespace.unwrap_or_else(|| {
> +            NamespaceConstraint::Specific(namespace_empty_string_and_prefix::<Impl>())

Are you sure this serializes correctly? It also feels somewhat footgunny to handle `div` and `DIV` differently, but it may not be a huge issue.

::: servo/components/style/Cargo.toml
@@ +65,5 @@
>  string_cache = { version = "0.7", optional = true }
>  style_derive = {path = "../style_derive"}
>  style_traits = {path = "../style_traits"}
>  servo_url = {path = "../url", optional = true}
> +thin_slice = {path = "../thin_slice"}

I think this could ideally live in crates.io

::: servo/components/thin_slice/lib.rs
@@ +110,5 @@
> +        } else if len < 0xffff {
> +            mem::forget(value);
> +            Storage::Inline(ptr, len)
> +        } else {
> +            Storage::OutOfLine(Box::into_raw(Box::new(value)))

It's a bit unfortunate that this requires an extra heap allocation + indirection, but I guess this is only for arrays >= 65535 which we'll almost-never see.

@@ +127,5 @@
> +                Storage::Inline(ptr, len) => {
> +                    Box::from_raw(slice::from_raw_parts_mut(ptr, len))
> +                }
> +                Storage::OutOfLine(ptr) => {
> +                    *Box::from_raw(ptr)

this is not fine, I think.

This Box::from_raw gives you a Box<Box<[T]>>, which will be dropped after returning from here, won't it? So you're returning a pointer to freed memory.
Attachment #8991799 - Flags: feedback?(emilio)
(In reply to Emilio Cobos Álvarez (:emilio) from comment #4)
> @@ +127,5 @@
> > +                Storage::Inline(ptr, len) => {
> > +                    Box::from_raw(slice::from_raw_parts_mut(ptr, len))
> > +                }
> > +                Storage::OutOfLine(ptr) => {
> > +                    *Box::from_raw(ptr)
> 
> this is not fine, I think.
> 
> This Box::from_raw gives you a Box<Box<[T]>>, which will be dropped after
> returning from here, won't it? So you're returning a pointer to freed memory.

Actually, I guess it's fine, and it gets moved, given this builds:

struct Foo;

fn takes_box_foo(_: Box<Foo>) {}

fn main() {
    let foo: Box<Box<Foo>> = Box::new(Box::new(Foo));
    takes_box_foo(*foo)
}

So never mind about this :)
Thanks for the feedback.

(In reply to Emilio Cobos Álvarez (:emilio) from comment #4)
> Also it's unfortunate to handle div and DIV differently, though probably
> it's ok as long as we test the serialization properly.
> 
> I wonder if there are easier wins to be had by shrinking the selector lists
> to fit and similar.

Nice idea.  I just tried this (sticking a shrink_to_fit() call in SelectorList::parse), but only got 1040 bytes saved unfortunately.

> @@ +1715,4 @@
> >      let local_name = local_name.as_ref().into();
> > +    if namespace.is_some() || unique_lower {
> > +        let namespace = namespace.unwrap_or_else(|| {
> > +            NamespaceConstraint::Specific(namespace_empty_string_and_prefix::<Impl>())
> 
> Are you sure this serializes correctly? It also feels somewhat footgunny to
> handle `div` and `DIV` differently, but it may not be a huge issue.

I've not done any testing yet.  (And you're right I need to adjust AttrSelectorWithNamespace::to_css.)

> ::: servo/components/style/Cargo.toml
> @@ +65,5 @@
> >  string_cache = { version = "0.7", optional = true }
> >  style_derive = {path = "../style_derive"}
> >  style_traits = {path = "../style_traits"}
> >  servo_url = {path = "../url", optional = true}
> > +thin_slice = {path = "../thin_slice"}
> 
> I think this could ideally live in crates.io

Yes, this was my plan if you thought the overall approach sounded good.

> It's a bit unfortunate that this requires an extra heap allocation +
> indirection, but I guess this is only for arrays >= 65535 which we'll
> almost-never see.

Yes, hopefully. :-)  Also once we've got arrays that big the work to eliminate the indirection and allocation is going to be much too much.
Attachment #8991799 - Attachment is obsolete: true
Comment on attachment 8992529 [details]
Bug 1475197 - Part 1: Shrink selectors::Component to 24 bytes.

https://reviewboard.mozilla.org/r/257376/#review264318

::: servo/components/selectors/parser.rs:834
(Diff revision 1)
>      },
> +    // Used only when local_name is already lowercase.
>      AttributeInNoNamespace {
>          local_name: Impl::LocalName,
> -        local_name_lower: Impl::LocalName,
>          operator: AttrSelectorOperator,

Would it be enough to get the size win to move `operator` (which is just an enum) after `value` (which is an atom?).

That should do it and avoid the weirdness and serialization issue altogether, right?

::: servo/components/selectors/parser.rs:1723
(Diff revision 1)
> +        local_name_is_ascii_lowercase = matches!(local_name_lower_cow, Cow::Borrowed(..));
>      }
>      let local_name = local_name.as_ref().into();
> -    if let Some(namespace) = namespace {
> +    if namespace.is_some() || !local_name_is_ascii_lowercase {
> +        let namespace = namespace.unwrap_or_else(|| {
> +            NamespaceConstraint::Specific(namespace_empty_string_and_prefix::<Impl>())

I think this will mean we serialize `[fOO]` as `[|fOO]` instead of `[fOO]`, which is a behavior change.

Let's try to avoid this? Also, this will mean that `AttrSelectorWithNamespace` may not have a namespace anymore. Probably we should rename it to something else?f

::: servo/components/style/gecko_string_cache/mod.rs:229
(Diff revision 1)
>              },
>          }
>      }
>  
> +    /// Returns whether this atom is ASCII lowercase.
> +    pub fn is_ascii_lowercase(&self) -> bool {

nit: I'd #[inline] this.
Attachment #8992529 - Flags: review?(emilio)
Comment on attachment 8992530 [details]
Bug 1475197 - Part 2: Revendor Rust dependencies.

https://reviewboard.mozilla.org/r/257378/#review264324

As discussed it may be worth adding some micro-benchmarks to ensure the thin slice performance doesn't suck, but other than that it looks fine.

It may be worth pointing out in the description of the crate what it relies on (userspace pointers that don't use the upper bits), and such. Other than that it looks great!

::: third_party/rust/thin-slice/src/lib.rs:70
(Diff revision 1)
> +    #[cfg(target_arch = "x86_64")]
> +    _phantom: PhantomData<Box<[T]>>,
> +}
> +
> +#[cfg(target_arch = "x86_64")]
> +const TAG_MASK: usize = 0xffff000000000000;

May be worth documenting some of these, though not a big deal.

::: third_party/rust/thin-slice/src/lib.rs:534
(Diff revision 1)
> +    let ptr = ThinBoxedSlice::into_raw(x);
> +    let y = unsafe { Box::from_raw(ptr) };
> +    assert_eq!(y[123], 456);
> +}
> +
> +#[cfg(target_arch = "x86_64")]

The tests aren't really arch dependent right? As in, the API should be the same.
Attachment #8992530 - Flags: review?(emilio) → review+
Comment on attachment 8992529 [details]
Bug 1475197 - Part 1: Shrink selectors::Component to 24 bytes.

https://reviewboard.mozilla.org/r/257376/#review264330

::: servo/components/selectors/parser.rs:1723
(Diff revision 1)
> +        local_name_is_ascii_lowercase = matches!(local_name_lower_cow, Cow::Borrowed(..));
>      }
>      let local_name = local_name.as_ref().into();
> -    if let Some(namespace) = namespace {
> +    if namespace.is_some() || !local_name_is_ascii_lowercase {
> +        let namespace = namespace.unwrap_or_else(|| {
> +            NamespaceConstraint::Specific(namespace_empty_string_and_prefix::<Impl>())

Err, you actually did fix this above. It does mean we serialize `[|foo]` as `[foo]`, but we already do this.

I still think a test checking that lowercase and uppercase attribute selector serialization is consistent would be worth it, and that maybe renaming it and / or making AttrSelectorWithNamespace take an `Option<Namespace>` would be better than having it empty / default.
I like the idea of making it take an Option<Namespace> instead, so I'll do that.
(In reply to Emilio Cobos Álvarez (:emilio) from comment #11)
> Err, you actually did fix this above. It does mean we serialize `[|foo]` as
> `[foo]`, but we already do this.

FWIW it looks like this matches Safari and Edge, but that Chrome preserves the `|`.
Attached file microbenchmark — 
Here's a microbenchmark that should exercise the use of ThinArcSlice while parsing selectors.

without patch: 1785.25 ms
with patch:    1724.875 ms

so about the same.
Can you re-review part 1?
Flags: needinfo?(emilio)
Comment on attachment 8992529 [details]
Bug 1475197 - Part 1: Shrink selectors::Component to 24 bytes.

https://reviewboard.mozilla.org/r/257376/#review266274

Looks great, thanks!

Maybe worth posting the ThinBoxedSlice perf numbers somewhere?

::: layout/style/test/test_selectors.html:306
(Diff revision 2)
>      }
>  
>      // [attr] selector
>      test_parseable("[attr]")
>      test_parseable_via_api("[attr");
> +    test_parseable("[ATTR]");

Could you also check `should_serialize_to("[ATTR]", "[ATTR]")` and same for `[attr]`? test_parseable only checks that the serialization is also parseable.

::: servo/components/selectors/parser.rs:1267
(Diff revision 2)
>          W: fmt::Write,
>      {
>          dest.write_char('[')?;
>          match self.namespace {
> -            NamespaceConstraint::Specific((ref prefix, _)) => {
> +            Some(NamespaceConstraint::Specific((ref prefix, _))) => {
>                  display_to_css_identifier(prefix, dest)?;

Maybe debug_assert!(!prefix.is_empty()), if there's an easy way to do so?

::: servo/components/style/gecko/selector_parser.rs:319
(Diff revision 2)
>  
>      type PseudoElement = PseudoElement;
>      type NonTSPseudoClass = NonTSPseudoClass;
>  }
>  
> +impl IsAsciiLowercase for Atom {

I'd remove this if it's only for the assertion, but you already wrote it and adding the assertion was my idea (I thought it didn't require any extra support code), so feel free to do whatever you want about it :)
Attachment #8992529 - Flags: review?(emilio) → review+
Oh, I had missed comment 16 :)

Thanks!
Flags: needinfo?(emilio)
Comment on attachment 8992529 [details]
Bug 1475197 - Part 1: Shrink selectors::Component to 24 bytes.

https://reviewboard.mozilla.org/r/257376/#review266274

> Could you also check `should_serialize_to("[ATTR]", "[ATTR]")` and same for `[attr]`? test_parseable only checks that the serialization is also parseable.

Good catch.

> Maybe debug_assert!(!prefix.is_empty()), if there's an easy way to do so?

There's not. :(

> I'd remove this if it's only for the assertion, but you already wrote it and adding the assertion was my idea (I thought it didn't require any extra support code), so feel free to do whatever you want about it :)

OK, I'm going to drop it.
Comment on attachment 8992530 [details]
Bug 1475197 - Part 2: Revendor Rust dependencies.

https://reviewboard.mozilla.org/r/257378/#review264324

> The tests aren't really arch dependent right? As in, the API should be the same.

The API's the same but the use of TAG_LIMIT is, and I'm not sure how useful the tests are when we're on a non-x86_64 arch.
Pushed by cam@mcc.id.au:
https://hg.mozilla.org/integration/autoland/rev/4bd5f8588422
Part 1: Shrink selectors::Component to 24 bytes. r=emilio
https://hg.mozilla.org/integration/autoland/rev/108e22d963cb
Part 2: Update Cargo.lock and re-vendor Rust dependencies. r=emilio
Backed out for causing build bustages because of compile errors.

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=autoland&filter-resultStatus=busted&filter-resultStatus=exception&fromchange=108e22d963cb5fe47634fd33f1d5a787920c4eb1&tochange=129b25a6bcfd65ef7e096d445faebdc63781ee1c&selectedJob=190174602

Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=190177424&repo=autoland&lineNumber=42138

Backout link: https://hg.mozilla.org/integration/autoland/rev/129b25a6bcfd65ef7e096d445faebdc63781ee1c

[task 2018-07-26T04:29:48.924Z] 04:29:48     INFO - error: Could not compile `selectors`.
[task 2018-07-26T04:29:48.924Z] 04:29:48     INFO - Caused by:
[task 2018-07-26T04:29:48.925Z] 04:29:48     INFO -   process didn't exit successfully: `/builds/worker/workspace/build/src/sccache2/sccache /builds/worker/workspace/build/src/rustc/bin/rustc --crate-name selectors servo/components/selectors/lib.rs --emit=dep-info,link -C opt-level=3 --test -C metadata=50c97d6fc20a7990 -C extra-filename=-50c97d6fc20a7990 --out-dir /builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps --target i686-unknown-linux-gnu -C linker=/builds/worker/workspace/build/src/build/cargo-linker -L dependency=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps -L dependency=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/release/deps --extern bitflags=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libbitflags-54792ad1ea4a24de.rlib --extern cssparser=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libcssparser-0d34191efb825c85.rlib --extern fnv=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libfnv-50a44d98bf897c79.rlib --extern log=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/liblog-da8e7f953e71525a.rlib --extern matches=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libmatches-5d7d17857b18cb0c.rlib --extern phf=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libphf-521fd21c49fe1ca3.rlib --extern precomputed_hash=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libprecomputed_hash-0ec057f695c8f91c.rlib --extern servo_arc=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libservo_arc-f57f48bf89fa3703.rlib --extern smallvec=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libsmallvec-a79936103952e682.rlib --extern thin_slice=/builds/worker/workspace/build/src/obj-firefox/toolkit/library/i686-unknown-linux-gnu/release/deps/libthin_slice-0341840947771c5a.rlib -C opt-level=2 -C debuginfo=2` (exit code: 101)
[task 2018-07-26T04:29:48.925Z] 04:29:48     INFO - warning: build failed, waiting for other jobs to finish...
[task 2018-07-26T04:30:06.232Z] 04:30:06     INFO - warning: method is never used: `get_stable_c_enum_layout`
[task 2018-07-26T04:30:06.232Z] 04:30:06     INFO -    --> third_party/rust/serde_derive/src/internals/ast.rs:133:5
[task 2018-07-26T04:30:06.232Z] 04:30:06     INFO -     |
[task 2018-07-26T04:30:06.232Z] 04:30:06     INFO - 133 |     pub fn get_stable_c_enum_layout(&self) -> Option<&'static str> {
[task 2018-07-26T04:30:06.232Z] 04:30:06     INFO -     |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[task 2018-07-26T04:30:06.233Z] 04:30:06     INFO -     |
[task 2018-07-26T04:30:06.233Z] 04:30:06     INFO -     = note: #[warn(dead_code)] on by default
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - error: build failed
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - /builds/worker/workspace/build/src/config/rules.mk:995: recipe for target 'force-cargo-test-run' failed
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[2]: *** [force-cargo-test-run] Error 101
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[2]: Target 'check' not remade because of errors.
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[2]: Leaving directory '/builds/worker/workspace/build/src/obj-firefox/toolkit/library/rust'
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - /builds/worker/workspace/build/src/config/recurse.mk:101: recipe for target 'toolkit/library/rust/check' failed
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[1]: *** [toolkit/library/rust/check] Error 2
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[1]: Target 'recurse_check' not remade because of errors.
[task 2018-07-26T04:30:06.240Z] 04:30:06     INFO - make[1]: Leaving directory '/builds/worker/workspace/build/src/obj-firefox'
[task 2018-07-26T04:30:06.241Z] 04:30:06     INFO - /builds/worker/workspace/build/src/config/recurse.mk:32: recipe for target 'check' failed
[task 2018-07-26T04:30:06.241Z] 04:30:06     INFO - make: *** [check] Error 2
Flags: needinfo?(cam)
There were also Tier2 wpt leaks "LeakSanitizer | leak at alloc_system::platform"

Log link: https://treeherder.mozilla.org/logviewer.html#?job_id=190179051&repo=autoland&lineNumber=18380
I've fixed the assertions in the BR job.  For the leaks, I spent most of the day today trying to narrow down which tests in this job were causing the leak.  Then I noticed that there are these `lsan-allowed` entries in the WPT meta files for some test, which were added last week in bug 1354232.

James, can you tell me if these new LSAN errors are ones that should just be whitelisted, and if so, what values I need to add to `lsan-allowed`?  Please see the link in comment 26.  I don't know what the criteria were for adding the existing `lsan-allowed` values were so I don't know whether it's right for me to add more.
Flags: needinfo?(cam)
Flags: needinfo?(james)
Right, sorry, I haven't communicated well around this.

The existing values were added to get the patch to land and because we need a way to import new tests that cause existing leaks; there are bugs for a few of them but I need to fill in the gaps. However adding new leaks via changes in Gecko doesn't seem desirable.
Flags: needinfo?(james)
It seems like the leaking tests are in /fetch/api/abort/ (we restart every directory so in theory leaks are localised to the directory level).
(In reply to James Graham [:jgraham] from comment #29)
> It seems like the leaking tests are in /fetch/api/abort/ (we restart every
> directory so in theory leaks are localised to the directory level).

Thanks, I narrowed it down to the last sub-test in fetch/api/abort/serviceworker-intercepted.https.html.  But I'm no closer to understanding whether my changes are really a new leak, or just a new manifestation of the existing leaks, since (a) the Rust allocations stack traces that LSAN shows don't show enough context to know where the allocation is really coming from, (b) running WPT under LSAN locally results in many more leaks than are reported on the try server, confusing the matter.  I can't say for sure that these new leaks are just the same as the existing ones, but it is suspicious that the new leaks from Rust would only show up in this particular test that already leaks a bunch of other things.  If I don't make any progress soon I plan to just cut my losses and whitelist the two new failures.
After some more investigation, running the test locally in a debug build, it looks like an entire DOM window is being leaked.  The window holds on to the nsLayoutStylesheetCache, which has the UA sheets in it, which hold the new Rust allocations related to selectors from my patches on this bug.  I will whitelist these allocations for this test.
(I wonder if that leak is bug 1451381.)
Pushed by cam@mcc.id.au:
https://hg.mozilla.org/integration/autoland/rev/046c059acbd3
Part 1: Shrink selectors::Component to 24 bytes. r=emilio
https://hg.mozilla.org/integration/autoland/rev/04caa95515e5
Part 2: Revendor Rust dependencies. r=emilio
https://hg.mozilla.org/mozilla-central/rev/046c059acbd3
https://hg.mozilla.org/mozilla-central/rev/04caa95515e5
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
status-firefox63: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla63
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: