Closed Bug 1361745 Opened 3 years ago Closed 3 years ago

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

Categories

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

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: ehsan, Assigned: ehsan)

Details

Attachments

(2 files, 3 obsolete files)

We can use the API added in bug 1359848 to be a bit smarter here.
Attachment #8864175 - Flags: review?(michael) → review+
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?
Flags: needinfo?(nfroyd)
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.
Flags: needinfo?(nfroyd)
(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...
Asking for a quick re-review because I had to change this and now it looks less nice...
Attachment #8864288 - Flags: review?(michael)
Attachment #8864175 - Attachment is obsolete: true
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.
(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 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.
Attachment #8864288 - Flags: review?(michael)
(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?
Flags: needinfo?(nfroyd)
(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)
Reasonable. I'd just implement the two versions of the method with different names in that case. Seems like the simplest option.
(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?
Flags: needinfo?(nfroyd) → needinfo?(ehsan)
(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.
Flags: needinfo?(ehsan)
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.
Attachment #8865072 - Flags: review?(nfroyd)
Attachment #8864288 - Attachment is obsolete: true
Attachment #8865073 - Flags: review?(michael) → review+
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.
Ah yes, good idea!
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.
Attachment #8865160 - Flags: review?(nfroyd)
Attachment #8865072 - Attachment is obsolete: true
Attachment #8865072 - Flags: review?(nfroyd)
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(...);
Attachment #8865160 - Flags: review?(nfroyd) → review+
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.
Pushed by eakhgari@mozilla.com:
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
https://hg.mozilla.org/mozilla-central/rev/d93f890967c0
https://hg.mozilla.org/mozilla-central/rev/00b0dbfee0d6
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.