1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package util
6
7import "time"
8
9// A Throttle permits throttling of a goroutine by
10// calling the Throttle method repeatedly.
11//
12type Throttle struct {
13	f  float64       // f = (1-r)/r for 0 < r < 1
14	dt time.Duration // minimum run time slice; >= 0
15	tr time.Duration // accumulated time running
16	ts time.Duration // accumulated time stopped
17	tt time.Time     // earliest throttle time (= time Throttle returned + tm)
18}
19
20// NewThrottle creates a new Throttle with a throttle value r and
21// a minimum allocated run time slice of dt:
22//
23//	r == 0: "empty" throttle; the goroutine is always sleeping
24//	r == 1: full throttle; the goroutine is never sleeping
25//
26// A value of r == 0.6 throttles a goroutine such that it runs
27// approx. 60% of the time, and sleeps approx. 40% of the time.
28// Values of r < 0 or r > 1 are clamped down to values between 0 and 1.
29// Values of dt < 0 are set to 0.
30//
31func NewThrottle(r float64, dt time.Duration) *Throttle {
32	var f float64
33	switch {
34	case r <= 0:
35		f = -1 // indicates always sleep
36	case r >= 1:
37		f = 0 // assume r == 1 (never sleep)
38	default:
39		// 0 < r < 1
40		f = (1 - r) / r
41	}
42	if dt < 0 {
43		dt = 0
44	}
45	return &Throttle{f: f, dt: dt, tt: time.Now().Add(dt)}
46}
47
48// Throttle calls time.Sleep such that over time the ratio tr/ts between
49// accumulated run (tr) and sleep times (ts) approximates the value 1/(1-r)
50// where r is the throttle value. Throttle returns immediately (w/o sleeping)
51// if less than tm ns have passed since the last call to Throttle.
52//
53func (p *Throttle) Throttle() {
54	if p.f < 0 {
55		select {} // always sleep
56	}
57
58	t0 := time.Now()
59	if t0.Before(p.tt) {
60		return // keep running (minimum time slice not exhausted yet)
61	}
62
63	// accumulate running time
64	p.tr += t0.Sub(p.tt) + p.dt
65
66	// compute sleep time
67	// Over time we want:
68	//
69	//	tr/ts = r/(1-r)
70	//
71	// Thus:
72	//
73	//	ts = tr*f with f = (1-r)/r
74	//
75	// After some incremental run time δr added to the total run time
76	// tr, the incremental sleep-time δs to get to the same ratio again
77	// after waking up from time.Sleep is:
78	if δs := time.Duration(float64(p.tr)*p.f) - p.ts; δs > 0 {
79		time.Sleep(δs)
80	}
81
82	// accumulate (actual) sleep time
83	t1 := time.Now()
84	p.ts += t1.Sub(t0)
85
86	// set earliest next throttle time
87	p.tt = t1.Add(p.dt)
88}
89