633690 - add HashMap::lookupWithDefault helper

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Luke Wagner [:luke]]

Right now, we add elements to hash sets/maps like so:

  typedef HashMap<K,V> HS;
  HS &hs = ...
  if (HS::AddPtr p = hs.lookupForAdd(k)) {
     ... = p->value;
  } else {
     hs.add(p, k, v);
     ...
  }

The weird part (if you have not already been desensitized) is that 'p', which looks false-y, is passed to add().  This is an implementation detail that makes its way into the interface; passing the AddPtr 'p' to add() allows add() to avoid a second lookup of 'k'.  Can/should we do better?

Two alternatives come to mind:

1. take away the truthiness (possibly rename AddPtr type)

  HM::AddPtr p = hm.lookupForAdd(k);
  if (p.found()) {
    ... = p->value;
  } else {
    hm.add(p, k, v);
  }

2. separate the hint from the result

  HM::AddHint hint;
  if (HM::Ptr p = hm.lookupForAdd(k, &hint)) {
    ... = p->value;
  } else {
    hm.add(hint, k, v);
  }

(1) is actually rather like the 'hint' versions of certain C++ STL (replacing p != hm.end() with p.found() (down with iterators, long live ranges!)).  Also, it gets rid of the truth-y confusion that bugs Brendan in bug 631951 comment 74.

However, (1) also has this role-confusion between p as a pointer and as an opaque hint-thing passed to add().  So, despite my initial distaste due to its relative verbosity and potential to be a hair slower (if the compiler misses the CSE opportunity), I like (2).  The reason is that it clearly represents what this goofy lookupForAdd operation is doing in the types: it returns a nullable pointer and it fills in some opaque hint that is consumed by add.

Thus, I'd either like to keep things exactly the way they are (which clearly hasn't been too bad, given the uptake of hash map/set) or I'd like to move to (2).

Opinions and alternate APIs welcome.  (Not an immediate concern, just filing since the issue came up.)

Comment 1

[Boris Zbarsky [:bzbarsky]]

For what it's worth, thinking of something as both "a pointer" and "put it here" doesn't seem that odd to me.

Then again, maybe I just have a high API pain tolerance.  :(  The current API seemed ok to me (certainly coming from pldhash and live vs nonlive entry tests and whatnot, though those are more similar to (1) above).

Comment 2

[Brendan Eich [:brendan]]

(In reply to comment #1)
> For what it's worth, thinking of something as both "a pointer" and "put it
> here" doesn't seem that odd to me.

That is not the objection I raised. Try "a falsy-as-if-null pointer"...

/be

Comment 3

[Boris Zbarsky [:bzbarsky]]

> That is not the objection I raised.

Sure; but it was Luke's objection to (1) above.

Comment 4

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Another idea, which makes the common case a little shorter, is to pass the default value to the add method. Then you don't have to pass around any hints.
  if (Ptr p = h.lookupWithDefault(k, v)) {
    p->value++;
  }
If |k| is not found in the table, a new mapping to v would be added and NULL would be returned. Otherwise the usual thing would happen.

This roughly resembles Python's {}.setdefault method.

Comment 5

[Luke Wagner [:luke]]

(In reply to comment #4)
That is almost exactly what the compound-helper-op Hash{Set,Map}::put does, which is built on lookupForAdd.  ("Almost" because HashMap::put overwrites 'p->value' even on hit.)  New compound-helper-ops welcome, though :)

Comment 6

[Brendan Eich [:brendan]]

+1 on lookupWithDefault (or a better name if there is one) -- thanks.

/be

Comment 7

[Luke Wagner [:luke]]

I'm not getting any great interest in changing lookupForAdd, so perhaps keep it as is and add the lookupWithDefault helper Bill suggested?

Comment 8

[Brendan Eich [:brendan]]

Sure.

/be

Comment 9

[Luke Wagner [:luke]]

Attachment: add lookupWithDefault, change code to use it

This adds the lookupWithDefault helper and changes several pre-existing uses of lookupForAdd to use it (good verification of utility!).  While grepping through lookupForAdd uses, I changed a couple to use 'put' as well.

Comment 10

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 521329 [details] [diff] [review]
add lookupWithDefault, change code to use it

Great, this looks nice. We lose the assertion in PropertyTree::insertChild that the shape wasn't already there, though. It's not a big deal, but is there an easy way to fix it?

Comment 11

[Luke Wagner [:luke]]

From IRC: Bill and I agreed to add another 'putNew' helper which was like 'put' except that it asserted previous non-membership.  This also saves a branch for the caller.

Comment 12

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/743a77266bd5

Comment 13

[Chris Leary [:cdleary] (not checking bugmail)]

http://hg.mozilla.org/mozilla-central/rev/743a77266bd5