How Do They Do It: Timers in Go
This article covers the internal implementation of timers in Go. Note that there are a lot of links to Go repo in this article, I recommend to follow them to understand the material better.
Article was part of Go Advent 2016 series: https://blog.gopheracademy.com/advent-2016/go-timers/
Timers
Timers in Go just do something after a period of time. They are located in the standard package time. In particular, timers are time.Timer, time.Ticker, and less obvious timer time.Sleep. It’s not clear from the documentation how timers work exactly. Some people think that each timer spawns its own goroutine which exists until the timer’s deadline is reached because that’s how we’d implement timers in “naive” way in Go. We can check that assumption with the small program:
package main
import (
"fmt"
"os"
"runtime/debug"
"time"
)
func main() {
debug.SetTraceback("system")
if len(os.Args) == 1 {
panic("before timers")
}
for i := 0; i < 10000; i++ {
time.AfterFunc(time.Duration(5*time.Second), func() {
fmt.Println("Hello!")
})
}
panic("after timers")
}
It prints all goroutine traces before timers spawned if run without arguments
and after timers spawned if any argument is passed. We need those shady panics
because otherwise there is no easy way to see runtime goroutines - they’re excluded
from runtime.NumGoroutines and runtime.Stack, so the only way to see them
is crash(refer to golang/go#9791
for reasons). Let’s see how many goroutines Go spawns before spawning any timers:
go run afterfunc.go 2>&1 | grep "^goroutine" | wc -l
4
and after spawning 10k timers:
go run afterfunc.go after 2>&1 | grep "^goroutine" | wc -l
5
Whoa! It’s only one goroutine, in my case its trace looks like:
goroutine 5 [syscall]:
runtime.notetsleepg(0x5014b8, 0x12a043838, 0x0)
/home/moroz/go/src/runtime/lock_futex.go:205 +0x42 fp=0xc42002bf40 sp=0xc42002bf10
runtime.timerproc()
/home/moroz/go/src/runtime/time.go:209 +0x2ec fp=0xc42002bfc0 sp=0xc42002bf40
runtime.goexit()
/home/moroz/go/src/runtime/asm_amd64.s:2160 +0x1 fp=0xc42002bfc8 sp=0xc42002bfc0
created by runtime.addtimerLocked
/home/moroz/go/src/runtime/time.go:116 +0xed
Let’s take a look at why there’s only one additional goroutine.
runtime.timer
All timers are based on the same data structure -
runtime.timer.
To add new timer, you need to instantiate runtime.timer and pass it to the function
runtime.startTimer.
Here is example from time package:
func NewTimer(d Duration) *Timer {
c := make(chan Time, 1)
t := &Timer{
C: c,
r: runtimeTimer{
when: when(d),
f: sendTime,
arg: c,
},
}
startTimer(&t.r)
return t
}
So, here we’re converting duration to an exact timestamp when timer should call
function f with argument c. There are three types of function f used in
package time:
- sendTime - sends current time to the channel or discards it if send blocks. Used in time.Timer and time.Ticker.
- goFunc - executes some function in a goroutine. Used in time.AfterFunc.
- goroutineReady -
wakes up a specific goroutine. Used in
runtime.timeSleep
which is linked to
time.Sleep.
Note that each new timer takes at least 40 bytes of memory. Large amount of timers can significantly increase the memory footprint of your program.
So, now we understand what timers look like in the runtime and what they are supposed to do. Now let’s see how the runtime stores timers and calls functions when it’s time to call them.
runtime.timers
runtime.timers
is just a Heap data structure.
Heap is very useful when you want to repeatedly find extremum (minimum or maximum) among
some elements. In our case extremum is a timer with closest when to the current
time. Very convenient, isn’t it? So, let’s see what algorithmic complexity the
operations with timers for the worst case:
- add new timer - O(log(n))
- delete timer - O(log(n))
- spawning timers functions - O(log(n))
So, if you have 1 million timers, the number of operations with heap will usually be less than 1000(log(1kk) ~= 20, but spawning can require multiple minimum deletions, because multiple timers can reach their deadline at about the same time). It’s very fast and all the work is happening in a separate goroutine, so it doesn’t block. The siftupTimer and siftdownTimer functions are used for maintaining heap properties. But data structures don’t work on their own; something should use them. In our case it’s just one goroutine with the function timerproc. It’s spawned on first timer start.
runtime.timerproc
It’s kinda hard to describe what’s going on without source code, so this section
will be in the form of commented Go code. Code is a direct copy from the src/runtime/time.go
file with added comments.
// Add a timer to the heap and start or kick the timerproc if the new timer is
// earlier than any of the others.
func addtimerLocked(t *timer) {
// when must never be negative; otherwise timerproc will overflow
// during its delta calculation and never expire other runtime·timers.
if t.when < 0 {
t.when = 1<<63 - 1
}
t.i = len(timers.t)
timers.t = append(timers.t, t)
// maintain heap invariant
siftupTimer(t.i)
// new time is on top
if t.i == 0 {
// siftup moved to top: new earliest deadline.
if timers.sleeping {
// wake up sleeping goroutine, put to sleep with notetsleepg in timerproc()
timers.sleeping = false
notewakeup(&timers.waitnote)
}
if timers.rescheduling {
// run parked goroutine, put to sleep with goparkunlock in timerproc()
timers.rescheduling = false
goready(timers.gp, 0)
}
}
if !timers.created {
// run timerproc() goroutine only once
timers.created = true
go timerproc()
}
}
// Timerproc runs the time-driven events.
// It sleeps until the next event in the timers heap.
// If addtimer inserts a new earlier event, addtimerLocked wakes timerproc early.
func timerproc() {
// set timer goroutine
timers.gp = getg()
// forever loop
for {
lock(&timers.lock)
// mark goroutine not sleeping
timers.sleeping = false
now := nanotime()
delta := int64(-1)
// iterate over timers in heap starting from [0]
for {
// there are no more timers, exit iterating loop
if len(timers.t) == 0 {
delta = -1
break
}
t := timers.t[0]
delta = t.when - now
if delta > 0 {
break
}
// t.period means that it's ticker, so change when and move down
// in heap to execute it again after t.period.
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)
siftdownTimer(0)
} else {
// remove from heap
// this is just removing from heap operation:
// - swap first(extremum) with last
// - set last to nil
// - maintain heap: move first to its true place with siftdownTimer.
last := len(timers.t) - 1
if last > 0 {
timers.t[0] = timers.t[last]
timers.t[0].i = 0
}
timers.t[last] = nil
timers.t = timers.t[:last]
if last > 0 {
siftdownTimer(0)
}
// set i to -1, so concurrent deltimer won't do anything to
// heap.
t.i = -1 // mark as removed
}
f := t.f
arg := t.arg
seq := t.seq
unlock(&timers.lock)
if raceenabled {
raceacquire(unsafe.Pointer(t))
}
// call timer function without lock
f(arg, seq)
lock(&timers.lock)
}
// if delta < 0 - timers is empty, set "rescheduling" and park timers
// goroutine. It will sleep here until "goready" call in addtimerLocked.
if delta < 0 || faketime > 0 {
// No timers left - put goroutine to sleep.
timers.rescheduling = true
goparkunlock(&timers.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
continue
}
// At least one timer pending. Sleep until then.
// If we have some timers in heap, we're sleeping until it's time to
// spawn soonest of them. notetsleepg will sleep for `delta` period or
// until notewakeup in addtimerLocked.
// notetsleepg fills timers.waitnote structure and put goroutine to sleep for some time.
// timers.waitnote can be used to wakeup this goroutine with notewakeup.
timers.sleeping = true
noteclear(&timers.waitnote)
unlock(&timers.lock)
notetsleepg(&timers.waitnote, delta)
}
}
There are two variables which I think deserve explanation: rescheduling and
sleeping. They both indicate that the goroutine was put to sleep, but different
synchronization mechanisms are used, let’s discuss them.
sleeping is set when all “current” timers are processed, but there are more
which we need to spawn in future. It uses OS-based synchronization, so it calls
some OS syscalls to put to sleep and wake up the goroutine and syscalls means it spawns
OS threads for this.
It uses note
structure and next functions for synchronization:
- noteclear - resets note state.
- notetsleepg -
puts goroutine to sleep until
notewakeupis called or after some period of time (in case of timers it’s time until next timer). This func fillstimers.waitnotewith “pointer to timer goroutine”. - notewakeup -
wakes up goroutine which called
notetsleepg.
notewakeup might be called in addtimerLocked if the new timer is “earlier” than
the previous “earliest” timer.
rescheduling is set when there are no timers in our heap, so nothing to do.
It uses the go scheduler to put the goroutine to sleep with function
goparkunlock.
Unlike notetsleepg it does not consume any OS resources, but also does not
support “wakeup timeout” so it can’t be used instead of notetsleepg in
the sleeping branch.
The goready
function is used for waking up the goroutine when a new timer is added with addTimerLocked.
Conclusion
We learned how Go timers work “under the hood” - the runtime neither uses one goroutine per timer, nor are timers “free” to use. It’s important to understand how things work to avoid premature optimizations. Also, we learned that it’s quite easy to read runtime code and you shouldn’t be afraid to do so. I hope you enjoyed this reading and will share info to your fellow Gophers.