Argument in favor of adding "has" in the WeakMap API

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Argument in favor of adding "has" in the WeakMap API

David Bruant-4
Hi,

I've recently been thinking about the case of memoizing. Let's assume that a function f takes an object o as a parameter and that f is a pure function (results only depends on argument).
----
function f(o){
/* perform a computation, return the result */
}
----

A memoizer could be written to improve f time performance (by the cost of memory, of course).
----
function memoizer(f){
  var cache = WeakMap();
  return function(o){
    var res;

    if(WeakMap.has(o))
      return cache.get(o);
    res = f.apply(this, o);
   
    cache.set(o, res);
  };
}
----
But as you can see, this implementation requires a .has method. harmony:weak_maps shows how to implement has (and delete) on top of "get" and "set", but this comes to the cost of an object per WeakMap (well, actually, the same mascot could be factorized out and used for all ExplicitSoftOwnField) and the cost of being a non-native implementation.

As an argument to add delete to the API, I'd say that it will be an encouragement for people to remove keys from the weak map. In the design of WeakMap is written: "for each mapping k ⇒ v in a reachable weak map m, if k is reachable then v is reachable". If people see that the API is "get+set", they won't think of memory at all, while if they see a "delete" method in the API, they are more likely to wonder why it's here and understand that they should use it to free memory up. This is, of course, nothing else than a guess.

David


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Felix-54
On Wed, May 11, 2011 at 11:16, David Bruant <[hidden email]> wrote:

> A memoizer could be written to improve f time performance (by the cost of
> memory, of course).
> ----
> function memoizer(f){
>   var cache = WeakMap();
>   return function(o){
>     var res;
>     if(WeakMap.has(o))
>       return cache.get(o);
>     res = f.apply(this, o);
>
>     cache.set(o, res);
>   };
> }
> ----

I'm not sure I understand your code.

it's not clear to me why you need .has at all, since you can check the
return value of .get instead.  in the case where 'undefined' is a
valid value that you would want to memoize, you can store a unique
object to represent 'undefined'.

also, memoization is usually caching on argument values rather than
argument identity, but weakmap lookups are by object identity not
object value.  You can't use non-object keys in a weekmap, so in order
to gain the benefits of the memoization above, a caller would have to
be careful to avoid constructing new objects with the same values, and
somehow keep re-using the same argument objects, which is pretty
inconvenient for typical uses of memoization.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Mark S. Miller-2
In reply to this post by David Bruant-4


On Wed, May 11, 2011 at 11:16 AM, David Bruant <[hidden email]> wrote:
Hi,

I've recently been thinking about the case of memoizing. Let's assume that a function f takes an object o as a parameter and that f is a pure function (results only depends on argument).
----
function f(o){
/* perform a computation, return the result */
}
----

A memoizer could be written to improve f time performance (by the cost of memory, of course).
----
function memoizer(f){
  var cache = WeakMap();
  return function(o){
    var res;

    if(WeakMap.has(o))
      return cache.get(o);
    res = f.apply(this, o);
   
    cache.set(o, res);
  };
}
----
But as you can see, this implementation requires a .has method. harmony:weak_maps shows how to implement has (and delete) on top of "get" and "set", but this comes to the cost of an object per WeakMap (well, actually, the same mascot could be factorized out and used for all ExplicitSoftOwnField) and the cost of being a non-native implementation.

As an argument to add delete to the API, I'd say that it will be an encouragement for people to remove keys from the weak map. In the design of WeakMap is written: "for each mapping k ⇒ v in a reachable weak map m, if k is reachable then v is reachable". If people see that the API is "get+set", they won't think of memory at all, while if they see a "delete" method in the API, they are more likely to wonder why it's here and understand that they should use it to free memory up. This is, of course, nothing else than a guess.

After offline conversations with Andreas Gal and Dave Herman, we've changed the WeakMaps API we'd like to propose for Harmony to match approximately what Andreas has already implemented for FF6.0a1 (Nightly). This moves the methods up to WeakMap.prototype approximately as Arv suggested in his comments on the current proposal page. It hangs the WeakMap state off of internal [[???]] properties of WeakMap instances which only these methods can access. And it adds "has" and "delete" methods, making the base abstraction more like the pattern explained at <http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#explicit_soft_own_fields>. Since WeakMaps are already accepted for ES-next, and since the upcoming May meeting is already overloaded with strawmen under consideration, this discussion about WeakMap API changes can wait till the July mtg. Of course, we can begin discussion on the list now.

More later.

 

David


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss




--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

David Bruant-4
In reply to this post by Felix-54
Le 11/05/2011 20:38, felix a écrit :

> On Wed, May 11, 2011 at 11:16, David Bruant <[hidden email]> wrote:
>> A memoizer could be written to improve f time performance (by the cost of
>> memory, of course).
>> ----
>> function memoizer(f){
>>   var cache = WeakMap();
>>   return function(o){
>>     var res;
>>     if(WeakMap.has(o))
>>       return cache.get(o);
>>     res = f.apply(this, o);
>>
>>     cache.set(o, res);
>>   };
>> }
>> ----
> I'm not sure I understand your code.
>
> it's not clear to me why you need .has at all, since you can check the
> return value of .get instead.  in the case where 'undefined' is a
> valid value that you would want to memoize, you can store a unique
> object to represent 'undefined'.
The ambiguity of "get" returning "undefined" when the key is actually
undefined or when it is defined but its value is "undefined" already
happened with objects. The solution to that was the "in" operator (or
Object.prototype.hasOwnProperty depending on cases). I'm just asking an
equivalent for weak maps. I agree its not necessary as proved in
harmony:weak_maps#explicit_soft_own_fields . However, a native
implementation would be a good addition.

> also, memoization is usually caching on argument values rather than
> argument identity,
I consider that the most important word in your sentence is "usually".
Just to clarify, the argument is either a primitive value
(http://es5.github.com/#x4.3.2) or an object. Memoization is usually
caching on primitive value. Caching on objects could have been an idea,
but it would have created a (potentially big) memory leak and lookup
would have been linear. Now, with WeakMap, memoizing on objects doesn't
leak memory (the gc comes to clean the weak map for you!) and lookup is
handled by the engine which means it is at worst O(log(n)) and certainly
constant and small in practice.

> but weakmap lookups are by object identity not
> object value.  You can't use non-object keys in a weekmap, so in order
> to gain the benefits of the memoization above, a caller would have to
> be careful to avoid constructing new objects with the same values, and
> somehow keep re-using the same argument objects, which is pretty
> inconvenient for typical uses of memoization.
So you say. I'd like a proof of that statement. Anyway, I am not saying
that object-based memoization will solve all problems. But if people
have a use case for it, why not. Once again, above you said "usually";
we are so used to not have these kinds of things (WeakMaps, maybe other
features) that we've found workaround over the years. It may be time to
question these choices in our library/applications and see if weak maps
aren't a good fit now that we have them (or are about to).


Regardless, if people want to use object-identity-based memoization and
it forces them to think of their object instanciations more carefully
than creating new objects all the time, then I see this as a benefit,
not a problem.

"Reusing when possible instead of creating new things to serve the same
purpose". Sounds like I want to save the planet from consumerism :-)

David
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Oliver Hunt-2

On May 11, 2011, at 12:38 PM, David Bruant wrote:

> Le 11/05/2011 20:38, felix a écrit :
>> On Wed, May 11, 2011 at 11:16, David Bruant <[hidden email]> wrote:
>>> A memoizer could be written to improve f time performance (by the cost of
>>> memory, of course).
>>> ----
>>> function memoizer(f){
>>>  var cache = WeakMap();
>>>  return function(o){
>>>    var res;
>>>    if(WeakMap.has(o))
>>>      return cache.get(o);
>>>    res = f.apply(this, o);
>>>
>>>    cache.set(o, res);
>>>  };
>>> }
>>> ----
>> I'm not sure I understand your code.
>>
>> it's not clear to me why you need .has at all, since you can check the
>> return value of .get instead.  in the case where 'undefined' is a
>> valid value that you would want to memoize, you can store a unique
>> object to represent 'undefined'.
> The ambiguity of "get" returning "undefined" when the key is actually
> undefined or when it is defined but its value is "undefined" already
> happened with objects. The solution to that was the "in" operator (or
> Object.prototype.hasOwnProperty depending on cases). I'm just asking an
> equivalent for weak maps. I agree its not necessary as proved in
> harmony:weak_maps#explicit_soft_own_fields . However, a native
> implementation would be a good addition.

So you want to do
if (map.has(bar))
   wiffle = map.get(bar)

or some such?

The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.

GC is (from the language's perspective) non-deterministic, so any non-atomic operation with a weak map leads to "non-sensical" behaviour.

--Oliver

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Brendan Eich-3
On May 11, 2011, at 12:44 PM, Oliver Hunt wrote:

> So you want to do
> if (map.has(bar))
>   wiffle = map.get(bar)
>
> or some such?
>
> The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.

Not if bar refers to the key object, since it must be a strong ref.

If you do

  if (map.has(bar)) {
    bar = null;
    // might GC here, or do stuff that might
    wiffle = map.get(bar);
    . . .
  }

then you get what you deserve.


> GC is (from the language's perspective) non-deterministic, so any non-atomic operation with a weak map leads to "non-sensical" behaviour.

True, but this does not apply to

  if (map.has(bar))
    wiffle = map.get(bar);

as written.

/be
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Oliver Hunt-2

On May 11, 2011, at 12:54 PM, Brendan Eich wrote:

> On May 11, 2011, at 12:44 PM, Oliver Hunt wrote:
>
>> So you want to do
>> if (map.has(bar))
>>  wiffle = map.get(bar)
>>
>> or some such?
>>
>> The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.
>
> Not if bar refers to the key object, since it must be a strong ref.

Re-reading the weakmap definition makes weakmaps seem fundamentally different to any other weakmap API i've ever encountered.  The most common weakmap use cases i am aware of are all essentially caches, and this definition doesn't support that use case at all.

It seems completely bizarre to me that the key should act as a root for the value it is associated with.

--Oliver


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

David Bruant-4
In reply to this post by Brendan Eich-3
Le 11/05/2011 21:54, Brendan Eich a écrit :

> On May 11, 2011, at 12:44 PM, Oliver Hunt wrote:
>
>> So you want to do
>> if (map.has(bar))
>>   wiffle = map.get(bar)
>>
>> or some such?
>>
>> The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.
> Not if bar refers to the key object, since it must be a strong ref.
>
> If you do
>
>   if (map.has(bar)) {
>     bar = null;
>     // might GC here, or do stuff that might
>     wiffle = map.get(bar);
>     . . .
>   }
>
> then you get what you deserve.
>
>
>> GC is (from the language's perspective) non-deterministic, so any non-atomic operation with a weak map leads to "non-sensical" behaviour.
> True, but this does not apply to
>
>   if (map.has(bar))
>     wiffle = map.get(bar);
>
> as written.
Exactly. Said in another way, if you are able to call map.has(bar),
then, you hold a reference to bar, so the garbage collector cannot
consider collecting the object which bar references to (by definition of
"holding a reference").

As a side note, I didn't receive initial Olivier Hunt's e-mail. It
appears on es-discuss archive, but I didn't receive it. I am under the
impression that it's not the first time this happens to me. Am I the
only one in that case?

David
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Brendan Eich-3
In reply to this post by Oliver Hunt-2
On May 11, 2011, at 1:04 PM, Oliver Hunt wrote:

> On May 11, 2011, at 12:54 PM, Brendan Eich wrote:
>
>> On May 11, 2011, at 12:44 PM, Oliver Hunt wrote:
>>
>>> So you want to do
>>> if (map.has(bar))
>>> wiffle = map.get(bar)
>>>
>>> or some such?
>>>
>>> The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.
>>
>> Not if bar refers to the key object, since it must be a strong ref.
>
> Re-reading the weakmap definition makes weakmaps seem fundamentally different to any other weakmap API i've ever encountered.  The most common weakmap use cases i am aware of are all essentially caches, and this definition doesn't support that use case at all.

WeakMap is useful for caching. You just have to kill your strong refs if you don't want to hit the cache.


> It seems completely bizarre to me that the key should act as a root for the value it is associated with.

You must be assuming key is a "weak pointer" that magically gets nulled when the GC runs and finds only the variable named key and the map entry referencing (weakly) the key object. But there is no such notion, because we do not want to leak the non-determistic GC schedule by allowing users to poll for null.

/be
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

David Bruant-4
In reply to this post by Oliver Hunt-2
False alarm. I have finally (just) received the e-mail.

David

Le 11/05/2011 21:44, Oliver Hunt a écrit :

> On May 11, 2011, at 12:38 PM, David Bruant wrote:
>
>> Le 11/05/2011 20:38, felix a écrit :
>>> On Wed, May 11, 2011 at 11:16, David Bruant <[hidden email]> wrote:
>>>> A memoizer could be written to improve f time performance (by the cost of
>>>> memory, of course).
>>>> ----
>>>> function memoizer(f){
>>>>  var cache = WeakMap();
>>>>  return function(o){
>>>>    var res;
>>>>    if(WeakMap.has(o))
>>>>      return cache.get(o);
>>>>    res = f.apply(this, o);
>>>>
>>>>    cache.set(o, res);
>>>>  };
>>>> }
>>>> ----
>>> I'm not sure I understand your code.
>>>
>>> it's not clear to me why you need .has at all, since you can check the
>>> return value of .get instead.  in the case where 'undefined' is a
>>> valid value that you would want to memoize, you can store a unique
>>> object to represent 'undefined'.
>> The ambiguity of "get" returning "undefined" when the key is actually
>> undefined or when it is defined but its value is "undefined" already
>> happened with objects. The solution to that was the "in" operator (or
>> Object.prototype.hasOwnProperty depending on cases). I'm just asking an
>> equivalent for weak maps. I agree its not necessary as proved in
>> harmony:weak_maps#explicit_soft_own_fields . However, a native
>> implementation would be a good addition.
> So you want to do
> if (map.has(bar))
>    wiffle = map.get(bar)
>
> or some such?
>
> The problem here is that you can't guarantee that GC won't happen between those two calls, and therefore you could still end up getting undefined in response to the get.
>
> GC is (from the language's perspective) non-deterministic, so any non-atomic operation with a weak map leads to "non-sensical" behaviour.
>
> --Oliver
>

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Mike Samuel
In reply to this post by David Bruant-4
2011/5/11 David Bruant <[hidden email]>:

> Hi,
>
> I've recently been thinking about the case of memoizing. Let's assume that a
> function f takes an object o as a parameter and that f is a pure function
> (results only depends on argument).
> ----
> function f(o){
> /* perform a computation, return the result */
> }
> ----
>
> A memoizer could be written to improve f time performance (by the cost of
> memory, of course).
> ----
> function memoizer(f){
>   var cache = WeakMap();
>   return function(o){
>     var res;
>     if(WeakMap.has(o))
>       return cache.get(o);
>     res = f.apply(this, o);
>
>     cache.set(o, res);
>   };
> }

Does this do what you were trying to accomplish with has, but without
requiring has?

function memoizer(f){
  var cache = WeakMap();
  // Used in cache to distinguish undefined value but known from
  // undefined.  Does not escape, so cannot be returned by f.
  var undefSubstitute = {};
  return function(o){
    var res = cache.get(o);
    if (res === void 0) {
      res = f.apply(this, o);
      cache.set(o, res === void 0 ? undefSubstitute : res);
    } else if (res === undefSubstitute) {
      res = void 0;
    }
    return res;
  };
}




> ----
> But as you can see, this implementation requires a .has method.
> harmony:weak_maps shows how to implement has (and delete) on top of "get"
> and "set", but this comes to the cost of an object per WeakMap (well,
> actually, the same mascot could be factorized out and used for all
> ExplicitSoftOwnField) and the cost of being a non-native implementation.
>
> As an argument to add delete to the API, I'd say that it will be an
> encouragement for people to remove keys from the weak map. In the design of
> WeakMap is written: "for each mapping k ⇒ v in a reachable weak map m, if k
> is reachable then v is reachable". If people see that the API is "get+set",
> they won't think of memory at all, while if they see a "delete" method in
> the API, they are more likely to wonder why it's here and understand that
> they should use it to free memory up. This is, of course, nothing else than
> a guess.
>
> David
>
>
> _______________________________________________
> es-discuss mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/es-discuss
>
>
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

David Bruant-4
Le 13/05/2011 01:19, Mike Samuel a écrit :

> 2011/5/11 David Bruant <[hidden email]>:
>> Hi,
>>
>> I've recently been thinking about the case of memoizing. Let's assume that a
>> function f takes an object o as a parameter and that f is a pure function
>> (results only depends on argument).
>> ----
>> function f(o){
>> /* perform a computation, return the result */
>> }
>> ----
>>
>> A memoizer could be written to improve f time performance (by the cost of
>> memory, of course).
>> ----
>> function memoizer(f){
>>   var cache = WeakMap();
>>   return function(o){
>>     var res;
>>     if(WeakMap.has(o))
>>       return cache.get(o);
>>     res = f.apply(this, o);
>>
>>     cache.set(o, res);
>>   };
>> }
> Does this do what you were trying to accomplish with has, but without
> requiring has?
Yes, I'm sorry, I shouldn't have used the word "require".
Your example does work. It is some derivation of what can be found at
http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps&s=weakmap#explicit_soft_own_fields
I get that neither "has" nor "delete" are required, as proves the above
link and your example. Still, I'm confident that the engine would be a
better place to handle it and my point was that there are some use cases
that may do "heavy" usage of a ".has" method on weak maps which in my
opinion is an argument in favor of adding "has" in the WeakMap API.
It turns out, it seems to already be the plan as wrote Mark Miller in a
previous e-mail. The wiki just cannot be updated yet, before consensus
is reached during a TC-39 meeting.

David
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Argument in favor of adding "has" in the WeakMap API

Mark S. Miller-2


On Thu, May 12, 2011 at 4:29 PM, David Bruant <[hidden email]> wrote:
Le 13/05/2011 01:19, Mike Samuel a écrit :
> 2011/5/11 David Bruant <[hidden email]>:
>> Hi,
>>
>> I've recently been thinking about the case of memoizing. Let's assume that a
>> function f takes an object o as a parameter and that f is a pure function
>> (results only depends on argument).
>> ----
>> function f(o){
>> /* perform a computation, return the result */
>> }
>> ----
>>
>> A memoizer could be written to improve f time performance (by the cost of
>> memory, of course).
>> ----
>> function memoizer(f){
>>   var cache = WeakMap();
>>   return function(o){
>>     var res;
>>     if(WeakMap.has(o))
>>       return cache.get(o);
>>     res = f.apply(this, o);
>>
>>     cache.set(o, res);
>>   };
>> }
> Does this do what you were trying to accomplish with has, but without
> requiring has?
Yes, I'm sorry, I shouldn't have used the word "require".
Your example does work. It is some derivation of what can be found at
http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps&s=weakmap#explicit_soft_own_fields
I get that neither "has" nor "delete" are required, as proves the above
link and your example. Still, I'm confident that the engine would be a
better place to handle it and my point was that there are some use cases
that may do "heavy" usage of a ".has" method on weak maps which in my
opinion is an argument in favor of adding "has" in the WeakMap API.
It turns out, it seems to already be the plan as wrote Mark Miller in a
previous e-mail. The wiki just cannot be updated yet, before consensus
is reached during a TC-39 meeting.

I am planning to update the wiki to reflect what I expect to propose in July[1], which includes "has", but I won't get to it till well after the May meeting. When I do get to it, I will revisit this thread, so don't wait on my updates to discuss this here.


[1] Which is approx what Andreas Gal already implemented and is shipping in FF6.0a1 Nightly.
 

David
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss