Go vs. FP

[Ian Taylor]

There is an issue about floating point code in Go that I don't recall
that we've ever really settled. That is: how should Go programs
behave with regard to precisely predictable FP behaviour?

There are two basic historical approaches. In C/C++, there are no
promises about FP behaviour at all. Different processors are expected
to produce different results. This is the approach that leads many
programmers to believe statements like "you must never compare
floating point values for equality" (this statement is false).

Java's philosophy, on the other hand, is write once, run anywhere.
That means that a Java program is supposed to produce identical
results whereever it run. Java specifies IEEE-754 floating point
values, and says "The Java programming language requires that
floating-point arithmetic behave as if every floating-point operator
rounded its floating-point result to the result precision."

This means that a Java program has precisely predictable floating
point behaviour, and people who understand how floating point works
can with confidence compare floating point values for equality.
However, Java's approach notoriously led to a strong criticism by
Kahan: How Java's Floating-Point Hurts Everyone Everywhere, at
http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf .

I won't get into the details of Kahan's criticisms, but one that I
think we need to discuss for Go is whether Go expects the same results
for floating point evaluation on all processors. The case that arises
most often in practice is whether the generated code is permitted to
use a floating point fused multiply-and-add instruction. Such an
instruction is faster and is numerically more precise. However, it's
not hard to construct calculations in which it produces a different
result compared to rounding the multiply and add operations
separately.

There are several issues we need to pin down for Go's floating point
format, but let's start with that one: is a Go compiler permitted to
generate a fused multiply-and-add instruction that does not round the
intermediate operation?

The immediate context is http://golang.org/issue/9066 (which is
unfortunately a confusing mix of several different issues) and a
proposed patch to the ken/cplx2.go test to make it pass on S/390
processors
(https://groups.google.com/d/msg/gofrontend-dev/5erZWm2lNI0/ajFz0c7tO5cJ).


My first reaction was that FP behaviour should be predictable, but on
reflection I now think that we should permit fused multiply-and-add.


This then leads to a further question: should we require floating
point values to be rounded when assigned to a variable? For example,
that would mean that this could produce different results on some
processors:

var f1, f2, f3 float64

...

a := f1 * f2 + f3

or

a := f1 * f2
a += f3


To put all this another way, we have already said that floating point
operations must obey parentheses for associative operators. What we
have so far failed to specify is when and whether rounding must occur.

(Subsequent issues will be whether we should expose IEEE-754 floating
point flags and traps in any predictable way.)

Ian

[ron minnich]

We dealt with this problem in my former life (supercomputing) and the
conclusion in the end was that Java had made an unforgiveable mistake
:-)

I think you need to go with the route that lets you take advantage of
the availability of things like FMA.

ron

[Brendan Tracey]

As someone for whom floating point math takes up >95% of my CPU cycles, I am in favor of giving go good improved performance. In terms of absolute reproducibility between executions, concurrency already makes that basically impossible. Go explicitly makes no promises about the order of execution of concurrent goroutines, and floating point results for concurrent programs are already effectively stochastic. Additionally, at least in the numeric world, floating point imprecision already creates problems. For example, convex functions become non-convex when you zoom sufficiently far in (because f(x) may vary by slightly up or down for vary small changes in x). In the gonum optimization package, for example, it is already necessary to guard against the rounding noise. Our codes are already written assuming that floating point math is not perfect, and given that I'm dealing with it already, I'd like it to at least gain speed for it.

I don't understand the web world enough to comment on what Go should do, but if Go could start challenging c++ for floating point speed, it would be a force to be reckoned with for HPC (and in my opinion Go already makes a strong case).

[p...@golang.org]

I went through the same sequence of opinions, and think insisting on exact reproducibility is a mistake. [I didn't particularly like the 80-bit old Intel stuff (although taking a different position from Kahan is deeply troubling) because I couldn't tell if the compiler needed to spill in a complex expression.] Fused multiply-add seems ok to me. The second question iant raises amounts to asking what control users can have, and his implicit proposal is that assigning to a variable causes rounding.

That is

x := a*b

x += c

does rounding twice, while

x := a*b+c

may only do rounding once.

Good so far, but could the compiler generate fused mult-add for

x := (a*b)+c

or does it have two generate both * and +? And in any case, if it can generate the fused op, does it have to?

At the far end of specification, go could add builtins

float64 round64(float64)

and round32

to be used where the user insists on rounding, and otherwise the compiler has more freedom. I suspect these would be overused and misused, but one could insert them automatically around every floating point operation to get a completely reproducible program.

i don't know where to draw the lines...

[Michael Jones]

REASON 1:

I am very strongly in favor of compiler freedom to make choices about instruction issue approaches. I'm with Kahan since 1992. The rules I recommend for Go are the FORTRAN rules: obey separate source statements with respect to assignment, 

a = x*y

a += z

means "compute x*y; assign that to a as if a memory store[1]; add z to a" and cannot mean "a = x*y + z" as FMA. However, "a = x*y + z" allows either style of instruction issue.

and, obey parenthesis as denoting mandated subexpression boundaries.

a = (x*y)+z means the same as the above.

This is easy to conceptualize for programmers with the notion "single statements without unnecessary parenthesis give the compiler full freedom; extra parenthesis and multiple statements restrict that freedom." This allows oblivious programmers to get generally good results and clever numerical analysts to get stunningly good results, both at the maximum speed the processor and compiler allow.

REASON 2:

Go may go to new places. Wimpy machines slack FP, fancy machines with 128-bit FP, etc. Make no unnecessary promises about the future. Doing so risks it becoming "quaint, from back in the day before ..."

Michael

[1] The memory store proviso is how one deals with on-chip precisions greater than stored precisions. This is not a minor issue. It would be great for precision if float32 calculations were done in float64 and only converted to float32 on store. By adopting the rules above, this would be allowed or disallowed by the single/multiple statement coding style.

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Russ Cox]

On Fri, Nov 7, 2014 at 2:09 PM, 'Michael Jones' via golang-dev <golan...@googlegroups.com> wrote:

REASON 1:

I am very strongly in favor of compiler freedom to make choices about instruction issue approaches. I'm with Kahan since 1992. The rules I recommend for Go are the FORTRAN rules: obey separate source statements with respect to assignment, 

a = x*y

a += z

means "compute x*y; assign that to a as if a memory store[1]; add z to a" and cannot mean "a = x*y + z" as FMA. However, "a = x*y + z" allows either style of instruction issue.

and, obey parenthesis as denoting mandated subexpression boundaries.

a = (x*y)+z means the same as the above.

Are you saying that in FORTRAN, a = x*y + z can use a fused multiply-add, but a = (x*y) + z cannot? Regardless of precedent, it seems very dangerous to give such an important meaning to parentheses. That's not how people think about them in Go at least. The distinction between one statement and two seems more defensible.

In constant evaluation, saying float64(x) or float32(x) forces rounding of the possibly higher precision x to an exact float64 or float32 value. (This is in the spec.)

Russ

[Michael Jones]

from a Cray Fortran document:

Although alternative evaluations are allowed, three properties should be noted:

Parentheses must not be violated. Consider the following expression:

(2 * A) + (2 * B)

This expression must not be evaluated as follows:

2 * (A + B)

This gives the programmer some control over the method of evaluation.

I'll dig through specs...

[Robert Griesemer]

- My understanding is that people who care about FP codes want speed, but they also want control. Fused multiply-and-add (fused mac) is something that we may want to be able to use, but a programmer should be able to tell when and where it's used.

- I am weary of giving ()'s more meaning than what they have now (grouping).

- I am weary of using statement boundaries as a method to define where rounding happens - this will force people to avoid assignments to temporary variables, and it will prevent standard compiler optimizations.

- We already say that conversions are the place where rounding is happening, so if we want to disallow a*b+c to become a fused mac, we can just write float64(a*b) + c (or float32, respectively). If a*b is doing proper rounding, the compiler can throw away the conversion. Basically, use explicit (and possibly redundant) conversions where rounding is crucial.

- gri

--

[ron minnich]

I don't have lots of sympathy with the fortran rules and magic () either.

I don't see a lot of point in going overboard given that Go is not
likely to be scientific computing language -- the first question a
friend asked me today was about pragmas such as OpenMP directives --
so in my case, I think just "don't do what Java did" is enough,
coupled with 'we'll use the hardware that's there effectively, and you
should not count on things happening a certain way'. But I'm going to
ask around.

ron

[minux]

On a related note, Go's tests also implicitly make the assumption that
denormal numbers are supported. Of all the ARM platform I've ported,
almost all of them treat denormal numbers as zero by default, and
some still don't have a way to disable that mode on some popular
boards (e.g. Raspberry Pi) due to lack of proper VFP support code.

This is problem similar to the FMA situation. On ARM, it's much faster
to calculate with denormals flushed to zero because otherwise VFP
might need to trap to kernels to emulate operations involving denormals.

To make all.bash pass, we will have to disable the denormal-flush-to-
zero mode for every Go program, even though most of them won't care
about denormals.

If we decided to relax Go's FP rules, could we also consider make
proper denormal support conditional as well?

btw, the gc compiler also relies proper denormal support to be able to
compile some of our test code.

[Mike Andrews]

let's not forget that almost all real numbers are even uncomputable in principle anyway, so this discussion is really just about how we approximate in go (since exactly correct answers are thus generally impossible even with infinite precision). so framed in those terms, i would say the more pragmatic approach is not strict reproducibility per se (since all answers are wrong anyway), but how inaccuracy grows after repeated operations and how to minimize or test for it. for instance, if we have some go code for computing pi~3.14 in pi.go, in pi_test.go we could test that after x iterations of the algorithm (say 1,000,000), the computed result is within some tolerance (say ±0.00000001) of the expected answer. that test code might produce slightly different float64's on each os or architecture (amd64, arm, etc.), or version of go (1.1, 1.2, etc...), but still be within the accuracy mandated and expected by the go platform and float64's generally. we'd put that one and other such tests into the standard golang.org test suite for building the language. that would be good enough for me, and also let the go authors take advantage of particular features of each platform while not endangering the utmost floating point accuracy (sans reproducibility)... perhaps even gpu's, whose floating point ops semantics are beyond our control, but probably still accurate enough for most folks.

i personally never benefited from java's strict reproducibility of floating point operations in all my years using it for numerical work. for go, it might still be nice and easy to get the same number on repeated invocations of the same binary on the same platform though (i.e., determinism vs reproducibility).

see http://en.wikipedia.org/wiki/Computable_number#Properties

best,

mike

[Michael Hudson-Doyle]

Robert Griesemer <g...@golang.org> writes:

> - My understanding is that people who care about FP codes want speed, but
> they also want control. Fused multiply-and-add (fused mac) is something
> that we may want to be able to use, but a programmer should be able to tell
> when and where it's used.

This is my perspective too. Unfortunately it tends to lead to
conditional code (sure, you can implement fma on architectures that lack
it in hw -- in fact, I think C99 mandates it -- but you're not going to
want to call it if you care about performance...), but I don't see a way
around that.

Cheers,
mwh

[minux]

On Fri, Nov 7, 2014 at 6:13 PM, Robert Griesemer <g...@golang.org> wrote:
> - My understanding is that people who care about FP codes want speed, but
> they also want control. Fused multiply-and-add (fused mac) is something that
> we may want to be able to use, but a programmer should be able to tell when
> and where it's used.
>
> - I am weary of giving ()'s more meaning than what they have now (grouping).
>
> - I am weary of using statement boundaries as a method to define where
> rounding happens - this will force people to avoid assignments to temporary
> variables, and it will prevent standard compiler optimizations.
>
> - We already say that conversions are the place where rounding is happening,
> so if we want to disallow a*b+c to become a fused mac, we can just write
> float64(a*b) + c (or float32, respectively). If a*b is doing proper
> rounding, the compiler can throw away the conversion. Basically, use
> explicit (and possibly redundant) conversions where rounding is crucial.

Having thought about this issue more, I think changing the FP rules might be a
backwards incompatible language change (although the spec is not clear on that,
it has been a de-facto standard implemented in both compilers and our tests also
test them, so the "exact reproduction rule" is somewhat official)

What about introducing math.FusedMAC function and specified that it might use
FMA instructions if available, and otherwise an instruction sequence
will emulate
it? The 6g compiler can recognize the pattern and inline the function
with appropriate
instructions.

This is closely related to the idea of making gc compiler able to
inline assembly
functions (even with some annotation from the programmer). If that's supported,
I think the numeric computing people will be much happier. And some of
the assembly
functions in the standard library can also be reduced as much of them
just need to
use some specific instructions (e.g. AES-NI or CRC32), but as Go doesn't support
inline assembly (which is a good thing), all of the function must be
implemented in
assembly entirely to make efficient use of such instructions.

[Ian Taylor]

On Sun, Nov 9, 2014 at 6:24 PM, minux <mi...@golang.org> wrote:
>
> Having thought about this issue more, I think changing the FP rules might be a
> backwards incompatible language change (although the spec is not clear on that,
> it has been a de-facto standard implemented in both compilers and our tests also
> test them, so the "exact reproduction rule" is somewhat official)

I don't think that's accurate: gccgo has never refused to generate
fused multiply-add instructions. It does not use them when compiling
the standard math library, but otherwise it does permit them by
default on platforms that support them. Of course you will only get
them when compiling with optimization.

I don't see this as an incompatible language change, but you're right
that it's in a grey area.

Ian

[Robert Griesemer]

Using a conversion to enforce IEEE rounding is an explicitly documented feature and doesn't require a language change.

[Taru Karttunen]

On 10.11 05:41, Robert Griesemer wrote:
> Using a conversion to enforce IEEE rounding is an explicitly documented
> feature and doesn't require a language change.

Thus the rules would be:

floatXX(expression) -> enforce rounding

t := a*b // no required rounding
c := t+4 // may be fused as fma
c = float64(c) // explicitely rounded
d := float64(a*b)+c // no fma here...

Seems simple and expressive.

- Taru Karttunen

[Dan Kortschak]

On Fri, 2014-11-07 at 15:31 -0800, ron minnich wrote:
> I don't see a lot of point in going overboard given that Go is not
> likely to be scientific computing language

This is demonstrably false. It is already being used as a scientific
programming language.

[ron minnich]

Neat. I'm glad to be shown wrong. Pointers are welcome, so I can pass them on to people I know.

Thanks!

ron 

[Dan Kortschak]

On Mon, 2014-11-10 at 23:08 +0000, ron minnich wrote:
> Neat. I'm glad to be shown wrong. Pointers are welcome, so I can pass
> them on to people I know.
>

Sebastien Binet[0] has been using it a fair amount I think for HEP and
there are a number of people working up numerical support in the gonum
project[1] which various people are using. Also see go.science on G+
(Seb has some talks there).

I have to admit the morale is a little low at the moment because of some
of the changes that are coming soon wrt interfacing with C.

Dan

[0]https://github.com/sbinet
[1]https://github.com/gonum

[Rob Pike]

What changes are those?

-rob

[Ian Taylor]

On Mon, Nov 10, 2014 at 3:29 PM, Rob Pike <r...@golang.org> wrote:
>
> What changes are those?

The concern would be passing Go pointers to C code, e.g., passing the
address of a matrix to vectorized C functions.

I think it will all be OK, though.

Ian

[Dan Kortschak]

On Mon, 2014-11-10 at 15:31 -0800, Ian Taylor wrote:
> The concern would be passing Go pointers to C code, e.g., passing the
> address of a matrix to vectorized C functions.

Yes, these.

> I think it will all be OK, though.
>

I hope so.

thanks
Dan

[Rob Pike]

Nothing is changing, really, except that if a moving collector comes along the author of a cgo package will need to be meticulous about keeping Go pointers out of the C heap. Cross-language bindings are hard, but they should not be notably harder when Go is involved.

-rob

[Dan Kortschak]

On Tue, 2014-11-11 at 10:51 +1100, Rob Pike wrote:
> Nothing is changing, really, except that if a moving collector comes
> along the author of a cgo package will need to be meticulous about
> keeping Go pointers out of the C heap.

This will significantly complicate our matrix code unless we drop
support for C-based BLAS implementations.

[Rob Pike]

I believe it shouldn't be a problem with the right API and if it is a real problem, we can think about solutions.

-rob

[Maxim Khitrov]

On Mon, Nov 10, 2014 at 6:31 PM, Ian Taylor <ia...@golang.org> wrote:
> On Mon, Nov 10, 2014 at 3:29 PM, Rob Pike <r...@golang.org> wrote:
>>
>> What changes are those?
>
> The concern would be passing Go pointers to C code, e.g., passing the
> address of a matrix to vectorized C functions.

Or passing the address of a Go struct to C so that it can later be
passed to a Go callback function (Go -> C -> Go).

> I think it will all be OK, though.

Like Dan, I'm a little pessimistic based on everything I've read
recently. The current proposals of copying and reallocating data will
make the C interface very inefficient, which I think is a bit odd for
a systems programming language.

[Dan Kortschak]

On Tue, 2014-11-11 at 10:59 +1100, Rob Pike wrote:
> I believe it shouldn't be a problem with the right API and if it is a
> real problem, we can think about solutions.

The issue is that at this stage the matrix API makes significant use
make([]float64) by the client. I can see an alternative where our BLAS
implementations and wrappers also implement an allocator and all the
associated book keeping, but this is the additional complexity I am
concerned about. Alternatively we copy at language interfaces and then
we lose our performance benefits.

Dan

[Mike Andrews]

so right now i can use common blas libraries like this in go --- https://gist.github.com/xoba/5780979 --- i.e., pretty easily and without any copying.

are folks saying that it'll get more difficult or lose some performance (like by copying) with upcoming or proposed changes to the go/c interface?

mike

[Russ Cox]

On Mon, Nov 10, 2014 at 7:41 PM, Mike Andrews <m...@xoba.com> wrote:

so right now i can use common blas libraries like this in go --- https://gist.github.com/xoba/5780979 --- i.e., pretty easily and without any copying.

are folks saying that it'll get more difficult or lose some performance (like by copying) with upcoming or proposed changes to the go/c interface?

A few months ago, we (the people working on the Go runtime) were considering some new rules on pointer sharing that would require copying of Go data to C instead of sharing a Go heap pointer directly with C. Based in part on the feedback we got from developers like Dan Kortschak, we decided not to adopt those rules for Go 1.4. We have discussed some other less strict rules and had hoped to include those in Go 1.4, but we were unable even to get those into a state we thought was reasonable even to propose, much less adopt. Go 1.4 will allow all the same cgo code that Go 1.3 does.

Some future version of Go may introduce new restrictions on pointer sharing. I certainly wouldn't promise otherwise - it would constrain the runtime implementation too much. But at the same time, we now recognize that applications that share large amounts of non-pointer data between C and Go are an important use case, and we will be sensitive to their performance if we do need to add restrictions.

In short, don't worry about cgo.

Russ

[andrewc...@gmail.com]

GC discussion seems far from the original fused multiply add topic but ...

If the future planned moving collectors move from nursery to a final generation that never moves again then
an ugly hack would be something like FixedNew() which forces allocation in the final generation or a non moving area.

We should probably create a new topic if people really want to talk about the moving GC and interop.

[Brendan Tracey]

Thanks for the reply, Russ. I’ll admit I got a bit worried today when I saw Ian's change to the cgo documentation. At gonum, we’d certainly like to have gophers all the way down, and in fact, we ensure it’s possible to use pure go, but the c blas libraries are still 5-10x faster than our pure-go equivalents. Thanks for letting us know that you’re aware of the issue and agree it’s important.

On the original topic, I like Robert’s suggestion of conversions. It's much cleaner that the fortran rules, and a statement like 

math.Sqrt(float64(x*x) - float64(y*y))   // x > y but not by much

looks much better than

xs := x * x 

ys := y * y

math.Sqrt(xs - ys)

[Michael Jones]

If the aggressive line-spanning expression merge for evaluation comes to fruition, then we'll need to reconsider the source of the math libraries. That's work, but good work, if we can count on FMA.

[Sebastien Binet]

FYI, most of my HEP work is there:
github.com/go-hep/...

-s

> [1]https://github.com/gonum

[jto...@gmail.com]

After being pointed to this thread, I just wanted to point out that a FixedNew solution won't work for many useful cases of passing Go-allocated memory to C.

For a concrete example, if someone is implementing an io.Reader or io.Writer interface and using C code to read from/fill in the target byte slice, they have no control over where or how the byte slice got allocated.

-JT