Questions about the behavior of append and slice-slices

[slate stump]

1. what is the effect of appending to the slice s[:0] instead of nil? I'm guessing it overwrites parts of the existing slice, by sort of passing a pointer to just the beginning of the slice (length of 0) instead of the entire slice?

sum := sha.Sum(s[:0]) // internal behavior of Sum: append(param, otherSlice...)

example: https://cs.opensource.google/go/x/crypto/+/refs/tags/v0.5.0:nacl/box/box.go;l=179

2. what is the effect of spreading a slice of a slice out? (difference between these two options)

s = append(s, other...)
s = append(s, other[:]...) // extra allocation for the sub-slice, yes, but why?

example: https://cs.opensource.google/go/go/+/refs/tags/go1.19.4:src/crypto/sha256/sha256.go;l=223

second one I'm more curious about. I think I have that first one figured out

[quiet yew]

slices have two length.
len and cap
len <= cap
The len you know about it already, the capacity is more intresting, basically when you append to a slice, the most simple thing go could do is allocate some memory that fits both slices copy everything and return that.
This works but is very inefficient, let's assume you append 1000 elements one by one, go would allocate 1000 slices.

So slices have a cap, the space between len and cap can be reused.
So what go will do is allocate 2~1.25x the space it need, so then next time hopefully it will just write into that extra space.

s[:0] will set the length to 0 but leave the capacity untouched, s[:0:0] would set both to zero.
The point of doing this is that there is now a bunch of extra capacity, so sha.Sum is allowed to skip an allocation if it can reuse the extra space.

About the second example, your code is slightly wrong. in your example it does nothing because other must already be a slice.
In the code you linked hash is an array, [:] create a slice whos storage is points to the array.
[:] does not allocate anything because slices are secretely pointers (the content of the slice is passed by reference, however the slice itself is passed by value)

[slate stump]

mini allocation

like struct { original []T; start, stop int }

to denote the slice-of-a-slice info

[quiet yew]

Actually sometime [:] can force an allocation where it doesn't without, that is because since this is a reference to the array, if the slice leaks, it will prevent the stack allocation of the array and make it heap allocated, but it's not [:] allocating, it's the leak (the difference is that once something is on the heap [:] can't make it allocate once again)

[quiet yew]

?

[slate stump]

eh nevermind lul

[quiet yew]

no slices use pointer arithmetic because it's faster

[slate stump]

well surely there's a struct somewhere in memory to denote information about the slice

[quiet yew]

no it's in registers

[quiet yew]

and in the past it was passed by the stack, so it's not allocated

[slate stump]

s := []int{1, 2, 3, 4, 5, 6, 7}
v := s[0:2]
v[5] == 6 // pointer arithmetic

anyways not central

might peek at some more source later lol

s[:0:0] so how does this work? setting the capacity to 0, or some value less than the current capacity, by somehow deallocating the end?

s := make([]int, 0, 20)
s = s[:0:10]
s = s[:0:0]
```seems weird, I'm curious what's going on under the hood

about 2nd example above, I missed that part being a regular array -- thanks :p

makes sense

[quiet yew]

func Example[T any](s []T) []T {
  return s[2:3]
}

func ExampleCompilesTo[T any](s []T) []T {
  if len(s) <= 3 {
    panicOutOfBoundAccess(3, len(s))
  }

  var element T
  return runtime.slice{
    data: unsafe.Add(s.data, 2 * unsafe.SizeOf(element)),
    len: 3,
    cap: s.cap,
  }
}

[slate stump]

alright yeah, little struct going on there

[quiet yew]

this just compiles to:

s := runtime.slice{runtime.makeslice(&int.type, 0, 20), 0, 20}
s = runtime.slice{s.data, 0, 10}
s = runtime.slice{s.data, 0, 0}

the definition of a slice is:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

[slate stump]

what does it mean to have a slice of a slice when the capacities don't line up?

[quiet yew]

https://github.com/golang/go/blob/bae7d772e800207ed764b70a9e5963f0c1e8f0aa/src/runtime/slice.go#L15-L19

no nvm I miss understood what you meant

[quiet yew]

I don't fully understand the question, could you write an example ?

[slate stump]

hmmm

I'm just curious what it means for a slice to have a capacity

if it makes sense on its own, it stops making sense when the capacity is something different than the parent slice

oh, wait

s := make([]int, 10, 20)
v := s[5:15:10]

so if you tried to append up to 10 elements to v, those could overwrite the middle 10 elements of s?

and on the 11th append, or a single append with >10 elements, it would realloc elsewhere

[quiet yew]

that wrong the capacity can never be smaller than the length

[slate stump]

oh uhhhhh

[quiet yew]

let's assume:

s := make([]int, 10, 20)
v := s[5:10:15]

The first 5 appends to v will overwrite the data of s, but after that it's gonna allocate a brand new slice just for v

Actually appending 5 elements at once it will be 1 single call to append

[slate stump]

I don't see the issue here? it's pointing to indices 5 (inclusive) to 15 (exclusive) with a capacity of 10, being those 10 elements there

or does the capacity need to be from the start of the original slice, to the end of the sliced slice

capacity is confusing lol

[quiet yew]

when you reslice a slice everything is indexed reference to the original slice.
The compiler then make it a subtraction.
So:

s := make([]int, 10, 20)
v := s[5:10:15]

compiles to:

s := make([]int, 10, 20)
v := runtime.slice{s.data, 10-5, 15-5]

[slate stump]

actually since the effective length of this slice is 5, since s[5:10], I don't see what effect the capacity has on it at all

alright that makes sense

I've confused myself even more thinking about the ramifications of having a slice partially cover the used space, and partially covering unused but allocated space

s := make([]int, 10, 20)
v := s[5:15]
v[6] // aka s[11]; not ok

I'll just have to play around with this stuff some more

[quiet yew]

@slate stump

package main

import "fmt"

func main() {
    s := make([]string, 5, 10)
    fulls := s[:cap(s)-1]
    for i := range fulls {
        fulls[i] = fmt.Sprintf("s%d", i)
    }
    v := s[3:4:7]
    for i := 4; i < 7; i++ {
        v = append(v, fmt.Sprintf("v%d", i))
    }
    fmt.Println(s) // [s0 s1 s2 s3 v4] see how the last element was overwritten by v
    fmt.Println(v) // [s3 v4 v5 v6]
    for i := 5; i < 10; i++ {
        s = append(s, fmt.Sprintf("s%d", i))
    }
    fmt.Println(s) // [s0 s1 s2 s3 v4 s5 s6 s7 s8 s9]
    fmt.Println(v) // [s3 v4 s5 s6] see how it's now s overwriting v
    // basically v is some shifted view of s, they point to the same data
}

[slate stump]

apparently v[6] is perfectly valid, but s[11] is not (panic) 🤔

[quiet yew]

you need to do a capacity extension first v = v[:cap(v)-1]

[quiet yew]

the index checks are based on the length not the capacity, however when reslicing it's capacity that matters

[slate stump]

that's interesting

makes sense

so it seems the slice-of-a-slice capacity, plus the start point, needs to not exceed the original slice's capacity ```go
s := make([]int, length, capacity)
v := s[start:stop:other]
// requirement: start + other <= capacity

[quiet yew]

exactly

[slate stump]

alright cool

[quiet yew]

no actually

[quiet yew]

other <= capacity

[quiet yew]

other is relative to s not v

[slate stump]

oh alright

[quiet yew]

go will internally compute other-start but that done for you behind the scenes

[slate stump]

this is setting the length to capacity?

[quiet yew]

yes

[slate stump]

awesome

[balmy harbor]

I find it helpful to think of a slice as a window into an array, the len is how much the window is open, cap is how open the window can be

[slate stump]

I think that's all I really have for now, thank you

sure sure

and I'll have to remember cap being relative to the start of the original slice

okay...slice of a slice of a slice

[quiet yew]

@slate stump actually mb it's v = v[:cap(v)]

idk what I messed up before

[slate stump]

yee

probably thinking about getting the last element

s[:len(s)-1]

[slate stump]

still relative to the base slice, right?

[quiet yew]

yes

[slate stump]

cool

[balmy harbor]

don't do this, slices of slices is a type question, not a "how do slices work" question. refer to s[:] as slicing (or re-slicing depending on context)

[slate stump]

slicing a slice of a slice 👍

sort of

s[:][:]

[quiet yew]

that still a single slice

[slate stump]

I'm not gonna actually get into that now though :p

[quiet yew]

@slate stump a slice of slice is [][]int

[slate stump]

oh hmmm

[quiet yew]

it's just wording thing

this caught me before too

[slate stump]

it's all stored relative to the original slice []T

so no more complexity there besides being based on where the sliced thing came from

like

s := []int{1, 2, 3}
a := s[1:] // 2, 3
b := a[1:] // 3

[quiet yew]

no it's relative to what you are slicing.

s1 := []int{1,2,3}
s2 := s1[1:]
s3 := s2[1:]

s3[0] poinst to s1[2] (because 1+1=2)

[quiet yew]

yes

[slate stump]

internally, like with the capacity, relative to the original slice

in code, based on where it's being sliced from

alright

I think that should be all for now :p