cmd/compile: optimize code in the encoding/binary package

[perillo]

The encoding/binary package uses portable bit operations to read and write integers.

Using the program:

package test

func readUint64BigEndian(b []byte) uint64 {
	_ = b[7] // bounds check hint to compiler; see golang.org/issue/14808

	return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
		uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
}

and building with:

GOAMD64=v3 go1.18 build -o test.o test.go

the resulting assembly is:

SUBQ $0x18, SP		
MOVQ BP, 0x10(SP)	
LEAQ 0x10(SP), BP	
MOVQ AX, 0x20(SP)	
CMPQ $0x7, BX		
JBE 0x9ac		
MOVBE 0(AX), AX		
MOVQ 0x10(SP), BP	
ADDQ $0x18, SP		
RET			
MOVL $0x7, AX		
MOVQ BX, CX		
CALL 0x9b9		[1:5]R_CALL:runtime.panicIndex	
NOPL

The Zig compiler, with the same code and ReleaseSafe build mode, is able to generate the assembly:

movbe   rax, qword ptr [rdi]
ret

See https://godbolt.org/z/MPbE3P9j8.

Note that the movbe instruction was added in AMD64 v3 (https://en.wikipedia.org/wiki/X86-64).

Zig currently uses the LLVM backend, so I don't know if the cost/complexity of this optimization is high.

[ALTree]

That zig code is not equivalent because you're passing a [8]u8, while the Go snippet uses a slice, which we need to boundcheck. This Go Function:

func readUint64BigEndian(b [8]byte) uint64 {
	return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
		uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
}

generates with GOAMD64=v3 go tool compile -S test.go:

0x0000 00000 (test.go:5)	MOVBEQ	"".b+8(SP), AX
0x0007 00007 (test.go:5)	RET

Which is the same as the LLVM output.

[perillo]

@ALTree, thank you for the clarification.

I did not notice the problem, since in Zig it is possible to convert a slice to an array; as an example:

var start: usize = 2;
var buf = [_]u8{ 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8 };
var b = buf[start..]; // A slice since start is not a constant
var bytes = b[0..8]; // An array since the indices are constants

It should be possible(?) to implement this in Go, but it will break compatibility.

[ALTree]

In the Go version that takes a slice we have to boundcheck it, but if you remove the instructions related to that, it's just a single MOVBEQ (AX), AX again (but I could be missing something). Is there anything else the compiler should do? (I mean for the binary part which is the topic of this issue).

[perillo]

I wrote this test code:

package test

import "encoding/binary"

func Parse(b []byte) uint64 {
	v := binary.BigEndian.Uint64(b[0:8])

	return v
}

func ParseUint64(b []byte, start, end int) uint64 {
	v := binary.BigEndian.Uint64(b[start:end])

	return v
}

func ParseUint64_2(b []byte, start, end int) uint64 {
	v := binary.BigEndian.Uint64(b[start:end][0:8])

	return v
}

The first and last functions (where slicing is done using constants), generate a single MOVBEQ instruction for the binary.BigEndian.Uint64 function, while the second function generates additional instructions.

I searched for real examples and found:
https://cs.opensource.google/go/x/net/+/27dd8689:http2/frame.go;l=764

The code can probably be improved with (not tested):

binary.BigEndian.Uint16(buf[i*6:][:2])

Zig, as a counter example, will report a compiler error so it is more easy to detect the problem.

NOTE:
The actual instruction I see is MOVBE, not MOVBEQ.
Also, for binary.BigEndian.UInt16, the Go compiler generates two instructions:

MOVZX 0(AX), AX
ROLW $0x8, AX

while the Zig compiler generates

movbe  ax,WORD PTR [rdi]

The source code is:

package test

import "encoding/binary"

func Parse(b []byte) uint16 {
	v := binary.BigEndian.Uint16(b[0:2])

	return v
}

Is there a reason for not using MOVBE?

[randall77]

Is there a reason for not using MOVBE?

No particular reason, 16-bit versions just hasn't been implemented yet.

[gopherbot]

Change https://go.dev/cl/395474 mentions this issue: cmd/compile: add MOVBE index load/store

[gopherbot]

Change https://go.dev/cl/396617 mentions this issue: cmd/compile: add MOVBEWstore support for GOAMD64>=3