Bug 225838 – GraphicsLayer::setName() causes heap fragmentation

• Component: New Bugs
• Status: RESOLVED FIXED

[Geoffrey Garen]

GraphicsLayer::setName() causes heap fragmentation

[Geoffrey Garen]

Created attachment 428702 [details]
Patch

[Darin Adler]

Comment on attachment 428702 [details]
Patch

r=me, I guess, but how well does this work?

These names eventually are turned into NSString objects by PlatformCALayerCocoa::setName. Is there some guarantee those won’t cause the same kind of fragmentation? I’d think we’d want a scheme where these names end up being a single set of NSString objects, one for each individual names. Doesn’t seem necessary for the literals to ever be turned into WTF::String; the WTF::String is just a way to ferry the data along to get to the NSString, except for the case of "structural layers". Looking into those, it looks like nothing prevents GraphicsLayerCA::updateNames from creating a new WTF::String each time!

I’d try to go further like I am saying above, because I would be surprised if the WTF::String objects were causing fragmentation in a way that the NSString objects we make from them are not.

Likely we can take advantage of a fixed set of layer names to make sure we don't do allocation, at the risk of having layer name machinery be a little less cleanly cross-platform.

[Chris Dumez]

(In reply to Darin Adler from comment #2)
> Comment on attachment 428702 [details]
> Patch
> 
> r=me, I guess, but how well does this work?
> 
> These names eventually are turned into NSString objects by
> PlatformCALayerCocoa::setName. Is there some guarantee those won’t cause the
> same kind of fragmentation? I’d think we’d want a scheme where these names
> end up being a single set of NSString objects, one for each individual
> names. Doesn’t seem necessary for the literals to ever be turned into
> WTF::String; the WTF::String is just a way to ferry the data along to get to
> the NSString, except for the case of "structural layers". Looking into
> those, it looks like nothing prevents GraphicsLayerCA::updateNames from
> creating a new WTF::String each time!
> 
> I’d try to go further like I am saying above, because I would be surprised
> if the WTF::String objects were causing fragmentation in a way that the
> NSString objects we make from them are not.
> 
> Likely we can take advantage of a fixed set of layer names to make sure we
> don't do allocation, at the risk of having layer name machinery be a little
> less cleanly cross-platform.

Instead of updating the call sites, would it make sense to update GraphicsLayer::setName()'s parameter type to be AtomString (and GraphicsLayer::m_name)? Or are they many call sites with unique names?

[Geoffrey Garen]

> Instead of updating the call sites, would it make sense to update
> GraphicsLayer::setName()'s parameter type to be AtomString (and
> GraphicsLayer::m_name)? Or are they many call sites with unique names?

There are some call sites with unique names. Not necessarily many. Seems like I could just update setName()? What do you think?

[Chris Dumez]

(In reply to Geoffrey Garen from comment #4)
> > Instead of updating the call sites, would it make sense to update
> > GraphicsLayer::setName()'s parameter type to be AtomString (and
> > GraphicsLayer::m_name)? Or are they many call sites with unique names?
> 
> There are some call sites with unique names. Not necessarily many. Seems
> like I could just update setName()? What do you think?

I personally would be in favor of that. It would be nicer than explicit AtomString{}s at call sites.

[Geoffrey Garen]

> These names eventually are turned into NSString objects by
> PlatformCALayerCocoa::setName. Is there some guarantee those won’t cause the
> same kind of fragmentation?

There's no guarantee. But, for whatever reason, PlatformCALayerCocoa::setName and StringImpl::createCFString() do not sure up as contributors to fragmentation. Maybe because GraphicsLayerCA::ensureStructuralLayer() includes NameChanged in the default set of flags, so it always allocates a new name? Maybe because we throw away some platform layers on memory warning?
 
> Likely we can take advantage of a fixed set of layer names to make sure we
> don't do allocation, at the risk of having layer name machinery be a little
> less cleanly cross-platform.

This was my first instinct but there's a non-trivial set of callers  that want to put interesting non-fixed text in there.

[Geoffrey Garen]

Created attachment 428712 [details]
Patch

[Chris Dumez]

Comment on attachment 428712 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=428712&action=review

> Source/WebCore/platform/graphics/GraphicsLayer.h:281
> +    virtual void setName(const AtomString& name) { m_name = name; }

You probably need to update the overrides too?

[Simon Fraser (smfr)]

Comment on attachment 428712 [details]
Patch

Won't this cause the AtomString table to get bloated with lots of single-use, unique strings from the call site in RenderLayerBacking::createPrimaryGraphicsLayer()?

[Simon Fraser (smfr)]

Seems like what we want is:
* AtomStings for the constant name call sites
* Sharing of the resulting NSStrings that get set on layers
* Non-atom strings for the variable call sites.

[Chris Dumez]

(In reply to Simon Fraser (smfr) from comment #9)
> Comment on attachment 428712 [details]
> Patch
> 
> Won't this cause the AtomString table to get bloated with lots of
> single-use, unique strings from the call site in
> RenderLayerBacking::createPrimaryGraphicsLayer()?

It will cause some extra hashing but why bloat unless those strings live for a long time?

[Chris Dumez]

(In reply to Simon Fraser (smfr) from comment #10)
> Seems like what we want is:
> * AtomStings for the constant name call sites

This is what Geoff has the earlier iteration. I suggested the more concise approach given that few call sites seem to use unique strings. 

> * Sharing of the resulting NSStrings that get set on layers
> * Non-atom strings for the variable call sites.

[Chris Dumez]

(In reply to Chris Dumez from comment #11)
> (In reply to Simon Fraser (smfr) from comment #9)
> > Comment on attachment 428712 [details]
> > Patch
> > 
> > Won't this cause the AtomString table to get bloated with lots of
> > single-use, unique strings from the call site in
> > RenderLayerBacking::createPrimaryGraphicsLayer()?
> 
> It will cause some extra hashing but why bloat unless those strings live for
> a long time?

Do we expect many unique layer names to live for an extended period of time?

[Sam Weinig]

Comment on attachment 428712 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=428712&action=review

> Source/WebCore/ChangeLog:9
> +        GraphicsLayer::setName() causes heap fragmentation
> +        https://bugs.webkit.org/show_bug.cgi?id=225838

Double title.

>> Source/WebCore/platform/graphics/GraphicsLayer.h:281
>> +    virtual void setName(const AtomString& name) { m_name = name; }
> 
> You probably need to update the overrides too?

There aren't that many places that call setName(), so I would recommend also going to those places and doing the whole `static MainThreadNeverDestroyed<const AtomString> fooString("foo", AtomString::ConstructFromLiteral);`.

The places I could find where that would beneficial are:
- RenderLayerCompositor (a bunch of calls to setName with constant strings)
- TileGrid / TileController (specifically TileController::zoomedOutTileGridContainerLayerName() and TileController::tileGridContainerLayerName())
- TileCoverageMap
- GraphicsLayerCA (some are constructed, but there are a few constant ones in here)
- PageOverlayController
- And then calls to RenderLayerBacking::createGraphicsLayer in RenderLayerBacking.

[Simon Fraser (smfr)]

(In reply to Chris Dumez from comment #13)
> (In reply to Chris Dumez from comment #11)
> > (In reply to Simon Fraser (smfr) from comment #9)
> > > Comment on attachment 428712 [details]
> > > Patch
> > > 
> > > Won't this cause the AtomString table to get bloated with lots of
> > > single-use, unique strings from the call site in
> > > RenderLayerBacking::createPrimaryGraphicsLayer()?
> > 
> > It will cause some extra hashing but why bloat unless those strings live for
> > a long time?
> 
> Do we expect many unique layer names to live for an extended period of time?

For most documents, they will last the lifetime of the document, yes.

[Sam Weinig]

(In reply to Simon Fraser (smfr) from comment #10)
> Seems like what we want is:
> * AtomStings for the constant name call sites
> * Sharing of the resulting NSStrings that get set on layers
> * Non-atom strings for the variable call sites.

If we don't think we are going to get much uniquing for the non-constant ones, I would recommend just swapping out the constant ones with static Strings so they are shared and avoiding AtomString.

[Sam Weinig]

(In reply to Darin Adler from comment #2)
> Comment on attachment 428702 [details]
> Patch
> 
> I’d try to go further like I am saying above, because I would be surprised
> if the WTF::String objects were causing fragmentation in a way that the
> NSString objects we make from them are not.
> 

We do try to reuse the underlying buffer when creating an NSString or CFString from a StringImpl, so in the ideal case, we would only be adding fragmentation for the objective-c object overhead.

[Darin Adler]

(In reply to Sam Weinig from comment #16)
> If we don't think we are going to get much uniquing for the non-constant
> ones, I would recommend just swapping out the constant ones with static
> Strings so they are shared and avoiding AtomString.

This is good advice.

[Darin Adler]

(In reply to Sam Weinig from comment #17)
> We do try to reuse the underlying buffer when creating an NSString or
> CFString from a StringImpl, so in the ideal case, we would only be adding
> fragmentation for the objective-c object overhead.

I would love to have more confidence about this. Specifically, are these fixed size Objective-C objects unlikely to cause fragmentation for some reason?

[Darin Adler]

(In reply to Sam Weinig from comment #16)
> (In reply to Simon Fraser (smfr) from comment #10)
> > Seems like what we want is:
> > * AtomStings for the constant name call sites
> > * Sharing of the resulting NSStrings that get set on layers
> > * Non-atom strings for the variable call sites.
> 
> If we don't think we are going to get much uniquing for the non-constant
> ones, I would recommend just swapping out the constant ones with static
> Strings so they are shared and avoiding AtomString.

I said this was good advice, but I think one fly in the ointment is the structural layers based on these constant-named layers. We would get uniquing from those, and also we won’t be using the MainThreadNeverDestroyed technique there. I don’t know how common they are, though, and how big a part of the problem.

Why can’t this be simpler?!

[Geoffrey Garen]

Let’s focus on WebKit strings for now and not NSStrings, since the heap profiler showed fragmentation in WebKit strings and not NSStrings, and the WebKit strings topic has turned out to be meaty enough on its own.

Options suggested so far as I understand them:
(1) Use AtomString always
(2) Use AtomString only for the constant strings
(3) Use MainThreadNeverDestroyed<AtomString> only for the constant strings
(4) Use MAKE_STATIC_STRING_IMPL only for the constant strings

Let’s not do (3). A permanent heap allocation initialized at an unpredictable time is a new source of fragmentation. It’s a bold move to start a race by running backwards. Let’s not be so bold.

That leaves (1), (2), and (4).

I have a slight preference for (1) because it’s the easiest developer ergonomics and the most future proof.  We’ve learned that setName() tends to produce long-lives strings that cause fragmentation, and it would be nice to encode that knowledge in code instead of making each developer re-learn it at each call site. I’d hate for a developer to reintroduce this fragmentation just by adding a new setName() call; or, worse, I’d hate for a developer to introduce a new setName() call and then encounter four different opinions about which argument type to use in their specific case.

There is a downside to adding an entry to the AtomString table: 16 bytes. Seems a lot smaller than the typical graphics layer and associated platform graphics layer.

Simon, you mentioned RenderLayerBacking::createPrimaryGraphicsLayer() — but that function seems to adopt the owning layer’s name, so I don’t see how it would produce a unique name in any proposal? (Maybe you were thinking of the truncation case? Is that common? Wouldn’t it be a win for multiple truncated-named layers to share names?)

Considering alternatives, (2) and (4) are probably good enough. Simon, Darin, Sam, do you want to form a consensus around (2) or (4)? I’d be happy to do (2) or (4) if either won consensus. Right now (1) has two votes, and I'm not sure if that's a plurality or not.

[Simon Fraser (smfr)]

(In reply to Geoffrey Garen from comment #21)

> There is a downside to adding an entry to the AtomString table: 16 bytes.
> Seems a lot smaller than the typical graphics layer and associated platform
> graphics layer.

The overhead is at least twice that because HashTables normally run at < 50% capacity. I forget if Yusuke changed AtomString's HashTable to use Robin Hood hashing to reduce this overhead, but the AtomString hash table is perhaps the largest source of hash table capacity (stale data in bug 186727). 

> Simon, you mentioned RenderLayerBacking::createPrimaryGraphicsLayer() — but
> that function seems to adopt the owning layer’s name, so I don’t see how it
> would produce a unique name in any proposal? (Maybe you were thinking of the
> truncation case? Is that common? Wouldn’t it be a win for multiple
> truncated-named layers to share names?)

m_owningLayer.name() returns a new String each time (via StringBuilder).

> Considering alternatives, (2) and (4) are probably good enough. Simon,
> Darin, Sam, do you want to form a consensus around (2) or (4)? I’d be happy
> to do (2) or (4) if either won consensus. Right now (1) has two votes, and
> I'm not sure if that's a plurality or not.

Can we actually gather data and measure?

[Geoffrey Garen]

(In reply to Simon Fraser (smfr) from comment #22)
> (In reply to Geoffrey Garen from comment #21)
> 
> > There is a downside to adding an entry to the AtomString table: 16 bytes.
> > Seems a lot smaller than the typical graphics layer and associated platform
> > graphics layer.
> 
> The overhead is at least twice that because HashTables normally run at < 50%
> capacity. I forget if Yusuke changed AtomString's HashTable to use Robin
> Hood hashing to reduce this overhead, but the AtomString hash table is
> perhaps the largest source of hash table capacity (stale data in bug
> 186727). 

No, AtomStringTable is a HashSet and the key is a StringImpl pointer, so 16 bytes includes the 2X overhead.

> > Simon, you mentioned RenderLayerBacking::createPrimaryGraphicsLayer() — but
> > that function seems to adopt the owning layer’s name, so I don’t see how it
> > would produce a unique name in any proposal? (Maybe you were thinking of the
> > truncation case? Is that common? Wouldn’t it be a win for multiple
> > truncated-named layers to share names?)
> 
> m_owningLayer.name() returns a new String each time (via StringBuilder).

Got it.

> > Considering alternatives, (2) and (4) are probably good enough. Simon,
> > Darin, Sam, do you want to form a consensus around (2) or (4)? I’d be happy
> > to do (2) or (4) if either won consensus. Right now (1) has two votes, and
> > I'm not sure if that's a plurality or not.
> 
> Can we actually gather data and measure?

You mean implement all of (1), (2), and (4), and run our 24 hour fragmentation test and Membuster and PLUM3 on each of them to measure if any had a statistically significant memory win vs the others? Yes, we could do that. It would probably take about a month.

Do you think this discussion warrants a month's worth of investigation? Darin, Sam, do you want to form consensus around a month of investigation?

[Darin Adler]

I’m not trying to interfere with your decision making. I was trying to point out some things you might have overlooked. I’m still back where I was originally: "review+ and does this work?"

[Simon Fraser (smfr)]

My proposed level of investigation would be to add some logging, visit a few websites, and pipe the results into 'sort | uniq -c | sort -rn' to just get a feel for the relative frequencies of unique and non-unique strings.

[Simon Fraser (smfr)]

Quick experiment with logging and browsing twitter, YouTube, apple.com, gmail, theverge shows:

1236 ancestor clipping
 298 child clipping
 218 clip for scroller
  27 vertical scrollbar container
  26 overflow controls host
  26 frame scrolled contents
  26 frame clipping
  26 content root
  26 Page TiledBacking containment
  25 mask
  22 RenderBlock (positioned) 0x75d9d2f70 DIV 0x75d9242a0 class='c-nav-list__inner'
  22 RenderBlock (positioned) 0x75d9893d0 A 0x75d90c400 class='sr-only link-skip'
  16 overhang areas
  14 scrolled contents
  14 scroll container
  14 overflow controls container
  12 vertical scrollbar
   8 RenderBlock 0x7d733f5a0 DIV 0x7d73dccb0 id='header' class='style-scope ytd-browse'
   7 View overlay container
   7 RenderBlock 0x448f4f078 DIV 0x448841420 id=':3' class='Tm aeJ'
   7 Document overlay Container
   6 RenderSVGRoot 0x7d7340460 svg 0x7d185a4f0
...
and a long tail of 2300 more mostly unique names.

One obvious fix is to not include addresses the the strings in release builds (which I thought we did not but I guess I was wrong).

[Simon Fraser (smfr)]

 Note: these are frequencies of non-redundant calls to setName(), not of live strings.

[Geoffrey Garen]

(In reply to Simon Fraser (smfr) from comment #25)
> My proposed level of investigation would be to add some logging, visit a few
> websites, and pipe the results into 'sort | uniq -c | sort -rn' to just get
> a feel for the relative frequencies of unique and non-unique strings.

Sounds good. And thanks for gathering this.

Given the combination of repeated and unrepeated strings, does that make you prefer (2) or (4) to (1)? (Or maybe remove the pointers in release builds and then do (1)?)

Where are the setName calls that use pointers?

[Simon Fraser (smfr)]

(In reply to Geoffrey Garen from comment #28)
> (In reply to Simon Fraser (smfr) from comment #25)
> > My proposed level of investigation would be to add some logging, visit a few
> > websites, and pipe the results into 'sort | uniq -c | sort -rn' to just get
> > a feel for the relative frequencies of unique and non-unique strings.
> 
> Sounds good. And thanks for gathering this.
> 
> Given the combination of repeated and unrepeated strings, does that make you
> prefer (2) or (4) to (1)? (Or maybe remove the pointers in release builds
> and then do (1)?)
> 
> Where are the setName calls that use pointers?

Strings that come out of renderer().debugDescription(). I'll fix via bug 225926.

[Darin Adler]

That histogram says that more than half the names are unique!

[Simon Fraser (smfr)]

Without addresses, after some not-very-scientific browsing of common sites:

 724 ancestor clipping
 514 child clipping
 327 RenderFlexibleBox  DIV class='css-1dbjc4n r-xoduu5 r-1udh08x'
 327 RenderBlock  SPAN class='css-901oao css-16my406 r-poiln3 r-n6v787 r-1cwl3u0 r-1k6nrdp r-1e081e0 ...'
 167 RenderBlock (positioned)  DIV class='stroke style-scope yt-interaction'
 167 RenderBlock (positioned)  DIV class='fill style-scope yt-interaction'
 129 RenderBlock (positioned)  DIV
 119 RenderBlock (positioned)  <pseudo>
  79 RenderFlexibleBox  YTD-CHANNEL-NAME id='channel-name' class='style-scope ytd-video-meta-block'
  77 RenderFlexibleBox  YTD-MENU-RENDERER class='style-scope ytd-rich-grid-media'
  72 RenderFlexibleBox  ARTICLE class='css-1dbjc4n r-1loqt21 r-18u37iz r-1ny4l3l r-1udh08x r-1qhn6m8 r-i0...
  72 RenderBlock (positioned)  YT-INTERACTION class='extended'
  60 RenderBlock (relative positioned)  DIV class='c-entry-box--compact__image'
  56 RenderFlexibleBox  YTD-THUMBNAIL-OVERLAY-NOW-PLAYING-RENDERER class='style-scope ytd-thumbnail'
  54 clip for scroller
  44 RenderBlock  DIV
  37 RenderFlexibleBox  ARTICLE class='css-1dbjc4n r-1loqt21 r-18u37iz r-1ut4w64 r-1ny4l3l r-1udh08x r-1q...
  32 RenderBlock (positioned)  DIV class='circle style-scope paper-spinner'
  26 RenderBlock (relative positioned)  DIV class='css-1dbjc4n r-1adg3ll r-1udh08x'
  24 overflow controls host
  24 mask
  24 frame scrolled contents
  24 frame clipping
  24 content root
  24 RenderView 
  24 RenderFlexibleBox  DIV class='css-1dbjc4n r-17bb2tj r-1muvv40 r-127358a r-1ldzwu0'
  24 Page TiledBacking containment
  22 RenderBlock (positioned)  DIV class='c-nav-list__inner'
  22 RenderBlock (positioned)  A class='sr-only link-skip'
  20 vertical scrollbar container
  16 RenderBlock (relative positioned)  DIV class='circle-clipper right style-scope paper-spinner'
  14 overhang areas
  14 RenderImage  IMG class='adk T-I-J3'
  14 RenderFlexibleBox  DIV class='G-atb D E'
  12 scrolled contents
  12 scroll container
  12 overflow controls container
  12 RenderFlexibleBox  DIV id='label' class='style-scope ytd-thumbnail-overlay-toggle-button-renderer'
  12 RenderBlock (positioned)  DIV class='n00je7tq arfg74bv qs9ysxi8 k77z8yql i09qtzwb n7fi1qx3 b5wmifdl ...
  11 vertical scrollbar
  11 RenderFlexibleBox  DIV class='css-1dbjc4n r-1bs4hfb r-1867qdf r-1phboty r-rs99b7 r-1s2bzr4 r-1ny4l3l...
  11 RenderBlock (relative positioned)  DIV
  10 RenderBlock (relative positioned)  DIV class='y4'
  10 RenderBlock (relative positioned)  DIV class='css-1dbjc4n r-1adg3ll r-1pi2tsx r-1udh08x r-bnwqim r-1...
  10 RenderBlock (positioned)  DIV class='nH bno adC'
   8 RenderVideo  VIDEO
   7 View overlay container
   7 RenderBlock (relative positioned)  DIV class='css-1tfqggw'
   7 RenderBlock (positioned)  A class='p-badge p-badge__overlay p-badge__play'
   7 Document overlay Container
   5 RenderImage  IMG class='css-1j5kxti'

and about 290 more strings at 5 and lower.

[Geoffrey Garen]

Even though the top two strings, and the top fragmentation profiled strings, are constant strings, it looks like there's a significant pile of duplicate non-constant strings here (once bug 225926 is resolved).

Is that a reason to prefer (1)?

[Darin Adler]

Too much unknown: If those non-constant strings are unique and used non-overlapping (used only once, or used, destroyed, then separately used again), then (1) will not reduce fragmentation (no reduction of the amount or improvement in the timing of allocation), but will have a performance cost (storing each string in the AtomString table).

[Simon Fraser (smfr)]

(In reply to Darin Adler from comment #33)
> Too much unknown: If those non-constant strings are unique and used
> non-overlapping (used only once, or used, destroyed, then separately used
> again), then (1) will not reduce fragmentation (no reduction of the amount
> or improvement in the timing of allocation), but will have a performance
> cost (storing each string in the AtomString table).

These non-constant strings will generally have the lifetime of the Document, though there will be some churn as document contents change. Some strings will be common to different documents from the same origin. It's possible that all copies of a given string will be destroyed then re-created when navigating to a new Document.

[Radar WebKit Bug Importer]

<rdar://problem/78222774>

[Geoffrey Garen]

I did a little logging similar to Simon’s, but instrumenting whether the AtomString passed to setName() was new or duplicated (i.e. reused). A reasonable number of strings ended up as duplicated text but not duplicated AtomStrings — because they did not overlap in time.

I guess this means that (1) is a good way to put a ceiling on the cost of these strings, but (4) is slightly more impactful on average. We could do both, but I don’t know how I would measure the net benefit. So, I guess I’ll post a patch for (4).

[Geoffrey Garen]

Created attachment 429109 [details]
AtomString duplication logging

[Geoffrey Garen]

Created attachment 429112 [details]
Patch

[Geoffrey Garen]

Created attachment 429181 [details]
Patch for landing

[EWS]

Committed r277792 (237953@main): <https://commits.webkit.org/237953@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 429181 [details].