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.

Change https://golang.org/cl/136935 mentions this issue: image/draw: optimize bounds checks in loops

s/the new capacity is 0/the new capacity is 4/
s/x.ptr += 0/x.ptr += i*sizeof(int)/

Change https://golang.org/cl/137495 mentions this issue: image: optimize bounds checking for At and Set methods

@randall77

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.

I wonder if we should revisit using 'shift and mask tricks' here. It reminds me a bit of #26306 (i.e. the extra pointer arithmetic might be interfering with speculative loads). Since setting the pointer to nil only usually happens on the last iteration of a loop, perhaps we should just emit the obvious code instead:

if likely(newcap > 0) {
     x.ptr += 4*sizeof(int)
} else {
     x.ptr = nil
}

Might be worth an experiment. Plus prove wouldn't need a special case to optimize the branch away.

I'm happy for someone to experiment with this.
The special case here is going to be ugly either way, I expect.

I wonder if we should revisit using 'shift and mask tricks' here.

Aside: There are also a few other alternatives (of the pointer arithmetic tricks) variety here.

We currently do:

SUBQ k, i
NEGQ i
SARQ $63, i
ANDQ i, off

We could also do:

SUBQ k, i
SETNE x
NEGL x
ANDQ x, off

Or even:

SUBQ k, i
SETNE i
MULQ i, off

I hacked these in locally. They all execute at basically identical speeds, but the middle form encodes shortest.

To use the middle form throughout, in practice we'd need to have a OpReslice that can pass all the way through to lowering. (This is because we treat SUBQ and SUBQborrow differently, which inhibits CSE. And because other architectures might want to use their own specialized slicing tricks, e.g. conditional instructions on ARM.)

A dedicated OpReslice might make the prove pass simpler as well, since (I believe) the prove pass doesn't care whether the resulting pointer is at the beginning or in the middle of the object.

(Or another variant of the middle form: SUBQ; SETEQ; DECQ; ANDQ, which might be even shorter. I'll explore if folks think it is worth it.)

SETNE only sets the low byte of the target register. You'd need to add an XORL x, x before the subtraction or MOVL $0, AX before the SETNE.

Thanks! It still appears to be a minor win. The bigger question is about moving slicing from SSA gen to a dedicated op.

A dedicated op is fine. It should make it easier to generate better code for arm as well.

we'd need to have a OpReslice

One thing I was wondering is whether we should subtract the length from the capacity when decomposing slices in SSA. That way we wouldn't need to update the capacity when re-slicing. It would mean slightly more work when doing append-like operations though. We'd also need to re-add the length to the capacity when storing the slice back to memory.

For example:

for len(x) > 0 {
    ...
    x = x[n:]
}

Currently compiles to:

for x.len > 0 {
    ...
    x.cap += n
    x.len += n
    x.ptr += SliceMask(n, cap)
}

If we instead replaced the capacity (x.cap) with the length subtracted from the length (x.ext) then the loop could be done as:

x.ext = x.cap - x.len
for x.len > 0 {
    ...
    x.len += n
    t := n
    if unlikely(x.len == 0) {
        t = SliceMask(n, x.ext)
    }
    x.ptr += t
}
x.cap = x.len + x.ext

This involves a branch but crucially means we don't have to load/update the capacity in the likely path of the loop, reducing register pressure. I started hacking on this idea but haven't finished it yet - seems to be relatively simple to achieve 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.

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.

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

@mundaym if you want a real life test case, the code in #31586 (comment) 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)

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.

I'm not very understanding why spix[i:i+4:len(spix)] is not obvious to prove that the resulting slice has a capacity larger than zero. At least it is obvious for humans.

It looks the performances of the two ways are on par now with Go 1.21.2. Any change has ever made for this?

[edit]: sorry, it looks no change here. It is just that some benchmarks becomes slice length sensitive since Go 1.21.