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

Jump to bottom

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
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Unplanned

Comments

@egonelbre
Copy link
Contributor

egonelbre commented Dec 28, 2020 •
edited

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

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

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

@egonelbre
Copy link
Contributor Author

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

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

@toothrot toothrot added the NeedsFix The path to resolution is known, but the work has not been done. label Jan 5, 2021
gopherbot pushed a commit that referenced this issue Mar 17, 2021
@mengzhuo
math/bits: folded reverse tables by using const string
119d76d 
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
@twmb
kbin: minor speedup
3d1563d 
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
@twmb
kbin: minor speedup
167de6b 
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)
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@toothrot @josharian @egonelbre @ALTree @gopherbot