From 6a7c63a08ab353c7e41cb24ae66e73fb3cb7cb56 Mon Sep 17 00:00:00 2001
From: Aliaksandr Valialkin <valyala@gmail.com>
Date: Tue, 12 Sep 2017 14:04:34 +0300
Subject: [PATCH] runtime: optimize siftupTimer and siftdownTimer a bit
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Write the moving timer only once, since it is overwritten
by swapped timers on all the iterations except the last one.

Additionally, explicitly pass timers heap into siftupTimer
and siftdownTimer in order to make the code more clear.

Relevant benchmark results on linux/amd64:

Stop                      700µs ± 7%   608µs ± 1%  -13.13%  (p=0.000 n=10+10)
Stop-2                    440µs ± 4%   376µs ± 4%  -14.48%  (p=0.000 n=10+10)
Stop-4                    339µs ± 2%   330µs ± 3%   -2.66%  (p=0.015 n=10+10)
SimultaneousAfterFunc     702µs ± 9%   709µs ± 1%     ~     (p=0.436 n=9+9)
SimultaneousAfterFunc-2   573µs ± 2%   546µs ± 2%   -4.71%  (p=0.000 n=10+10)
SimultaneousAfterFunc-4   387µs ± 1%   368µs ± 1%   -4.89%  (p=0.000 n=8+10)
StartStop                 268µs ± 0%   270µs ± 0%   +0.91%  (p=0.000 n=9+9)
StartStop-2               155µs ± 6%   145µs ± 6%   -6.70%  (p=0.000 n=10+10)
StartStop-4               125µs ± 1%   124µs ± 1%     ~     (p=0.065 n=10+9)

Change-Id: I3685835b5e3e82844e2e5e73ee03a1e22100bf0e
Reviewed-on: https://go-review.googlesource.com/63110
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
---
 src/runtime/time.go | 28 +++++++++++++++-------------
 1 file changed, 15 insertions(+), 13 deletions(-)

diff --git a/src/runtime/time.go b/src/runtime/time.go
index 6bfa6ba160..b9454d6e2b 100644
--- a/src/runtime/time.go
+++ b/src/runtime/time.go
@@ -142,7 +142,7 @@ func (tb *timersBucket) addtimerLocked(t *timer) {
 	}
 	t.i = len(tb.t)
 	tb.t = append(tb.t, t)
-	tb.siftupTimer(t.i)
+	siftupTimer(tb.t, t.i)
 	if t.i == 0 {
 		// siftup moved to top: new earliest deadline.
 		if tb.sleeping {
@@ -182,8 +182,8 @@ func deltimer(t *timer) bool {
 	tb.t[last] = nil
 	tb.t = tb.t[:last]
 	if i != last {
-		tb.siftupTimer(i)
-		tb.siftdownTimer(i)
+		siftupTimer(tb.t, i)
+		siftdownTimer(tb.t, i)
 	}
 	unlock(&tb.lock)
 	return true
@@ -212,7 +212,7 @@ func timerproc(tb *timersBucket) {
 			if t.period > 0 {
 				// leave in heap but adjust next time to fire
 				t.when += t.period * (1 + -delta/t.period)
-				tb.siftdownTimer(0)
+				siftdownTimer(tb.t, 0)
 			} else {
 				// remove from heap
 				last := len(tb.t) - 1
@@ -223,7 +223,7 @@ func timerproc(tb *timersBucket) {
 				tb.t[last] = nil
 				tb.t = tb.t[:last]
 				if last > 0 {
-					tb.siftdownTimer(0)
+					siftdownTimer(tb.t, 0)
 				}
 				t.i = -1 // mark as removed
 			}
@@ -317,8 +317,7 @@ func timeSleepUntil() int64 {
 
 // Heap maintenance algorithms.
 
-func (tb *timersBucket) siftupTimer(i int) {
-	t := tb.t
+func siftupTimer(t []*timer, i int) {
 	when := t[i].when
 	tmp := t[i]
 	for i > 0 {
@@ -328,14 +327,15 @@ func (tb *timersBucket) siftupTimer(i int) {
 		}
 		t[i] = t[p]
 		t[i].i = i
-		t[p] = tmp
-		t[p].i = p
 		i = p
 	}
+	if tmp != t[i] {
+		t[i] = tmp
+		t[i].i = i
+	}
 }
 
-func (tb *timersBucket) siftdownTimer(i int) {
-	t := tb.t
+func siftdownTimer(t []*timer, i int) {
 	n := len(t)
 	when := t[i].when
 	tmp := t[i]
@@ -366,10 +366,12 @@ func (tb *timersBucket) siftdownTimer(i int) {
 		}
 		t[i] = t[c]
 		t[i].i = i
-		t[c] = tmp
-		t[c].i = c
 		i = c
 	}
+	if tmp != t[i] {
+		t[i] = tmp
+		t[i].i = i
+	}
 }
 
 // Entry points for net, time to call nanotime.
-- 
2.50.0