latency numbers

// Package latency measures a few rungs of the latency ladder on the machine that runs it.
// Each function returns the median of several runs, because one run is easy to disturb.
package latency

import (
	"bufio"
	"io"
	"math/rand/v2"
	"net"
	"os"
	"path/filepath"
	"slices"
	"sync"
	"time"
)

const runs = 7

func median(f func() time.Duration) time.Duration {
	ds := make([]time.Duration, runs)
	for i := range ds {
		ds[i] = f()
	}
	slices.Sort(ds)
	return ds[runs/2]
}

// chase builds a random cycle over n slots and follows it, so every load depends on the
// previous one. The CPU cannot prefetch or overlap the loads, so the time per step is the
// real latency of one memory access at that working-set size.
func chase(bytes, steps int) time.Duration {
	n := bytes / 8
	next := make([]int32, n)
	perm := rand.Perm(n)
	for i := range n {
		next[perm[i]] = int32(perm[(i+1)%n])
	}
	var p int32
	for range min(n, steps) { // warm up
		p = next[p]
	}
	start := time.Now()
	for range steps {
		p = next[p]
	}
	d := time.Since(start)
	sink = int(p)
	return d / time.Duration(steps)
}

var sink int

// L1Hit is one dependent load from a 16 KB working set, which fits in the L1 data cache.
func L1Hit() time.Duration {
	return median(func() time.Duration { return chase(16<<10, 20_000_000) })
}

// RandomMemoryRead is one dependent load from a 512 MB working set, which is far larger than
// every cache, so almost every load goes to main memory. The cycle is built once.
func RandomMemoryRead() time.Duration {
	memOnce.Do(func() { memResult = median(func() time.Duration { return chase(512<<20, 4_000_000) }) })
	return memResult
}

var (
	memOnce   sync.Once
	memResult time.Duration
)

// SequentialMemoryReadMB is the time to read 1 MB that is already in memory, in order.
func SequentialMemoryReadMB() time.Duration {
	buf := make([]byte, 64<<20)
	for i := range buf {
		buf[i] = byte(i)
	}
	return median(func() time.Duration {
		var sum uint64
		start := time.Now()
		for i := 0; i < len(buf); i += 8 {
			sum += uint64(buf[i])
		}
		d := time.Since(start)
		sink = int(sum)
		return d / 64
	})
}

// MutexLockUnlock is one Lock and Unlock of a sync.Mutex that no other goroutine holds.
func MutexLockUnlock() time.Duration {
	var mu sync.Mutex
	return median(func() time.Duration {
		const n = 10_000_000
		start := time.Now()
		for range n {
			mu.Lock()
			mu.Unlock()
		}
		return time.Since(start) / n
	})
}

// LoopbackRoundTrip sends a 64-byte message to a local TCP echo server and waits for the
// answer. It measures the operating system's network path with no physical network.
func LoopbackRoundTrip() (time.Duration, error) {
	ln, err := net.Listen("tcp", "127.0.0.1:0")
	if err != nil {
		return 0, err
	}
	defer ln.Close()
	go func() {
		c, err := ln.Accept()
		if err != nil {
			return
		}
		defer c.Close()
		_, _ = io.Copy(c, c)
	}()
	c, err := net.Dial("tcp", ln.Addr().String())
	if err != nil {
		return 0, err
	}
	defer c.Close()
	c.(*net.TCPConn).SetNoDelay(true)
	msg := make([]byte, 64)
	got := make([]byte, 64)
	r := bufio.NewReader(c)
	trip := func() error {
		if _, err := c.Write(msg); err != nil {
			return err
		}
		_, err := io.ReadFull(r, got)
		return err
	}
	for range 1000 { // warm up the connection
		if err := trip(); err != nil {
			return 0, err
		}
	}
	var failed error
	d := median(func() time.Duration {
		const n = 5000
		start := time.Now()
		for range n {
			if err := trip(); err != nil {
				failed = err
			}
		}
		return time.Since(start) / n
	})
	return d, failed
}

// SyncedWrite4KB writes 4 KB to a file and calls fsync, so the data must reach the storage
// device before the call returns. This is the cost that a database pays to make a commit durable.
func SyncedWrite4KB(dir string) (time.Duration, error) {
	f, err := os.Create(filepath.Join(dir, "sync.bin"))
	if err != nil {
		return 0, err
	}
	defer f.Close()
	block := make([]byte, 4096)
	var failed error
	d := median(func() time.Duration {
		const n = 50
		start := time.Now()
		for range n {
			if _, err := f.Write(block); err != nil {
				failed = err
			}
			if err := f.Sync(); err != nil {
				failed = err
			}
		}
		return time.Since(start) / n
	})
	return d, failed
}

// SequentialFileReadMB reads a 64 MB file in order and returns the time for each MB. The file
// was just written, so the operating system serves it from its page cache in memory.
func SequentialFileReadMB(dir string) (time.Duration, error) {
	path := filepath.Join(dir, "seq.bin")
	if err := os.WriteFile(path, make([]byte, 64<<20), 0o600); err != nil {
		return 0, err
	}
	buf := make([]byte, 1<<20)
	var failed error
	d := median(func() time.Duration {
		f, err := os.Open(path)
		if err != nil {
			failed = err
			return 0
		}
		defer f.Close()
		start := time.Now()
		for {
			_, err := io.ReadFull(f, buf)
			if err == io.EOF || err == io.ErrUnexpectedEOF {
				break
			}
			if err != nil {
				failed = err
				break
			}
		}
		return time.Since(start) / 64
	})
	return d, failed
}

package latency

import (
	"testing"
	"time"
)

// These tests check the shape of the latency ladder, not exact values: each rung must be
// slower than the one below it by a clear margin. They log the measured numbers, which the
// "Numbers every engineer should know" lesson quotes.

func TestCacheHitIsFasterThanRandomMemoryRead(t *testing.T) {
	hit := L1Hit()
	mem := RandomMemoryRead()
	t.Logf("cache hit (pointer chase, 16 KB): %s", hit)
	t.Logf("random main-memory read (pointer chase, 512 MB): %s", mem)
	if mem < 10*hit {
		t.Fatalf("a random memory read should be at least 10× a cache hit; got %s vs %s", mem, hit)
	}
}

func TestSequentialMemoryReadPerMB(t *testing.T) {
	d := SequentialMemoryReadMB()
	t.Logf("read 1 MB sequentially from memory: %s", d)
	if d <= 0 || d > 5*time.Millisecond {
		t.Fatalf("1 MB sequential memory read should take well under 5 ms; got %s", d)
	}
}

func TestMutexLockUnlock(t *testing.T) {
	d := MutexLockUnlock()
	t.Logf("mutex lock + unlock (no contention): %s", d)
	if d <= 0 || d > 1*time.Microsecond {
		t.Fatalf("an uncontended mutex should take well under 1 µs; got %s", d)
	}
}

func TestLoopbackRoundTrip(t *testing.T) {
	d, err := LoopbackRoundTrip()
	if err != nil {
		t.Fatal(err)
	}
	t.Logf("TCP round trip on localhost (64-byte message): %s", d)
	if d < time.Microsecond || d > 5*time.Millisecond {
		t.Fatalf("a localhost round trip should be between 1 µs and 5 ms; got %s", d)
	}
}

func TestDiskSyncedWrite(t *testing.T) {
	d, err := SyncedWrite4KB(t.TempDir())
	if err != nil {
		t.Fatal(err)
	}
	t.Logf("write 4 KB and fsync to SSD: %s", d)
	if d < time.Microsecond || d > 100*time.Millisecond {
		t.Fatalf("a synced 4 KB write should be between 1 µs and 100 ms; got %s", d)
	}
}

func TestSequentialDiskReadPerMB(t *testing.T) {
	d, err := SequentialFileReadMB(t.TempDir())
	if err != nil {
		t.Fatal(err)
	}
	t.Logf("read 1 MB sequentially from a file (OS page cache): %s", d)
	if d <= 0 || d > 50*time.Millisecond {
		t.Fatalf("1 MB file read should take under 50 ms; got %s", d)
	}
}

func TestLadderOrder(t *testing.T) {
	hit := L1Hit()
	mem := RandomMemoryRead()
	rtt, err := LoopbackRoundTrip()
	if err != nil {
		t.Fatal(err)
	}
	if !(hit < mem && mem < rtt) {
		t.Fatalf("expected cache hit < memory read < network round trip; got %s, %s, %s", hit, mem, rtt)
	}
	t.Logf("ratio: memory read / cache hit = %.0f×", float64(mem)/float64(hit))
	t.Logf("ratio: localhost round trip / memory read = %.0f×", float64(rtt)/float64(mem))
}