First version of bitmap use tracking in SkPictureRecord

This is just the first version and shows how I intend to orchestrate this. Future enhancements will:

track the portion of the bitmap required
track any resizing that might be required
actually preload something

Committed: http://code.google.com/p/skia/source/detail?r=13704

[bsalomon, 2014-03-05 21:15:34]

logically makes sense to me. I'm not sure I know the picture code well enough to
spot potential bugs or problems with the implementation details.

[robertphillips, 2014-03-06 13:01:31]

adding Mike K.

[mtklein, 2014-03-06 16:20:37]

Sorry, I think I've mixed in questions about the implementation with questions
about the design.  The high-level design question is the comment on includes().

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.cpp
File src/core/SkPicturePlayback.cpp (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.c...
src/core/SkPicturePlayback.cpp:691: void SkPicturePlayback::preLoadBitmaps(const
SkTDArray<void*> &results) {
Can you add a note about the true type of the pointers and maybe find a better
name than results?  results isn't even really very clear down in draw(), but
here there's just no context at all.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.h
File src/core/SkPicturePlayback.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.h...
src/core/SkPicturePlayback.h:111: void preLoadBitmaps(const SkTDArray<void*>
&results);
we'd usually put the & with the >, no?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.cpp
File src/core/SkPictureRecord.cpp (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.cpp...
src/core/SkPictureRecord.cpp:1632: if (SkBitmapHeap::INVALID_SLOT == bitmapID) {
Is this something we can also SkASSERT doesn't happen?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:29: class SkOffsetTable : public SkRefCnt {
Give this class its own .h/.cpp pair?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:33: for (int i = 0; i < fOffsetArrays.count(); ++i) {
fOffsetArrays.deleteAll(); ?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:38: void add(int id, size_t offset) {
// Record that this ID is used by the command starting at this offset.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:39: if (id >= fOffsetArrays.count()) {
Can you note somewhere, maybe at the top of the class, that we expect IDs to be
dense?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:45: }
Are we assuming |IDs| << |offsets|?  If there are many IDs, add is going to
scale badly.  (Might tack on O(|IDs|)?)

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:57: bool overlap(int id, size_t min, size_t max) {
// Do the offsets of any commands referencing this ID fall in the range [min,
max] (both inclusive)?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:64: SkASSERT(fOffsetArrays[id]->count() > 0);
->front() and ->back() are about to check this anyway, right?  I guess it
doesn't hurt to leave it in.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:65: if (max < fOffsetArrays[id]->front() || min >
fOffsetArrays[id]->back()) {
Might help readability here to rename front to low or min, and back to high or
max?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:72: bool includes(int id, size_t offset) {
Note that this is linear in the number of commands referencing ID?

This table seems like something we could implement with O(1) guarantees for all
its operations.  If we're not going to do that, I'd want to be pretty clear
about the cost of each of these methods.  I'm worried these linear ops are going
to cause some picture screw case to take quadratic time.

Alternatively, maybe we should just make it all O(1)?  Should work with a
top-level hash table of IDs to (min offset, max offset, hash set of offsets)? 
And looks like if we make includes fast enough, we can eliminate overlaps() and
the need to track min and max altogether?

If the pairs of (ID, offset) are sparse enough, there's no real benefit even to
having a two layer hash: we could just make a single hash set of (ID, offset)
pairs directly.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:85: SkASSERT(0);
Why this assert?  I guess we don't expect people to be asking questions about
offsets we haven't yet swept past?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:92: void add(size_t offset) { *fOffsets.append() =
offset;  }
Seems like we'd want to add
  SkASSERT(fOffsets.count() == 0 || offset > this->back());
to make the ordering assumption clear?  It's probably worth mentioning that
offsets must be added in increasing order on SkOffsetTable::add()?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:388: SkOffsetTable* fBitmapUseOffsets;
SkAutoTUnref<SkOffsetTable> ?

[robertphillips, 2014-03-06 20:18:26]

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.cpp
File src/core/SkPicturePlayback.cpp (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.c...
src/core/SkPicturePlayback.cpp:691: void SkPicturePlayback::preLoadBitmaps(const
SkTDArray<void*> &results) {
On 2014/03/06 16:20:38, mtklein wrote:
> Can you add a note about the true type of the pointers and maybe find a better
> name than results?  results isn't even really very clear down in draw(), but
> here there's just no context at all.

Done?

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.h
File src/core/SkPicturePlayback.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPicturePlayback.h...
src/core/SkPicturePlayback.h:111: void preLoadBitmaps(const SkTDArray<void*>
&results);
On 2014/03/06 16:20:38, mtklein wrote:
> we'd usually put the & with the >, no?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.cpp
File src/core/SkPictureRecord.cpp (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.cpp...
src/core/SkPictureRecord.cpp:1632: if (SkBitmapHeap::INVALID_SLOT == bitmapID) {
addBitmap can return this value so we need this check somewhere. It seemed
cleaner to have it in here rather then distributed throughout the draw* calls.
Since we never want to preload a bad bitmap I just don't track it at all
(SkPicturePlayback::getBitmap will return a stock bad bitmap).

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:29: class SkOffsetTable : public SkRefCnt {
Will do. I will leave that as a final refactoring so there is some continuity in
the code review.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:33: for (int i = 0; i < fOffsetArrays.count(); ++i) {
On 2014/03/06 16:20:38, mtklein wrote:
> fOffsetArrays.deleteAll(); ?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:38: void add(int id, size_t offset) {
On 2014/03/06 16:20:38, mtklein wrote:
> // Record that this ID is used by the command starting at this offset.

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:39: if (id >= fOffsetArrays.count()) {
On 2014/03/06 16:20:38, mtklein wrote:
> Can you note somewhere, maybe at the top of the class, that we expect IDs to
be
> dense?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:45: }
|IDs| is < |offsets| but it varies widely between pages (e.g., for baidu |IDs|
== 1). We can always gather some stats about how many textures webpages have but
I think this will ultimately wind up being a hash table and then the stats we're
concerned about change a bit.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:57: bool overlap(int id, size_t min, size_t max) {
On 2014/03/06 16:20:38, mtklein wrote:
> // Do the offsets of any commands referencing this ID fall in the range [min,
> max] (both inclusive)?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:64: SkASSERT(fOffsetArrays[id]->count() > 0);
I've added a comment. The assert here was basically "if there is an offset array
there should be at least one use". The ones in front & back are more for if they
are ever used elsewhere.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:65: if (max < fOffsetArrays[id]->front() || min >
fOffsetArrays[id]->back()) {
On 2014/03/06 16:20:38, mtklein wrote:
> Might help readability here to rename front to low or min, and back to high or
> max?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:72: bool includes(int id, size_t offset) {
Yep - right now I'm just trying to get it working. I think it will ultimately
wind up being a hash table. I've added a TODO to capture this.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:85: SkASSERT(0);
Given that this should always be guarded by a 'overlap' call, we should always
have some entry in 'array' that is >= to 'offset' (and return from within the
loop).

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:92: void add(size_t offset) { *fOffsets.append() =
offset;  }
On 2014/03/06 16:20:38, mtklein wrote:
> Seems like we'd want to add
>   SkASSERT(fOffsets.count() == 0 || offset > this->back());
> to make the ordering assumption clear?  It's probably worth mentioning that
> offsets must be added in increasing order on SkOffsetTable::add()?

Done.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:388: SkOffsetTable* fBitmapUseOffsets;
On 2014/03/06 16:20:38, mtklein wrote:
> SkAutoTUnref<SkOffsetTable> ?

Done.

[tomhudson, 2014-03-07 11:28:42]

+ some of LON who are working in SkPicture subclasses.

[mtklein, 2014-03-07 13:04:07]

lgtm

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:85: SkASSERT(0);
On 2014/03/06 20:18:26, robertphillips wrote:
> Given that this should always be guarded by a 'overlap' call, we should always
> have some entry in 'array' that is >= to 'offset' (and return from within the
> loop).

Ah, can you add // We're guarded by an overlap() call, so we should always find
something.  ?

[robertphillips, 2014-03-07 13:23:00]

And I split SkOffsetTable into its own files.

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/187833003/diff/1/src/core/SkPictureRecord.h#n...
src/core/SkPictureRecord.h:85: SkASSERT(0);
On 2014/03/07 13:04:08, mtklein wrote:
> On 2014/03/06 20:18:26, robertphillips wrote:
> > Given that this should always be guarded by a 'overlap' call, we should
always
> > have some entry in 'array' that is >= to 'offset' (and return from within
the
> > loop).
> 
> Ah, can you add // We're guarded by an overlap() call, so we should always
find
> something.  ?

Done.

[robertphillips, 2014-03-07 14:50:46]

The CQ bit was checked by robertphillips@google.com

[commit-bot: I haz the power, 2014-03-07 14:50:57]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/robertphillips@google.com/187833003/6...

[commit-bot: I haz the power, 2014-03-07 15:53:06]

Change committed as 13704