Go: cmd/compile: precalculate constant square roots

[josharian]

Low priority, but probably also an easy ssa rule.

package x

import "math"

func root2() float64 {
    return math.Sqrt(2)
}

yields (amd64):

"".root2 t=1 size=32 args=0x8 locals=0x0
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:5)   TEXT    "".root2(SB), $0-8
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:5)   NOP
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:5)   NOP
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:5)   FUNCDATA    $0, gclocals·5184031d3a32a42d85027f073f873668(SB)
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:5)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (/Volumes/Data/src/go.tip/src/sqrt.go:6)   MOVSD   $f64.4000000000000000(SB), X0
    0x0008 00008 (/Volumes/Data/src/go.tip/src/sqrt.go:6)   SQRTSD  X0, X0
    0x000c 00012 (/Volumes/Data/src/go.tip/src/sqrt.go:6)   MOVSD   X0, "".~r0+8(FP)
    0x0012 00018 (/Volumes/Data/src/go.tip/src/sqrt.go:6)   RET

But sqrt(2) is a constant.

cc @randall77 @brtzsnr

[cznic]

const root2 = 1.41421356237309504880168872420969807856967187537694807317667973799

[josharian]

That's why it's low priority.

[minux]

What's more interesting and generally useful is perhaps compile time
constant folding of pure (inlinable?) functions, esp. those in the math
package.

[josharian]

Another small, straightforward sqrt-related compiler learning bug. Paging the crew from #16804: @odeke-em @kevinburke @martisch

[kevinburke]

I'm interested in both but likely won't have time until Monday

On Friday, August 19, 2016, Josh Bleecher Snyder [email protected]
wrote:

Another small, straightforward sqrt-related compiler learning bug. Paging
the crew from #16804 https://github.com/golang/go/issues/16804:
@odeke-em https://github.com/odeke-em @kevinburke
https://github.com/kevinburke @martisch https://github.com/martisch

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/15543#issuecomment-241170923, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAOSI6tL6oyHmaZ1gghIryRS0u0e03FNks5qhlyTgaJpZM4IXe8K
.

Kevin Burke
925.271.7005 | kev.inburke.com

[kevinburke]

Is this in walk.go the right place for it or is this too early?

        if n.Left.Op == ONAME && n.Left.Sym.Name == "Sqrt" && n.Left.Sym.Pkg.Path == "math" {
            if Thearch.LinkArch.InFamily(sys.AMD64, sys.ARM, sys.ARM64, sys.PPC64, sys.S390X) {
                n.Op = OSQRT
                n.Left = n.List.First()
                n.List.Set(nil)
                break opswitch
            }
        }

[josharian]

I think it'd be better in generic.rules (and the code that gets generated from it, see cmd/compile/internal/ssa/gen).

[gopherbot]

CL https://golang.org/cl/27457 mentions this issue.

[mwhudson]

To be pedantic, math.Sqrt is not a pure function -- it depends on the rounding mode the FPU is in. But as Go does not provide any way to change that, it's probably not a real problem.

[minux]

Does setting the FPU rounding mode to non-round-to-nearest
pass the builtin tests for math.Sqrt?

[mwhudson]

On 22 August 2016 at 13:06, Minux Ma [email protected] wrote:

Does setting the FPU rounding mode to non-round-to-nearest
pass the builtin tests for math.Sqrt?

Probably not. The tests compare the result of the Go sqrt code with the
Sqrt code and the Go sqrt (according to the comments) omits checking of
rounding mode.

Cheers,
mwh

[randall77]

It seems that Go plays pretty fast and loose with how floating-point ops are rounded (not just sqrt). The spec is silent on the topic. I'm not sure if/how we should support e.g. C code changing the rounding mode.

[josharian]

Possibly apropos:

https://github.com/golang/go/commit/4a8cb4a49c8bda0759dd3bc0c9fc6bdf5f6aa6b7

There Russ said:

In general, if a Go program changes the floating point math modes to something other than what Go expects, the math library is not going to work exactly as intended, so we might be justified in not fixing this at all.

[minux]

Perhaps the spec should just specify the rounding mode?

The only time specific rounding mode is mentioned is converting
ideal floating point values to float32/float64 uses rounds to nearest
even.

[randall77]

But what does Go expect? Ideally we should set the rounding mode on process (or OS thread) start and at the start of each C->Go transition. I don't see anything in our code for startup (except plan9), but maybe the default is OK. For returns from cgo calls I think we can rely on the calling convention which states that fp rounding mode is callee-save. But for callbacks from C->Go I don't see where we do anything, and I think we should save+set and restore the fp mode (on x86 at least).

[griesemer]

The expected rounding mode is To Nearest Even - that's the only default that makes sense. I'm pretty sure a lot of things would break if that changed. For instance, some of the math/big.Float tests assume that float32/64 are rounded that way (and it's tested against big.Floats with that rounding mode).

I don't know that C or C++ say much about float rounding but I'd be surprised if things wouldn't break if the mode is changed. Probably the same for Java.

I have a vague memory that we talked about that in the long past and the conclusion was that all bets are off if a piece of code (Go or anywhere else) changes the rounding mode. Or in other words: if some code changes it locally, it better changes it back.

[minux]

So the question is: should we specify the rounding mode
in the language spec?

[griesemer]

@minux I may not recall this correctly, but I believe we deliberately didn't specify it.

I suspect this is mostly for historical reasons (in the distant past, not every architecture had IEEE floating-point support, say the Cray machines) - and languages wouldn't want to exclude themselves from being "correctly" implementable. Now any relevant hardware supports IEEE floats, so perhaps it's ok to request it (we already refer to the standard in the spec. But I doubt it makes a difference in practice, so why risk it?

Related, Java took a big floating-point performance hit in the 90's because it specified floating-point details such as rounding in very much detail: on x87 hardware, intermediate results not stored to memory where held in 80bit registers which lead to different results because rounding was not done to 64bits. As a result, a -strict interpretation of Java floating-point operations required that each intermediate result be stored to memory to achieve correct rounding. Intel was not happy about that (it made their chips look slower than others) - hence it was a JVM option.

[dr2chase]

Java's strictfp is very picky about arithmetic, and specifies not just rounding mode, but mantissa sizes, exponent ranges, use of denormalized numbers, particular NaN encodings, and a limit of only one rounding per mathematical operation. I'm not sure we want all that for Go, but I think specified rounding would be helpful. Changing rounding would change (for example) our random-number stream. In our currently generated code, we're not especially careful about exponent ranges and mantissa sizes, which means that there are cases where differences could be seen if people knew what to look for (examples: x87 might use 80-bit FP, which can result in double-rounding even with storeback; PPC FP registers are double-precision only, and so "float32" calculations may have extra precision in their intermediate results; any architecture with a so-called "fused multiply-add" will perform the addition in a*b+c in a double-width mantissa before rounding).

One thing to possibly consider that might placate the small-but-nonempty set of numerically oriented people who actually _do_ care about rounding modes and understand how to write code that depends on them, is something along the lines of runInRoundingMode(mode Mode, f func()) where a (presumably small) piece of Go code could be run in a non-standard rounding mode. The compiler would be responsible for saving/restoring current rounding mode correctly in those places where it tinkers with it for code generation purposes.

[dr2chase]

IBM 360 was a notable non-standard FP architecture: https://en.wikipedia.org/wiki/IBM_Floating_Point_Architecture

[mwhudson]

I guess I should apologize a bit for opening this can of worms :-)

On 23 August 2016 at 03:34, Robert Griesemer [email protected]
wrote:

@minux https://github.com/minux I may not recall this correctly, but I
believe we deliberately didn't specify it.

I suspect this is mostly for historical reasons (in the distant past, not
every architecture had IEEE floating-point support, say the Cray machines)

• and languages wouldn't want to exclude themselves from being "correctly"
  implementable. Now any relevant hardware supports IEEE floats, so perhaps
  it's ok to request it (we already refer to the standard in the spec. But I
  doubt it makes a difference in practice, so why risk it?

Making it clear one way or another if changing the rounding mode is
supported would make it clear whether or not the compiler can constant fold
fp math. Mandating that the fp environment is a constant thing is a bit
different from mandating exactly what that fp environment is.

[mwhudson]

On 23 August 2016 at 09:47, Michael Hudson-Doyle [email protected]
wrote:

Making it clear one way or another if changing the rounding mode is
supported would make it clear whether or not the compiler can constant fold
fp math.

Although it's been decided elsewhere that floating point constants are
_not_ IEEE floats, so I'm probably making a fuss over nothing!

[griesemer]

@dr2chase "Starting with the S/390 G5 in 1998,[5] IBM mainframes have also included IEEE binary floating-point units which conform to the IEEE 754 Standard for Floating-Point Arithmetic."

@mwhudson This is not about Go constants, this is about the compiler optimizing float32/64 variables that it recognizes as constants.

The spec requires IEEE floats (definition of float32, float64). I'd be ok with stating that the rounding mode used should be round-to-nearest even. I'm pretty sure we can't guarantee anything if it's changed. And we'd have to carefully rewrite a lot of code if we'd support changing the rounding mode underneath.

The other rounding modes are useful to implement things such as interval arithmetic, but it would be rather tedious to do this in Go for float32/64's.

That all said, it's nowhere written that math.Sqrt(2) cannot return the exact rounded result, internally stored as a constant (and that instead it must return the possibly incorrect, computed value).