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

cmd/compile: introduce CINT64 to reduce memory footprint #4617

Open
davecheney opened this Issue Jan 5, 2013 · 25 comments

Comments

Projects
None yet
8 participants
@davecheney
Copy link
Contributor

davecheney commented Jan 5, 2013

What steps will reproduce the problem?

Compiling exp/locale/collate consumes more than 200mb on 32bit platforms like arm (more
than 300 mb on amd64). The is most likely caused by the 50k line tables.go, and its ~
300k values.

Can anything be done to reduce the amount of memory consumed when compiling this package?
@minux

This comment has been minimized.

Copy link
Member

minux commented Jan 5, 2013

Comment 1:

yes. cmd/gc now allocates a Mpint (16 words) for each number in source,
we should be able to share them or even use a smaller representation if
suffice; I've tried this approach, but it changed so many things.
I propose we introduce one extra level of indirection for Mpint, something
like this:
union {
    struct realMpint *p;
    long taggedWord; // last bit is 1 for a 31-bit or 63-bit integer
} Mpint;
and use this to replace Mpint* in the Val struct.
or, alternatively, we can share Mpint*, but that still a big change as we must
take care when changing the shared copy.
Any thoughts on this?
@minux

This comment has been minimized.

Copy link
Member

minux commented Jan 5, 2013

Comment 2:

for Mpflt, we can even use NaN-boxing to hide a pointer to realMpflt inside a
normal double, however, this might be too hacky (it should be portable as we do
require IEEE-754 floating point, and the only problem i can think of is that Solaris
sometimes return addresses in the upper half of amd64 virtual address space).
@davecheney

This comment has been minimized.

Copy link
Contributor Author

davecheney commented Jan 5, 2013

Comment 3:

Thank you for your fast reply
re #1: is there a simple way I could instrument the compiler to tell how many Mpints
would fit into a long, or would require indirection to a readMpint ? My suspicion is the
number would be quite small, so this patch would turn out to be a net positive for
almost all compilations.
Re: sharing *Mpints, I did a very quick summary of the different numbers in tables.go
(see attached), and while there is a lot of duplication, there are close to 200k lines
in the file, unless sharing an Mpint cost very little, I don't think this would save
memory, or time.

Attachments:

  1. tables.txt (3503457 bytes)
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 7, 2013

Comment 4:

Mpflt contains a high-precision floating point number. It is not IEEE in any way. There
are no NaNs.
Two possibilities that come to mind:
1) Add a new val.ctype = CTINT64 and add a int64 field to the val union. Make sure that
CTINT is only ever used for values that do not fit in an int64.
2) In lex.c, at the ncu: label, before allocating an mpint, look in a hash table (can
reuse lookup probably) to see if we've seen this number before, and if so, reuse the
Mpint from the last time.  (They are not modified once craeted.)
I think (1) is more work but will end up significantly cleaner and more robust. I think
(2) is a small amount of work but might introduce subtle bugs and may not work at all.

Labels changed: added priority-later, removed priority-triage.

Status changed to Accepted.

@remyoudompheng

This comment has been minimized.

Copy link
Contributor

remyoudompheng commented Jan 7, 2013

Comment 5:

I have tried 2) once, but it didn't work due to a mutation that happened later, but
maybe I was just doing wrong.
2) would be quite effective on rotate.go where we have many many small literals, but I
think the more common use case is the collate one, where we have many small-sized
literals, but usually all different (or in cryptography/numerical computations/video
encoding with precomputed, possibly large tables).
So I think 1) is useful for large precomputed tables with non-trivial values, 2) is
useful for large auto-generated code with many small constants (but then the size of the
AST dwarfs the size used for literals).
@minux

This comment has been minimized.

Copy link
Member

minux commented Jan 8, 2013

Comment 6:

Re #4, I mean we use a IEEE double to contain a Mpflt that's representable
and embed a pointer to the real Mpflt by using Nan-boxing.
Ok, I agree introducing a new CINT64/CFLT64 is clearer.
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 9, 2013

Comment 7:

Please only introduce CINT64. CFLT64 will be a lot of work and almost
never used. Remember that constants need to be ideal and
high-precision. Even if you can store one particular floating-point
value 100% accurately in a float64, any mathematical operation on it
will need significant work to figure out whether the result also fits
exactly in a float64, and it almost never will.
Russ
@minux

This comment has been minimized.

Copy link
Member

minux commented Jan 12, 2013

Comment 10:

300k numbers means Mpint structures consume ~18MiB RAM,
will reducing that value to 2.3MiB make a big difference?
I guess we still need to see pprof svg image to see where
the bulk of memory goes.
@davecheney

This comment has been minimized.

Copy link
Contributor Author

davecheney commented Jan 12, 2013

Comment 11:

ok. so we are back to converting Node into a union. I will make some svgs
On Saturday, January 12, 2013, wrote:
@minux

This comment has been minimized.

Copy link
Member

minux commented Jan 12, 2013

Comment 12:

just for clarification: I don't mean this issue is not important,
and in fact, saving ~16MiB is well worth doing.
I just want to know whether there is other (potentially bigger)
memory saving possibilities for issue #1860 and the original
exp/locale/collate/tables.go issue.
@davecheney

This comment has been minimized.

Copy link
Contributor Author

davecheney commented Jan 12, 2013

Comment 13:

(pprof) top
Total: 510.8 MB
   409.5  80.2%  80.2%    409.5  80.2% nod
    53.9  10.5%  90.7%     54.0  10.6% _yylex
    22.9   4.5%  95.2%     22.9   4.5% prog
     6.8   1.3%  96.5%     28.3   5.5% nodintconst
     6.0   1.2%  97.7%      6.0   1.2% list1
     5.8   1.1%  98.8%      5.8   1.1% entry
     2.8   0.5%  99.4%      2.8   0.5% typ
     1.5   0.3%  99.7%      1.5   0.3% inithash
     0.8   0.1%  99.8%      0.8   0.1% rega
     0.4   0.1%  99.9%      0.4   0.1% pkglookup

Attachments:

  1. 8g.ecab7a7e7c7e.svg (47771 bytes)
@remyoudompheng

This comment has been minimized.

Copy link
Contributor

remyoudompheng commented Mar 6, 2013

Comment 14:

I believe implementing this is too hard for Go 1.1.
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Mar 6, 2013

Comment 15:

Agreed.

Labels changed: removed go1.1.

@davecheney

This comment has been minimized.

Copy link
Contributor Author

davecheney commented May 16, 2013

Comment 16:

Issue #5483 has been merged into this issue.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jul 30, 2013

Comment 17:

Related: []byte(`long string`) turns into []byte{0: 'l', 1: 'o', ...}, because all
composite literals have keys introduced. That creates a ton of garbage. It would be nice
to do better.

Labels changed: added go1.3maybe.

@robpike

This comment has been minimized.

Copy link
Contributor

robpike commented Aug 20, 2013

Comment 18:

Labels changed: removed go1.3maybe.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Nov 27, 2013

Comment 19:

Labels changed: added go1.3maybe.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 4, 2013

Comment 20:

Labels changed: added release-none, removed go1.3maybe.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 4, 2013

Comment 21:

Labels changed: added repo-main.

@rsc rsc changed the title cmd/gc: introduce CINT64 to reduce memory footprint cmd/compile: introduce CINT64 to reduce memory footprint Jun 8, 2015

@josharian

This comment has been minimized.

Copy link
Contributor

josharian commented Mar 12, 2016

Now that the compiler is in Go, and we have a nice union type for constant values, and there's a renewed concern about compiler speed, adding CTINT64 might be worth another look.

@martisch

This comment has been minimized.

Copy link
Member

martisch commented Mar 28, 2017

I started evaluating replacing Mpint by several type implementations: one for CTRUNE and CTINT and an implementation for each one using an int64 and one using a big.int.

I have gotten as far as replacing Mpint by an interface and changing the compiler not to depend on internal implementation details of CTINT/CTRUNE types. I also separated out the the CTRUNE type from Mpint by embedding an Mpint into a new Mprune type. My next step is to make an Integer interface satisfying type that uses only a int64 for storage and returns an Mpint which uses big.int on overflow when operated on. Ones i have gotten as far producing a working prototype that shows memory savings i will write another update with benchmark numbers.

@martisch martisch self-assigned this Mar 28, 2017

@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented Mar 29, 2017

@martisch Have you considered go/constant? We could just use it, or borrow from it heavily.

@martisch

This comment has been minimized.

Copy link
Member

martisch commented Mar 29, 2017

@griesemer
it indeed seems better to not have two duplicated implementations of constant values.

go/constant looks like it could be used as a drop in replacement (with some extensions) for gc Val when the compiler does not depend on implementation details of Val anymore.

go/constant does not seem to support an extra rune type or nil value type.
We would need to store that info elsewhere (e.g. in an enculapsing struct) or
would it be acceptable to extend go/constant directly to support new types rune32Val, runeVal, nilVal? Alternatively we can create an internal copy and extend it with these types.

We might not need the type constants CTINT, CTRUNE, ... as such after all and can just differentiate on the Kind of value directly always.

I will try out a CL first that just uses an texteneded go/constant and modify all the users in the compiler to use the new Val interface together with some helper functions. Will write back here if i encounter any not yet known problems with that approach.

@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented Mar 29, 2017

@martisch A few things to consider:

  • go/constant was written to work with go/types - one might be able to add rune values but I'd much prefer not to: go/constants doesn't consider types, it's about values, and I'd rather not mix the concepts. A rune32 is really an int32. A runeVal is a value of untyped rune type. Nil is not a constant value and thus not represented as such. (go/types uses different untyped "ideal" types for the basic types).

  • go/constant uses big.Rat to represent floats up to a certain size, at which point it transparently switches to a big.Float representation (when the rationals get too large). Not per see an issue, but something to keep in mind.

@martisch

This comment has been minimized.

Copy link
Member

martisch commented Mar 29, 2017

go/constants doesn't consider types, it's about values

agreed. seems better to keep it pure and store the ideal type information in an extra field besides the constant value. This also should allow to use the go/constant package without further modifications.

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