Slice in Golang: append, make, len e cap, e il bug della condivisione

Uno slice in un esempio

Uno slice è una vista espandibile su un array. Lo crei con un letterale o con make, lo fai crescere con append e ne leggi la dimensione con len.

package main

import "fmt"

func main() {
	langs := []string{"Go", "Rust"}
	langs = append(langs, "Zig", "C")
	fmt.Println(langs, len(langs))

	for i, l := range langs {
		fmt.Println(i, l)
	}

	fmt.Println(langs[1:3]) // elements 1 and 2
}

[]string non ha una lunghezza tra le parentesi. È questa la differenza rispetto a un tipo array come [4]string, la cui dimensione è fissa.

Cos'è uno slice

Un valore slice è una piccola intestazione con tre campi:

• un puntatore a un elemento di un array sottostante
• una lunghezza: quanti elementi lo slice può vedere
• una capacità: quanti elementi esistono da quel puntatore fino alla fine dell'array sottostante

Copiare uno slice (assegnarlo, passarlo a una funzione) copia solo questa intestazione. Entrambe le copie puntano agli stessi elementi. Quasi tutte le sorprese con gli slice nascono dal dimenticarlo.

make: lunghezza e capacità

make([]T, len, cap) alloca un array sottostante e restituisce uno slice su di esso. La capacità è facoltativa e per default è uguale alla lunghezza.

package main

import "fmt"

func main() {
	a := make([]int, 3) // len 3, cap 3, all zeros
	fmt.Println(a, len(a), cap(a))

	b := make([]int, 0, 10) // len 0, room for 10
	fmt.Println(b, len(b), cap(b))

	for i := range 5 {
		b = append(b, i*i)
	}
	fmt.Println(b, len(b), cap(b)) // no reallocation happened
}

Una confusione comune: make([]int, 5) seguito da cinque chiamate ad append ti dà dieci elementi, i primi cinque a zero. Usa make([]int, 0, 5) quando intendi usare append, oppure make([]int, 5) quando intendi assegnare per indice.

Preallocare la capacità quando conosci la dimensione finale evita crescite ripetute. È un'ottimizzazione, non un obbligo.

append e la crescita

append aggiunge elementi dopo la lunghezza attuale. Se la capacità basta, scrive sul posto. Altrimenti alloca un array più grande, ci copia i vecchi elementi e restituisce uno slice che punta al nuovo array.

package main

import "fmt"

func main() {
	var s []int
	prevCap := cap(s)
	for i := range 2000 {
		s = append(s, i)
		if cap(s) != prevCap {
			fmt.Printf("len %4d  cap %4d\n", len(s), cap(s))
			prevCap = cap(s)
		}
	}
}

La capacità circa raddoppia finché lo slice è piccolo e cresce di un fattore minore (verso 1,25x) quando supera i 256 elementi. I numeri esatti sono un dettaglio del runtime che è cambiato tra le versioni di Go, quindi non scrivere mai codice che ne dipenda.

Dato che append può restituire un array diverso, devi usarne il risultato:

append(s, 4)     // compile error: append(s, 4) (value of type []int) is not used
s = append(s, 4) // correct

Per aggiungere un intero slice si usa la sintassi di espansione: s = append(s, other...).

Lo slicing condivide l'array sottostante

s[low:high] crea una nuova intestazione di slice sullo stesso array, che copre gli indici da low fino a high escluso. Si può omettere uno dei due estremi. Nessun elemento viene copiato.

package main

import "fmt"

func main() {
	nums := []int{10, 20, 30, 40, 50}
	mid := nums[1:4] // 20 30 40
	mid[0] = 99
	fmt.Println(nums) // the write shows up in nums

	fmt.Println(len(mid), cap(mid)) // cap runs to the end of nums
}

Output:

[10 99 30 40 50]
3 4

È questa condivisione che rende lo slicing economico. Ed è anche l'origine del bug più famoso degli slice.

Il bug di aliasing con append

Quando un sotto-slice ha capacità libera, un append su di esso scrive nell'array del genitore, sopra elementi che il genitore usa ancora.

package main

import "fmt"

func main() {
	base := []int{1, 2, 3, 4, 5}
	first := base[:2] // [1 2], cap 5

	first = append(first, 100) // fits in capacity: overwrites base[2]
	fmt.Println(base)
	fmt.Println(first)

	// Two slices built from the same prefix clobber each other.
	prefix := make([]string, 0, 4)
	prefix = append(prefix, "cmd")
	a := append(prefix, "build")
	b := append(prefix, "test")
	fmt.Println(a, b) // both print test
}

Output:

[1 2 100 4 5]
[1 2 100]
[cmd test] [cmd test]

a e b condividono la posizione dell'array dopo "cmd", quindi il secondo append ha sovrascritto il primo. Il codice sembra corretto e funziona ogni volta che la capacità è già piena, ed è per questo che il bug compare solo a volte.

Due soluzioni:

1. L'espressione slice completa s[low:high:max] limita la capacità a max-low. Senza capacità libera, il prossimo append deve allocare. first := base[:2:2] rende sicuro il primo esempio.
2. Copia esplicitamente quando uno slice sopravviverà alla chiamata o riceverà append in modo indipendente: slices.Clone(prefix) oppure append([]string(nil), prefix...).

Una trappola collegata: un piccolo slice di un array enorme tiene in vita l'intero array per il garbage collector. Se leggi un file da 100 MB e tieni data[:10], i 100 MB restano in memoria. Clona la parte che ti serve.

copy

La funzione integrata copy(dst, src) copia min(len(dst), len(src)) elementi e restituisce quel numero. Non fa mai crescere dst.

package main

import (
	"fmt"
	"slices"
)

func main() {
	src := []int{1, 2, 3}

	dst := make([]int, len(src))
	n := copy(dst, src)
	dst[0] = 100
	fmt.Println(n, src, dst) // independent

	var empty []int
	fmt.Println(copy(empty, src)) // 0: dst has no length

	c := slices.Clone(src) // the one-line version (Go 1.21)
	fmt.Println(c)
}

copy gestisce correttamente sorgente e destinazione sovrapposte, quindi copy(s[1:], s) sposta gli elementi in avanti senza corromperli.

Il pacchetto slices

Da Go 1.21 il pacchetto standard slices offre funzioni generiche per le operazioni che prima scrivevi a mano.

package main

import (
	"fmt"
	"slices"
)

func main() {
	s := []int{5, 2, 8, 2, 9}

	fmt.Println(slices.Contains(s, 8)) // true
	fmt.Println(slices.Index(s, 2))    // 1
	fmt.Println(slices.Max(s), slices.Min(s))

	slices.Sort(s)
	fmt.Println(s)
	i, found := slices.BinarySearch(s, 8)
	fmt.Println(i, found)

	s = slices.Compact(s) // drop adjacent duplicates
	fmt.Println(s)

	s = slices.Delete(s, 1, 2) // remove index 1
	fmt.Println(s)

	s = slices.Insert(s, 1, 3, 4)
	fmt.Println(s)

	slices.Reverse(s)
	fmt.Println(s, slices.Equal(s, []int{9, 8, 4, 3, 2}))
}

Delete e Insert restituiscono uno slice che devi assegnare, come append. L'ordinamento ha una sua pagina: ordinamento.

Rimuovere elementi mentre scorri per indice fa saltare degli elementi. Usa invece slices.DeleteFunc:

s = slices.DeleteFunc(s, func(n int) bool { return n%2 == 0 }) // drop evens

Slice 2D

Uno slice di slice ti dà una griglia le cui righe possono avere lunghezze diverse. Ogni riga va allocata separatamente.

package main

import "fmt"

func main() {
	rows, cols := 3, 4
	grid := make([][]int, rows)
	for r := range grid {
		grid[r] = make([]int, cols)
	}
	grid[1][2] = 7

	for _, row := range grid {
		fmt.Println(row)
	}

	// Rows of different lengths are fine.
	triangle := [][]int{{1}, {1, 1}, {1, 2, 1}}
	fmt.Println(triangle)
}

Se dimentichi il make interno ogni riga resta nil, e grid[1][2] = 7 va in panic con index out of range [2] with length 0.

Slice nil e slice vuoti

package main

import (
	"encoding/json"
	"fmt"
)

func main() {
	var a []int  // nil
	b := []int{} // empty, not nil

	fmt.Println(len(a), len(b), a == nil, b == nil)

	a = append(a, 1) // append works on nil
	fmt.Println(a)

	ja, _ := json.Marshal(struct{ Items []int }{})
	jb, _ := json.Marshal(struct{ Items []int }{Items: []int{}})
	fmt.Println(string(ja), string(jb))
}

Uno slice nil si comporta come uno vuoto per len, cap, range e append, quindi preferisci var s []T come stato zero. Inizializza a []T{} solo quando la differenza conta, cioè soprattutto nell'output JSON (null o []). Verifica se è vuoto con len(s) == 0, non con s == nil.

Slice e funzioni

Una funzione che riceve uno slice può modificarne gli elementi, e il chiamante vede le modifiche. Non può cambiare la lunghezza del chiamante, perché ha ricevuto una copia dell'intestazione. Una funzione che fa append deve restituire il nuovo slice:

func addAll(s []int, vals ...int) []int {
	return append(s, vals...)
}

Ecco perché append, slices.Delete e slices.Insert restituiscono tutti uno slice.

Errori comuni

• Ignorare il risultato di append. Non compila se lo scarti del tutto, ma assegnare append(s, x) a una variabile diversa da quella che continui a usare è un bug di logica.
• Due append dalla stessa base. Possono condividere la memoria. Clona la base o usa un'espressione slice completa.
• make([]T, n) e poi append. Lascia n zeri all'inizio.
• Indice fuori intervallo. s[len(s)] va in panic. L'ultimo elemento è s[len(s)-1].
• Confrontare slice con ==. Compila solo s == nil. Usa slices.Equal.