Quando Golang append() crea una nuova fetta?

Question

In base allo builtin api docs, append() verrà riallocato e copiato in un nuovo blocco di matrice quando la capacità della sezione originale non è sufficientemente grande.

Ecco una (versione semplificata di) un algoritmo ricorsivo per la creazione di combinazioni di un alfabeto (in questo caso i booleani). I membri dell'alfabeto (vero, falso) vengono aggiunti in modo ricorsivo a una sezione finché non è la lunghezza corretta, a quel punto viene inviata sul canale.

package main 

import (
    "fmt" 
) 

func AddOption(c chan []bool, combo []bool, length int) { 
    if length == 0 { 
     fmt.Println(combo, "!") 
     c <- combo 
     return 
    } 
    var newCombo []bool 
    for _, ch := range []bool{true, false} { 
     newCombo = append(combo, ch) 
     AddOption(c, newCombo, length-1) 
    } 
} 

func main() { 
    c := make(chan []bool) 
    go func(c chan []bool) { 
     defer close(c) 
     AddOption(c, []bool{}, 4) 
    }(c) 
    for combination := range c { 
     fmt.Println(combination) 
    } 
} 

Here è il campo di gioco per questo codice. Nell'output:

[true true true true] ! 
[true true true false] ! 
[true true true false] 
[true true true false] 
[true true false true] ! 
[true true false false] ! 
[true true false false] 
[true true false false] 
[true false true true] ! 
[true false true false] ! 
[true false true false] 
[true false true false] 
[true false false true] ! 
[true false false false] ! 
[true false false false] 
[true false false false] 
[false true true true] ! 
[false true true false] ! 
[false true true false] 
[false true true false] 
[false true false true] ! 
[false true false false] ! 
[false true false false] 
[false true false false] 
[false false true true] ! 
[false false true false] ! 
[false false true false] 
[false false true false] 
[false false false true] ! 
[false false false false] ! 
[false false false false] 
[false false false false] 

Le righe che terminano con un punto esclamativo sono quelle inviate nel canale da AddOption. Quelli senza sono ciò che emerge dall'altra parte (cioè in main()). È chiaro che le slice inviate sul canale vengono cambiate dopo che sono state inviate.

Dal AddOption ritorna immediatamente dopo l'invio la fetta, la modifica deve venire dal blocco di codice

var newCombo []bool 
for _, ch := range []bool{true, false} { 
    newCombo = append(combo, ch) 
    AddOption(c, newCombo, length-1) 
} 

Ma, secondo la documentazione, aggiungere() dovrebbe restituire una nuova fetta (cap (combinata) è non abbastanza grande). Secondo this answer, il descrittore di slice inviato a AddOption dovrebbe essere una copia; non è vero? Per quanto posso dire, il valore inviato come secondo argomento di AddOption() è o un puntatore a un descrittore di sezione o append() non restituisce una nuova porzione.

Answer 1

Quando append() crea una nuova porzione, non crea una fetta che è solo una più grande della sezione precedente. In realtà crea una slice che è già un paio di elementi più grandi di quella precedente. Date un'occhiata a questo codice:

package main 

import "fmt" 

func main() { 
    var sl []bool 

    for i := 0; i < 100; i++ { 
     sl = append(sl, true) 
     fmt.Println(cap(sl)) 
    } 
} 

Playground

Se si esegue questo codice, si vede che la capacità raddoppia inizialmente su ogni allocazione; questa strategia è ovviamente cambiata per dimensioni di fetta più grandi.

Answer 2

Si tratta di una sezione confusa, il tipo di dati, con la rappresentazione effettiva. The slice descriptor è composto da una coppia di interi, uno per len e uno per cap e un puntatore ai dati sottostanti.

Quindi, quale append restituisce è effettivamente una nuova porzione e ciò che viene passato per aggiungere l'opzione è in effetti una copia del descrittore di slice. Ma dal momento che il descrittore ha un puntatore ai dati, il valore del puntatore (l'indirizzo ai dati sottostanti) è lo stesso.

EDIT: Ecco un frammento di codice per illustrare il mio punto:

package main 

import "fmt" 

func main() { 
    s := make([]int, 0, 5) 
    s = append(s, []int{1, 2, 3, 4}...) 

    a := append(s, 5) 
    fmt.Println(a) 

    b := append(s, 6) 
    fmt.Println(b) 
    fmt.Println(a) 
} 

Se run this, si ottiene:

[1 2 3 4 5] 
[1 2 3 4 6] 
[1 2 3 4 6] 

Perché da s dispone ancora di capacità, sia a e b condividere gli stessi dati ptr.Se si modifica la capacità di 4, esso stampa:

[1 2 3 4 5] 
[1 2 3 4 6] 
[1 2 3 4 5] 

Answer 3

Rif: http://criticalindirection.com/2016/02/17/slice-with-a-pinch-of-salt/

Secondo il link:

Go ha un approccio più magra e pigro nel fare questo. Mantiene modificando lo stesso array sottostante fino a raggiungere la capacità di una slice pari a .

Questo è molto diverso dal comportamento di fette in altre lingue:

maggior parte dei linguaggi, come Python, creare un'altra copia del sottostante serie quando una delle fette che puntano ad esso fa una scrittura .

L'output di example menzionato, spiega il comportamento.

Slice a len=7 cap=7 [0 0 0 0 0 0 0] 
Slice b refers to the 2, 3, 4 indices in slice a. Hence, the capacity is 5 (= 7-2). 
b := a[2:5] 
Slice b len=3 cap=5 [0 0 0] 

Modifying slice b, also modifies a, since they are pointing to the same underlying array. 
b[0] = 9 
Slice a len=7 cap=7 [0 0 9 0 0 0 0] 
Slice b len=3 cap=5 [9 0 0] 

Appending 1 to slice b. Overwrites a. 
Slice a len=7 cap=7 [0 0 9 0 0 1 0] 
Slice b len=4 cap=5 [9 0 0 1] 

Appending 2 to slice b. Overwrites a. 
Slice a len=7 cap=7 [0 0 9 0 0 1 2] 
Slice b len=5 cap=5 [9 0 0 1 2] 

Appending 3 to slice b. Here, a new copy is made as the capacity is overloaded. 
Slice a len=7 cap=7 [0 0 9 0 0 1 2] 
Slice b len=6 cap=12 [9 0 0 1 2 3] 

Verifying slices a and b point to different underlying arrays after the capacity-overload in the previous step. 
b[1] = 8 
Slice a len=7 cap=7 [0 0 9 0 0 1 2] 
Slice b len=6 cap=12 [9 8 0 1 2 3] 

Qui, in ultima verifica-passo, si sente un po 'spettrale che qualsiasi modifica b non più sta causando modifica del sottostante puntato da un. Un'aspettativa logica sarebbe quella: quando b raggiunge il limite, a e b puntano entrambi alla stessa matrice allocata appena allocata, invece di continuare a puntare a quella precedente.

Avere più slice che puntano allo stesso array sottostante, con frequenti operazioni append può risultare complicato. Maggiori informazioni su questo nel link sopra.