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

[iand]

Using tip (go version devel +b794ca64d2 Mon Sep 3 07:14:25 2018 +0000 linux/amd64)

While implementing some bounds check optimizations in image/draw CL 136935 I came across an unexpected performance difference between accessing elements of a slice s created like this

s := spix[i : i+4 : len(spix)]

and

s := spix[i : i+4 : i+4]

Both forms eliminate bound checks for accessing elements 0-3 of s but the second form has a significant performance improvement over the first (see CL for benchmarks).

Building with go build -gcflags="-d=ssa/check_bce/debug=1" shows no difference in bounds checks between the two forms so presumably it has something to do with the resulting size of the slice.

Attached is a simple program and disassembly derived from the image/draw code that demonstrates the effect. You can see that the assembly generated for the second form is quite a bit shorter.

bounds.go.txt
bounds.asm.txt

[randall77]

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.

[gopherbot]

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

[randall77]

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

[gopherbot]

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

[mundaym]

@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.

[randall77]

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

[josharian]

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.

[josharian]

(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.)

[randall77]

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.

[josharian]

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

[randall77]

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

[mundaym]

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.

[josharian]

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.

[josharian]

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

[josharian]

@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)