code review 6206077: cmd/gc: improve compilation speed by exporting constant...

cmd/gc: improve compilation speed by exporting constants in hexadecimal

[atom, 2012-05-16 14:56:50]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[atom, 2012-05-16 14:59:01]

I would like to know whether this approach (files used as cache) is acceptable
in the compiler.

[r, 2012-05-16 15:00:56]

Why do you want this? Caches are sources of mysterious bugs that don't
happen when you test, only much later when you and your user are far
apart.

-rob

[rsc, 2012-05-16 15:07:27]

I do believe there are opportunities for removing unnecessary floating
point work, but it's hard to believe that storing conversions on disk
is the right solution.  What code exists with a large, repeated number
of such huge floating point constants?

Russ

[0xe2.0x9a.0x9b_gmail.com, 2012-05-16 15:11:28]

On Wednesday, May 16, 2012 5:00:56 PM UTC+2, r wrote:
>
> Why do you want this?


Compiler performance.
 

> Caches are sources of mysterious bugs that don't 
> happen when you test, only much later when you and your user are far 
> apart.


That is an interesting point.

[0xe2.0x9a.0x9b_gmail.com, 2012-05-16 15:25:26]

On Wednesday, May 16, 2012 5:07:05 PM UTC+2, rsc wrote:
>
> I do believe there are opportunities for removing unnecessary floating 
> point work,


I do not see how. Can you describe this more closely?
 

> but it's hard to believe that storing conversions on disk 
> is the right solution.


I seemed to be the easiest and the most high performance solution. The code 
I submitted is only an initial version which I used to start this 
discussion.
 

>  What code exists with a large, repeated number 
> of such huge floating point constants?


It is Go's math package. This means that all Go source codes which are 
importing "math" are affected. On my computer, the cost of importing math 
is 200 milliseconds of compilation time. These 200 ms can be attributed to 
function mpatoflt.

[rsc, 2012-05-16 15:53:03]

On Wed, May 16, 2012 at 11:25 AM, ⚛ <0xe2.0x9a.0x9b@gmail.com> wrote:
> On Wednesday, May 16, 2012 5:07:05 PM UTC+2, rsc wrote:
>> I do believe there are opportunities for removing unnecessary floating
>> point work,
>
> I do not see how. Can you describe this more closely?

Maybe not floating point work, but at least big integers.  Right now
if you write

var x = []byte{1,2,3,4,5,6,7,8,9,10}

that ends up creating 10 big integers, which is overkill.  I think it
might make sense to have a cache for small numbers (say, 0..1023) so
that

var y = []byte{1,2,3,4,5,6,7,8,9,10}

will reuse the same numbers.  It might also work to have a CTINT64
type for constants that is just an int64 instead of an Mpint*.
However, then you get into problems with the big-int code paths
executing only rarely, which worries me.  The cache for even [0..255]
would help a lot for programs that have large byte arrays, I believe,
and also for

var z = []byte("hello")

I would rather try the Mpint* cache (a simple array indexed by value)
than a new CTINT64 type.  But that doesn't address what you are
seeing.

>>  What code exists with a large, repeated number
>> of such huge floating point constants?
>
> It is Go's math package. This means that all Go source codes which are
> importing "math" are affected. On my computer, the cost of importing math is
> 200 milliseconds of compilation time. These 200 ms can be attributed to
> function mpatoflt.

I see, thanks.  There are arguably two problems here.  One is that the
export data includes constants that are unnecessary, like pp0.  Some
unexported constants might be necessary for inlined function bodies,
but most are not.  We could spend some effort on not exporting the
ones that don't matter.  As for mpatoflt itself, I think it would help
to allow the 'p' floating point constants to use hexadecimal.  In
lex.c:1274 or so, where it says goto ncu it could say if(c == 'p')
goto casep.  Then mpatoflt would be passed strings of the form
0x123p-45, which it should have an easier time of.  It can convert the
hex to words directly instead of needing all the multiply by 10
operations.  Using hex in the exported constants would probably
eliminate the mpatoflt time entirely, which would make the export
trimming less important.

Are you interested in looking into either of these?

Russ

[0xe2.0x9a.0x9b_gmail.com, 2012-05-17 07:04:11]

On Wednesday, May 16, 2012 5:52:38 PM UTC+2, rsc wrote:
>
> >>  What code exists with a large, repeated number 
> >> of such huge floating point constants? 
> > 
> > It is Go's math package. This means that all Go source codes which are 
> > importing "math" are affected. On my computer, the cost of importing 
> math is 
> > 200 milliseconds of compilation time. These 200 ms can be attributed to 
> > function mpatoflt. 
>
> I see, thanks.  There are arguably two problems here.  One is that the 
> export data includes constants that are unnecessary, like pp0.  Some 
> unexported constants might be necessary for inlined function bodies, 
> but most are not.  We could spend some effort on not exporting the 
> ones that don't matter.  As for mpatoflt itself, I think it would help 
> to allow the 'p' floating point constants to use hexadecimal.  In 
> lex.c:1274 or so, where it says goto ncu it could say if(c == 'p') 
> goto casep.  Then mpatoflt would be passed strings of the form 
> 0x123p-45, which it should have an easier time of.  It can convert the 
> hex to words directly instead of needing all the multiply by 10 
> operations.  Using hex in the exported constants would probably 
> eliminate the mpatoflt time entirely, which would make the export 
> trimming less important. 
>

I will try this and submit another patch.

[atom, 2012-05-18 11:32:29]

Hello golang-dev@googlegroups.com, r@golang.org, rsc@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[0xe2.0x9a.0x9b_gmail.com, 2012-05-18 12:19:38]

On Wednesday, May 16, 2012 5:00:56 PM UTC+2, r wrote:
>
> Caches are sources of mysterious bugs that don't 
> happen when you test, only much later when you and your user are far 
> apart.
>

I was thinking about your statement and I have some trouble understanding 
what you mean by "caches".

Consider the following: The Go compiler reads in .go and .a files, and 
outputs .8 files. The linker reads in .8 and .a files, and outputs an 
executable.

Those .a files are only caching the contents of valid .go files. So the 
compiler is using a cache each time it reads an .a file. In addition to 
this, .a files are more consistent than .go files (.a files have a definite 
structure, but .go files are potentially just arbitrary text).

If you are against caches, then it seems irrational to generate and use .a 
files.

Considering all of this, how would you explain your statement about caches?

[iant2, 2012-05-18 13:24:32]

⚛ <0xe2.0x9a.0x9b@gmail.com> writes:

> Consider the following: The Go compiler reads in .go and .a files, and 
> outputs .8 files. The linker reads in .8 and .a files, and outputs an 
> executable.
>
> Those .a files are only caching the contents of valid .go files. So the 
> compiler is using a cache each time it reads an .a file. In addition to 
> this, .a files are more consistent than .go files (.a files have a definite 
> structure, but .go files are potentially just arbitrary text).
>
> If you are against caches, then it seems irrational to generate and use .a 
> files.

That's not a cache, that's a transformation.  The term "cache" implies
storing a value temporarily, such that when the cache is full you eject
some value and then recreate it on demand.  The .8 and .a files are
never evicted.  The tool that uses them can not recreate them.

Ian

[rsc, 2012-05-18 15:47:33]

Thanks.  Do you have timings for how much it helps?  I'm just curious.

The changes to fmt seem more significant than necessary. I think you
can revert both fmt.c and go.h and still make this change.

I think you can change the last few lines of Fconv from saying %B to
%#B and then in Bconv instead of using the global flag, consult
fp->flags&FmtSharp.

Thanks again.
Russ

[atom, 2012-05-18 17:45:44]

On 2012/05/18 15:47:33, rsc wrote:
> Thanks.  Do you have timings for how much it helps?  I'm just curious.

In case of compiling the following program:

package main
import "math"
func main() { println(math.Pi) }

the time spent in 8g goes down from 244ms to 22ms.

> The changes to fmt seem more significant than necessary. I think you
> can revert both fmt.c and go.h and still make this change.
> 
> I think you can change the last few lines of Fconv from saying %B to
> %#B and then in Bconv instead of using the global flag, consult
> fp->flags&FmtSharp.

This would lead to %F printing out the mantissa in hexadecimal all the time.
mparith3.c uses %F to print out some debugging messages.

[rsc, 2012-05-18 17:50:22]

On Fri, May 18, 2012 at 1:45 PM,  <0xE2.0x9A.0x9B@gmail.com> wrote:
> This would lead to %F printing out the mantissa in hexadecimal all the
> time. mparith3.c uses %F to print out some debugging messages.

That's fine with me.

[0xe2.0x9a.0x9b_gmail.com, 2012-05-18 18:09:44]

On Friday, May 18, 2012 3:24:23 PM UTC+2, Ian Lance Taylor wrote:
>
> ⚛ <0xe2.0x9a.0x9b@gmail.com> writes: 
>
> > Consider the following: The Go compiler reads in .go and .a files, and 
> > outputs .8 files. The linker reads in .8 and .a files, and outputs an 
> > executable. 
> > 
> > Those .a files are only caching the contents of valid .go files. So the 
> > compiler is using a cache each time it reads an .a file. In addition to 
> > this, .a files are more consistent than .go files (.a files have a 
> definite 
> > structure, but .go files are potentially just arbitrary text). 
> > 
> > If you are against caches, then it seems irrational to generate and use 
> .a 
> > files. 
>
> That's not a cache, that's a transformation.  The term "cache" implies 
> storing a value temporarily, such that when the cache is full you eject 
> some value and then recreate it on demand.  The .8 and .a files are 
> never evicted.  The tool that uses them can not recreate them. 
>

Ok. But why are, according to Rob Pike, "caches sources of mysterious bugs 
that don't happen when you test, only much later when you and your user are 
far apart" and transformations aren't sources of such mysterious bugs?   I 
agree that caches are harder to implement because they need an eviction 
algorithm, but I am not sure I understand how this alone can be the source 
of "mysterious bugs".

[iant2, 2012-05-18 20:04:16]

⚛ <0xe2.0x9a.0x9b@gmail.com> writes:

> On Friday, May 18, 2012 3:24:23 PM UTC+2, Ian Lance Taylor wrote:
>>
>> ⚛ <0xe2.0x9a.0x9b@gmail.com> writes: 
>>
>> > Consider the following: The Go compiler reads in .go and .a files, and 
>> > outputs .8 files. The linker reads in .8 and .a files, and outputs an 
>> > executable. 
>> > 
>> > Those .a files are only caching the contents of valid .go files. So the 
>> > compiler is using a cache each time it reads an .a file. In addition to 
>> > this, .a files are more consistent than .go files (.a files have a 
>> definite 
>> > structure, but .go files are potentially just arbitrary text). 
>> > 
>> > If you are against caches, then it seems irrational to generate and use 
>> .a 
>> > files. 
>>
>> That's not a cache, that's a transformation.  The term "cache" implies 
>> storing a value temporarily, such that when the cache is full you eject 
>> some value and then recreate it on demand.  The .8 and .a files are 
>> never evicted.  The tool that uses them can not recreate them. 
>>
>
> Ok. But why are, according to Rob Pike, "caches sources of mysterious bugs 
> that don't happen when you test, only much later when you and your user are 
> far apart" and transformations aren't sources of such mysterious bugs?   I 
> agree that caches are harder to implement because they need an eviction 
> algorithm, but I am not sure I understand how this alone can be the source 
> of "mysterious bugs".

I can't speak for Rob, but the issue with a cache is recreating the
value after it has been evicted.  That code is not routinely tested and
can contain bugs that only arise in unusual eviction cases.  Something
like generating a .8 or .a file is tested every time.

Ian

[rsc, 2012-05-18 20:13:43]

More generally, any change that introduces a new code path means you
have to worry about exercising that path during testing (or else
suffer bugs).  This is why, when we discussed possible ways to reduce
bignum time in the compiler, I suggested that I'd rather have 256 or
1024 fixed mpints for the small values instead of introducing a
separate kind of "not-big-int" constant inside the compiler.  The
former introduces fewer new, possibly buggy, hard to exercise code
paths than the latter.

Russ

[atom, 2012-05-19 09:06:20]

Hello golang-dev@googlegroups.com, r@golang.org, rsc@golang.org, iant@google.com
(cc: golang-dev@googlegroups.com),

Please take another look.

[atom, 2012-05-19 18:32:27]

Hello golang-dev@googlegroups.com, r@golang.org, rsc@golang.org, iant@google.com
(cc: golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2012-05-19 18:48:11]

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c
File src/cmd/gc/mparith1.c (right):

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c#newcod...
src/cmd/gc/mparith1.c:274: // required syntax is [+-]d*[.]d*[e[+-]d*] or
[+-]0xH*[e[+-]d*]
is this using an hexadecimal mantissa and a decimal exponent? I though the CL
was about using 0xdeadc0de0123456789p+12345 syntax? Or maybe the comment must be
updated to explain that "p" exponents are accepted?

[atom, 2012-05-20 05:42:25]

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c
File src/cmd/gc/mparith1.c (right):

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c#newcod...
src/cmd/gc/mparith1.c:274: // required syntax is [+-]d*[.]d*[e[+-]d*] or
[+-]0xH*[e[+-]d*]
On 2012/05/19 18:48:12, remyoudompheng wrote:
> is this using an hexadecimal mantissa and a decimal exponent? I though the CL
> was about using 0xdeadc0de0123456789p+12345 syntax? Or maybe the comment must
be
> updated to explain that "p" exponents are accepted?

Some comments in mparith.c and fmt.c were imprecise already, and are remaining
imprecise.

[dave_cheney.net, 2012-05-20 05:59:57]

While I can't claim to understand what you have done here, the results on 5g are
remarkable, thank you.

before:
% /usr/bin/time -v ~/go/pkg/tool/linux_arm/5g pi.go 
        Command being timed: "/home/dfc/go/pkg/tool/linux_arm/5g pi.go"
        User time (seconds): 0.89
        System time (seconds): 0.01
        Percent of CPU this job got: 99%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.91

after:
% /usr/bin/time -v ~/go/pkg/tool/linux_arm/5g pi.go 
        Command being timed: "/home/dfc/go/pkg/tool/linux_arm/5g pi.go"
        User time (seconds): 0.17
        System time (seconds): 0.02
        Percent of CPU this job got: 98%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.20

[rsc, 2012-05-21 17:16:46]

Thanks.  The code looks good except for some C style nits.  I apologize for
them, but it is a significant long term help to keep everything uniform.

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c
File src/cmd/gc/mparith1.c (right):

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c#newcod...
src/cmd/gc/mparith1.c:253: long d;
Please move all variable declarations to the top of the function; that's the
prevailing style of the rest of the code.  Thanks.

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c#newcod...
src/cmd/gc/mparith1.c:316: char *start = 0;
Same.
Also please use nil for pointers, not 0.

http://codereview.appspot.com/6206077/diff/16002/src/cmd/gc/mparith1.c#newcod...
src/cmd/gc/mparith1.c:546: int digit = mpgetfix(&r);
Same.

[atom, 2012-05-22 07:54:10]

Hello golang-dev@googlegroups.com, r@golang.org, rsc@golang.org,
iant@google.com, remyoudompheng@gmail.com, dave@cheney.net (cc:
golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-05-22 15:57:35]

LGTM

[rsc, 2012-05-22 17:53:40]

*** Submitted as http://code.google.com/p/go/source/detail?r=8f4c9f27ea77 ***

cmd/gc: export constants in hexadecimal

R=golang-dev, r, rsc, iant, remyoudompheng, dave
CC=golang-dev
http://codereview.appspot.com/6206077

Committer: Russ Cox <rsc@golang.org>