[golang-dev] code review 6613064: container/heap: optimization in case heap has many dupl... (issue 6613064)

Reviewers: gri,

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

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


Description:
container/heap: optimization in case heap has many duplicates

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

Please review this at http://codereview.appspot.com/6613064/

Affected files:
M src/pkg/container/heap/heap.go
M src/pkg/container/heap/heap_test.go


Index: src/pkg/container/heap/heap.go
===================================================================
--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -79,7 +79,7 @@
func up(h Interface, j int) {
for {
i := (j - 1) / 2 // parent
- if i == j || h.Less(i, j) {
+ if i == j || !h.Less(j, i) {
break
}
h.Swap(i, j)
@@ -97,7 +97,7 @@
if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
j = j2 // = 2*i + 2 // right child
}
- if h.Less(i, j) {
+ if !h.Less(j, i) {
break
}
h.Swap(i, j)
Index: src/pkg/container/heap/heap_test.go
===================================================================
--- a/src/pkg/container/heap/heap_test.go
+++ b/src/pkg/container/heap/heap_test.go
@@ -170,3 +170,15 @@
}
}
}
+
+func BenchmarkDup(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ h := new(myHeap)
+ for j := 0; j < 10000; j++ {
+ Push(h, 0) // all elements are the same
+ }
+ for h.Len() > 0 {
+ Pop(h)
+ }
+ }
+}