Deterministic SkTSet and PDF Output

Deterministic SkTSet and PDF Output

Addresses this issue: https://code.google.com/p/skia/issues/detail?id=1277

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

[ducky, 2013-07-16 01:03:10]

Deterministic PDF output by guaranteeing SkTSet's output is sorted in order of
insertion.

This uses an additional array in SkTSet to maintain sorted order (in addition to
the original array sorted by pointer to allow fast find())

Relevant bug: https://code.google.com/p/skia/issues/detail?id=1277

https://codereview.chromium.org/19283005/diff/7001/src/pdf/SkTSet.h
File src/pdf/SkTSet.h (right):

https://codereview.chromium.org/19283005/diff/7001/src/pdf/SkTSet.h#newcode59
src/pdf/SkTSet.h:59: int mergeInto(const SkTSet<T>& src) {
So this is now a O(n^2) algorithm (src loop, then array insertion memmove). With
a bit of extra complexity, O(n log n) is possible (separate fSetArray and
fOrderedArray merge stages). Is it worth optimizing - the current GMs seem to
run fine?

[vandebo (ex-Chrome), 2013-07-16 15:46:10]

Would there be a big penalty to pulling the extra functionality out of SkTSet? 
I was thinking another class (SkTOrderedSet?) that uses SkTSet.

[edisonn, 2013-07-16 15:57:02]

On 2013/07/16 15:46:10, vandebo wrote:
> Would there be a big penalty to pulling the extra functionality out of SkTSet?

> I was thinking another class (SkTOrderedSet?) that uses SkTSet.

I don't think it is a good idea to get better test tool experience at the
expense of user performance.
If we are going to make improvements for our tools, we should not degrade that
much the perf for users - from O(nlogn) to O(n^2)

[ducky, 2013-07-16 18:36:14]

On 2013/07/16 15:57:02, edisonn wrote:
> On 2013/07/16 15:46:10, vandebo wrote:
> > Would there be a big penalty to pulling the extra functionality out of
SkTSet?
> 
> > I was thinking another class (SkTOrderedSet?) that uses SkTSet.
> 
> I don't think it is a good idea to get better test tool experience at the
> expense of user performance.
> If we are going to make improvements for our tools, we should not degrade that
> much the perf for users - from O(nlogn) to O(n^2)

The original merge algorithm was O(n), but I don't think I can obtain that kind
of performance without additional bookkeeping data structures (and a larger
constant factor), which will also make everything messier...
Is O(n log n) fine?

It should be possible to put things into a separate class, but are there usage
cases for SkTSet which it's not generating a resource list? Or are we going to
conditionally instantiate SkTSet / SkTOrderedSet based on debug flags? Is
deterministic output (at the cost of a little bit of performance) a feature we
want in production?

[ducky, 2013-07-16 22:11:29]

Merge now O(n log n), using a two-stage algorithm as documented in the function
comments.

[edisonn, 2013-07-17 12:32:09]

LGTM with comments (please fix them before check in)

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h
File src/pdf/SkTSet.h (right):

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode139
src/pdf/SkTSet.h:139: SkASSERT(fOrderedArray);
assert fSetArray is empty too

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode146
src/pdf/SkTSet.h:146: SkASSERT(fOrderedArray);
assert both array have the same number of elements

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode153
src/pdf/SkTSet.h:153: SkASSERT(fOrderedArray);
I think we should report the number of total bytes (fSetArray)

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode231
src/pdf/SkTSet.h:231: fSetArray->reset();
I don't think we should reset fSetArray. We just call unref() on all elements,
we don't dispose of them.

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode240
src/pdf/SkTSet.h:240: fSetArray->reset();
I don't think we should reset fSetArray. We just safely call unref() on all
elements,
we don't dispose of them.

https://codereview.chromium.org/19283005/diff/17001/tests/TSetTest.cpp
File tests/TSetTest.cpp (right):

https://codereview.chromium.org/19283005/diff/17001/tests/TSetTest.cpp#newcod...
tests/TSetTest.cpp:121: REPORTER_ASSERT(reporter, set[COUNT+i] == 2 * i + 1);
COUNT + i instead of COUTN+i

[vandebo (ex-Chrome), 2013-07-17 15:30:43]

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h
File src/pdf/SkTSet.h (right):

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode25
src/pdf/SkTSet.h:25: template <typename T> class SkTSet {
Should this be renamed to SkTOrderedSet now?

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode280
src/pdf/SkTSet.h:280: // Checking fSetArray -> fOrderedArray should also be
done, but
What about sorting fSetArray into a temporary copy and checking that it's the
same as fOrderedArray ?

[ducky, 2013-07-17 19:32:21]

I've added a sort for SkTSet::validate / SkTSet::arraysConsistent - the check is
fast and through now.
I've also addressed the code review comments, though I'm not sure about some of
them.

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h
File src/pdf/SkTSet.h (right):

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode25
src/pdf/SkTSet.h:25: template <typename T> class SkTSet {
On 2013/07/17 15:30:43, vandebo wrote:
> Should this be renamed to SkTOrderedSet now?

Renaming this class would require a lot of changes throughout the PDF code. I'm
not sure it's worth it to go through and change everything, especially since in
most of the use cases, you're only using the plain set functionality?

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode139
src/pdf/SkTSet.h:139: SkASSERT(fOrderedArray);
On 2013/07/17 12:32:09, edisonn wrote:
> assert fSetArray is empty too

Done.

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode146
src/pdf/SkTSet.h:146: SkASSERT(fOrderedArray);
On 2013/07/17 12:32:09, edisonn wrote:
> assert both array have the same number of elements

Done.

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode153
src/pdf/SkTSet.h:153: SkASSERT(fOrderedArray);
On 2013/07/17 12:32:09, edisonn wrote:
> I think we should report the number of total bytes (fSetArray)

Should we? According to the function comments, it should be equivalent to
count*sizeof(T), which is the bytes taken by the output array.
I don't know what the current usage cases are, but with proper encapsulation,
fSetArray should be completely hidden, right?

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode231
src/pdf/SkTSet.h:231: fSetArray->reset();
On 2013/07/17 12:32:09, edisonn wrote:
> I don't think we should reset fSetArray. We just call unref() on all elements,
> we don't dispose of them.

This was a tricky one. I looked into SkTDArray.h, and it seems like unrefAll()
and safeUnrefAll() both invoke this->reset(). Since we don't want to
double-unref things, I've just moved the reset for the other array into SkTSet.
I'll add a comment to clarify this point (unless there's something wrong with my
logic?).

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode240
src/pdf/SkTSet.h:240: fSetArray->reset();
On 2013/07/17 12:32:09, edisonn wrote:
> I don't think we should reset fSetArray. We just safely call unref() on all
> elements,
> we don't dispose of them.

See above comment - SkTDArray::safeUnrefAll does a reset on itself.

https://codereview.chromium.org/19283005/diff/17001/src/pdf/SkTSet.h#newcode280
src/pdf/SkTSet.h:280: // Checking fSetArray -> fOrderedArray should also be
done, but
On 2013/07/17 15:30:43, vandebo wrote:
> What about sorting fSetArray into a temporary copy and checking that it's the
> same as fOrderedArray ?

Done.

https://codereview.chromium.org/19283005/diff/17001/tests/TSetTest.cpp
File tests/TSetTest.cpp (right):

https://codereview.chromium.org/19283005/diff/17001/tests/TSetTest.cpp#newcod...
tests/TSetTest.cpp:121: REPORTER_ASSERT(reporter, set[COUNT+i] == 2 * i + 1);
On 2013/07/17 12:32:09, edisonn wrote:
> COUNT + i instead of COUTN+i

Done.

[edisonn, 2013-07-17 20:03:28]

LGTM

https://codereview.chromium.org/19283005/diff/27001/src/pdf/SkTSet.h
File src/pdf/SkTSet.h (right):

https://codereview.chromium.org/19283005/diff/27001/src/pdf/SkTSet.h#newcode157
src/pdf/SkTSet.h:157: size_t bytes() const {
if this function is not used anywhere, please remove it. If used, make sure the
previous contract is still respected.

[vandebo (ex-Chrome), 2013-07-17 20:20:57]

LGTM

[commit-bot: I haz the power, 2013-07-24 01:46:54]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/richardlin@chromium.org/19283005/27001

[commit-bot: I haz the power, 2013-07-24 01:51:10]

Change committed as 10298