{adamcoding}
← The Machine and the Market
Part II
07
Chapter 7

Lists in a Row

The problem

5,000 prices, in order, and you need to get at any of them quickly. This is the most common data shape in all of trading, and Go's answer is the slice.

Arrays first, briefly

An array has a fixed length baked into its type:

go
var week [7]float64
week[0] = 100.5
fmt.Println(len(week))     // 7

[7]float64 and [5]float64 are different types. You can't assign one to the other. This makes arrays nearly useless for market data, where you don't know the length in advance.

So Go gives you slices, which are arrays with the rigidity removed.

Slices

go
prices := []float64{100.5, 101.2, 99.8, 102.3}

fmt.Println(prices[0])        // 100.5   - first
fmt.Println(prices[3])        // 102.3   - last
fmt.Println(len(prices))      // 4
fmt.Println(cap(prices))      // 4       - remember this one

No number in the brackets. Length isn't part of the type. You can grow it:

go
prices = append(prices, 103.1)
fmt.Println(len(prices))      // 5

Reading past the end panics:

go
fmt.Println(prices[99])       // panic: index out of range [99] with length 5

That's a good failure - loud, immediate, with the numbers in it.

What a slice actually is

Here's the mechanism, and it explains every surprising thing slices do.

A slice is three fields: a pointer to an array somewhere in memory, a length, and a capacity.

   prices := []float64{100.5, 101.2, 99.8, 102.3}

   the slice (three small fields)
   ┌──────────┬─────┬─────┐
   │ pointer  │ len │ cap │
   │    •     │  4  │  4  │
   └────┼─────┴─────┴─────┘
        │
        ▼
   the actual array in memory
   ┌───────┬───────┬──────┬───────┐
   │ 100.5 │ 101.2 │ 99.8 │ 102.3 │
   └───────┴───────┴──────┴───────┘

Length is how many elements you can currently see. Capacity is how many the underlying array can hold before it needs a bigger one.

When you append and there's spare capacity, Go writes into the existing array - cheap. When there isn't, Go allocates a new, larger array, copies everything across, and points the slice at the new one - expensive.

See It Work: watch a slice grow

Don't take my word for the growth pattern. Measure it:

go
package main

import "fmt"

func main() {
	s := []float64{}
	lastCap := cap(s)

	fmt.Printf("%-8s %-8s %-8s %s\n", "len", "cap", "grew?", "address")
	for i := 0; i < 2000; i++ {
		s = append(s, float64(i))
		if cap(s) != lastCap {
			fmt.Printf("%-8d %-8d %-8s %p\n", len(s), cap(s), "YES", s)
			lastCap = cap(s)
		}
	}
}

Run it. You'll see something like:

len      cap      grew?    address
1        1        YES      0xc000012345
2        2        YES      0xc0000123f0
3        4        YES      0xc000014020
5        8        YES      0xc000016040
9        16       YES      0xc00001a080
...

Three things to notice, all of which you just proved rather than being told:

  1. Capacity roughly doubles at small sizes. Above a few hundred elements the growth factor drops - Go trades speed for memory as slices get big. The exact numbers vary by Go version, which is exactly why measuring beats memorising.
  2. The address changes every time it grows. That's the reallocation and copy.
  3. It grew only about 14 times for 2,000 appends. The copying is rare enough that append costs, on average, roughly constant time. That's what "amortised O(1)" means, and you just watched it happen. (My machine says 14 on Go 1.22; yours may differ, which is the point of measuring.)

Now run the benchmark from the interlude and see what preallocation is worth. If you know roughly how many elements you'll have, say so:

go
prices := make([]float64, 0, 5000)     // length 0, capacity 5000

The sharing trap

This is the part that bites everyone, and it follows directly from the pointer.

Slicing gives you a view of the same underlying array, not a copy:

go
prices := []float64{100, 101, 102, 103, 104}
window := prices[1:4]                  // elements 1, 2, 3

fmt.Println(window)                    // [101 102 103]

window[0] = 999
fmt.Println(prices)                    // [100 999 102 103 104]  ← changed!

prices[1:4] means "from index 1 up to but not including 4." Half-open ranges are universal in Go, and they compose nicely: prices[:3] is the first three, prices[3:] is everything from index 3 on, and len(prices[a:b]) is always b-a.

But the two slices share memory. Writing through one is visible through the other.

See It Work: prove the sharing

go
prices := []float64{100, 101, 102, 103, 104}
window := prices[1:4]

fmt.Printf("prices: ptr=%p len=%d cap=%d\n", prices, len(prices), cap(prices))
fmt.Printf("window: ptr=%p len=%d cap=%d\n", window, len(window), cap(window))
prices: ptr=0xc000018150 len=5 cap=5
window: ptr=0xc000018158 len=3 cap=4

The window's pointer is 8 bytes further along - one float64. And its capacity is 4, not 3: it can see to the end of the original array. Append to it and you'll silently overwrite prices[4].

When you want an independent copy, say so:

go
window := make([]float64, 3)
copy(window, prices[1:4])

copy moves as many elements as fit in the smaller of the two and returns the count.

The rule: if a function receives a slice and modifies it, the caller sees the change. That's usually what you want for performance and occasionally a disaster. Copy when you need isolation.

Slices of slices

For OHLCV data before we have structs (Chapter 10):

go
bars := [][]float64{
	{100.0, 102.5, 99.5, 101.0},
	{101.0, 103.0, 100.5, 102.5},
	{102.5, 104.0, 102.0, 103.5},
}

for i, bar := range bars {
	fmt.Printf("Bar %d: O=%.2f H=%.2f L=%.2f C=%.2f\n",
		i, bar[0], bar[1], bar[2], bar[3])
}

This works and is horrible - bar[1] tells you nothing about what it means. Chapter 10 fixes it.

Exercises

7.1 Write lastN(prices []float64, n int) []float64 returning the last n elements, or everything if there are fewer than n. Then prove whether your result shares memory with the input by modifying it and printing both.

7.2 Write reverse(prices []float64) that reverses in place. Then write reversed(prices []float64) []float64 that returns a reversed copy leaving the original untouched. Use %p to show the second really is a different array.

7.3 Instrument the growth of a slice as in See It Work, but for 100,000 appends. Count the total number of reallocations and print it. Then compute how many element-copies happened in total.

7.4 Benchmark three ways of building a 100,000-element slice: append with no preallocation, append with make([]T, 0, n), and make([]T, n) with index assignment. Run with -benchmem and explain the allocation counts.

7.5 This function has a bug that shows up only sometimes. Find it, explain it, and fix it:

go
func firstThree(prices []float64) []float64 {
	return prices[:3]
}

7.6 Harder. Write chunk(prices []float64, size int) [][]float64 splitting a slice into consecutive chunks, with the last one possibly shorter. Then answer: do the chunks share memory with the input? Prove your answer with code.

Solutions

7.1

go
func lastN(prices []float64, n int) []float64 {
	if n >= len(prices) {
		return prices
	}
	return prices[len(prices)-n:]
}

It shares memory - modifying the result changes the original. Returning prices directly when n is large also shares. If callers shouldn't be able to write through it, copy.

7.2

go
func reverse(prices []float64) {
	for i, j := 0, len(prices)-1; i < j; i, j = i+1, j-1 {
		prices[i], prices[j] = prices[j], prices[i]
	}
}

func reversed(prices []float64) []float64 {
	out := make([]float64, len(prices))
	copy(out, prices)
	reverse(out)
	return out
}

a, b = b, a swaps without a temporary variable. Note that reverse needs no return value - it modifies the caller's array, which is exactly the sharing behaviour from this chapter.

7.3 Around 30-40 reallocations for 100,000 appends. Total copies sum to roughly 2n - because each reallocation copies the current length, and those lengths form a geometric series. That's the proof that amortised constant time is real.

7.4 The third is fastest with exactly one allocation. The second also has one allocation but pays for the append bookkeeping. The first has 30-odd allocations and copies about 200,000 elements along the way.

7.5 It panics when len(prices) < 3. Guard it:

go
func firstThree(prices []float64) []float64 {
	if len(prices) < 3 {
		return prices
	}
	return prices[:3]
}

"Only sometimes" is the dangerous part - it works on all your test data and dies on the short first day of a new instrument.

7.6

go
func chunk(prices []float64, size int) [][]float64 {
	if size < 1 {
		return nil
	}
	var out [][]float64
	for i := 0; i < len(prices); i += size {
		end := i + size
		if end > len(prices) {
			end = len(prices)
		}
		out = append(out, prices[i:end])
	}
	return out
}

Yes, they share - every chunk is a view into the original array. Prove it by writing to chunks[0][0] and printing prices[0].