code review 83630044: cmd/gc, cmd/ld, runtime: compact liveness bitmaps

cmd/gc, cmd/ld, runtime: compact liveness bitmaps

Reduce footprint of liveness bitmaps by about 5x.

1. Mark all liveness bitmap symbols as 4-byte aligned
(they were aligned to a larger size by default).

2. The bitmap data is a bitmap count n followed by n bitmaps.
Each bitmap begins with its own count m giving the number
of bits. All the m's are the same for the n bitmaps.
Emit this bitmap length once instead of n times.

3. Many bitmaps within a function have the same bit values,
but each call site was given a distinct bitmap. Merge duplicate
bitmaps so that no bitmap is written more than once.

4. Many functions end up with the same aggregate bitmap data.
We used to name the bitmap data funcname.gcargs and funcname.gclocals.
Instead, name it gclocals.<md5 of data> and mark it dupok so
that the linker coalesces duplicate sets. This cut the bitmap
data remaining after step 3 by 40%; I was not expecting it to
be quite so dramatic.

Applied to "go build -ldflags -w code.google.com/p/go.tools/cmd/godoc":

                bitmaps           pclntab           binary on disk
before this CL  1326600           1985854           12738268
4-byte align    1154288 (0.87x)   1985854 (1.00x)   12566236 (0.99x)
one bitmap len   782528 (0.54x)   1985854 (1.00x)   12193500 (0.96x)
dedup bitmap     414748 (0.31x)   1948478 (0.98x)   11787996 (0.93x)
dedup bitmap set 245580 (0.19x)   1948478 (0.98x)   11620060 (0.91x)

While here, remove various dead blocks of code from plive.c.

Fixes issue 6929.
Fixes issue 7568.

[rsc, 2014-04-02 17:31:53]

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

I'd like you to review this change to
https://code.google.com/p/go/

[rsc, 2014-04-02 17:56:49]

I added code to this CL to dedup the eventual bitmap sets as well, by using
content-addressed names for them and letting the linker dedup. I didn't
expect to get much after what the CL was already getting, but it cut the
liveness bitmap footprint in godoc by an additional 40%. Now the savings in
the actual godoc binary due to this CL is over a megabyte, and the overall
liveness footprint reduction is about 5x (formerly 3x). CL description
updated. Here is the new table:
                bitmaps           pclntab           binary on disk
before this CL  1326600           1985854           12738268
4-byte align    1154288 (0.87x)   1985854 (1.00x)   12566236 (0.99x)
one bitmap len   782528 (0.54x)   1985854 (1.00x)   12193500 (0.96x)
dedup bitmap     414748 (0.31x)   1948478 (0.98x)   11787996 (0.93x)
dedup bitmap set 245580 (0.19x)   1948478 (0.98x)   11620060 (0.91x)

This CL completes the liveness efficiency changes for Go 1.3. Issue 7602
and issue 7676 remain (bug fixes).

Russ

[khr, 2014-04-02 20:17:49]

LGTM.  That's a pretty good space savings.

What happens on an md5 collision?

https://codereview.appspot.com/83630044/diff/110001/src/cmd/gc/pgen.c
File src/cmd/gc/pgen.c (right):

https://codereview.appspot.com/83630044/diff/110001/src/cmd/gc/pgen.c#newcode142
src/cmd/gc/pgen.c:142: fatal("cannot rosymdup %s with relocations", ls->name);
s/rosymdup/gcsymdup/

[rsc, 2014-04-02 20:19:25]

On Wed, Apr 2, 2014 at 4:17 PM, <khr@golang.org> wrote:

> LGTM.  That's a pretty good space savings.
>
> What happens on an md5 collision?
>

One bitmap overwrites the other, so that one of the two bitmap references
is now pointing at incorrect data. Are you worried?

Russ

[khr, 2014-04-02 20:24:09]

On 2014/04/02 20:19:25, rsc wrote:
> On Wed, Apr 2, 2014 at 4:17 PM, <mailto:khr@golang.org> wrote:
> 
> > LGTM.  That's a pretty good space savings.
> >
> > What happens on an md5 collision?
> >
> 
> One bitmap overwrites the other, so that one of the two bitmap references
> is now pointing at incorrect data. Are you worried?
> 
> Russ

It doesn't fill me with calm...  Maybe detect non-identical contents when
merging dupok symbols so that if it happens, at least we get an understandable
failure mode.

[rsc, 2014-04-02 20:49:03]

On Wed, Apr 2, 2014 at 4:24 PM, <khr@golang.org> wrote:

> On 2014/04/02 20:19:25, rsc wrote:
>
>  On Wed, Apr 2, 2014 at 4:17 PM, <mailto:khr@golang.org> wrote:
>>
>
>  > LGTM.  That's a pretty good space savings.
>> >
>> > What happens on an md5 collision?
>> >
>>
>
>  One bitmap overwrites the other, so that one of the two bitmap
>>
> references
>
>> is now pointing at incorrect data. Are you worried?
>>
>
>  Russ
>>
>
> It doesn't fill me with calm...  Maybe detect non-identical contents
> when merging dupok symbols so that if it happens, at least we get an
> understandable failure mode.
>

are you worried about md5 in particular or content-addressed naming in
general?
the latter seems well established, and we could switch to sha1 if we need
to.

i put code into liblink to check for dup equality for this specific name
form,
since it was already reading and discarding the duplicated data anyway.
the new linker will be smarter about i/o and i might push back in that
context.
but that won't happen until after go1.3.

russ

[rsc, 2014-04-02 20:49:37]

*** Submitted as https://code.google.com/p/go/source/detail?r=5052ec3ce1c1 ***

cmd/gc, cmd/ld, runtime: compact liveness bitmaps

Reduce footprint of liveness bitmaps by about 5x.

1. Mark all liveness bitmap symbols as 4-byte aligned
(they were aligned to a larger size by default).

2. The bitmap data is a bitmap count n followed by n bitmaps.
Each bitmap begins with its own count m giving the number
of bits. All the m's are the same for the n bitmaps.
Emit this bitmap length once instead of n times.

3. Many bitmaps within a function have the same bit values,
but each call site was given a distinct bitmap. Merge duplicate
bitmaps so that no bitmap is written more than once.

4. Many functions end up with the same aggregate bitmap data.
We used to name the bitmap data funcname.gcargs and funcname.gclocals.
Instead, name it gclocals.<md5 of data> and mark it dupok so
that the linker coalesces duplicate sets. This cut the bitmap
data remaining after step 3 by 40%; I was not expecting it to
be quite so dramatic.

Applied to "go build -ldflags -w code.google.com/p/go.tools/cmd/godoc":

                bitmaps           pclntab           binary on disk
before this CL  1326600           1985854           12738268
4-byte align    1154288 (0.87x)   1985854 (1.00x)   12566236 (0.99x)
one bitmap len   782528 (0.54x)   1985854 (1.00x)   12193500 (0.96x)
dedup bitmap     414748 (0.31x)   1948478 (0.98x)   11787996 (0.93x)
dedup bitmap set 245580 (0.19x)   1948478 (0.98x)   11620060 (0.91x)

While here, remove various dead blocks of code from plive.c.

Fixes issue 6929.
Fixes issue 7568.

LGTM=khr
R=khr
CC=golang-codereviews
https://codereview.appspot.com/83630044

[gobot, 2014-04-02 20:53:10]

This CL appears to have broken the linux-386 builder.
See http://build.golang.org/log/d5875279232ed71c5ca79d6c584fc5c1b07695b8

[khr, 2014-04-02 20:56:24]

On 2014/04/02 20:53:10, gobot wrote:
> This CL appears to have broken the linux-386 builder.
> See http://build.golang.org/log/d5875279232ed71c5ca79d6c584fc5c1b07695b8

Nothing in particular about MD5, collisions in general.
Your liblink detection looks good.