Bug 54133 – [chromium] Replace tiler data structure with something smarter

• Status: RESOLVED
• Resolution: FIXED
• Component: WebKit Misc.

[Adrienne Walker]

Currently, Chromium's tiled compositor uses a logical 2D array to hold all the tiles in a page, where their position is implicit based on their location in the array.  If the page size is large, this is inefficient.  At extremely large page sizes, this becomes impossible due to integer arithmetic overflow.

This needs to be changed to something that uses less memory and is more efficient when resizing.  Even just storing position explicitly and having a flat list of "visible" tiles might be just as reasonable.

[Adrienne Walker]

Created attachment 83403 [details]
Patch

[Kenneth Russell]

Comment on attachment 83403 [details]
Patch

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

Looks good overall. A couple of minor comments/questions and one small must-fix bug.

> Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:206
>      for (size_t i = 0; i < m_tiles.size(); ++i) {
> -        if (m_tiles[i])
> -            m_unusedTiles.append(m_tiles[i].release());
> +        m_unusedTiles.append(m_tiles[i].release());
>      }

No braces for one-line bodies.

> Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:223
> +    // To avoid an O(n^2) check for tile existence via tileAt, keep a flag
> +    // vector indexed by tile location marking all the tiles we've seen already.

Wouldn't it be better to just bite the bullet and use a HashMap whose keys are the (i,j) pairs of ints and whose values are Tile*'s?

> Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:497
> +    m_tiler->m_tiles[m_idx].release();

This leaks memory! You probably meant to call clear(), but you shouldn't need to do this at all -- the resize() call after the swap() should take care of destroying the last OwnPtr<Tile> and therefore its referent.

[Adrienne Walker]

(In reply to comment #2)
> (From update of attachment 83403 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=83403&action=review
> 
> Looks good overall. A couple of minor comments/questions and one small must-fix bug.
> 
> > Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:206
> >      for (size_t i = 0; i < m_tiles.size(); ++i) {
> > -        if (m_tiles[i])
> > -            m_unusedTiles.append(m_tiles[i].release());
> > +        m_unusedTiles.append(m_tiles[i].release());
> >      }
> 
> No braces for one-line bodies.

Oh, quite right.  I'm sad that check-webkit-style didn't yell at me first.

> > Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:223
> > +    // To avoid an O(n^2) check for tile existence via tileAt, keep a flag
> > +    // vector indexed by tile location marking all the tiles we've seen already.
> 
> Wouldn't it be better to just bite the bullet and use a HashMap whose keys are the (i,j) pairs of ints and whose values are Tile*'s?

That's a good suggestion.  It'd probably clean up this code quite a bit, so I'll look into that.

> > Source/WebCore/platform/graphics/chromium/LayerTilerChromium.cpp:497
> > +    m_tiler->m_tiles[m_idx].release();
> 
> This leaks memory! You probably meant to call clear(), but you shouldn't need to do this at all -- the resize() call after the swap() should take care of destroying the last OwnPtr<Tile> and therefore its referent.

Ack! You're quite right.  Thanks for catching that.

[Adrienne Walker]

Re: HashMap.  It's definitely the right data structure to use and the code is a lot cleaner for it.  However, as it turns out, HashMap is incompatible with OwnPtr as a value type (because there's no copy constructor on an OwnPtr).

The easiest, but most terrible solution is to leak/adopt the memory manually in LayerTilerChromium when adding and removing from the HashMap, but it subverts the whole reason for using OwnPtr in the first place.

A better approach might be creating an OwnPtrHashMap.  abarth proposed this last year, but it didn't materialize.  I think it also might be possible to add some additional template parameters to HashMap to allow for the storing of raw pointers in the underlying implementation but use PassOwnPtr at the HashMap API boundary to ensure that no memory leaks.

This looks like a not terribly small yak to shave, so I will likely punt on this patch temporarily.

[Kenneth Russell]

(In reply to comment #4)
> Re: HashMap.  It's definitely the right data structure to use and the code is a lot cleaner for it.  However, as it turns out, HashMap is incompatible with OwnPtr as a value type (because there's no copy constructor on an OwnPtr).
> 
> The easiest, but most terrible solution is to leak/adopt the memory manually in LayerTilerChromium when adding and removing from the HashMap, but it subverts the whole reason for using OwnPtr in the first place.
> 
> A better approach might be creating an OwnPtrHashMap.  abarth proposed this last year, but it didn't materialize.  I think it also might be possible to add some additional template parameters to HashMap to allow for the storing of raw pointers in the underlying implementation but use PassOwnPtr at the HashMap API boundary to ensure that no memory leaks.
> 
> This looks like a not terribly small yak to shave, so I will likely punt on this patch temporarily.

I assume you mean you'll go ahead with using a list and then potentially upgrade to a hash map in the future? I don't mean to derail this patch.

[Adrienne Walker]

Created attachment 85383 [details]
Patch

[Kenneth Russell]

Comment on attachment 85383 [details]
Patch

This looks much better. Thanks for cleaning it up and researching how best to use a map for the tiles.

[Adrienne Walker]

Committed r80767: <http://trac.webkit.org/changeset/80767>