Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
covrom opened this issue Feb 23, 2019 · 15 comments
Closed
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance

Comments

@covrom
Copy link

covrom commented Feb 23, 2019

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.

@covrom covrom changed the title Compiler hidden error is possible, that downgrade perfomance of binary search in array cmd/compile: compiler hidden error is possible, that downgrade perfomance of binary search in array Feb 23, 2019
@josharian
Copy link
Contributor

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
Copy link

bochsdbg commented Feb 23, 2019

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
Copy link
Contributor

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

@covrom
Copy link
Author

covrom commented Feb 23, 2019

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

@josharian
Copy link
Contributor

Yes, as I wrote:

the nil check should be hoisted out of the loop.

@covrom
Copy link
Author

covrom commented Feb 23, 2019

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
Copy link
Author

covrom commented Feb 23, 2019

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
Copy link
Contributor

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
Copy link
Author

covrom commented Feb 23, 2019

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
Copy link
Author

covrom commented Feb 23, 2019

We found ssa.Op386LoweredNilCheck. Thanks for GOSSAFUNC :)

@covrom covrom closed this as completed Feb 23, 2019
@covrom covrom reopened this Feb 23, 2019
@covrom
Copy link
Author

covrom commented Feb 23, 2019

But we need to pull this check out of the loop

@covrom covrom changed the title cmd/compile: compiler hidden error is possible, that downgrade perfomance of binary search in array cmd/compile: ssa: LoweredNilCheck downgrade perfomance of binary search in array Feb 23, 2019
@covrom
Copy link
Author

covrom commented Feb 24, 2019

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

I analyze this report and see:

  1. On stage "start" compiler create this lines:
v30 (11) = Copy <*[2147483648]uint32> v55 (p[*[2147483648]uint32])
v31 (11) = Copy <mem> v53
v32 (11) = NilCheck <void> v30 v31
  1. On stage "early copyelim" compiler reduce two lines:
v16 (6) = PtrIndex <*uint32> v15 v10 (p[*[2147483648]uint32])
...
-- v30 (11) = Copy <*[2147483648]uint32> v16
-- v31 (11) = Copy <mem> v1
v32 (+11) = NilCheck <void> v16 v1

At the "early copyelim" stage, v32 is not reduced.
It seems to me, a bug is here.

Another reason for remove this check: NilCheck does not add protection against a null pointer, since then there is "v38 (11) = PtrIndex <*uint32> v30 v33; v39 (11) = Copy v31; v40 (11) = Load v38 v39", which can also trigger SEGFAULT on invalid pointer.

@bcmills bcmills added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Feb 25, 2019
@bcmills
Copy link
Contributor

bcmills commented Feb 25, 2019

CC @martisch

@randall77
Copy link
Contributor

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

My change only marks the results of unsafe pointer arithmetic as non-nil. It doesn't do so for simple casts.

We could mark the results of &a[x] as non-nil, though, that seems safe. That might fix this issue.

@gopherbot
Copy link

Change https://golang.org/cl/163740 mentions this issue: cmd/compile: treat slice pointers as non-nil

@golang golang locked and limited conversation to collaborators Feb 26, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

6 participants