385809 - (js-memoize) consider switching to Oliver Steele's suggested memoization approach

Status: RESOLVED WONTFIX

(Firefox :: General, enhancement)

Description

[Myk Melez [:myk] [@mykmelez]]

Firefox code does a lot of memoization of nullary methods, especially for frequently-accessed XPCOM components.  Here's an example from the content prefs service:

 48   // Observer Service
 49   __observerSvc: null,
 50   get _observerSvc() {
 51     if (!this.__observerSvc)
 52       this.__observerSvc = Cc["@mozilla.org/observer-service;1"].
 53                            getService(Ci.nsIObserverService);
 54     return this.__observerSvc;
 55   },

But according to Oliver Steele in this blog post <http://osteele.com/archives/2006/04/javascript-memoization>, our typical implementation is naive and has a number of issues:

1. it's verbose;
2. it mixes domain with memoizaton logic;
3. every memoized method requires an additional private property (a memory hit);
4. every memoized method checks if its value has been computed every time it gets called (a performance hit).

Steele suggests an alternate approach that replaces nullary methods with constant functions that return the computed value.  The advantages to this approach are that it is less verbose, requires no additional private properties, and does no call-time checking if the value has been computed.  It does, however, continue to mix domain and memoization logic (Steele suggests alternatives that don't, but those have other drawbacks).

We should consider adopting Steele's suggested approach and switching existing memoized methods to it in our codebase.  One question about XPCOM components that I hope someone more familiar with XPCOM can answer: is there a danger of references to XPCOM components disappearing over time (i.e. in the example above from the content prefs service would the observer service reference ever go away and need to be recomputed)?

Another issue: how can we replace a getter with a constant function, or would we need to switch the getters to regular methods in order to implement Steele's approach?

Comment 1

[Brendan Eich [:brendan]]

Cc'ing sayrer who pointed out osteele's blog on irc the other week, and bsmedberg who can address XPCOM concerns.

You can replace a getter with __defineGetter__ in order to do the same kind of constant function memoization:

js> o = {
  get x(){
    if(this.y == 42)
      this.__defineGetter__('x', function()(print('memoized!',42));
    return this.y},
  y:0
}
[object Object]
js> o.x
0
js> o.y=1
1
js> o.x
1
js> o.y=42
42
js> o.x
42
js> o.x
memoized!
42
js> o.x
memoized!
42
js> o.x
memoized!
42

/be

Comment 2

[Benjamin Smedberg]

I can't think of XPCOM concerns offhand... but combined with getters, I don't see why you need a function after the data has been memoized:

o = {
  get _observerSvc() {
    var obs =
      Cc["@mozilla.org/observer-service;1"].getService(Ci.nsIObserverService);
    delete this._observerSvc;
    return this._observerSvc;
  }
};

Comment 3

[Brendan Eich [:brendan]]

(In reply to comment #2)
> I can't think of XPCOM concerns offhand... but combined with getters, I don't
> see why you need a function after the data has been memoized:
> 
> o = {
>   get _observerSvc() {
>     var obs =
>       Cc["@mozilla.org/observer-service;1"].getService(Ci.nsIObserverService);
>     delete this._observerSvc;
>     return this._observerSvc;
>   }
> };
> 

You don't need a function to replace a getter if you delete first, right (your example seems to be missing a crucial assignment after the delete, tho).

/be

Comment 4

[Myk Melez [:myk] [@mykmelez]]

bsmedberg's approach in comment 2 works fine when the getter is defined in an object literal:

js> var o = {
  get _foo() {
    print("not memoized - should appear only once");
    var foo = 42;

    delete this._foo;
    this._foo = foo;
    return this._foo;
  }
};
js> o._foo + o._foo;
not memoized - should appear only once
84


But it doesn't work when the getter is defined in an object's prototype:

js> function O() {};
js> O.prototype = {
  get _foo() {
    print("not memoized - should appear only once");
    var foo = 42;

    delete this._foo;
    this._foo = foo;
    return this._foo;
  }
};
[object Object]
js> var o = new O();
js> o._foo + o._foo;
not memoized - should appear only once
typein:194: TypeError: setting a property that has only a getter

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> bsmedberg's approach in comment 2 works fine when the getter is defined in an
> object literal:
> 
> js> var o = {
>   get _foo() {
>     print("not memoized - should appear only once");
>     var foo = 42;
> 
>     delete this._foo;
>     this._foo = foo;
>     return this._foo;
>   }
> };
> js> o._foo + o._foo;
> not memoized - should appear only once
> 84

Note that this.hasOwnProperty('_foo') when delete this._foo is evaluated.

> But it doesn't work when the getter is defined in an object's prototype:
> 
> js> function O() {};
> js> O.prototype = {
>   get _foo() {
>     print("not memoized - should appear only once");
>     var foo = 42;
> 
>     delete this._foo;
>     this._foo = foo;
>     return this._foo;
>   }
> };
> [object Object]
> js> var o = new O();
> js> o._foo + o._foo;
> not memoized - should appear only once
> typein:194: TypeError: setting a property that has only a getter

The getter runs with |this| bound to |o|, not to |O.prototype|. So per the fine ECMA spec, delete this._foo does not find a direct ("own") property named '_foo' in this and so stupidly evaluates to true without any effect. The rest follows as night follows day.

For this case, you really do want to shadow the prototype getter with an instance getter (note expression closure below, sweet!):

O.prototype = {
  get _foo() {
    print("not memoized - should appear only once");
    this.__defineGetter__('_foo', function () 42);
    return this._foo;
  }
};

You can't shadow a proto-getter by assigning to an instance property of the same name -- that defeats the purpose of proto-getters and -setters, and so runs into the "setting a property that has only a getter" exception.

/be

Comment 6

[timeless]

I'm sure someone will complain about this code, but hey, why not...

js> function A(){}
js> A.prototype={get x(){return 1;}}
[object Object]
js> a=new A;
[object Object]
js> a.x
1
js> (function (a,x){var proto = a.__proto__; a.__proto__=Object; a.x=x; a.__proto__=proto; return x;})(a, 2)
2
js> a.x
2

Comment 7

[:Gavin Sharp [email: [e-mail]]]

The style from comment 2 is probably most common now, but the style from comment 1 (with Object.defineProperty instead of __defineGetter__) is coming into fashion lately as well. I don't think tree-wide "switching" of existing code is cost-effective.