FAQ
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)
+ }
+ }
+}

Search Discussions

  • Gri at Oct 10, 2012 at 1:29 am
    Looks good. Some suggestions below.


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

    https://codereview.appspot.com/6613064/diff/3001/src/pkg/container/heap/heap_test.go#newcode176
    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.

    https://codereview.appspot.com/6613064/
  • Taj Khattra at Oct 10, 2012 at 1:43 pm
    Hello gri@golang.org (cc: golang-dev@googlegroups.com),

    Please take another look.


    http://codereview.appspot.com/6613064/
  • Taj Khattra at Oct 10, 2012 at 2:09 pm

    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%

    https://codereview.appspot.com/6613064/
  • Gri at Oct 10, 2012 at 7:28 pm
  • Gri at Oct 10, 2012 at 7:33 pm
    *** 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>


    http://codereview.appspot.com/6613064/

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedOct 7, '12 at 4:35a
activeOct 10, '12 at 7:33p
posts6
users2
websitegolang.org

2 users in discussion

Taj Khattra: 3 posts Gri: 3 posts

People

Translate

site design / logo © 2022 Grokbase