code review 9648043: container/alloc: add Cache component

container/alloc: add Cache component
A Cache caches interchangeable objects, two methods -- Put and Take.
Intended for optimization of memory allocation.
The final implementation is intended to use runtime support
to implement per-GOMAXPROC caching.
This implementation simply defines the interface and adds tests.
See the issue for context.
Update issue 4720.

[dvyukov, 2013-05-22 14:17:36]

Hello golang-dev@googlegroups.com,

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

[bradfitz, 2013-05-22 16:14:45]

https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
File src/pkg/container/alloc/cache.go (right):

https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:20: func (c *Cache) Put(v interface{}) {
I'd still like this to return a bool.  If I Put and it returns false, I could
further destroy/recycle sub-objects within v.

https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:24: c.buf = make([]interface{}, 0, 32)
why hard-coding 32? can this be an optional exported field on Cache? 32 could be
the default, if you like it.

https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:29: c.buf = append(c.buf, v)
is this whole method faster than the buffered channel pattern? or just because
you want LIFO?

https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:37: return nil
type Cache struct {
    ...
    New func() interface{}  // optional constructor, for cache misses
}


if c.New != nil {
     return c.New()
}
return nil

[dvyukov, 2013-05-22 16:30:50]

On 2013/05/22 16:14:45, bradfitz wrote:
>
https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
> File src/pkg/container/alloc/cache.go (right):
> 
>
https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:20: func (c *Cache) Put(v interface{}) {
> I'd still like this to return a bool.  If I Put and it returns false, I could
> further destroy/recycle sub-objects within v.
> 
>
https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:24: c.buf = make([]interface{}, 0, 32)
> why hard-coding 32? can this be an optional exported field on Cache? 32 could
be
> the default, if you like it.
> 
>
https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:29: c.buf = append(c.buf, v)
> is this whole method faster than the buffered channel pattern? or just because
> you want LIFO?
> 
>
https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:37: return nil
> type Cache struct {
>     ...
>     New func() interface{}  // optional constructor, for cache misses
> }
> 
> 
> if c.New != nil {
>      return c.New()
> }
> return nil


Please see the CL description:
"The final implementation is intended to use runtime support
to implement per-GOMAXPROC caching.
This implementation simply defines the interface and adds tests."


You have proposed a self-tuning cache because we have too many knobs.
A self-tuning cache will discard excessive elements at unknown points, so the
bool from Put() makes no sense.

32 will go away.

It's not yet faster.

A long time ago (2009) I had interface with both ctor() and dtor() functions:
https://codereview.appspot.com/4850045/diff/3002/src/pkg/co/resourcecache.go
But Russ talked me out of that. All that framework-like inverse-control thing...
it trivial to do outside, right?
v := c.Take()
if v == nil {
  v = New()
}

[bradfitz, 2013-05-22 19:08:21]

I don't know where this is going.

Here's what I want:

* composable pieces, if there are going to be multiple pieces

* not dozens of knobs. (2 integers is too much. 0 is ideal.)

* a high-level interface which lets me say Get() and it gets from cache or
calls a func to create.  fmt's is nice.  I could reimplement this in every
package, but why?  yes, if statements aren't too much work either, but it
means I can't use it in an expression.

* able to know when a Put failed (even if cache items can drop out all the
time silently) so I can do further recycling when I know for sure it's
possible.  I could live without this, but I don't see why not to return it
instead of returning nothing.



On Wed, May 22, 2013 at 9:30 AM, <dvyukov@google.com> wrote:

> On 2013/05/22 16:14:45, bradfitz wrote:
>
> https://codereview.appspot.**com/9648043/diff/5001/src/pkg/**
>
container/alloc/cache.go<https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cache.go>
>
>> File src/pkg/container/alloc/cache.**go (right):
>>
>
>
> https://codereview.appspot.**com/9648043/diff/5001/src/pkg/**
>
container/alloc/cache.go#**newcode20<https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cache.go#newcode20>
>
>> src/pkg/container/alloc/cache.**go:20: func (c *Cache) Put(v
>>
> interface{}) {
>
>> I'd still like this to return a bool.  If I Put and it returns false,
>>
> I could
>
>> further destroy/recycle sub-objects within v.
>>
>
>
> https://codereview.appspot.**com/9648043/diff/5001/src/pkg/**
>
container/alloc/cache.go#**newcode24<https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cache.go#newcode24>
>
>> src/pkg/container/alloc/cache.**go:24: c.buf = make([]interface{}, 0,
>>
> 32)
>
>> why hard-coding 32? can this be an optional exported field on Cache?
>>
> 32 could be
>
>> the default, if you like it.
>>
>
>
> https://codereview.appspot.**com/9648043/diff/5001/src/pkg/**
>
container/alloc/cache.go#**newcode29<https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cache.go#newcode29>
>
>> src/pkg/container/alloc/cache.**go:29: c.buf = append(c.buf, v)
>> is this whole method faster than the buffered channel pattern? or just
>>
> because
>
>> you want LIFO?
>>
>
>
> https://codereview.appspot.**com/9648043/diff/5001/src/pkg/**
>
container/alloc/cache.go#**newcode37<https://codereview.appspot.com/9648043/diff/5001/src/pkg/container/alloc/cache.go#newcode37>
>
>> src/pkg/container/alloc/cache.**go:37: return nil
>> type Cache struct {
>>      ...
>>      New func() interface{}  // optional constructor, for cache misses
>> }
>>
>
>
>  if c.New != nil {
>>       return c.New()
>> }
>> return nil
>>
>
>
> Please see the CL description:
>
> "The final implementation is intended to use runtime support
> to implement per-GOMAXPROC caching.
> This implementation simply defines the interface and adds tests."
>
>
> You have proposed a self-tuning cache because we have too many knobs.
> A self-tuning cache will discard excessive elements at unknown points,
> so the bool from Put() makes no sense.
>
> 32 will go away.
>
> It's not yet faster.
>
> A long time ago (2009) I had interface with both ctor() and dtor()
> functions:
> https://codereview.appspot.**com/4850045/diff/3002/src/pkg/**
>
co/resourcecache.go<https://codereview.appspot.com/4850045/diff/3002/src/pkg/co/resourcecache.go>
> But Russ talked me out of that. All that framework-like inverse-control
> thing... it trivial to do outside, right?
> v := c.Take()
> if v == nil {
>   v = New()
> }
>
>
https://codereview.appspot.**com/9648043/<https://codereview.appspot.com/9648...
>

[dvyukov, 2013-05-22 19:42:51]

On 2013/05/22 19:08:21, bradfitz wrote:
> I don't know where this is going.
> 
> Here's what I want:
> 
> * composable pieces, if there are going to be multiple pieces
> 
> * not dozens of knobs. (2 integers is too much. 0 is ideal.)
> 
> * a high-level interface which lets me say Get() and it gets from cache or
> calls a func to create.  fmt's is nice.  I could reimplement this in every
> package, but why?  yes, if statements aren't too much work either, but it
> means I can't use it in an expression.
> 
> * able to know when a Put failed (even if cache items can drop out all the
> time silently) so I can do further recycling when I know for sure it's
> possible.  I could live without this, but I don't see why not to return it
> instead of returning nothing.


Sounds reasonable.
Done. PTAL.

[bradfitz, 2013-05-22 20:12:00]

https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
File src/pkg/container/alloc/cache.go (right):

https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:16: // If not nil, used to create new
resources.
This isn't a complete sentence.

Go doc style would be more like:

// New optionally specifies a function to create
// new resources on cache miss.
// It may be called from multiple concurrent goroutines
// and must not be changed concurrently with calls to Take.

Also, blank line before.  Or put this first in the struct and put a blank line
before mu.

https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
src/pkg/container/alloc/cache.go:39: // If there are no objects to return and
c.New is not nil, then it returns the result of c.New().
we almost never write parens.

[dvyukov, 2013-05-23 07:31:59]

On 2013/05/22 20:12:00, bradfitz wrote:
>
https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
> File src/pkg/container/alloc/cache.go (right):
> 
>
https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:16: // If not nil, used to create new
> resources.
> This isn't a complete sentence.
> 
> Go doc style would be more like:
> 
> // New optionally specifies a function to create
> // new resources on cache miss.
> // It may be called from multiple concurrent goroutines
> // and must not be changed concurrently with calls to Take.
> 
> Also, blank line before.  Or put this first in the struct and put a blank line
> before mu.
> 
>
https://codereview.appspot.com/9648043/diff/9001/src/pkg/container/alloc/cach...
> src/pkg/container/alloc/cache.go:39: // If there are no objects to return and
> c.New is not nil, then it returns the result of c.New().
> we almost never write parens.

Done. PTAL.
I am happy to replace all comments with your versions :)

[dave_cheney.net, 2013-05-23 07:38:14]

Dmitry, thank you for working on this. Without trying to pour cold water on your
efforts I would not like to see any API that encouraged the use of interface{}
for Put and Take. I know that with the impasse over generics there are few other
options, but I would prefer to not add an API that uses interface{} as that
would prevent us from defining a better API with a generic type later.

[bradfitz, 2013-05-23 07:42:09]

Huh?

What do you propose as an alternative?

Go doesn't have generics.



On Thu, May 23, 2013 at 12:38 AM, <dave@cheney.net> wrote:

> Dmitry, thank you for working on this. Without trying to pour cold water
> on your efforts I would not like to see any API that encouraged the use
> of interface{} for Put and Take. I know that with the impasse over
> generics there are few other options, but I would prefer to not add an
> API that uses interface{} as that would prevent us from defining a
> better API with a generic type later.
>
>
https://codereview.appspot.**com/9648043/<https://codereview.appspot.com/9648...
>

[dave_cheney.net, 2013-05-23 07:45:30]

Yes, I am proposing not doing anything. I know this is not a popular
or useful position.

On Thu, May 23, 2013 at 5:42 PM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Huh?
>
> What do you propose as an alternative?
>
> Go doesn't have generics.
>
>
>
> On Thu, May 23, 2013 at 12:38 AM, <dave@cheney.net> wrote:
>>
>> Dmitry, thank you for working on this. Without trying to pour cold water
>> on your efforts I would not like to see any API that encouraged the use
>> of interface{} for Put and Take. I know that with the impasse over
>> generics there are few other options, but I would prefer to not add an
>> API that uses interface{} as that would prevent us from defining a
>> better API with a generic type later.
>>
>> https://codereview.appspot.com/9648043/
>
>

[dvyukov, 2013-05-23 07:47:20]

It's always possible to wrap it in a particular case, if it's a problem:

type MyCache alloc.Cache
func (c *MyCache) Put(v *Foo) {
  (*alloc.Cache)(c).Put(v)
}
func (c *MyCache) Take() *Foo {
  return (*alloc.Cache)(c).Take().(*Foo)
}


On Thu, May 23, 2013 at 11:42 AM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Huh?
>
> What do you propose as an alternative?
>
> Go doesn't have generics.
>
>
>
> On Thu, May 23, 2013 at 12:38 AM, <dave@cheney.net> wrote:
>>
>> Dmitry, thank you for working on this. Without trying to pour cold water
>> on your efforts I would not like to see any API that encouraged the use
>> of interface{} for Put and Take. I know that with the impasse over
>> generics there are few other options, but I would prefer to not add an
>> API that uses interface{} as that would prevent us from defining a
>> better API with a generic type later.
>>
>> https://codereview.appspot.com/9648043/
>
>

[dsymonds, 2013-05-23 08:38:25]

On Thu, May 23, 2013 at 5:38 PM,  <dave@cheney.net> wrote:

> I know that with the impasse over
> generics there are few other options, but I would prefer to not add an
> API that uses interface{} as that would prevent us from defining a
> better API with a generic type later.

Any form of generics in Go would almost definitely need to wait for
"Go 2", at which point backward compatibility would not constrain us.

[dvyukov, 2013-06-03 09:19:54]

Brad, ping.

[r, 2013-06-03 12:31:59]

just comments on the documentation

i am still undecided about the package itself.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
File src/pkg/container/alloc/cache.go (right):

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:12: // A Cache caches interchangeable objects.
this isn't a very helpful comment.

also this package needs an executable Example

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:20: // and must not be changed concurrently
with calls to Take.
New specifies an optional function to be used to create new entries when the
cache is empty.
It may be ...

what does "changed concurrently" mean?

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:26: // Note that the object still can be
discarded at a later point.
// The object may be deleted by the Cache at any time.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:40: // Take removes and returns one of the
objects previously put into the cache.
Take removes an item from the cache and returns it.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:41: // If there are no objects to return and
c.New is not nil, then it returns the result of c.New.
If the cache is empty and c.New is set, Take returns a new item allocated by
calling c.New.
If the cache is empty and c.New is nil, Take returns nil.

[bradfitz, 2013-06-03 14:04:28]

I don't care to review this more until everybody's in agreement with some
plan.

I don't think that's the case.



On Mon, Jun 3, 2013 at 2:19 AM, <dvyukov@google.com> wrote:

> Brad, ping.
>
>
https://codereview.appspot.**com/9648043/<https://codereview.appspot.com/9648...
>

[dvyukov, 2013-06-03 14:32:18]

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
File src/pkg/container/alloc/cache.go (right):

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:12: // A Cache caches interchangeable objects.
On 2013/06/03 12:31:59, r wrote:
> this isn't a very helpful comment.
> 
> also this package needs an executable Example

Will do if/when we decide on the package itself.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:20: // and must not be changed concurrently
with calls to Take.
On 2013/06/03 12:31:59, r wrote:
> New specifies an optional function to be used to create new entries when the
> cache is empty.
> It may be ...

Done.

> what does "changed concurrently" mean?

A user must not call Take() and concurrently assign a new value to New.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:26: // Note that the object still can be
discarded at a later point.
On 2013/06/03 12:31:59, r wrote:
> // The object may be deleted by the Cache at any time.

Done.

https://codereview.appspot.com/9648043/diff/16001/src/pkg/container/alloc/cac...
src/pkg/container/alloc/cache.go:41: // If there are no objects to return and
c.New is not nil, then it returns the result of c.New.
On 2013/06/03 12:31:59, r wrote:
> If the cache is empty and c.New is set, Take returns a new item allocated by
> calling c.New.
> If the cache is empty and c.New is nil, Take returns nil.

Done.

[rsc, 2013-12-18 20:12:16]

R=close

sync.Pool replaces this.