sync: add Pool type

[bradfitz]

Many Go programs and packages try to reuse memory either for locality reasons or to
reduce GC pressure:

pkg/regexp: pool of available threads

pkg/net/http: wants to reuse a lot and has TODOs, but has resisted the temptation so far

pkg/fmt: print.go's var ppFree = newCache(func() interface{} { return new(pp) })

pkg/io: for the 32 KB copy buffers; see discussion at
https://golang.org/cl/7206048/ (which spawned this bug).  These buffers showed
up in dl.google.com profiles.  Lot of things in the Go standard library use io.Copy, so
this can't be fixed by caller code.

pkg/io/ioutil: see
https://code.google.com/p/go/source/browse/src/pkg/io/ioutil/blackhole.go for reusing
the Discard buffers

dl.google.com: was allocating hundreds of MB/s, causing lots of GCs, until we added a
google-internal (for now) []byte pool reuse library, with an API like:

    package pool
    func NewBytePool(...opts...) *BytePool
    func (*BytePool) Alloc(n int) []byte
    func (*BytePool) Free(buf []byte)

There are two distinct but related uses:

    * reusing small-ish structs (like regexp, fmt)
    * reusing bigger []byte (io, ioutil, dl.google.com)

The former would benefit more from a per-m cache. Dmitry and Russ had some thoughts
towards this.  With big []byte, per-m doesn't matter as much, but you do care about
things not being able to burst to some threshold (yet not retain memory for too long
unnecessarily) and grouping things into size classes (i.e. a "user-space"
tcmalloc) when the sizes differ.

The question:

Do we make a new package or facility to promote this pattern?

The status quo is that it keeps being reimplemented in each package privately, and
poorly.  It'd be nice to have a good implementation that everybody could reuse.

Almost all uses are beyond what I believe are reasonable with static liveness/escape
analysis.  This isn't a GC problem, because by the time the GC's involved, it's too late
and we've already allocated too much.  This is about allocating less and reusing memory
when caller code knows it's no longer needed.

[rsc]

Comment 1:

Labels changed: added priority-later, go1.1maybe, removed priority-triage, go1.1.

Status changed to Thinking.

[gopherbot]

Comment 2 by jgrahamc:

I would like this very much. In one project at CloudFlare I have implemented some code
to recycle []byte buffers which are used to hold web pages. These were being allocated
and released to the GC for cleanup. We now have a small package that accepts them back
on a channel and maintains a list in a goroutine of available buffers. Anyone needing a
buffer just receives on a channel and gets the next item from the list or a new buffer
if none are available.
The code also keeps track of the size of the list discarding buffers if it looks like
there are 'too many'. The idea being that we don't keep buffers that were allocated
during a burst of activity.

[dvyukov]

Comment 3:

What you are proposing is essentially to provide free() function. That's the easiest and
the most efficient way to implement your interface :)
Another option is to provide generic pool for interface{}:
type Pool struct {...}
func (p *Pool) Get() interface{}
func (p *Pool) Put(res interface{}) bool
func (p *Pool) Drain() []interface{}
func (p *Pool) SetCapacity(global, local int)
And then if the buffer sizes have some reasonable limits, then one can have, say, 16
pools for blocks of size 4k, 8k, 12k, ..., 64k, and manually choose the right one. Brad,
would it suffice dl.google.com server?
The idea behind SetCapacity(global, local int) is that you can set local=0, and then it
will be a slower pool for expensive resources.
Yes, the fast version with local cache would benefit greatly from per-m caches.

[dvyukov]

Comment 4:

I've prototyped a sync.Cache component, but now I think that sync.Pool would be a better
name. Because there are LRU/timed/key-addressed/etc caches, so Cache will be a confusing
name.

[dvyukov]

Comment 5:

I think it will be useful. Even not particularly concurrent packages like fmt/io would
benefit. And caches in http/rpc will become bottlenecks when we optimize other
bottlenecks and got more cores.

[bradfitz]

Comment 6:

> And then if the buffer sizes have some reasonable limits, then one can have,
> say, 16 pools for blocks of size 4k, 8k, 12k, ..., 64k, and manually choose 
> the right one. Brad, would it suffice dl.google.com server?
I think asking for and freeing n bytes is common enough that it should be first-class. 
We shouldn't make people create their own set of ever size class []byte.

[dvyukov]

Comment 7:

The function for asking for n bytes is already there -- make([]byte, n), the function
for freeing n bytes was removed -- runtime.Free().

[bradfitz]

Comment 8:

The problem with runtime.Free is that using it incorrectly from buggy package A affects
not-buggy package B.
With my NewBytePool proposal as implemented for dl.google.com, the byte pools are owned
by whoever made them.
But for everything needing []byte that I care about right now (io Copy buffers, ioutil
Discard buffers, and dl.google.com buffers), they're all fixed size.  So I'm fine
ignoring variably-sized []byte allocation pools and not muddling this discussion.
Pools of interface{} works for me.

[rsc]

Comment 9:

This bug is about sync.Cache, a cache of interchangeable fixed-size items.
The idea is that a sync.Cache might replace fmt's internal cache, and it
might be used for a cache of fixed-size buffers for io.Copy. A cache of
non-fixed-size items such as variable-length byte slices is quite a bit
more complicated.

[robpike]

Comment 10:

Labels changed: removed go1.1maybe.

[dvyukov]

Comment 11:

I have a preliminary version of sync.Cache based on proc-local data:
https://golang.org/cl/7686043/
And here it is applied to fmt:
https://golang.org/cl/7637047
benchmark                         old ns/op    new ns/op    delta
BenchmarkSprintfInt                     363          368   +1.38%
BenchmarkSprintfInt-2                   457          249  -45.51%
BenchmarkSprintfInt-4                   850          142  -83.29%
BenchmarkSprintfInt-8                  1220           78  -93.61%
BenchmarkSprintfInt-16                 1226           58  -95.22%
BenchmarkManyArgs                      2233         2296   +2.82%
BenchmarkManyArgs-2                    1255         1316   +4.86%
BenchmarkManyArgs-4                    1250          714  -42.88%
BenchmarkManyArgs-8                    1100          429  -61.00%
BenchmarkManyArgs-16                   1528          361  -76.37%

[rsc]

Comment 12:

I think it's too late to add this in Go 1.1. Too much in the runtime is still in flux.

[bradfitz]

Comment 13:

Pretty please? :) The runtime part looks relatively tiny:
https://golang.org/cl/7686043/diff/6001/src/pkg/runtime/proc.c

[rsc]

Comment 14:

Make all the other runtime churn stop, and then we can negotiate. :-)

[alberts]

Comment 15:

If you put this in, we promise to test it hard in the next few weeks.