code review 3373041: Sort: reduced stack depth to lg(n) in quickSort

Sort: reduced stack depth to lg(n) in quickSort

Doing the tail recursion elimination explicitly
seems safer than leaving it to the compiler;
the code is still clean and easy to understand.

[snilsson, 2010-12-01 19:51:48]

Hello r (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[r2, 2010-12-01 19:54:23]

gri@golang.org is the right reviewer.

-rob

On Dec 1, 2010, at 11:51 AM, snilsson@nada.kth.se wrote:

> Reviewers: r,
> 
> Message:
> Hello r (cc: golang-dev@googlegroups.com),
> 
> I'd like you to review this change.
> 
> 
> Description:
> Sort: reduced stack depth to lg(n) in quickSort
> 
> Doing the tail recursion elimination explicitly
> seems safer than leaving it to the compiler;
> the code is still clean and easy to understand.
> 
> Please review this at http://codereview.appspot.com/3373041/
> 
> Affected files:
>  M src/pkg/sort/sort.go
> 
> 
> Index: src/pkg/sort/sort.go
> ===================================================================
> --- a/src/pkg/sort/sort.go
> +++ b/src/pkg/sort/sort.go
> @@ -122,12 +122,22 @@
> }
> 
> func quickSort(data Interface, a, b int) {
> -	if b-a > 7 {
> -		mlo, mhi := doPivot(data, a, b)
> -		quickSort(data, a, mlo)
> -		quickSort(data, mhi, b)
> -	} else if b-a > 1 {
> -		insertionSort(data, a, b)
> +	for b-a > 0 {
> +		if b-a > 7 {
> +			mlo, mhi := doPivot(data, a, b)
> +			// Avoiding recursion on the larger subproblem guarantees
> +			// a stack depth of at most lg(b-a).
> +			if mlo-a < b-mhi {
> +				quickSort(data, a, mlo)
> +				a = mhi // i.e., quickSort(data, mhi, b)
> +			} else {
> +				quickSort(data, mhi, b)
> +				b = mlo // i.e., quickSort(data, a, mlo)
> +			}
> +		} else {
> +			insertionSort(data, a, b)
> +			return
> +		}
> 	}
> }
> 
> 
> 

[gri, 2010-12-01 22:01:19]

http://codereview.appspot.com/3373041/diff/2001/src/pkg/sort/sort.go
File src/pkg/sort/sort.go (right):

http://codereview.appspot.com/3373041/diff/2001/src/pkg/sort/sort.go#newcode124
src/pkg/sort/sort.go:124: func quickSort(data Interface, a, b int) {
I think this can be simplified to:

func quickSort(data Interface, a, b int) {
	for b-a > 7 {
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		insertionSort(data, a, b)
	}
}

[snilsson, 2010-12-01 22:41:41]

Cool, that also seems to shave off a few percents from the benchmarks.

Would it be OK to adjust the breakpoint here as well, or should that go into a
separate thread?

(It seems to me that a breakpoint in the 10-20 range, 16 perhaps, would be a
better choice than 7. The performance should be quite stable for breakpoints in
that range, but I see a performance hit for smaller and larger values.)

On 2010/12/01 22:01:19, gri wrote:
> I think this can be simplified to:
> 
...

[gri, 2010-12-01 22:44:44]

Let's change the breakpoint separately so that we have a clearly isolated CL
where we changed performance by adjusting the breakpoint.
- gri

On Wed, Dec 1, 2010 at 2:41 PM, <snilsson@nada.kth.se> wrote:

> Cool, that also seems to shave off a few percents from the benchmarks.
>
> Would it be OK to adjust the breakpoint here as well, or should that go
> into a separate thread?
>
> (It seems to me that a breakpoint in the 10-20 range, 16 perhaps, would
> be a better choice than 7. The performance should be quite stable for
> breakpoints in that range, but I see a performance hit for smaller and
> larger values.)
>
>
> On 2010/12/01 22:01:19, gri wrote:
>
>> I think this can be simplified to:
>>
>
> ...
>
>
>
>
> http://codereview.appspot.com/3373041/
>

[snilsson, 2010-12-01 23:12:05]

Hello r, r2, gri (cc: golang-dev@googlegroups.com),

Please take another look.

[gri, 2010-12-02 17:11:49]

LGTM
Thanks!
- gri

On Wed, Dec 1, 2010 at 3:12 PM, <snilsson@nada.kth.se> wrote:

> Hello r, r2, gri (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
>
> http://codereview.appspot.com/3373041/
>

[gri, 2010-12-02 17:18:23]

*** Submitted as http://code.google.com/p/go/source/detail?r=5866a9db7a1d ***

Sort: reduced stack depth to lg(n) in quickSort

Doing the tail recursion elimination explicitly
seems safer than leaving it to the compiler;
the code is still clean and easy to understand.

R=r, r2, gri
CC=golang-dev
http://codereview.appspot.com/3373041

Committer: Robert Griesemer <gri@golang.org>