Simplify and speed up SkIntroSort.

Simplify and speed up SkIntroSort.

[bungeman, 2013-02-04 17:17:44]

This makes the sort_skqsort_ bench ~7% faster in the rand case and ~12% faster
in the rand10 case. Note that this almost exclusively comes from increasing the
insertion sort threshold from 8 to 32. At these sizes insertion sort takes about
the same time as the pivot, but leaves a sorted sub-list. Doing the same
(increasing the insertion sort threshold) with the existing (previous) code
makes it run with this same improved time. However, the code in this CL is
smaller and easier to reason about.

The main simplification is that we're already using heap sort as a depth cutoff,
so we no longer need to recurse on the smaller side to avoid O(n) stack usage.
Also, recursing on the left side improves cache locality (as we will tend to
move from left to right through the list).

[reed1, 2013-02-04 18:39:08]

lgtm w/ request for comment.

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

https://codereview.appspot.com/7273048/diff/1/src/core/SkTSort.h#newcode187
src/core/SkTSort.h:187: }
Unrelated to this specific CL, but sure seems like this line deserves some
comment (what its computing, and where that gets used and why).

[bungeman, 2013-02-04 20:58:05]

Committed revision 7552.

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

https://codereview.appspot.com/7273048/diff/1/src/core/SkTSort.h#newcode187
src/core/SkTSort.h:187: }
On 2013/02/04 18:39:08, reed1 wrote:
> Unrelated to this specific CL, but sure seems like this line deserves some
> comment (what its computing, and where that gets used and why).

Done.