go: cmd/compile: unexpected performance difference accessing slices with different caps

Go has a special case when slicing and generating the empty slice. This has the potential to generate a pointer to the next object in memory, like this:

x := make([]int, 4)
x = x[4:]

The resulting x has capacity 0, and if we just computed its base pointer as x.ptr += 4*sizeof(int) then x.ptr would point to the next object in memory after the [4]int that was allocated. This is bad because it could mistakenly retain a random object in the heap.

So when slicing, we need to somehow avoid contructing such a pointer. Currently we do this by avoiding the add when the capacity is 0. So we do x.ptr += newcap == 0 ? 0 : 4*sizeof(int). And we do it without a conditional, using shift and mask tricks.

When you do spix[i:i+4:i+4] the new capacity is 4, and the compiler knows that. So the conditional in the expression above constant folds, and we just get x.ptr += i*sizeof(int). When you do spix[i:i+4:len(spix)], it’s not obvious whether the resulting slice has capacity 0 or not, so the arithmetic is still all there.

The optimization that would fix this is that if the resulting slice is known to have nonzero length (we know that here because i+4-i > 0), we don’t need to guard against next object pointers.

One thing I was wondering is whether we should subtract the length from the capacity when decomposing slices in SSA.

Interesting. How often do we slice in a loop as opposed to straight line code? Seems worth exploring.

Another, crazier, idea is to change the underlying representation in memory of all slices to be {ptr, len, cap-len/extra/slack}. This would make calling cap involve addition, but I think that calling cap is much rarer than slicing, appending, etc. This would probably break so much code as to be impossible, though.

Anyway, just thought I’d bring this up since I’m not sure if this idea would compliment or conflict with the OpReslice idea.

Conflict, I think. The idea behind OpReslice is to bundle a bunch of these calculations into a single op (easier to deal with during prove, etc.) and do the complex decomposition on a per-arch basis. I’m quite content to let you experiment with your ideas first, since they seem quite promising. And if you end up not liking the results, we can experiment some with OpReslice etc.

@mundaym if you want a real life test case, the code in https://github.com/golang/go/issues/31586#issuecomment-486469682 spends about 50% of its time reslicing in a loop. TL;DR: go get nhooyr.io/websocket, git checkout 40b4, go test -bench=Mask/4096//nhooyr, line 74 (b = b[8:]) is >50% of execution time. (cc @nhooyr)

One argument in favor of writing out the if statement: For code like this

if lo < hi {
  s = s[lo:hi]
}

Then we can entirely avoid adjusting ptr, whereas with masking tricks we always end up masking. (We could add a special check for boundedness, like we do with shifts, and perhaps should, but with a branch, it falls out for free.) Code example from discussion at https://go-review.googlesource.com/c/go/+/169518