go cmd/compile: 遗漏了微不足道的边界检查消除,

4smxwvx5 于 5个月前发布在 Go

关注(0)|答案(8)|浏览(57)

Go版本
go版本 go1.22.2 darwin/arm64

在你的模块/工作区中`go env`的输出：

GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/filippo/Library/Caches/go-build'
GOENV='/Users/filippo/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/filippo/pkg/mod'
GONOPROXY='github.com/FiloSottile/*,filippo.io/*'
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/filippo'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org'
GOROOT='/Users/filippo/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.2.darwin-arm64'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/Users/filippo/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.2.darwin-arm64/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.2'
GCCGO='gccgo'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='/Users/filippo/src/filippo.io/mlkem768/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/_j/hq4ytn1n4b94fhrpvvb9tktr0000gn/T/go-build3556564162=/tmp/go-build -gno-record-gcc-switches -fno-common'

你做了什么？

我在一个相当热的循环中有一个这样的函数。

const n = 256
type fieldElement uint16
type nttElement [n]fieldElement

func nttMul(f, g nttElement) nttElement {
	var h nttElement
	for i := 0; i < 128; i++ {
		a0, a1 := f[2*i], f[2*i+1]
		b0, b1 := g[2*i], g[2*i+1]
		h[2*i] = fieldAdd(fieldMul(a0, b0), fieldMul(fieldMul(a1, b1), gammas[i]))
		h[2*i+1] = fieldAdd(fieldMul(a0, b1), fieldMul(a1, b0))
	}
	return h
}

你看到了什么发生？

f[2*i]和f[2*i+1]都得到了一个isInBounds()。而g[2*i]和g[2*i+1]没有。

你期望看到什么？

一次或零次边界检查。
如果编译器意识到如果f[2*i+1]在i的范围内且为正数且较小(0到127),那么f[2*i]显然在范围内。
如果编译器算出i的范围是0到127,那么2*i+1的范围是0到255,而f的大小是一个常数256。

来源：https://github.com/golang/go/issues/66826

8条答案

按热度按时间

vs3odd8k1#

看起来现在有一个解决方法：

func nttMul(f, g nttElement) nttElement {
	var h nttElement
	for i := 0; i < 256; i += 2 {
		a0, a1 := f[i], 
		f[i+1]
		b0, b1 := g[i], 
		g[i+1]
		_, _, _, _ = a0, a1, b0, b1
	}
	return h
}

还没有对其进行基准测试。
[edit]顺便说一下，为什么不使用切片作为参数呢？

func nttMul(f, g []fieldElement) nttElement {
	var h nttElement
	f, g = f[:256], g[:256]
	for i := 0; i < 256; i += 2 {
		a0, a1 := f[i], 
		f[i+1]
		b0, b1 := g[i], 
		g[i+1]
		_, _, _, _ = a0, a1, b0, b1
	}
	return h
}

赞(0）回复(0）举报 5个月前

m4pnthwp2#

这确实移除了对f的边界检查，但我们得到了一个对gammas[i/2]的边界检查，这也感觉是可以避免的。
理论上，切片应该比const大小的数组增加开销，并从类型系统中删除信息。

赞(0）回复(0）举报 5个月前

92dk7w1h3#

是的，仍然有一些 BCE 无法处理。
现在，一个解决方法是将 gammas 的长度加倍，并仅使用其在 2N 索引处的元素。

赞(0）回复(0）举报 5个月前

xa9qqrwz4#

现在，一个解决方法是将 gammas 的长度加倍，并仅使用其在 2N 索引处的元素。有趣的是，这些基准测试明显更差，消耗了删除 f 边界检查速度提升的 10% 到 20%。🤷

赞(0）回复(0）举报 5个月前

c7rzv4ha5#

这是可能的。BCE并不总是产生积极的效果。
另一种移除所有绑定检查的方法是声明fieldElement为[2]uint16。我不确定最终效果如何。

赞(0）回复(0）举报 5个月前

vuktfyat6#

简单的复制器：

func f(a [256]byte) {
	for i := 0; i < 128; i++ {
		_ = a[2*i]
	}
}

我们应该能够去除边界检查。目前我认为它失败了，因为证明传递无法告诉数学 2*i 不会溢出并变为负数。它似乎确实理解了 2*i < 256 。
应该是可以修复的。然而，这段代码很微妙，对我来说，立即明显地知道修复在哪里并不容易。

赞(0）回复(0）举报 5个月前

aelbi1ox7#

https://go.dev/cl/599096提到了这个问题：cmd/compile: rewrite the constant parts of the prove pass

赞(0）回复(0）举报 5个月前

5w9g7ksd8#

https://go.dev/cl/599256提到了这个问题：cmd/compile: propagate constant ranges through multiplies and shifts

赞(0）回复(0）举报 5个月前

我来回答

go cmd/compile: 遗漏了微不足道的边界检查消除,

在你的模块/工作区中`go env`的输出：

你做了什么？

你看到了什么发生？

你期望看到什么？

8条答案

相关问题

热门标签

最新问答

go cmd/compile: 遗漏了微不足道的边界检查消除,

在你的模块/工作区中go env的输出：

你做了什么？

你看到了什么发生？

你期望看到什么？

8条答案

相关问题

热门标签

最新问答

在你的模块/工作区中`go env`的输出：