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

math/bits: Division by constant #31582

Open
TuomLarsen opened this issue Apr 20, 2019 · 5 comments
Open

math/bits: Division by constant #31582

TuomLarsen opened this issue Apr 20, 2019 · 5 comments

Comments

@TuomLarsen
Copy link

@TuomLarsen TuomLarsen commented Apr 20, 2019

What version of Go are you using (go version)?

1.12

Does this issue reproduce with the latest release?

Yes.

What did you do?

When dividing by constant (e.g. x/5), Go uses multiplication by a magic constant, instead of using DIVQ instruction. However, bits.Div64 apparently still uses that instruction.

What did you expect to see?

That the following two functions would compile roughly to same code, i.e. there would be no DIVQ.

func Div(x uint64) (uint64, uint64) {
    z := x
    y := x/5
    z -= y
    return y, z
}

func Div(x uint64) (uint64, uint64) {
    y, z := bits.Div64(0, x, 5)
    return y, z
}

What did you see instead?

First function compiles to:

    movq    $-3689348814741910323, AX
    mulq    CX
    shrq    $2, DX
    subq    DX, CX

The second function includes DIVQ.

    xorl    DX, DX
    movl    $5, CX
    divq    CX
@josharian josharian added this to the Unplanned milestone Apr 20, 2019
@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Apr 20, 2019

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Apr 20, 2019

Change https://golang.org/cl/173197 mentions this issue: cmd/compile: reduce bits.Div64(0, lo, y) to 64 bit division

gopherbot pushed a commit that referenced this issue Apr 20, 2019
With this change, these two functions generate identical code:

func f(x uint64) (uint64, uint64) {
	return bits.Div64(0, x, 5)
}

func g(x uint64) (uint64, uint64) {
	return x / 5, x % 5
}

Updates #31582

Change-Id: Ia96c2e67f8af5dd985823afee5f155608c04a4b6
Reviewed-on: https://go-review.googlesource.com/c/go/+/173197
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@rasky

This comment has been minimized.

Copy link
Member

@rasky rasky commented Apr 23, 2019

@josharian isn’t this fixed?

@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Apr 24, 2019

My CL handles Div64(0, lo, y). It doesn't handle Div64(hi, lo, 5). You can imagine wanting to use magic division techniques for 128 bit division by a constant.

@TuomLarsen

This comment has been minimized.

Copy link
Author

@TuomLarsen TuomLarsen commented Apr 24, 2019

Sorry, I should have distinguished Div64(0, lo, y) and Div64(hi, lo, y). While I agree a general case is useful as well, I originally meant the former. I noticed the discrepancy between the particular case of bits.Div64 and plain /, which the CL fixes.

Perhaps this issue could be used to track the eventual development for the general case, somewhat in sync with #30282.

Thank you, @josharian !

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.