code review 122680043: runtime: cache unrolled GC bitmask

runtime: cache unrolled GC bitmask
Cache unrolled GC bitmask for types up to 64/32K on 64/32-bit systems,
this corresponds to up to 4K cached bitmask.
Perf builders say that 2% of time is spent in unrollgcproginplace_m/unrollgcprog1
on http benchmark:
http://goperfd.appspot.com/log/f42045f45bf61a0da53b724a7c8567824a0ad6c9

[dvyukov, 2014-08-15 19:24:34]

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

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

[rsc, 2014-08-15 19:25:17]

NOT LGTM

We already had this discussion. I want to see some attention paid to making
unrolling fast before we start wasting memory on this.

[rsc, 2014-08-15 19:27:14]

Another thing I'd like to see is what size is actually needed. Why not
MaxGCMask = 16? Does that get most of the savings?

[dvyukov, 2014-08-20 13:09:36]

I've collected unroll stats on godoc after serving a dozen of different pages.

Here are all types that were unrolled:

gcmasksize= 51	godoc.Corpus
gcmasksize= 46	build.Package
gcmasksize= 45	godoc.Presentation
gcmasksize= 384	strings.byteStringReplacer
gcmasksize= 31	regexp.machine
gcmasksize= 31	json.decodeState
gcmasksize= 29	map.bucket[string]http.muxEntry
gcmasksize= 27	parse.Tree
gcmasksize= 25	map.bucket[string]syntax.charGroup
gcmasksize= 25	map.bucket[string]reflect.Value
gcmasksize= 23	parser.parser
gcmasksize= 23	godoc.PageInfo
gcmasksize= 21	printer.printer
gcmasksize= 21	map.bucket[string][]vfs.mountedFS
gcmasksize= 21	map.bucket[string][]string
gcmasksize= 21	map.bucket[reflect.layoutKey]reflect.layoutType
gcmasksize= 21	map.bucket[reflect.Type][]json.field
gcmasksize= 19	map.bucket[tls.alert]string
gcmasksize= 19	map.bucket[string]template.element
gcmasksize= 19	map.bucket[string]template.contentType
gcmasksize= 19	map.bucket[string]bool
gcmasksize= 19	map.bucket[reflect.Type]bool
gcmasksize= 19	http.response
gcmasksize= 17	runtime.g
gcmasksize= 17	map.bucket[string]types.Object
gcmasksize= 17	map.bucket[string]string
gcmasksize= 17	map.bucket[string]reflect.Type
gcmasksize= 17	map.bucket[string]os.FileInfo
gcmasksize= 17	map.bucket[string]interface {}
gcmasksize= 17	map.bucket[string]expvar.Var
gcmasksize= 17	map.bucket[reflect.Type]string
gcmasksize= 17	map.bucket[reflect.Type]gob.gobType
gcmasksize= 17	map.bucket[crypto.Hash][]uint8
gcmasksize= 17	doc.reader
gcmasksize= 17	doc.Type
gcmasksize= 17	base64.Encoding
gcmasksize= 105	runtime.m

Total size of unrolled masks is 1306 bytes. That is the additional memory that
we would use if we cache all masks.

There are 2 buckets:
1. Normal structs with mask size <= 64 bytes.
2. Structs with large embed arrays, we have a dozen of them in std lib:

type byteStringReplacer struct {
    old byteBitmap
    new [256][]byte
}
pkg/strings/replace.go

type Reader struct {
        Header
        r            flate.Reader
        decompressor io.ReadCloser
        digest       hash.Hash32
        size         uint32
        flg          byte
        buf          [512]byte
pkg/compress/gzip/gunzip.go

type decoder struct {
        r    io.Reader
        bits bits
        bytes struct {
                buf  [4096]byte
pkg/image/jpeg/reader.go

type encoder struct {
        w   writer
        err error
        g *GIF
        buf [1024]byte

Let's set the limit so that it covers 8K of memory, that is a 4k byte array +
something, or [256][]byte as in byteStringReplacer + something.
That's 512 bytes of memory per type and any given program allocate only a
handful of them. So this will consume at most few KB of memory.

I especially don't want to optimize unrolling, because:
1. It just does not worth our time taking into account the negligible amount of
memory that it consumes (we waste orders of magnitude more in other places).
2. Fast unrolling will require modifications to program generation as well.
3. It still won't be as fast as direct copy.

[dvyukov, 2014-08-20 13:19:16]

PTAL

[rsc, 2014-08-20 18:11:22]

On Wed, Aug 20, 2014 at 9:09 AM, <dvyukov@google.com> wrote:

> Here are all types that were unrolled:
>

Thanks very much. From this I would say we should do 32 bytes. That will
handle the vast majority of cases at a very modest storage cost (certainly
only a fraction of the runtime.Type structure). To me, that's much a much
better bound than 4096 or even 512.

Total size of unrolled masks is 1306 bytes. That is the additional
> memory that we would use if we cache all masks.
>
> There are 2 buckets:
> 1. Normal structs with mask size <= 64 bytes.
> 2. Structs with large embed arrays, we have a dozen of them in std lib:
>

#1 seems fine, although from the numbers I think <= 32 is a better cutoff.
Nearly everything seems to be just under that line.

#2 is exactly the kind of thing I don't want to waste space on unrolling.
They're already expensive enough to allocate that it doesn't happen all the
time in efficient programs. I just don't see that they are particularly
important.

Let's set the limit so that it covers 8K of memory, that is a 4k byte
> array + something, or [256][]byte as in byteStringReplacer + something.
> That's 512 bytes of memory per type and any given program allocate only
> a handful of them. So this will consume at most few KB of memory.
>

You're quoting average case. This is a production compiler, so I care about
worst case too, not just average case. That's why I care about locking down
the limit further. 32 bytes seems like you get all the win and the worst
case is not much more space than the type structures already take up.


> I especially don't want to optimize unrolling, because:
> 1. It just does not worth our time taking into account the negligible
> amount of memory that it consumes (we waste orders of magnitude more in
> other places).
>

Being wasteful in some places does not justify being wasteful in another
place. We are actively working on reducing the waste elsewhere. Let's not
compound the problem, especially when we can avoid it easily.


> 2. Fast unrolling will require modifications to program generation as
> well.
>

Yes, that is true. I don't see why that would be a problem.


> 3. It still won't be as fast as direct copy.
>

I don't see why this is necessarily true. For large unrollings, it seems to
me that fast unrolling might be up to 50% memory bandwidth savings compared
to memmove (you're still doing all the writes, but many fewer reads).

I'm willing to spend 32 bytes on a cached unrolled image with the current
unroller. To justify going beyond that we need to squeeze what we can out
of the unroller and measure.

Russ

[dvyukov, 2014-08-21 11:09:25]

Here are types with [33-64] masks in std lib:

56      png.decoder
49      json.Decoder
47      pkix.CertificateList
46      build.Package
45      x509.certificate
43      main.typeConv
42      gzip.Reader
41      xml.Decoder
39      gif.blockReader
39      asn1.Certificate
37      tls.clientHelloMsg
37      map.bucket[http.connectMethodKey][]*http.persistConn
35      x509.tbsCertificateRequest
35      map.bucket[reflect.visit]bool
35      map.bucket[build.osPkg]bool
35      map.bucket[[2]reflect.Type]bool
33      x509.CertificateRequest
33      tls.Config

And here are >64:

4102    lzw.encoder
2575    lzw.decoder
1645    jpeg.decoder
545     flate.decompressor
384     strings.byteStringReplacer
261     strings.stringFinder
165     scanner.Scanner
140     bzip2.reader
137     png.encoder
135     tar.Writer
135     base64.encoder
135     base32.encoder
133     gif.encoder
133     ascii85.decoder
117     base64.decoder
115     main.Package
109     base32.decoder
105     runtime.m
83      tls.Conn
74      gif.decoder
71      x509.tbsCertificate
71      tar.Reader
67      ascii85.encoder
66      x509.Certificate

There are several important names in 33-64 bucket: xml, json, http, tls.

xml.Decoder is 44 and looks like pretty normal fat struct:

type Decoder struct {
        Strict         bool
        AutoClose      []string
        Entity         map[string]string
        CharsetReader  func(charset string, input io.Reader) (io.Reader, error)
        DefaultSpace   string
        r              io.ByteReader
        buf            bytes.Buffer
        saved          *bytes.Buffer
        stk            *stack
        free           *stack
        needClose      bool
        toClose        Name
        nextToken      Token
        nextByte       int
        ns             map[string]string
        err            error
        line           int
        offset         int64
        unmarshalDepth int
}

I am ready to agree on 64.

The memory overhead in this case is O(source_code_size), so the worst case is
under control (to waste another 64 bytes, a user must explicitly write out
another type). But the wasted time is O(number_of_allocations) which is easy to
get very high.

[dvyukov, 2014-08-21 11:11:28]

set maxGCMask to 64
PTAL

[rsc, 2014-08-23 22:57:28]

LGTM

[dvyukov, 2014-08-24 08:04:55]

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

runtime: cache unrolled GC bitmask
Cache unrolled GC bitmask for types up to 64/32K on 64/32-bit systems,
this corresponds to up to 4K cached bitmask.
Perf builders say that 2% of time is spent in
unrollgcproginplace_m/unrollgcprog1
on http benchmark:
http://goperfd.appspot.com/log/f42045f45bf61a0da53b724a7c8567824a0ad6c9

LGTM=rsc
R=golang-codereviews, rsc
CC=golang-codereviews, khr, rlh
https://codereview.appspot.com/122680043

[gobot, 2014-08-24 10:54:59]

This CL appears to have broken the freebsd-amd64-race builder.
See http://build.golang.org/log/41b29b4ea40f7f102f6e75e31bf41e1e655ba695