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: constant indexing to private array should be folded #43403

Open
egonelbre opened this issue Dec 28, 2020 · 4 comments
Open

cmd/compile: constant indexing to private array should be folded #43403

egonelbre opened this issue Dec 28, 2020 · 4 comments

Comments

@egonelbre
Copy link
Contributor

@egonelbre egonelbre commented Dec 28, 2020

Lookup tables are quite common, as in https://golang.org/src/math/bits/bits_tables.go. However none of functions that rely on those tables can be constant folded.

Simplest example is https://go.godbolt.org/z/MhMTqb which compiles to:

movblzx math/bits.rev8tab+12(SB), AX
movb    AL, "".~r0+8(SP)

The rev8tab only contains indexing to that table, so it should be possible to prove that the array is not being modified. Of course that only holds, when assignment, slicing or addressing operator is not used.

If such table is replaced with a string, then the constant folding does work. However, that seems like an ugly hack to have.

Related Issues:

@ALTree ALTree added this to the Unplanned milestone Dec 28, 2020
@josharian
Copy link
Contributor

@josharian josharian commented Dec 29, 2020

If anyone wants to work on this, one way to approach it would be to mark the array symbol as readonly in the pre-SSA phase of the compiler (if you can prove it is in fact readonly). Then SSA optimizations for loading from readonly memory should kick in.

@egonelbre
Copy link
Contributor Author

@egonelbre egonelbre commented Dec 29, 2020

@mdempsky mentioned that two other concerns are assembly code and //go:linkname.

@egonelbre
Copy link
Contributor Author

@egonelbre egonelbre commented Dec 29, 2020

I also realized there's a way to declare an array or slice, such that it's guaranteed to be read-only:

func lut() [256]byte { return [256]byte{1,2,3,4} }

@gopherbot
Copy link

@gopherbot gopherbot commented Dec 29, 2020

Change https://golang.org/cl/280645 mentions this issue: math/bits: folded reverse tables by using const string

gopherbot pushed a commit that referenced this issue Mar 17, 2021
linux/mips64le

name            old time/op  new time/op  delta
Reverse         2.31ns ± 1%  2.27ns ± 1%  -1.53%  (p=0.001 n=10+10)
Reverse8        0.65ns ± 1%  0.65ns ± 1%  -1.19%  (p=0.000 n=9+10)
Reverse16       1.15ns ± 2%  1.14ns ± 2%    ~     (p=0.062 n=9+10)
Reverse32       1.96ns ± 1%  1.94ns ± 1%  -1.16%  (p=0.000 n=10+9)
Reverse64       2.29ns ± 1%  2.26ns ± 0%  -0.94%  (p=0.000 n=9+9)
ReverseBytes    0.66ns ± 3%  0.65ns ± 1%  -1.58%  (p=0.006 n=9+10)
ReverseBytes16  0.66ns ± 2%  0.65ns ± 1%  -2.05%  (p=0.000 n=10+9)
ReverseBytes32  0.41ns ± 1%  0.40ns ± 0%  -1.68%  (p=0.000 n=10+10)
ReverseBytes64  0.66ns ± 1%  0.65ns ± 1%  -1.50%  (p=0.000 n=10+9)

cpu=1 benchtime=100ms count=100

name            old time/op  new time/op  delta
Reverse         28.0ns ± 3%  27.7ns ± 3%   -0.80%  (p=0.000 n=100+98)
Reverse8        2.24ns ± 1%  2.24ns ± 1%     ~     (p=0.142 n=98+100)
Reverse16       4.07ns ± 3%  4.05ns ± 3%   -0.66%  (p=0.000 n=99+99)
Reverse32       11.3ns ± 0%  11.3ns ± 0%     ~     (p=0.283 n=94+97)
Reverse64       12.6ns ± 0%  12.6ns ± 0%   +0.60%  (p=0.000 n=100+98)
ReverseBytes    5.25ns ± 1%  5.24ns ± 1%   -0.18%  (p=0.000 n=100+100)
ReverseBytes16  2.00ns ± 0%  2.21ns ± 3%  +10.07%  (p=0.000 n=88+100)
ReverseBytes32  4.08ns ± 2%  4.13ns ± 2%   +1.39%  (p=0.000 n=99+99)
ReverseBytes64  5.48ns ± 1%  5.45ns ± 1%   -0.50%  (p=0.000 n=98+99)

Update #43403

Change-Id: I7e7e00bb17608739d9f6b927c6dfef2580493a0e
Reviewed-on: https://go-review.googlesource.com/c/go/+/280645
Trust: Meng Zhuo <mzh@golangcn.org>
Trust: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Go Bot <gobot@golang.org>
twmb added a commit to twmb/franz-go that referenced this issue Mar 20, 2021
After seeing golang/go#43403, this converts the 256 byte array to a
string so that this can allow stuff to be constant folded.

Uvarint/uvarint_len_1-8  1.98ns ± 0%  1.94ns ± 3%  -2.03%  (p=0.010 n=9+10)
Uvarint/uvarint_len_2-8  2.26ns ± 0%  2.20ns ± 3%  -2.52%  (p=0.000 n=10+10)
Uvarint/uvarint_len_3-8  2.54ns ± 0%  2.48ns ± 3%  -2.15%  (p=0.012 n=9+10)
Uvarint/uvarint_len_4-8  3.11ns ± 1%  3.00ns ± 1%  -3.46%  (p=0.000 n=9+8)
Uvarint/uvarint_len_5-8  3.67ns ± 0%  3.58ns ± 2%  -2.30%  (p=0.001 n=10+10)
twmb added a commit to twmb/franz-go that referenced this issue Mar 21, 2021
After seeing golang/go#43403, this converts the 256 byte array to a
string so that this can allow stuff to be constant folded.

Uvarint/uvarint_len_1-8  1.98ns ± 0%  1.94ns ± 3%  -2.03%  (p=0.010 n=9+10)
Uvarint/uvarint_len_2-8  2.26ns ± 0%  2.20ns ± 3%  -2.52%  (p=0.000 n=10+10)
Uvarint/uvarint_len_3-8  2.54ns ± 0%  2.48ns ± 3%  -2.15%  (p=0.012 n=9+10)
Uvarint/uvarint_len_4-8  3.11ns ± 1%  3.00ns ± 1%  -3.46%  (p=0.000 n=9+8)
Uvarint/uvarint_len_5-8  3.67ns ± 0%  3.58ns ± 2%  -2.30%  (p=0.001 n=10+10)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants