cmd/compile: ssa: LoweredNilCheck downgrade perfomance of binary search in array

[covrom]

What version of Go are you using (go version)?

go version go1.11.5 linux/amd64

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

go env Output

GOARCH="amd64"
GOOS="linux"

What did you do?

Create a binary search in an sorted array int32 without checking boundaries, using unsafe.

func unsafeBinSearch(a []uint32, x uint32) uint32 {
	p := (*[1 << 31]uint32)(unsafe.Pointer(&a[0]))
	n := uint32(len(a))
	i, j := uint32(0), n
	for i < j {
		h := (i + j) >> 1
		if p[h] < x {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

What did you expect to see?

Maximum performance of compiled code without checking the boundaries inside the loop.

What did you see instead?

Compiler hidden error is possible, that downgrade perfomance, which may occur in other cases.

The result of compiling the above code:

0x001f 00031 (intunsafe.go:9)	XORL	BX, BX
0x0021 00033 (intunsafe.go:9)	CMPL	BX, AX
0x0023 00035 (intunsafe.go:9)	JCC	60

** 0x0025 00037 (intunsafe.go:11)	TESTB	AL, (DX) **

0x0027 00039 (intunsafe.go:10)	LEAL	(BX)(AX*1), SI
0x002a 00042 (intunsafe.go:10)	SHRL	$1, SI
0x002c 00044 (intunsafe.go:11)	MOVL	(DX)(SI*4), DI
0x002f 00047 (intunsafe.go:11)	CMPL	DI, CX
0x0031 00049 (intunsafe.go:11)	JCC	56
0x0033 00051 (intunsafe.go:12)	LEAL	1(SI), BX
0x0036 00054 (intunsafe.go:12)	JMP	33
0x0038 00056 (intunsafe.go:9)	MOVL	SI, AX
0x003a 00058 (intunsafe.go:14)	JMP	33

The compiler creates an additional instruction TESTB AL, (DX) for comparing two numbers, the result of which is not used further, because is replaced by the next CMPL DI, CX.

[josharian]

Just from looking at the assembly here on my phone, I’d say that that line is checking whether p is nil; it’d fault if so. It is thus not redundant.

If that’s right, of course, the nil check should be hoisted out of the loop. And I believe that @randall77 had plans to mark some manually constructed unsafe.Pointers as non-nil (which this one clearly is, as it points to the first element of a slice).

[bochsdbg]

It is thus not redundant.

Yeah, this is probably true. But pay attention that there is no "complete" check, it's only TEST instruction. No jumps, no any other side effects which should follow after it.

[josharian]

If it faults, we’ll receive a segfault signal, which the runtime will catch and turn into a panic.

[covrom]

Why is this test inside the loop? Pointer is declared at the beginning of the function.

[josharian]

Yes, as I wrote:

the nil check should be hoisted out of the loop.

[covrom]

If it faults, we’ll receive a segfault signal, which the runtime will catch and turn into a panic.

It seems to me, this test is not for null pointer. This test check cap(a)==0, because 0x001a 00026 (intunsafe.go:9) MOVQ "".a+16(SP), DX, where a+16 is cap in slice struct (a+0 is pointer to data, a+8 is len), if I read the assembly code correctly

Please see full asm code:

0x0000 00000 (intunsafe.go:5)	TEXT	"".unsafeBinSearch(SB), NOSPLIT, $8-40
0x0000 00000 (intunsafe.go:5)	SUBQ	$8, SP
0x0004 00004 (intunsafe.go:5)	MOVQ	BP, (SP)
0x0008 00008 (intunsafe.go:5)	LEAQ	(SP), BP
0x000c 00012 (intunsafe.go:5)	FUNCDATA	$0, gclocals·1a65e721a2ccc325b382662e7ffee780(SB)
0x000c 00012 (intunsafe.go:5)	FUNCDATA	$1, gclocals·69c1753bd5f81501d95132d08af04464(SB)
0x000c 00012 (intunsafe.go:5)	FUNCDATA	$3, gclocals·ebb0e8ce1793da18f0378b883cb3e122(SB)
0x000c 00012 (intunsafe.go:6)	PCDATA	$2, $0
0x000c 00012 (intunsafe.go:6)	PCDATA	$0, $0
0x000c 00012 (intunsafe.go:6)	MOVQ	"".a+24(SP), AX
0x0011 00017 (intunsafe.go:6)	TESTQ	AX, AX
0x0014 00020 (intunsafe.go:6)	JLS	73
0x0016 00022 (intunsafe.go:9)	MOVL	"".x+40(SP), CX
0x001a 00026 (intunsafe.go:9)	PCDATA	$2, $1
0x001a 00026 (intunsafe.go:9)	PCDATA	$0, $1
0x001a 00026 (intunsafe.go:9)	MOVQ	"".a+16(SP), DX
0x001f 00031 (intunsafe.go:9)	XORL	BX, BX
0x0021 00033 (intunsafe.go:9)	CMPL	BX, AX
0x0023 00035 (intunsafe.go:9)	JCC	60
0x0025 00037 (intunsafe.go:11)	TESTB	AL, (DX)
0x0027 00039 (intunsafe.go:10)	LEAL	(BX)(AX*1), SI
0x002a 00042 (intunsafe.go:10)	SHRL	$1, SI
0x002c 00044 (intunsafe.go:11)	MOVL	(DX)(SI*4), DI
0x002f 00047 (intunsafe.go:11)	CMPL	DI, CX
0x0031 00049 (intunsafe.go:11)	JCC	56
0x0033 00051 (intunsafe.go:12)	LEAL	1(SI), BX
0x0036 00054 (intunsafe.go:12)	JMP	33
0x0038 00056 (intunsafe.go:9)	MOVL	SI, AX
0x003a 00058 (intunsafe.go:14)	JMP	33
0x003c 00060 (intunsafe.go:17)	PCDATA	$2, $0
0x003c 00060 (intunsafe.go:17)	MOVL	BX, "".~r2+48(SP)
0x0040 00064 (intunsafe.go:17)	MOVQ	(SP), BP
0x0044 00068 (intunsafe.go:17)	ADDQ	$8, SP
0x0048 00072 (intunsafe.go:17)	RET
0x0049 00073 (intunsafe.go:6)	CALL	runtime.panicindex(SB)

Please correct me.

[covrom]

I am wrong. MOVQ "".a+16(SP), DX is a pointer to data, because MOVL (DX)(SI*4), DI extract data at SI*4 byte.

[josharian]

In case it helps you understand, this is how the compiler views that code, step by step:

ssa.html.zip

(Generate with $ GOSSAFUNC=unsafeBinSearch go tool compile p.go.)

[covrom]

Thanks. Then, AX = j, SI = h, BX = i, DX = pointer to data.
If AX=j, why compiler test one low byte of 'j' (AL) by bitwise 'and' with byte '*p'?
Very strange selection for test case.

[covrom]

We found ssa.Op386LoweredNilCheck. Thanks for GOSSAFUNC :)

[covrom]

But we need to pull this check out of the loop