code review 6613064: container/heap: optimization in case heap has many dupl...

container/heap: optimization in case heap has many duplicates

benchmark       old ns/op    new ns/op    delta
BenchmarkDup      3075682       609448  -80.18%

[taj, 2012-10-06 20:57:33]

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

I'd like you to review this change to
https://go.googlecode.com/hg/

[gri, 2012-10-10 01:29:09]

Looks good. Some suggestions below.

https://codereview.appspot.com/6613064/diff/3001/src/pkg/container/heap/heap_...
File src/pkg/container/heap/heap_test.go (right):

https://codereview.appspot.com/6613064/diff/3001/src/pkg/container/heap/heap_...
src/pkg/container/heap/heap_test.go:176: h := new(myHeap)
You can move this outside the loop - no need to measure creation as well. After
each iteration, the heap is empty again.

You could even pre-allocate it, so that the append doesn't have to grow the
heap:

const n = 10000
h := make(myHeap, n)

as in:

	const n = 10000
	h := make(myHeap, n)
	for i := 0; i < b.N; i++ {
		for j := 0; j < n; j++ {
			Push(&h, 0) // all elements are the same
		}
		for h.Len() > 0 {
			Pop(&h)
		}
	}

This way, we really just measure the cost of a pure Push and Pop.

[taj, 2012-10-10 06:52:23]

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

Please take another look.

[taj, 2012-10-10 06:54:38]

On 2012/10/10 06:52:23, taj wrote:
> Hello mailto:gri@golang.org (cc: mailto:golang-dev@googlegroups.com),
> 
> Please take another look.

benchmark       old ns/op    new ns/op    delta
BenchmarkDup      3105734       540219  -82.61%

[gri, 2012-10-10 18:35:07]

LGTM

Thanks!
- gri

[gri, 2012-10-10 18:36:01]

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

container/heap: optimization in case heap has many duplicates

benchmark       old ns/op    new ns/op    delta
BenchmarkDup      3075682       609448  -80.18%

R=gri
CC=golang-dev
http://codereview.appspot.com/6613064

Committer: Robert Griesemer <gri@golang.org>