From 41e176fbe09de9487fad9577df8222d2073d6d21 Mon Sep 17 00:00:00 2001
From: Josh Bleecher Snyder <josharian@gmail.com>
Date: Fri, 25 Mar 2016 07:33:39 -0700
Subject: [PATCH] cmd/compile/ssa: generate less garbage in schedule
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Passes toolstash -cmp.

name       old alloc/op    new alloc/op    delta
Template      58.5MB ± 0%     57.8MB ± 0%  -1.15%        (p=0.000 n=10+10)
Unicode       41.3MB ± 0%     41.2MB ± 0%  -0.17%        (p=0.000 n=10+10)
GoTypes        196MB ± 0%      193MB ± 0%  -1.26%        (p=0.000 n=10+10)
Compiler       863MB ± 0%      850MB ± 0%  -1.49%        (p=0.000 n=10+10)

name       old allocs/op   new allocs/op   delta
Template        522k ± 0%       507k ± 0%  -2.99%        (p=0.000 n=10+10)
Unicode         403k ± 0%       401k ± 0%  -0.42%        (p=0.000 n=10+10)
GoTypes        1.58M ± 0%      1.52M ± 0%  -3.61%        (p=0.000 n=10+10)
Compiler       6.47M ± 0%      6.17M ± 0%  -4.62%        (p=0.000 n=10+10)

Change-Id: Ia7a6242e8d226b41966c344d253814dcce6424a8
Reviewed-on: https://go-review.googlesource.com/21141
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
---
 src/cmd/compile/internal/ssa/schedule.go | 47 +++++++++++++-----------
 1 file changed, 25 insertions(+), 22 deletions(-)

diff --git a/src/cmd/compile/internal/ssa/schedule.go b/src/cmd/compile/internal/ssa/schedule.go
index 8124823040..765f0c1277 100644
--- a/src/cmd/compile/internal/ssa/schedule.go
+++ b/src/cmd/compile/internal/ssa/schedule.go
@@ -16,8 +16,8 @@ const (
 )
 
 type ValHeap struct {
-	a    []*Value
-	less func(a, b *Value) bool
+	a     []*Value
+	score []int8
 }
 
 func (h ValHeap) Len() int      { return len(h.a) }
@@ -36,7 +36,24 @@ func (h *ValHeap) Pop() interface{} {
 	h.a = old[0 : n-1]
 	return x
 }
-func (h ValHeap) Less(i, j int) bool { return h.less(h.a[i], h.a[j]) }
+func (h ValHeap) Less(i, j int) bool {
+	x := h.a[i]
+	y := h.a[j]
+	sx := h.score[x.ID]
+	sy := h.score[y.ID]
+	if c := sx - sy; c != 0 {
+		return c > 0 // higher score comes later.
+	}
+	if x.Line != y.Line { // Favor in-order line stepping
+		return x.Line > y.Line
+	}
+	if x.Op != OpPhi {
+		if c := len(x.Args) - len(y.Args); c != 0 {
+			return c < 0 // smaller args comes later
+		}
+	}
+	return x.ID > y.ID
+}
 
 // Schedule the Values in each Block. After this phase returns, the
 // order of b.Values matters and is the order in which those values
@@ -48,6 +65,9 @@ func schedule(f *Func) {
 	// by values that have not been scheduled yet.
 	uses := make([]int32, f.NumValues())
 
+	// reusable priority queue
+	priq := new(ValHeap)
+
 	// "priority" for a value
 	score := make([]int8, f.NumValues())
 
@@ -156,25 +176,8 @@ func schedule(f *Func) {
 
 		// To put things into a priority queue
 		// The values that should come last are least.
-		priq := &ValHeap{
-			a: make([]*Value, 0, 8), // TODO allocate once and reuse.
-			less: func(x, y *Value) bool {
-				sx := score[x.ID]
-				sy := score[y.ID]
-				if c := sx - sy; c != 0 {
-					return c > 0 // higher score comes later.
-				}
-				if x.Line != y.Line { // Favor in-order line stepping
-					return x.Line > y.Line
-				}
-				if x.Op != OpPhi {
-					if c := len(x.Args) - len(y.Args); c != 0 {
-						return c < 0 // smaller args comes later
-					}
-				}
-				return x.ID > y.ID
-			},
-		}
+		priq.score = score
+		priq.a = priq.a[:0]
 
 		// Initialize priority queue with schedulable values.
 		for _, v := range b.Values {
-- 
2.48.1