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

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
Labels
NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Unplanned

Comments

@TuomLarsen
Copy link

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 NeedsFix The path to resolution is known, but the work has not been done. Performance labels Apr 20, 2019
@josharian josharian added this to the Unplanned milestone Apr 20, 2019
@josharian
Copy link
Contributor

cc @bmkessler @randall77

@gopherbot
Copy link

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
@josharian
cmd/compile: reduce bits.Div64(0, lo, y) to 64 bit division
68d4b12 
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
Copy link
Member

rasky commented Apr 23, 2019

@josharian isn’t this fixed?

@josharian
Copy link
Contributor

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
Copy link
Author

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
Assignees
No one assigned
Labels
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
4 participants
@josharian @rasky @TuomLarsen @gopherbot