A queue that never holds more than three elements can sit on a backing array of a million. The naive Go implementation dequeues by moving the front of a slice forward, which is constant time and writes nothing back. Both indices bounding the live elements travel the same way, and the memory behind them is never revisited. None of that shows up in the complexity table, and none of it shows up in a test that checks the queue returns the right values in the right order.
Add at the back, take from the front
A queue holds elements in the order they arrived and removes them in that order. Push adds at the back, pop removes from the front, and the invariant is one sentence: for any two elements in the queue, the one pushed earlier is popped earlier. That admits exactly one correct output for any sequence of operations, which makes a queue one of the few structures a test can compare against an unambiguous reference.
Draw it as a line of elements with two live ends. New arrivals attach at the right, departures leave from the left, and the length is whatever is between them. Peek reads the left end without removing it, which is worth having because a consumer often has to look at the next item before deciding whether it can handle it. What a queue has no operation for is the middle: no index, no search, no removal of anything that is not at the front.
A stack is simpler still, and the difference between them is where a queue’s trouble starts. A stack adds and removes at the same end, so the live region of its array never travels. A queue’s two ends both march to the right, and an implementation has to decide what happens to the ground they leave behind.
The slice that keeps the front
The queue that falls out of a slice and append takes about six lines, and there are two shapes of it in the wild. The unbounded one keeps an index for the front and appends at the back.
// Broken. items only ever grows and head only ever advances, so the backing
// array tracks the total number of pushes rather than the number of elements
// present. A queue running at a steady depth of four for a week ends up on an
// array sized by a week of traffic.
type Naive[T any] struct {
items []T
head int
}
func (q *Naive[T]) Push(v T) { q.items = append(q.items, v) }
func (q *Naive[T]) Pop() (T, bool) {
var zero T
if q.head == len(q.items) {
return zero, false
}
v := q.items[q.head]
q.head++
return v, true
}
Both operations are constant time, both return the right values, and the memory is a function of total throughput. len(q.items) is the number of pushes that have ever happened, q.head is the number of pops, and the live queue is the difference. Nothing in the code reads the region before head again, and nothing releases it.
The shaded region has no upper bound and nothing that would shrink it. Where T is a pointer, or a struct containing one, every element in that region is still reachable from the array, so the collector keeps whatever it refers to. A queue of *http.Request handing requests to workers holds every request it has ever handled, headers and body buffer and all. The heap profile attributes the lot to the line that did the append.
The other shape moves the slice header instead of keeping an index.
// Also wrong, differently. q = q[1:] advances the slice's pointer into the
// same array and reduces its capacity by one, so append eventually reallocates
// and copies only the live elements. The array is bounded. The vacated slots
// are still never written, so every element already handed to a caller stays
// reachable until that reallocation, and the live run is copied again and
// again for the life of the queue.
q = append(q, v) // push
v, q = q[0], q[1:] // pop
This one is more defensible and still wrong twice over. A slice is a header over an array, and q[1:] builds a new header pointing one element further into the same array with one less capacity. Pops shrink the capacity, pushes consume it, and a push that finds length equal to capacity allocates a fresh array, copies the live elements across and abandons the old one. The memory is therefore bounded by roughly the live length rather than by total throughput, which is the good news.
The bad news is that a queue held at a steady depth of k loses a slot of capacity per pop, so it reallocates and copies all k live elements every k operations or so. The average is a constant per operation. But the same bytes are copied over and over for as long as the queue exists, where a structure that reuses its slots copies only when the high-water mark rises. Retention survives too, because the dequeue never writes over the slot it vacated.
Two changes fix both, and together they are the ring buffer: write the zero value over the slot just popped, and reuse slots instead of abandoning them, so the indices wrap rather than march.
What the three answers cost
A node per element
The linked queue keeps a head pointer and a tail pointer. Push allocates a node, writes it into tail.next and moves tail; pop reads head.value, moves head to head.next and leaves the old node to the collector. Both are constant time with no amortisation and no copying, which is the one thing this version has over the others. No operation occasionally takes O(n), so the worst case and the average case are the same.
Everything else is worse. One allocation per push, one object per element for the collector to trace, one pointer per element of overhead. Every pop is a dependent load too: the address of the next node arrives only after the current node is read. A long-lived queue churning nodes has them scattered across whatever the allocator had free, where a ring buffer walks consecutive addresses the hardware can fetch ahead of.
Two indices into one array
The ring buffer keeps one slice, an index for the front, and a count. Push writes at (head + n) % len(buf); pop reads at head, zeroes that slot and advances head modulo the length. When the count reaches the buffer length the buffer doubles and the live run is copied into the front of the new one, which is the only operation here that is not constant time.
Store the head and a count rather than a head and a tail. With two indices, head == tail describes an empty queue and a full one, and telling them apart needs either a wasted slot or a boolean the rest of the code has to maintain. A count has no such case.
This is the version to ship: one allocation per doubling, contiguous storage, nothing for the collector to trace beyond the elements, and a front slot cleared on every pop.
Two stacks, and the amortised argument
The two-stack queue is the construction worth understanding even if you never ship it. Keep two stacks, in and out. Push onto in. Pop from out, and when out is empty, pop every element off in and push it onto out, which reverses the order, then pop from out.
The reversal looks expensive and is not, because of where it happens. It runs only when out is empty, and an element reaching out never goes back. So over an element’s whole life in the queue it is pushed onto in once, moved from in to out once, and popped from out once. Three touches, fixed, however the pushes and pops interleave. A sequence of m operations does O(m) work in total, which is amortised constant time per operation.
The accounting form of that argument survives adversarial interleaving, which is why it is the one to keep. Give every push two units of credit on top of the work it does itself; a transfer of j elements spends j units. Each element is transferred at most once, so it spends at most the credit its own push deposited and the balance never goes negative.
What the amortised bound does not give is a bound on any single operation. A queue that has taken a thousand pushes and no pops has a thousand elements in in, and the next pop moves all thousand. Where the code popping is a request handler with a latency budget, the average is not the number that matters. The ring buffer has the same objection in a milder form, since its doubling copy is O(n) too, and the linked version has it not at all.
The structure is at home in functional languages, where the stacks are immutable lists, a push is a cons, and reversing one list onto another is the natural operation. The amortised argument there holds only while each version of the queue is used once. Pop repeatedly from one queue value whose out is empty and whose in is long, and the reversal happens on every pop. Making it lazy is the standard repair.
What the complexity table leaves out
| Ring buffer | Two stacks | Linked | |
|---|---|---|---|
| Push | amortised O(1) | amortised O(1) | O(1) |
| Pop | O(1) | amortised O(1), O(n) worst | O(1) |
| Peek | O(1) | O(1) | O(1) |
| Overhead beyond the elements | two ints, plus unused slots | two slice headers, plus unused slots | one pointer per element |
| Allocations to build n elements | O(log n) | O(log n) | n |
Those rows are the smaller part of the cost. The ring buffer’s elements sit at consecutive addresses, so the address of the next one is this one plus a constant the compiler knows. The linked version’s next address is the result of the previous load. Both are constant time per element and they are not the same speed. The ratio depends on the element size, the cache and how far the nodes have drifted apart, so take the benchmark below, run it on the machine you deploy to, and read the number there.
Allocation is the one cost that transfers between machines. n elements through the linked version is n allocations; through the ring buffer it is one allocation per doubling, and make([]T, 0, n) in advance makes it one. allocs/op under -benchmem is a property of the code and says the same thing on your laptop as in production.
The growth factor needs one caution. The ring buffer below doubles because that code says to double. The factor append uses is an implementation choice that has changed between Go releases and is not defined by the specification, so the only claim to make about append is that its growth is amortised constant. Escape analysis is the same kind of thing, and go build -gcflags=-m prints the decision the compiler made rather than the one you expected.
When a queue is the structure
Reach for a queue when work arrives at one rate, is handled at another, and has to be handled in arrival order.
That covers more than it sounds like. A breadth-first traversal is a queue of nodes at the current frontier, and it is breadth-first rather than depth-first entirely because the frontier is a queue rather than a stack. Swap the container for a stack and the same code becomes a depth-first walk. A task runner feeding a pool of workers is a queue, and so is every rate limiter, admission controller and batching layer, because all three exist to hold arrivals that cannot be served yet.
Those look alike because a queue is the standard model of a system under load. Two results from that modelling change how you size one.
Little’s law says the average number of items in a stable system equals the average arrival rate multiplied by the average time an item spends in the system: L = λW. It assumes nothing about how arrivals are distributed or how long service takes, only that the system is stable. Rearranged as W = L / λ, it says the queue depth and the arrival rate already tell you the latency. A queue twice as deep at the same arrival rate holds items twice as long.
The second result is about utilisation and needs a model to state. Take the simplest textbook one, a single server with arrivals following a Poisson process, exponentially distributed service times and an unbounded queue. In that model, with ρ as utilisation, the average number of items in the system is ρ / (1 − ρ). That is 1 at 50 per cent utilisation, 9 at 90 per cent, 99 at 99 per cent. Those figures describe the model and not your system, whose arrivals and service times will not match its assumptions. What transfers is the shape, and it is the same in every such model: waiting grows faster than linearly as utilisation approaches capacity, so near the top a small increase in load produces a large increase in delay.
A queue holds a burst that arrives faster than the server can take it and hands the burst over during the lull that follows. What it cannot do is add capacity. Where the long-run arrival rate exceeds the long-run service rate, the queue grows without bound and every element’s wait grows with it. No buffer size changes that, because the buffer is not the thing that was short. An unbounded queue in front of an under-provisioned service turns a throughput problem into a latency problem and then into an out-of-memory.
Which is the argument for a bounded queue with a stated policy for a full one: block the producer, drop the oldest, drop the newest, or return an error upstream. Any of those is a decision, and an unbounded queue is the same decision made by accident, answered by the process dying.
When something else is better
Use a stack when the order does not matter. A worklist of things to visit, a pool of recycled buffers, a set of pending jobs with no fairness requirement: all are cheaper as a stack. One end needs no wrap, no modulo and no second index, and the element most recently touched is the one next read, which is the access pattern a cache handles best.
Use container/heap when the next element is the most urgent rather than the oldest. A FIFO queue cannot express priority, and approximating it with several queues works only while the number of priorities is small and fixed. Going the other way is worse: a heap with a sequence number as the tie-break gives FIFO order at O(log n) per operation, for what two indices do in constant time.
Use a map when the question is membership rather than order, and do not ask it to do both. Go’s map iteration order is unspecified and the runtime randomises it deliberately, so a map keyed by sequence number has no readable front. Code that ranges it looking for the oldest entry is broken whether or not it has yet produced a wrong answer. Where both are needed, the standard shape is a map for the lookup and a separate structure holding the order.
Use a doubly linked list when elements have to come out of the middle, which a ring buffer cannot do without shifting. A cancellable work queue is the case: a job is queued, the request behind it is abandoned, and the job should come out from wherever it sits.
container/list will serve as a queue through PushBack, Front and Remove, and it is usually the wrong choice for one. It carries two pointers per node where a queue needs at most one. Its Element.Value field is declared any, which was the only way to write a reusable container before Go had type parameters and cannot change now without breaking the compatibility promise. Every read back needs a type assertion, so putting a string into a list the rest of the program asserts to int is a production panic rather than a build error. Generics removed the reason to accept that: a Ring[T] holds T directly and the compiler checks it.
A channel is not a container
Go’s channel is a queue and the standard library has no other one, which is why so much code uses a channel as a general-purpose FIFO. A channel is a synchronisation primitive with a queue inside it, which makes it the right answer for one job and the wrong answer for the rest.
What it does well is hand values between goroutines. make(chan T, n) gives a buffer of n; a send on a full channel blocks and a receive on an empty one blocks, so the channel carries both the values and the scheduling. That blocking send is backpressure, already correct, and the capacity is fixed at creation, so the design has to answer the bounding question an unbounded queue lets you avoid. Values come out in the order they went in, which is part of the language definition rather than a property of the current runtime.
What it does not do is behave like a container. There is no peek. Code that has to inspect the next value before committing to it must receive the value first and then find somewhere to keep it, because a channel has no front to return it to. There is no indexing and no removal from the middle. len(ch) and cap(ch) are defined, and len(ch) is a snapshot already out of date by the time the comparison runs, so a decision made from it is a race in waiting. The capacity cannot change, so growing a queue means a new channel and a migration. Every send and receive goes through the runtime, so a channel used inside one goroutine does the work of synchronising with nobody. How much that costs is a benchmark on your hardware rather than a figure anyone can quote.
The failure modes are a channel’s own too. A send on a closed channel panics, closing a closed channel panics, and only the sending side can close safely, so several producers need a coordination scheme on top. A receive from a nil channel blocks forever, which is useful inside a select and a hang anywhere else.
So: between goroutines, a channel. Inside one goroutine, a ring buffer, because the queue is the structure that was wanted and the synchronisation is not.
Writing one in Go
Two implementations follow, the ring buffer to ship and the two-stack queue to understand. The invariant comments are the part to read.
// Package queue holds two first-in-first-out queues: a ring buffer over one
// slice, and a queue built from two stacks.
package queue
import "iter"
// Ring is a FIFO queue over one slice used circularly. The invariants, which
// checkRing verifies in the tests: n is the number of live elements and is
// never greater than len(buf); head is a valid index into buf whenever n > 0;
// the live elements are buf[head], buf[head+1 mod len(buf)] and so on for n
// steps; and every slot outside that run holds the zero value of T, so the
// queue retains nothing it has handed back.
//
// head and n rather than head and tail: with two indices, head == tail
// describes an empty queue and a full one, and telling them apart needs
// either a wasted slot or a boolean the rest of the code has to maintain.
type Ring[T any] struct {
buf []T
head int
n int
}
func (q *Ring[T]) Len() int { return q.n }
// Push adds at the back. The growth factor below is chosen here. append's
// factor is an implementation choice the specification does not define, which
// is one reason to own the allocation.
func (q *Ring[T]) Push(v T) {
if q.n == len(q.buf) {
q.grow()
}
q.buf[(q.head+q.n)%len(q.buf)] = v
q.n++
}
// Pop removes from the front. The second return reports whether there was
// anything to remove, so an empty queue is neither a panic nor a zero value
// the caller cannot tell from a real one.
func (q *Ring[T]) Pop() (T, bool) {
var zero T
if q.n == 0 {
return zero, false
}
v := q.buf[q.head]
// Clearing the slot is the line the naive slice queue does not have.
// Without it a *Request already handed to the caller is still reachable
// from the buffer, and stays reachable until the slot is written again,
// which may be never.
q.buf[q.head] = zero
q.head = (q.head + 1) % len(q.buf)
q.n--
return v, true
}
// grow moves the live run to the front of a larger buffer. Two copies,
// because the run may wrap: head to the end of the old buffer, then the start
// of it up to head.
func (q *Ring[T]) grow() {
size := 2 * len(q.buf)
if size == 0 {
size = 8
}
next := make([]T, size)
copied := copy(next, q.buf[q.head:])
copy(next[copied:], q.buf[:q.head])
q.buf = next
q.head = 0
}
// Peek reads the front without removing it, which is the operation a channel
// has no equivalent of.
func (q *Ring[T]) Peek() (T, bool) {
var zero T
if q.n == 0 {
return zero, false
}
return q.buf[q.head], true
}
// All yields front to back without removing anything, so slices.Collect and a
// plain range loop both work. It holds no snapshot, so pushing or popping
// during the loop is a bug this iterator cannot detect.
func (q *Ring[T]) All() iter.Seq[T] {
return func(yield func(T) bool) {
for i := range q.n {
if !yield(q.buf[(q.head+i)%len(q.buf)]) {
return
}
}
}
}
The two-stack version is shorter, and transfer is where the amortised argument lives.
// Pair is a FIFO queue built from two stacks. in takes pushes, out serves
// pops, and out is refilled by reversing in into it, which happens only when
// out is empty. Contents front to back are out reversed, then in in order.
//
// Use it through a pointer. Copying the struct copies two slice headers that
// alias the same arrays, so two copies pushing to in write to the same slot
// and one of the two values is lost with nothing reported. A method with a
// value receiver would get exactly that copy.
type Pair[T any] struct {
in []T
out []T
}
func (q *Pair[T]) Len() int { return len(q.in) + len(q.out) }
func (q *Pair[T]) Push(v T) { q.in = append(q.in, v) }
func (q *Pair[T]) Pop() (T, bool) {
var zero T
if len(q.out) == 0 {
if len(q.in) == 0 {
return zero, false
}
q.transfer()
}
last := len(q.out) - 1
v := q.out[last]
q.out[last] = zero // same reason as Ring.Pop: let go of what we returned
q.out = q.out[:last]
return v, true
}
// transfer reverses in onto out. An element passes through here exactly once
// in its life in the queue, which is the whole of the amortised argument: m
// operations move at most m elements, so the total work is O(m) however the
// pushes and pops interleave.
func (q *Pair[T]) transfer() {
if cap(q.out) < len(q.in) {
q.out = make([]T, 0, len(q.in))
}
q.out = q.out[:0]
for i := len(q.in) - 1; i >= 0; i-- {
q.out = append(q.out, q.in[i])
}
clear(q.in) // zero the elements, so in retains nothing
q.in = q.in[:0] // keep the capacity, so the next batch reuses the array
}
The rest is mechanical. A Grow(n int) method sizing the buffer once in advance turns n pushes into one allocation. A fixed-capacity variant replaces grow with a full condition plus the policy the caller chose, which is where the bounding decision above gets written down.
How to test it
A queue has one correct answer for any operation sequence, so the reference test finds the bugs and the hand-written cases name the positions where an implementation goes wrong. Both invariant checkers run after every mutation below, because retention is invisible in a comparison of contents. A queue that returns every value in the right order and holds on to all of them passes every test that only reads the front.
package queue
import (
"container/list"
"fmt"
"math/rand/v2"
"slices"
"testing"
)
// checkRing verifies the invariants, including the one that matters most:
// every slot outside the live run holds the zero value.
//
// It is a function rather than a method because it needs comparable, and a
// method cannot add a constraint the receiver's type does not already carry.
// Ring is useful for element types that are not comparable, so the constraint
// belongs on the checker and not on the structure.
func checkRing[T comparable](q *Ring[T]) error {
if q.n < 0 || q.n > len(q.buf) {
return fmt.Errorf("n is %d with a buffer of %d slots", q.n, len(q.buf))
}
if len(q.buf) == 0 {
return nil
}
if q.head < 0 || q.head >= len(q.buf) {
return fmt.Errorf("head is %d with a buffer of %d slots", q.head, len(q.buf))
}
live := make([]bool, len(q.buf))
for i := range q.n {
live[(q.head+i)%len(q.buf)] = true
}
var zero T
for i, isLive := range live {
if !isLive && q.buf[i] != zero {
return fmt.Errorf("slot %d is outside the live run and still holds %v", i, q.buf[i])
}
}
return nil
}
func zeroedPastLen[T comparable](name string, s []T) error {
var zero T
full := s[:cap(s)]
for i := len(s); i < len(full); i++ {
if full[i] != zero {
return fmt.Errorf("%s: slot %d is past the length and holds %v", name, i, full[i])
}
}
return nil
}
func checkPair[T comparable](q *Pair[T]) error {
if err := zeroedPastLen("in", q.in); err != nil {
return err
}
return zeroedPastLen("out", q.out)
}
The named cases are the ones a ring buffer gets wrong, and they are all the wrap. A tape of operations keeps the table readable: p pushes the next value in sequence and . pops.
func TestRingNamedCases(t *testing.T) {
tests := []struct {
name string
tape string
want []int // the values the pops returned, in order
left []int // what remains, front to back
}{
{"pop an empty queue", ".", nil, nil},
{"one in, one out", "p.", []int{0}, nil},
{"pop past empty", "p..", []int{0}, nil},
{"fills the first buffer exactly", "pppppppp", nil, []int{0, 1, 2, 3, 4, 5, 6, 7}},
{"wraps without growing", "pppppppp.....pppp", []int{0, 1, 2, 3, 4}, []int{5, 6, 7, 8, 9, 10, 11}},
{"grows while wrapped", "pppppppp...ppppp", []int{0, 1, 2}, []int{3, 4, 5, 6, 7, 8, 9, 10, 11, 12}},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
var q Ring[int]
var got []int
next := 0
for _, op := range tt.tape {
if op == 'p' {
q.Push(next)
next++
} else if v, ok := q.Pop(); ok {
got = append(got, v)
}
if err := checkRing(&q); err != nil {
t.Fatal(err)
}
}
if !slices.Equal(got, tt.want) {
t.Errorf("pops returned %v, want %v", got, tt.want)
}
if left := slices.Collect(q.All()); !slices.Equal(left, tt.left) {
t.Errorf("queue holds %v, want %v", left, tt.left)
}
})
}
}
The test that finds the most is a random operation sequence against a slice reference, run over both implementations. The closure returned beside the queue carries the right checker, which is less machinery than a type switch on a generic interface value.
type fifo[T any] interface {
Push(T)
Pop() (T, bool)
Len() int
}
func TestMatchesSliceReference(t *testing.T) {
cases := []struct {
name string
build func() (fifo[int], func() error)
}{
{"ring", func() (fifo[int], func() error) {
q := &Ring[int]{}
return q, func() error { return checkRing(q) }
}},
{"two stacks", func() (fifo[int], func() error) {
q := &Pair[int]{}
return q, func() error { return checkPair(q) }
}},
}
for _, tc := range cases {
t.Run(tc.name, func(t *testing.T) {
rng := rand.New(rand.NewPCG(7, 11)) // fixed seed, so a failure replays
for range 300 {
q, check := tc.build()
// The reference dequeues with ref = ref[1:], the implementation
// argued against above. In a test that is the right
// call: it is three words, it cannot share a bug with the code
// under test, and the arrays it strands are collected when the
// iteration ends.
var ref []int
for range rng.IntN(80) {
if rng.IntN(3) == 0 && len(ref) > 0 {
got, ok := q.Pop()
if !ok {
t.Fatalf("Pop reported empty with %d in the reference", len(ref))
}
if got != ref[0] {
t.Fatalf("Pop returned %d, want %d", got, ref[0])
}
ref = ref[1:]
} else {
v := rng.IntN(1000)
q.Push(v)
ref = append(ref, v)
}
if q.Len() != len(ref) {
t.Fatalf("length %d, reference %d", q.Len(), len(ref))
}
if err := check(); err != nil {
t.Fatal(err)
}
}
// Draining catches an implementation that keeps the length
// right and the order wrong.
var drained []int
for {
v, ok := q.Pop()
if !ok {
break
}
drained = append(drained, v)
}
if !slices.Equal(drained, ref) {
t.Fatalf("drained %v, reference %v", drained, ref)
}
}
})
}
}
The memory claim gets its own test. It is about capacity rather than time, so it is deterministic and belongs with the unit tests rather than in a benchmark: a matched push and pop, repeated, must leave the buffer the size it was.
func TestCapacityTracksContentsNotThroughput(t *testing.T) {
var q Ring[int]
for range 1 << 16 {
q.Push(1)
if _, ok := q.Pop(); !ok {
t.Fatal("Pop found an empty queue immediately after a Push")
}
if q.Len() != 0 {
t.Fatalf("length %d after a matched Push and Pop", q.Len())
}
}
if cap(q.buf) > 16 {
t.Errorf("buffer grew to %d slots for a queue that never held more than one element", cap(q.buf))
}
}
Point that test at the Naive type and the last assertion fails with a capacity on the order of the loop count. That is the whole defect, caught in a second.
The retention half of it gets a test too, and that one is uncomfortable, because the assertion is about a slot the queue reports as gone.
func TestSlicingOffTheFrontLeavesThePointerBehind(t *testing.T) {
type payload struct{ id int }
array := make([]*payload, 0, 4)
for i := range 4 {
array = append(array, &payload{id: i})
}
first := array[0]
q := array
q = q[1:] // the naive dequeue, in full
if len(q) != 3 {
t.Fatalf("queue length %d, want 3", len(q))
}
if array[0] != first {
t.Fatal("the dequeue cleared the slot, so this is not the naive implementation")
}
// array[0] is unreachable through q and still reachable through the array
// q points into. This test holds array itself, which real code would not:
// there, q is the only reference, and this uncleared slot is what keeps
// the payload alive for as long as the queue exists.
}
The amortised claim is about how much work happens, so count the work rather than timing it. Every element passes through transfer at most once and each was put there by one push, so the elements moved can never outnumber the operations. A transfer that ran on every pop breaks this and breaks nothing else.
func TestTransferWorkIsLinearInOperations(t *testing.T) {
rng := rand.New(rand.NewPCG(3, 5))
var q Pair[int]
ops, moved := 0, 0
for range 200_000 {
if rng.IntN(2) == 0 {
q.Push(rng.IntN(100))
} else {
if len(q.out) == 0 {
moved += len(q.in) // the transfer about to happen moves this many
}
q.Pop()
}
ops++
}
if moved > ops {
t.Errorf("transfers moved %d elements across %d operations", moved, ops)
}
}
A fuzz target fits because the operation sequence is the input and a byte string is a tape for it. The low bit of each byte chooses the operation and the other seven are the value, so no value is reserved as an opcode.
func FuzzRingMatchesReference(f *testing.F) {
f.Add([]byte{3, 5, 0, 7, 2, 9, 0, 0})
f.Fuzz(func(t *testing.T, tape []byte) {
var q Ring[byte]
var ref []byte
for _, op := range tape {
if op&1 == 0 {
got, ok := q.Pop()
if ok != (len(ref) > 0) {
t.Fatalf("Pop reported %v with %d in the reference", ok, len(ref))
}
if ok {
if got != ref[0] {
t.Fatalf("Pop returned %d, want %d", got, ref[0])
}
ref = ref[1:]
}
} else {
q.Push(op >> 1)
ref = append(ref, op>>1)
}
if err := checkRing(&q); err != nil {
t.Fatal(err)
}
}
if got := slices.Collect(q.All()); !slices.Equal(got, ref) {
t.Fatalf("contents %v, reference %v", got, ref)
}
})
}
The cost claims are benchmarks, and their results are measurements on one machine rather than facts about Go. This one holds every queue at the same depth and alternates a push with a pop, which is the steady state a real queue runs in and the case the naive implementation handles worst.
var sink int
func BenchmarkChurn(b *testing.B) {
const depth = 1024
b.Run("ring", func(b *testing.B) {
b.ReportAllocs()
var q Ring[int]
for i := range depth {
q.Push(i)
}
for i := range b.N {
q.Push(i)
v, _ := q.Pop()
sink += v
}
})
b.Run("two stacks", func(b *testing.B) {
b.ReportAllocs()
var q Pair[int]
for i := range depth {
q.Push(i)
}
for i := range b.N {
q.Push(i)
v, _ := q.Pop()
sink += v
}
})
b.Run("container/list", func(b *testing.B) {
b.ReportAllocs()
l := list.New()
for i := range depth {
l.PushBack(i)
}
for i := range b.N {
l.PushBack(i)
sink += l.Remove(l.Front()).(int)
}
})
b.Run("buffered channel", func(b *testing.B) {
b.ReportAllocs()
ch := make(chan int, depth+1)
for i := range depth {
ch <- i
}
for i := range b.N {
ch <- i
sink += <-ch
}
})
b.Run("naive slice", func(b *testing.B) {
b.ReportAllocs()
var q Naive[int]
for i := range depth {
q.Push(i)
}
for i := range b.N {
q.Push(i)
v, _ := q.Pop()
sink += v
}
})
}
Read allocs/op before ns/op. The channel case runs in one goroutine, so it measures uncontended synchronisation and says nothing about contention, which is the case a channel exists for. The naive slice row needs a heap profile rather than the benchmark output, because its defect is resident memory and the benchmark reports neither that nor the collector work that comes with it.
None of these structures has internal synchronisation, so a shared queue needs a mutex around it and go test -race over a test that exercises the sharing. The shape that catches people is a queue behind an RWMutex with Pop taken as a read, on the grounds that it reads the front. Pop writes three fields, so two goroutines calling it under a read lock are a data race, and the detector reports it with both stacks the first time a test runs them together.