Part 2 of 2 · Keeping Time: Pacing Output and Following Clocks with a Phase-Locked Loop (PLL)

Keeping Time: Exact and Fast

Sending packets at higher speeds means doing more and staying cheap.

By ·8 min read

In broadcast television, an MPEG transport stream (MPEG-TS) runs at approximately 19.392 Mbps to match the transport capacity of a 6 MHz ATSC 1.0 broadcast channel — a slice of radio spectrum 6 MHz wide. Each MPEG-TS packet is 188 bytes. That works out to about 12,894 packets per second, or one packet every 77.56 µs.

If, perchance, you need to pace the equivalent of 256 ATSC 1.0 channels, the aggregate rate would be 4.964352 Gbps. That’s one 188-byte packet every 302.96 nanoseconds. That’s an interesting number because, in my M5 MacBook Pro run benchmarking the PLL Go library, the total rate was met and the median late time was just 2 µs. That’s my observed sender-loop result.1

From a programming perspective, the timing numbers are very, very small. The PLL library is not waking up and sending one packet every 300 nanoseconds. Instead, we’re using several methods to achieve the numbers and the accuracies.

Number and schedule the packets

A straightforward implementation repeatedly adds a packet interval:

go
1const interval = 303 * time.Nanosecond
2
3var next time.Duration
4for packet := uint64(0); packet < 1_000_000; packet++ {
5    // Packet's scheduled time is next.
6    next += interval
7}

But our interval is approximately 302.96 ns, not exactly 303 ns. Each addition repeats the same rounding error. Over millions of packets, that error accumulates.

The library instead numbers the scheduled opportunities, called slots, starting at zero. In this application, each slot represents one packet. A slot’s number determines its time; the previous slot’s rounded timestamp doesn’t enter the calculation.

The code excerpts below are from pll v0.4.0. In span.go, this is where an individual timestamp is requested:

go
1t, ok := s.seg.floorTime(s.First + i)
2if !ok {
3    panic(ErrOverflow)
4}
5return time.Duration(t)

First + i identifies the slot. floorTime calculates its time from the exact period, rounding down only at the end. The reported timestamp is less than one nanosecond from the exact scheduled time, and that rounding error never accumulates.

The seg field refers to a timing segment: a starting slot, a starting time called its anchor, and an exact period. When the rate is adjusted, the pacer creates a new segment rather than changing timing already handed to the caller.

There’s another important detail: timestamps and deadlines need different rounding. NextDue, which tells the application when the next slot becomes ready, uses ceilTime to round up. A slot scheduled at 8/3 ns gets a reported timestamp of 2 ns, but it isn’t ready until 3 ns.

Rounding down is appropriate for reporting its timestamp. Rounding up is necessary when deciding when to wake.

Send everything that’s ready

The operating system won’t reliably wake a Go program every 300 nanoseconds. Fortunately, it doesn’t need to.

Whenever the sending loop runs, it passes the elapsed time to the pacer. The pacer calculates which slots should be ready by then and returns those it hasn’t already handed out, up to a caller-specified limit.

An obvious implementation would check deadlines one by one until it found a slot in the future. If a million slots were overdue, it would perform a million checks just to discover the work.

The actual latestDue method turns the scheduling calculation around. Instead of asking when a particular slot is scheduled, it asks which slot corresponds to the current elapsed time. Here is its fast-path calculation from pacer.go:

go
1hi, lo := bits.Mul64(d, g.pd)
2if hi >= g.pn {
3    return math.MaxUint64, true
4}
5k, _ = bits.Div64(hi, lo, g.pn)

Here, d is elapsed nanoseconds from the segment’s anchor. pn and pd are the numerator and denominator of its exact period in nanoseconds. Multiplying elapsed time by pd and dividing by pn gives the last ready slot relative to the segment’s start. We’ll look at the arithmetic functions in the next section.

The pacer also maintains a cursor: the next slot it hasn’t handed out or skipped. Once Due has found the last ready slot and checked the bounds, it constructs the result:

go
1n := last - p.cursor + 1
2if n > max {
3    n = max
4}
5s := Span{First: p.cursor, Count: n, seg: p.seg}
6p.cursor += n
7return s, nil

There’s no loop and no array of timestamps. A Span describes the whole range: its first slot, its count, and its timing. Describing a thousand slots takes the same-sized value as describing one. An individual timestamp is calculated only when the application asks for it.

The application still has to process and send the packets. The library avoids walking through them merely to identify which ones are ready.

A delayed iteration can handle many packets at once, allowing the sender to catch up if it has enough capacity. That preserves the schedule, but it doesn’t guarantee that every packet physically leaves on time. An overloaded sender will fall further behind, however cheaply its schedule is calculated.

Keep the math cheap

Exact fractions might sound expensive. For comparison, a straightforward calculation using Go’s arbitrary-precision fractions could look like this:

go
1func slotTime(slot uint64, period *big.Rat) *big.Int {
2    s := new(big.Rat).SetInt(
3        new(big.Int).SetUint64(slot),
4    )
5    t := new(big.Rat).Mul(s, period)
6    return new(big.Int).Quo(t.Num(), t.Denom())
7}

For a positive period, this calculates the slot’s timestamp in whole nanoseconds, rounding down. It preserves exact arithmetic, but creates temporary arbitrary-precision values for each call.2

The library does the general-purpose preparation when constructing a timing segment. It reduces the period fraction to its lowest terms and checks whether both terms fit in uint64.

If they do, floorTime uses this fast path:

go
1hi, lo := bits.Mul64(k, g.pn)
2if hi >= g.pd {
3    return 0, false
4}
5q, _ := bits.Div64(hi, lo, g.pd)
6if q > uint64(math.MaxInt64-g.anchor) {
7    return 0, false
8}
9return int64(q) + g.anchor, true

k is the slot’s distance from the segment’s start. Multiplying two 64-bit integers can require 128 bits, even when the final answer fits in 64. Mul64 preserves that full product as two words, hi and lo. Div64 divides the product by the period’s denominator.3

The checks matter. Before division, the code checks whether the quotient will fit in 64 bits. After division, it checks whether adding the segment’s anchor would exceed the range of Go’s signed time.Duration. It doesn’t silently wrap an oversized result into an incorrect timestamp.

This path allocates no memory. If the reduced period’s terms don’t fit in uint64, the library uses arbitrary-precision arithmetic instead. Exactness isn’t limited to the fast case.

The lesson isn’t “avoid exact arithmetic.” It’s prepare the arithmetic once, then use the cheapest exact representation that fits.

Yes, the types have limits

Exact arithmetic doesn’t mean unlimited range. Go’s time.Duration stores nanoseconds in a signed 64-bit integer, giving the pacer a timeline of about 292 years from its chosen origin. Slot numbers use uint64; at our 4.964352 Gbps rate, those would last roughly 177,000 years.

Those boundaries aren’t just a concern for long-running programs. Callers supply times, rates, and slot counts. A simulation or a large advance through the schedule can reach a boundary immediately.

Operations that detect overflow return ErrOverflow, except Span.Time, which panics with that error if a requested timestamp cannot be represented. The limits are generous, but they’re still limits.

Try it

Run the library microbenchmarks, including the big.Rat comparison:

sh
1git clone https://github.com/version2beta/pll.git
2cd pll
3git checkout v0.4.0
4make bench

To repeat the setup for the 256-channel-equivalent run:

sh
1go run ./cmd/pllpace \
2    -bps 4964352000 \
3    -unit-bytes 188 \
4    -per-datagram 7 \
5    -udp loopback \
6    -seconds 10

To search for a throughput ceiling on your machine:

sh
1go run ./cmd/pllpace \
2    -find-max \
3    -bps 19392000 \
4    -unit-bytes 188 \
5    -per-datagram 7 \
6    -udp loopback \
7    -seconds 2

The search doubles the rate until a trial fails, then narrows the range. By default, a trial passes when both its reported ending backlog and its 99th-percentile lateness are within 5 ms. That is the throughput acceptance threshold. Results near the ceiling depend on system load and trial duration.

Exact turned out to be cheap because reducing a fraction happens when the timing changes, not when a packet goes out. Most of making this fast was deciding where each piece of work belongs.


  1. These sender-loop measurements use one aggregate stream. Lateness measures how far past its scheduled time the oldest slot is when a nonempty batch is obtained. The commands below pin v0.4.0: that harness reports offered units separately from writer-accepted bytes and stops on write errors or short writes. ↩︎

  2. This illustrative function creates fresh working values. The BenchmarkSlotTimeBigRat benchmark reuses its working values, giving the general-purpose approach a fairer comparison. make bench measures arithmetic operations and allocations, separately from the UDP sending loop. ↩︎

  3. Go’s math/bits package provides Mul64, which returns a full 128-bit product, and Div64, which divides a 128-bit dividend by a 64-bit divisor. Div64 requires a nonzero divisor and a quotient that fits in 64 bits. ↩︎

See also