Avoid possible O(n) stack space use by skqsort.

Avoid possible O(n) stack space use by skqsort.

[bungeman, 2013-01-25 21:58:37]

This prevents using O(n) stack space in bad cases. It slows down the skqsort
benches by ~3%. Note that this same change has already been snuck in with
https://code.google.com/p/skia/source/detail?r=7397 for the ** specialization to
prevent bench from crashing.

There may be better ways of doing this, for instance keeping track of the stack
level and using a heap sort if we get too deep (similarly to using an insertion
sort below a certain partition size). Other proposals and ideas welcome.

[edisonn, 2013-01-28 14:39:31]

I would vote to keep the same algorithm across all QSort implementations, thus
extend 7397 to all QSort functions.

passing an extra parameter on the stack would clutter the algorithm, I like your
version more.


LGTM  

On 2013/01/25 21:58:37, bungeman wrote:
> This prevents using O(n) stack space in bad cases. It slows down the skqsort
> benches by ~3%. Note that this same change has already been snuck in with
> https://code.google.com/p/skia/source/detail?r=7397 for the ** specialization
to
> prevent bench from crashing.
> 
> There may be better ways of doing this, for instance keeping track of the
stack
> level and using a heap sort if we get too deep (similarly to using an
insertion
> sort below a certain partition size). Other proposals and ideas welcome.

[reed1, 2013-01-28 14:54:30]

Has the call-insertion-sort optimization been landed yet? If not, I'd prefer to
land that first (assuming we plan to) before we make this sort of change. That
way we can get a better measure of its impact.

[bungeman, 2013-01-28 21:52:30]

Patch set 2 makes SkTQSort(T* left, T* right) very fast, O(lg(n)) storage worst
bound, O(lg(n)) time worst bound, and is slightly faster than what we had
before. From what I've seen, this is more or less what most std:sort
implementations are doing these days.

[bungeman, 2013-01-29 16:15:51]

Now with all of the duplicate sorting code removed.

[reed1, 2013-01-29 16:30:32]

https://codereview.appspot.com/7222043/diff/12001/src/core/SkPictureStateTree.h
File src/core/SkPictureStateTree.h (right):

https://codereview.appspot.com/7222043/diff/12001/src/core/SkPictureStateTree...
src/core/SkPictureStateTree.h:38: uint32_t fOffset;
Lets land this part now

[reed1, 2013-01-29 16:35:43]

I think these are important enough, and subtle enough, that every function
deserves a block-comment of some sort.

Certainly the public top-level APIs deserve Doxygen style comment block, if just
to single them out as being the public APIs.

Seems like great work. Lets go the full mile and make the implementation be
super clear and maintainable.

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h
File src/core/SkTSort.h (right):

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h#newcode15
src/core/SkTSort.h:15: 
SkTOperatorLT ?

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h#newcode174
src/core/SkTSort.h:174: int depth = 0;
while (...) {
}

[bungeman, 2013-01-29 19:32:00]

Added comments and removed the function pointer wrapping version SkQSort.

https://codereview.appspot.com/7222043/diff/12001/src/core/SkPictureStateTree.h
File src/core/SkPictureStateTree.h (right):

https://codereview.appspot.com/7222043/diff/12001/src/core/SkPictureStateTree...
src/core/SkPictureStateTree.h:38: uint32_t fOffset;
On 2013/01/29 16:30:32, reed1 wrote:
> Lets land this part now

Done. See revision 7452.

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h
File src/core/SkTSort.h (right):

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h#newcode15
src/core/SkTSort.h:15: 
On 2013/01/29 16:35:43, reed1 wrote:
> SkTOperatorLT ?

Done. SkTCompareLT seemed a bit better, as it isn't really an operator (as in a
c++ operator), but it is a comparator.

https://codereview.appspot.com/7222043/diff/12001/src/core/SkTSort.h#newcode174
src/core/SkTSort.h:174: int depth = 0;
On 2013/01/29 16:35:43, reed1 wrote:
> while (...) {
> }

Done.

[reed1, 2013-01-30 18:19:40]

https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h#newcode130
src/core/SkRTree.h:130: 
Do we need struct+operator, or can we just write a static function with the same
signature?

https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h
File src/core/SkTSort.h (right):

https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h#newcode192
src/core/SkTSort.h:192: template <typename T, typename C> void SkTQSort(T* left,
T* right, C lessThan) {
can you use SkCLZ() here instead of a loop?

[bungeman, 2013-01-30 19:20:51]

https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h#newcode130
src/core/SkRTree.h:130: 
On 2013/01/30 18:19:40, reed1 wrote:
> Do we need struct+operator, or can we just write a static function with the
same
> signature?

Yes, we need this to be a functor. If it's a static function then we still need
the function pointer version of sort, and the comparison would not be inlined.
The extra verbosity is a bit off-putting though.

We can't really write a SkRTree::Branch::operator< either, as we would need two
of them (one for right/left, one for bottom/top).

https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h
File src/core/SkTSort.h (right):

https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h#newcode192
src/core/SkTSort.h:192: template <typename T, typename C> void SkTQSort(T* left,
T* right, C lessThan) {
On 2013/01/30 18:19:40, reed1 wrote:
> can you use SkCLZ() here instead of a loop?

I was unaware of it's existence. Changed to use SkNextLog2 which does use
SkCLZ(). It doesn't look like we have an SkCLZ specialization for x86?

[reed1, 2013-01-30 20:42:12]

On 2013/01/30 19:20:51, bungeman wrote:
> https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h
> File src/core/SkRTree.h (right):
> 
>
https://codereview.appspot.com/7222043/diff/17001/src/core/SkRTree.h#newcode130
> src/core/SkRTree.h:130: 
> On 2013/01/30 18:19:40, reed1 wrote:
> > Do we need struct+operator, or can we just write a static function with the
> same
> > signature?
> 
> Yes, we need this to be a functor. If it's a static function then we still
need
> the function pointer version of sort, and the comparison would not be inlined.
> The extra verbosity is a bit off-putting though.

My ignorance, but I don't see the difference between the two. Do we know that
the functors are *always* inlined, and that the static function is not?

> 
> We can't really write a SkRTree::Branch::operator< either, as we would need
two
> of them (one for right/left, one for bottom/top).
> 
> https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h
> File src/core/SkTSort.h (right):
> 
>
https://codereview.appspot.com/7222043/diff/17001/src/core/SkTSort.h#newcode192
> src/core/SkTSort.h:192: template <typename T, typename C> void SkTQSort(T*
left,
> T* right, C lessThan) {
> On 2013/01/30 18:19:40, reed1 wrote:
> > can you use SkCLZ() here instead of a loop?
> 
> I was unaware of it's existence. Changed to use SkNextLog2 which does use
> SkCLZ(). It doesn't look like we have an SkCLZ specialization for x86?

[bungeman, 2013-01-30 21:39:07]

Committed revision 7470.

Issue with left >= right and SkNextPow2 resolved with revision 7474.

[robertphillips, 2013-01-31 16:17:26]

This CL causes some minor images differences in the following layout tests (only
on Linux):

 svg/batik/text/smallFonts.svg [ ImageOnlyFailure ]
 svg/batik/text/textDecoration.svg [ ImageOnlyFailure ]
 svg/batik/text/textFeatures.svg [ ImageOnlyFailure ]
 svg/text/selection-styles.xhtml [ ImageOnlyFailure ]