1397614 - stylo: shrink background-images representation

Status: RESOLVED FIXED

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

Description

[Nicholas Nethercote [inactive]]

DMD has this for gmail:

> Unreported {
>   11,578 blocks in heap block record 1 of 11,188
>   11,855,872 bytes (8,891,904 requested / 2,963,968 slop)
>   Individual block sizes: 1,024 x 11,578
>   6.09% of the heap (6.09% cumulative)
>   24.55% of unreported (24.55% cumulative)
>   Allocated at {
>     #01: replace_malloc (/home/njn/moz/autoland/memory/replace/dmd/DMD.cpp:1303 (discriminator 2))
>     #02: alloc::raw_vec::{{impl}}::double<style::values::Either<style::values::None_, style::values::generics::image::Image<style::values::generics::image::Gradient<style::values::specified::image::LineDirection, style::values::specified::length::Length, style::values::specified::length::LengthOrPercentage, style::values::specified::image::GradientPosition, style::values::specified::color::RGBAColor, style::values::specified::angle::Angle>, style::values::generics::image::MozImageRect<style::values::specified::NumberOrPercentage, style::gecko::url::SpecifiedUrl>, style::gecko::url::SpecifiedUrl>>> (/checkout/src/liballoc/raw_vec.rs:222)
>     #03: collections::vec::{{impl}}::push<style::values::Either<style::values::None_, style::values::generics::image::Image<style::values::generics::image::Gradient<style::values::specified::image::LineDirection, style::values::specified::length::Length, style::values::specified::length::LengthOrPercentage, style::values::specified::image::GradientPosition, style::values::specified::color::RGBAColor, style::values::specified::angle::Angle>, style::values::generics::image::MozImageRect<style::values::specified::NumberOrPercentage, style::gecko::url::SpecifiedUrl>, style::gecko::url::SpecifiedUrl>>> (/checkout/src/libcollections/vec.rs:973)
>     #04: style::properties::shorthands::background::parse_value::{{closure}} (/home/njn/moz/autoland/o64sty/toolkit/library/x86_64-unknown-linux-gnu/debug/build/style-e4d17c1a5eeb1576/out/properties.rs:50559)
>     #05: core::ops::impls::{{impl}}::call_once<(&mut cssparser::parser::Parser),closure> (/checkout/src/libcore/ops.rs:2732)
>     #06: cssparser::parser::Parser::parse_entirely (style.cgu-0.rs:?)
>     #07: cssparser::parser::parse_until_before<&mut closure,(),selectors::parser::SelectorParseError<style_traits::StyleParseError>> (/home/njn/moz/autoland/third_party/rust/cssparser/src/parser.rs:785)
>     #08: cssparser::parser::{{impl}}::parse_until_before<&mut closure,(),selectors::parser::SelectorParseError<style_traits::StyleParseError>> (/home/njn/moz/autoland/third_party/rust/cssparser/src/parser.rs:523)
>     #09: cssparser::parser::{{impl}}::parse_comma_separated<closure,(),selectors::parser::SelectorParseError<style_traits::StyleParseError>> (/home/njn/moz/autoland/third_party/rust/cssparser/src/parser.rs:484)
>     #10: style::properties::shorthands::background::parse_value (/home/njn/moz/autoland/o64sty/dist/bin/libxul.so)
>   }
> }

It's hard to read, but the long Either<None_, Image> type in entries #02 and #03 is ImageLayer, and heycam says this involves the representation of background-image values.

Image is 184 bytes, so boxing it would make this vector much smaller. Also, using a SmallVec might be a good idea.

Comment 2

[Xidorn Quan [:xidorn] UTC+10]

If majority of background-image items are taking the Image rather than None_ (which should be the usual case), I don't think boxing Image would be a good idea. That would effectively increase the memory usage rather than reducing.

It's worth checking what variant of Image is large, and we can box the corresponding variant rather than the whole Image, so that smaller variants would still be stored inline.

Also, given that Rust is still not able to flattern nested enum, it may also makes sense to make None as a variant of Image rather than using Either. With that, we should be able to save 1 word per item.

Comment 3

[Boris Zbarsky [:bzbarsky]]

I added some logging to Gecko's CSS parser to spit out background-image values when parsed on their own or as part of the background shorthand.  For gmail, I see 13086 values total, breaking down like so:

   941 -- none
    88 -- linear-gradient(stuff)
    17 -- radial-graient(stuff)
   237 -- -moz-linear-gradient(stuff)
 11803 -- url(stuff)

There are actually only 325 distinct url strings, as bug 1397971 comment 0 points out...

Anyway, the type stylo uses to store background-image values is:

  pub type ImageLayer = Either<None_, Image>;

  pub enum GenericImage<Gradient, MozImageRect, ImageUrl> {
    Url(ImageUrl),
    Gradient(Gradient),
    Rect(MozImageRect),
    Element(Atom),
  }

  pub type Image = GenericImage<Gradient, MozImageRect, SpecifiedUrl>;

  pub struct SpecifiedUrl {
    serialization: Arc<String>,
    pub extra_data: RefPtr<URLExtraData>,
    pub image_value: Option<RefPtr<ImageValue>>,
  }

  pub type Gradient = GenericGradient<
    LineDirection,
    Length,
    LengthOrPercentage,
    GradientPosition,
    RGBAColor,
    Angle,
  >;

  pub struct GenericGradient<LineDirection, Length, LengthOrPercentage, Position, Color, Angle> {
    pub kind: GradientKind<LineDirection, Length, LengthOrPercentage, Position, Angle>,
    pub items: Vec<GradientItem<Color, LengthOrPercentage>>,
    pub repeating: bool,
    pub compat_mode: CompatMode,
  }

  pub enum GradientKind<LineDirection, Length, LengthOrPercentage, Position, Angle> {
    Linear(LineDirection),
    Radial(EndingShape<Length, LengthOrPercentage>, Position, Option<Angle>),
  }

  pub enum EndingShape<Length, LengthOrPercentage> {
    Circle(Circle<Length>),
    Ellipse(Ellipse<LengthOrPercentage>),
  }

  pub enum Circle<Length> {
    Radius(Length),
    Extent(ShapeExtent),
  }

  pub enum Ellipse<LengthOrPercentage> {
    Radii(LengthOrPercentage, LengthOrPercentage),
    Extent(ShapeExtent),
  }

  pub enum LineDirection {
    Angle(Angle),
    Horizontal(X),
    Vertical(Y),
    Corner(X, Y),
    MozPosition(Option<Position>, Option<Angle>),
  }

OK.  How big are the leaves of this stuff?  LengthOrPercentage is at least 3 words, afaict (the CalcLengthOrPercentage) case.  So Ellipse is at least 6 words.  ShapeExtent is a keyword enum that I assume is smaller than that.  Ellipse is cleraly bigger than Circle, so EndingShape is at least 6 words, assuming all the discriminants get stashed somewhere (which I doubt).

Position is at least 2 words.  Then Radial is at least 9 words (again, I suspect in practice it's more because of the discriminants of various sorts; for example, I seriously doubt Option<Angle> is really one word).

That makes a GenericGradient at least 

Then Radial is at least 9 words for the GradientKind, 3 words (I'm told) for the Vec, let's be charitable and say one word for the bool and CompatMode.  That's 13 words.  That's the bare minimum size of a Gradient.

By way of comparison, SpecifiedUrl is 3 or 4 words, I'd think.

That's the theory.  Now the practice.  According to std::mem::size_of we have the following sizes on 64-bit Linux, in bytes, in an opt build:

  ImageLayer: 152 -- 19 words
  Gradient: 136 -- 17 words
  SpecifiedUrl: 32 -- 4 words
  MozImageRect: 64 -- 8 words

So looks like we're paying two words for the discriminants of GenericImage and ImageLayer.  And another word for the Option bit in Option<RefPtr> in SpecifiedUrl?  And Gradient is 4 more words than I calculated above, because of all the discriminants.... I hear tell that Rust will fix some of that sometime, but it's clearly not there yet.

Anyway, I would think that the URL and "none" cases cover the vast majority of background images.  If we just boxed Gradient and MozImageRect, we would shrink ImageLayer from 19 words to 6.

Oh, the best part?  If you push() into an empty Vec, it allocates enough capacity for 4 things.  So in our case that's 4*152 == 604 which with jemalloc means it's a 1024-byte allocation.  If we shrink to 6 words, we get 4 * 6 * 8 = 192, which will at least be an exact allocation....  Of course the right answer in a perfect world would be that SpecifiedUrl would be 3 words, we would have one of them in the Vec, for a 24-byte allocation...

I agree that SmallVec might be a good idea here, but more generally, this means that any place we use vecs and push() but usually have only 1 thing if we have any at all is wasting memory.  :(

Comment 4

[Boris Zbarsky [:bzbarsky]]

Er, my numbers for the struct/enum sizes were for computed ones, not specified ones.  For the specified ones, we have:

  ImageLayer: 192 -- 24 words
  Gradient: 176 -- 22 words
  SpecifiedUrl: 32 -- 4 words
  MozImageRect: 80 -- 10 words

So our arrays end up being 4*192 = 768 bytes, which still gets rounded to 1KB.

Comment 5

[Xidorn Quan [:xidorn] UTC+10]

My plan for this is to box Gradient and MozImageRect, and maybe merge Image with ImageLayer so that we don't pay a whole word for the unusual none value.

Comment 6

[Boris Zbarsky [:bzbarsky]]

One problem with using a SmallVec, of course, is that when there _isn't_ a background-image specified it would use 32 bytes extra memory...

Really, what we want here is a Vec, but without the "yeah, I'll way overallocate for you" behavior.  We can get there if we manually reserve() things, but then we get O(N^2) (in number of background images in the specified value) behavior....

Comment 7

[Xidorn Quan [:xidorn] UTC+10]

There cannot be no background-image. There must be at least one background-image, and by default that is a none.

Comment 8

[Simon Sapin (:SimonSapin)]

> Really, what we want here is a Vec, but without the "yeah, I'll way overallocate for you" behavior.  We can get there if we manually reserve() things, but then we get O(N^2) (in number of background images in the specified value) behavior....

Is the "exactly one background image layer" case more common? We could initially allocate one (with reserve() or with_capacity()), and then push() normally when there’s more. Or may manually reserve() up to N = 4, then let push() do its usual doubling?

Comment 9

[Boris Zbarsky [:bzbarsky]]

> Is the "exactly one background image layer" case more common?

I think the most common case is "no specified background image at all".  But as Xidorn points out, that doesn't even allocate the Vec so is irrelevant for our purposes.

The second most common case is "only one background image layer".

I expect everything else (multiple background image layers) to be extremely rare.  I don't have telemetry to back this up, though....

Comment 10

[Josh Matthews [:jdm]]

Two straightforward changes that would be useful to make for sake of comparison with anything smarter:
* change https://doc.servo.org/src/cssparser/parser.rs.html#481 to use with_capacity(1) (measure the cost of eagerly allocating one element for each comma-separated property value that is parsed, even if the result would be empty)
* change https://doc.servo.org/src/cssparser/parser.rs.html#481 to add a boolean that causes reserve(1) to be called right before the first element is pushed (measure the cost of ensuring that all single-value comma-separated property values do not over-allocate)

Comment 11

[Boris Zbarsky [:bzbarsky]]

Attachment: A more reproducible testcase than gmail

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: A second more-reproducible testcase, exercising different codepaths

Comment 13

[Boris Zbarsky [:bzbarsky]]

Some numbers for those reproducible testcases for the style-sheets number from about:memory.  For the one using "background":

  Current tip: 18.48 MB
  With gradient/rect boxed: 10.55 MB
  With arrays also not overallocated: 6.20 MB

For the one using background-image:

  Current tip: 11.08 MB
  With gradient/rect boxed: 3.15 MB
  With arrays also not overallocated: 1.78 MB

The change suggested in comment 10 helps the "background-image" testcase, but not the "background" testcase; that one sets up its arrays in a different spot.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Attachment: Bug 1397614 part 1. Box gradients and rects in Image.

Gradients and rects are rare, and large.  Image is much smaller with them boxed.

Review commit: https://reviewboard.mozilla.org/r/177994/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/177994/

Comment 15

[Boris Zbarsky [:bzbarsky]]

Attachment: Bug 1397614 part 2. Avoid array overallocation when parsing background shorthand.

Review commit: https://reviewboard.mozilla.org/r/177996/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/177996/

Comment 16

[Boris Zbarsky [:bzbarsky]]

Attachment: Bug 1397614 part 3. Avoid array overallocation when parsing background-image property.

Review commit: https://reviewboard.mozilla.org/r/177998/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/177998/

Comment 17

[Boris Zbarsky [:bzbarsky]]

Oh, and for gmail the headline number with those patches is about 20MB less stylesheet memory used, if I'm measuring it right.  The various iframes popping in and out make measurement a bit complicated...

Comment 18

[Nicholas Nethercote [inactive]]

Great numbers, bz!

Comment 19

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8906246 [details]
Bug 1397614 part 1.  Box gradients and rects in Image.

https://reviewboard.mozilla.org/r/177994/#review182964

::: servo/tests/unit/stylo/size_of.rs:56
(Diff revision 1)
> +// FIXME(bz): These can shrink if we move the None_ value inside the
> +// enum instead of paying an extra word for the Either discriminant.

I wonder whether we can just remove the `Image` type and use `ImageLayer` directly, which would include variants currently in `Image` as well as a `None_`.

Comment 20

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8906247 [details]
Bug 1397614 part 2.  Avoid array overallocation when parsing background shorthand.

https://reviewboard.mozilla.org/r/177996/#review182966

Comment 21

[Boris Zbarsky [:bzbarsky]]

> I wonder whether we can just remove the `Image` type and use `ImageLayer` directly
> which would include variants currently in `Image` as well as a `None_`.

I think we can, and I'm happy to look into it as a followup, or have you look if you have time.  Would need to double-check the consumers who currently don't need to deal with None_.

Comment 22

[Boris Zbarsky [:bzbarsky]]

Oh, I did awsy try runs without these changes (<https://treeherder.mozilla.org/#/jobs?repo=try&revision=829d081c3f1d9ea6ceefb16d6137cba2428e0208&selectedJob=129765927>) and with (<https://treeherder.mozilla.org/#/jobs?repo=try&revision=a9e59a003437270e3e5b428c3971c1b7f4736755&selectedJob=129767619>).  No effect on awsy, sadly.  :(

Comment 23

[Boris Zbarsky [:bzbarsky]]

https://github.com/servo/servo/pull/18430 for the first two parts.  I'll need to do a separate PR to rust-cssparser for part 3, once it has review...

Comment 24

[Xidorn Quan [:xidorn] UTC+10]

(In reply to Boris Zbarsky [:bz] (still digging out from vacation mail) from comment #21)
> > I wonder whether we can just remove the `Image` type and use `ImageLayer` directly
> > which would include variants currently in `Image` as well as a `None_`.
> 
> I think we can, and I'm happy to look into it as a followup, or have you
> look if you have time.  Would need to double-check the consumers who
> currently don't need to deal with None_.

I just had a look at this, and it seems to me this isn't that easy. <image> itself is a value type defined in CSS Images Lv3. Although majority of its uses are with none value, it isn't always that case. e.g. cursor can take <image> (although we currently only support <url>), in which case none is not a value at the same level as <image>.

So probably collapsing it isn't worth the effort, because we may want to decouple them at some point in the future.

If Rust is going to implement the enum flattening, we should probably just count on that.

Comment 25

[Simon Sapin (:SimonSapin)]

Comment on attachment 8906248 [details]
Bug 1397614 part 3.  Avoid array overallocation when parsing background-image property.

https://reviewboard.mozilla.org/r/177998/#review183208

r=me for this same change as a PR to https://github.com/servo/rust-cssparser/. Please also increment the version number to 0.20.2 in the same PR so that we can publish to crates.io with this change.

Comment 26

[Boris Zbarsky [:bzbarsky]]

The PR from comment 23 landed: https://hg.mozilla.org/integration/autoland/rev/d6c9a7de311e5e19a54e7403227c581d377a6718

https://github.com/servo/rust-cssparser/pull/195 and https://github.com/servo/servo/pull/18446 are for landing part 3.

Comment 27

[Boris Zbarsky [:bzbarsky]]

And https://hg.mozilla.org/integration/autoland/rev/ed8245718923a2b3470c4a1d4788c3282fa4ab3a