From d0051be847163f1bedb5a5c68f7827f40b4ef4e4 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 27 Mar 2024 22:14:27 -0400 Subject: [PATCH] runtime: simplify timers.siftDown MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit No effect on benchmarks, but the code is clearer. goos: linux goarch: amd64 pkg: time cpu: AMD Ryzen 9 7950X 16-Core Processor │ s7base.txt │ s7.txt │ │ sec/op │ sec/op vs base │ AdjustTimers10000-32 195.9µ ± 13% 198.1µ ± 2% ~ (p=0.436 n=10) AdjustTimers10000SingleThread-32 1.573m ± 13% 1.566m ± 10% ~ (p=0.739 n=10) AdjustTimers10000NoReset-32 170.6µ ± 1% 170.4µ ± 1% ~ (p=0.912 n=10) AdjustTimers10000NoSleep-32 183.9µ ± 2% 181.4µ ± 2% -1.39% (p=0.045 n=10) AdjustTimers10000NoResetNoSleep-32 151.3µ ± 1% 150.0µ ± 1% -0.90% (p=0.007 n=10) goos: darwin goarch: arm64 pkg: time cpu: Apple M3 Pro │ m3base.txt │ m3.txt │ │ sec/op │ sec/op vs base │ AdjustTimers10000-12 234.2µ ± 1% 234.5µ ± 1% ~ (p=0.796 n=10) AdjustTimers10000SingleThread-12 1.191m ± 1% 1.272m ± 1% +6.81% (p=0.000 n=10) AdjustTimers10000NoReset-12 239.6µ ± 2% 236.3µ ± 9% ~ (p=0.971 n=10) AdjustTimers10000NoSleep-12 223.3µ ± 2% 221.4µ ± 3% ~ (p=0.579 n=10) AdjustTimers10000NoResetNoSleep-12 209.2µ ± 2% 209.0µ ± 4% ~ (p=0.796 n=10) Change-Id: Id48aa893235d652814b7fa4605037f09b0b4d73b Reviewed-on: https://go-review.googlesource.com/c/go/+/574897 LUCI-TryBot-Result: Go LUCI Reviewed-by: Ian Lance Taylor --- src/runtime/time.go | 42 +++++++++++++++++++----------------------- 1 file changed, 19 insertions(+), 23 deletions(-) diff --git a/src/runtime/time.go b/src/runtime/time.go index 0d4eaa39ff..fc664f49eb 100644 --- a/src/runtime/time.go +++ b/src/runtime/time.go @@ -1077,8 +1077,8 @@ func (ts *timers) verify() { continue } - // The heap is 4-ary. See siftupTimer and siftdownTimer. - p := (i - 1) / 4 + // The heap is timerHeapN-ary. See siftupTimer and siftdownTimer. + p := int(uint(i-1) / timerHeapN) if tw.when < ts.heap[p].when { print("bad timer heap at ", i, ": ", p, ": ", ts.heap[p].when, ", ", i, ": ", tw.when, "\n") throw("bad timer heap") @@ -1139,6 +1139,8 @@ func timeSleepUntil() int64 { return next } +const timerHeapN = 4 + // Heap maintenance algorithms. // These algorithms check for slice index errors manually. // Slice index error can happen if the program is using racy @@ -1160,7 +1162,7 @@ func (ts *timers) siftUp(i int) { badTimer() } for i > 0 { - p := (i - 1) / 4 // parent + p := int(uint(i-1) / timerHeapN) // parent if when >= heap[p].when { break } @@ -1180,34 +1182,28 @@ func (ts *timers) siftDown(i int) { if i >= n { badTimer() } + if i*timerHeapN+1 >= n { + return + } tw := heap[i] when := tw.when if when <= 0 { badTimer() } for { - c := i*4 + 1 // left child - c3 := c + 2 // mid child - if c >= n { + leftChild := i*timerHeapN + 1 + if leftChild >= n { break } - w := heap[c].when - if c+1 < n && heap[c+1].when < w { - w = heap[c+1].when - c++ - } - if c3 < n { - w3 := heap[c3].when - if c3+1 < n && heap[c3+1].when < w3 { - w3 = heap[c3+1].when - c3++ - } - if w3 < w { - w = w3 - c = c3 + w := when + c := -1 + for j, tw := range heap[leftChild:min(leftChild+timerHeapN, n)] { + if tw.when < w { + w = tw.when + c = leftChild + j } } - if w >= when { + if c < 0 { break } heap[i] = heap[c] @@ -1222,11 +1218,11 @@ func (ts *timers) siftDown(i int) { // It takes O(n) time for n=len(ts.heap), not the O(n log n) of n repeated add operations. func (ts *timers) initHeap() { // Last possible element that needs sifting down is parent of last element; - // last element is len(t)-1; parent of last element is (len(t)-1-1)/4. + // last element is len(t)-1; parent of last element is (len(t)-1-1)/timerHeapN. if len(ts.heap) <= 1 { return } - for i := (len(ts.heap) - 1 - 1) / 4; i >= 0; i-- { + for i := int(uint(len(ts.heap)-1-1) / timerHeapN); i >= 0; i-- { ts.siftDown(i) } } -- 2.50.0