1361745 - Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, enhancement)

Description

[(no longer active)]

We can use the API added in bug 1359848 to be a bit smarter here.

Comment 1

[(no longer active)]

Attachment: Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup

Comment 2

[Nika Layzell [:nika] (ni? for response)]

This might be nicer if a convenience method `OrInsert` was added to `EntryPtr` (or perhaps just a method `LookupOrAddDefault` directly on nsClassHashtable).

It would perhaps look something like:

hashTable.LookupForAdd(key).OrInsert(value);
// -- with an overload for closures, which would only be evaluated if the value was missing --
hashTable.LookupForAdd(key).OrInsert([&] () { return value; });

where the OrInsert method would return either the value in the hashTable or the value which was just inserted.

As a LookupOrAddDefault method it would look something like:

hashTable.LookupOrAddDefault(key, value);
// -- with an overload for closures, which would only be evaluated if the value was missing --
hashTable.LookupOrAddDefault(key, [&] () { return value; });

These would simplify this patch, for example, to look like:

 NS_IMETHODIMP
 nsControllerCommandGroup::AddCommandToGroup(const char* aCommand,
                                             const char* aGroup)
 {
   nsDependentCString groupKey(aGroup);
-  nsTArray<nsCString>* commandList = mGroupsHash.Get(groupKey);
-  if (!commandList) {
-    // make this list
-    commandList = new AutoTArray<nsCString, 8>;
-    mGroupsHash.Put(groupKey, commandList);
-  }
+  auto commandList = mGroupsHash.LookupOrAddDefault(groupKey, [] () {
+    return new AutoTArray<nsCString, 8>;
+  });

What do you think about adding a convenience API like this nathan?

Comment 3

[Nathan Froyd [:froydnj]]

I think I like the LookupForAdd().OrInsert([&] {}) version better; the LookupOrAddDefault mixes together too many things in one method for my taste.  So we'd have:

auto commandList = mGroupsHash.LookupForAdd(key).OrInsert([] {
  return new AutoTArray<nsCString, 8>;
});

right?

I'd be fasincated to see the template magic that disambiguates between the single-arg value to insert and the single-arg closure to run to insert something.  We could probably trivially convert the existing LookupOrAdd callsites (and make them more efficient) with this.

Comment 4

[(no longer active)]

(In reply to Nathan Froyd [:froydnj] from comment #3)
> I think I like the LookupForAdd().OrInsert([&] {}) version better; the
> LookupOrAddDefault mixes together too many things in one method for my
> taste.  So we'd have:
> 
> auto commandList = mGroupsHash.LookupForAdd(key).OrInsert([] {
>   return new AutoTArray<nsCString, 8>;
> });
> 
> right?

Not quite.

auto p = mGroupHash.LookupForAdd(key).OrInsert([] {
  return new AutoTArray<nsCString, 8>;
});

nsTArray<nsCString>* commandList = &*p;

(Due to the change happened in bug 1361744)

If that looks good I'll file a follow-up, it should be pretty simple to do it.

> I'd be fasincated to see the template magic that disambiguates between the
> single-arg value to insert and the single-arg closure to run to insert
> something.

Sounds like something that SFINAE should be able to solve (can't it solve all of humanity's problems?)  But I'm not going to be tricked into giving it a shot any time soon myself.  :-)

> We could probably trivially convert the existing LookupOrAdd
> callsites (and make them more efficient) with this.

That seems very valuable indeed, it really sucks that we have at least 3 ways to insert into these hashtables now, it'd be nice to go back to 2 ways.  Sadly I won't have the cycles to do that work myself...

Comment 5

[(no longer active)]

Attachment: Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup

Asking for a quick re-review because I had to change this and now it looks less nice...

Comment 6

[Nathan Froyd [:froydnj]]

The OrInsert method can just return T*, right?  The value contained in the entry, or the value we just inserted that we returned from the lambda.

Comment 7

[Nika Layzell [:nika] (ni? for response)]

(In reply to Nathan Froyd [:froydnj] from comment #6)
> The OrInsert method can just return T*, right?  The value contained in the
> entry, or the value we just inserted that we returned from the lambda.

Yes, I would make OrInsert just directly return the T* value.

My idea behind the OrInsert API came from rust's HashMap::entry() API (https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.entry) which defines a separate `or_insert` and `or_insert_with` method, as rust does not have method overloading.

In this case, to distinguish between the two types, I imagine that you'd use mozilla::EnableIf<mozilla::IsConvertable<T, UserType>> to enable the direct insert method, and the opposite to enable the lambda method. There's probably something else you could use if you wanted, but we could also just always call the lambda, or have a separate OrInsertWith (which avoids some template misery).

Comment 8

[Nika Layzell [:nika] (ni? for response)]

Comment on attachment 8864288 [details] [diff] [review]
Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup

Review of attachment 8864288 [details] [diff] [review]:
-----------------------------------------------------------------

I'm OK (though it is ugly) with this, but if we're going to add OrInsert, then this patch should probably wait and just use that directly.

Comment 9

[(no longer active)]

(In reply to Nathan Froyd [:froydnj] from comment #6)
> The OrInsert method can just return T*, right?  The value contained in the
> entry, or the value we just inserted that we returned from the lambda.

It can, yes.  I'm just trying to figure out what you'd like me to do to avoid rewriting these patches a few more times.  :-)

Do you still want me to keep around nsClassHashtable::Insert() once I add EntryPtr::OrInsert()?

Are you still fine with the rest of the stuff exported on EntryPtr?  Any other changes I should make to the API?

Comment 10

[(no longer active)]

(In reply to Michael Layzell [:mystor] from comment #7)
> In this case, to distinguish between the two types, I imagine that you'd use
> mozilla::EnableIf<mozilla::IsConvertable<T, UserType>> to enable the direct
> insert method, and the opposite to enable the lambda method. There's
> probably something else you could use if you wanted, but we could also just
> always call the lambda, or have a separate OrInsertWith (which avoids some
> template misery).

(I'd rather not be the one to have to deal with that if possible...  That seems like a scope creep that would make this bug not worth fixing)

Comment 11

[Nika Layzell [:nika] (ni? for response)]

Reasonable. I'd just implement the two versions of the method with different names in that case. Seems like the simplest option.

Comment 12

[Nathan Froyd [:froydnj]]

(In reply to :Ehsan Akhgari (super long backlog, slow to respond) from comment #9)
> (In reply to Nathan Froyd [:froydnj] from comment #6)
> > The OrInsert method can just return T*, right?  The value contained in the
> > entry, or the value we just inserted that we returned from the lambda.
> 
> It can, yes.  I'm just trying to figure out what you'd like me to do to
> avoid rewriting these patches a few more times.  :-)

But changing the requirements on you is so much fun! :)

> Do you still want me to keep around nsClassHashtable::Insert() once I add
> EntryPtr::OrInsert()?

No, I think we should just have EntryPtr::OrInsert(), and...

> Are you still fine with the rest of the stuff exported on EntryPtr?  Any
> other changes I should make to the API?

...I'm kind of inclined to remove everything else from EntryPtr once we have OrInsert().  WDYT?

Comment 13

[(no longer active)]

(In reply to Nathan Froyd [:froydnj] from comment #12)
> (In reply to :Ehsan Akhgari (super long backlog, slow to respond) from
> comment #9)
> > (In reply to Nathan Froyd [:froydnj] from comment #6)
> > > The OrInsert method can just return T*, right?  The value contained in the
> > > entry, or the value we just inserted that we returned from the lambda.
> > 
> > It can, yes.  I'm just trying to figure out what you'd like me to do to
> > avoid rewriting these patches a few more times.  :-)
> 
> But changing the requirements on you is so much fun! :)

:D

> > Do you still want me to keep around nsClassHashtable::Insert() once I add
> > EntryPtr::OrInsert()?
> 
> No, I think we should just have EntryPtr::OrInsert(), and...
> 
> > Are you still fine with the rest of the stuff exported on EntryPtr?  Any
> > other changes I should make to the API?
> 
> ...I'm kind of inclined to remove everything else from EntryPtr once we have
> OrInsert().  WDYT?

Removing operator bool() isn't really practical, because sometimes the callers may want to know whether to call OrInsert() or not.  Consider nsPrefBranch::AddObserver() itself, for example, which wants to early return in the middle there.

Removing the rest sounds good.  I wrote the patches here but need to do the surgery to split them up and prepare them for review, and will post them later.

Comment 14

[(no longer active)]

Attachment: Part 1: Improve the nsClassHashtable::LookupForAdd() API

The OrInsert() method adds the new entry to the hashtable if needed, and
returns the newly added entry or the pre-existing one.  It allows for a
more concise syntax at the call site.

Comment 15

[(no longer active)]

Attachment: Part 2: Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup

Comment 16

[Nika Layzell [:nika] (ni? for response)]

Comment on attachment 8865072 [details] [diff] [review]
Part 1: Improve the nsClassHashtable::LookupForAdd() API

Review of attachment 8865072 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/ds/nsClassHashtable.h
@@ +99,5 @@
>        MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
>        return !!mEntry.mData;
>      }
>  
> +    T* OrInsert(const std::function<T*()>& func)

I think this should be a templated function, which will avoid a virtual function call and allocation for the `func` parameter.

template<typename F>
T* OrInsert(F func)
{
  MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
  if (!mEntry.mData) {
    mEntry.mData = func();
  }
  return mEntry.mData;
}

You also won't need the <functional> import if you change this.

Comment 17

[(no longer active)]

Ah yes, good idea!

Comment 18

[(no longer active)]

Attachment: Part 1: Improve the nsClassHashtable::LookupForAdd() API

The OrInsert() method adds the new entry to the hashtable if needed, and
returns the newly added entry or the pre-existing one.  It allows for a
more concise syntax at the call site.

Comment 19

[Nathan Froyd [:froydnj]]

Comment on attachment 8865160 [details] [diff] [review]
Part 1: Improve the nsClassHashtable::LookupForAdd() API

Review of attachment 8865160 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!

::: xpcom/ds/nsClassHashtable.h
@@ +131,1 @@
>     *   }

Can you add another example after this like:

Or, alternatively, if you want to do something with the value in the table:

auto* value = table.LookupForAdd(key).OrInsert(...);

Comment 20

[(no longer active)]

Comment on attachment 8865160 [details] [diff] [review]
Part 1: Improve the nsClassHashtable::LookupForAdd() API

Review of attachment 8865160 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/ds/nsClassHashtable.h
@@ +131,1 @@
>     *   }

This example exists in the comment I added above.

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/d93f890967c0
Part 1: Improve the nsClassHashtable::LookupForAdd() API; r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/00b0dbfee0d6
Part 2: Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup; r=mystor

Comment 22

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/d93f890967c0
https://hg.mozilla.org/mozilla-central/rev/00b0dbfee0d6