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

RESOLVED FIXED in Firefox 55

Status

()

RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: Ehsan, Assigned: Ehsan)

Tracking

unspecified
mozilla55
Points:
---

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(2 attachments, 3 obsolete attachments)

(Assignee)

Description

2 years ago
We can use the API added in bug 1359848 to be a bit smarter here.
(Assignee)

Comment 1

2 years ago
Created attachment 8864175 [details] [diff] [review]
Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup
Attachment #8864175 - Flags: review?(michael)

Updated

2 years ago
Attachment #8864175 - Flags: review?(michael) → review+

Comment 2

2 years ago
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)
(Assignee)

Comment 4

2 years ago
(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...
(Assignee)

Comment 5

2 years ago
Created attachment 8864288 [details] [diff] [review]
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...
Attachment #8864288 - Flags: review?(michael)
(Assignee)

Updated

2 years ago
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.

Comment 7

2 years ago
(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

2 years ago
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)
(Assignee)

Comment 9

2 years ago
(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?
(Assignee)

Updated

2 years ago
Flags: needinfo?(nfroyd)
(Assignee)

Comment 10

2 years ago
(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

2 years ago
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)
(Assignee)

Comment 13

2 years ago
(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)
(Assignee)

Comment 14

2 years ago
Created attachment 8865072 [details] [diff] [review]
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.
Attachment #8865072 - Flags: review?(nfroyd)
(Assignee)

Updated

2 years ago
Attachment #8864288 - Attachment is obsolete: true
(Assignee)

Comment 15

2 years ago
Created attachment 8865073 [details] [diff] [review]
Part 2: Avoid a double hashtable lookup for insertions in nsControllerCommandGroup::AddCommandToGroup
Attachment #8865073 - Flags: review?(michael)

Updated

2 years ago
Attachment #8865073 - Flags: review?(michael) → review+

Comment 16

2 years ago
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.
(Assignee)

Comment 17

2 years ago
Ah yes, good idea!
(Assignee)

Comment 18

2 years ago
Created attachment 8865160 [details] [diff] [review]
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.
Attachment #8865160 - Flags: review?(nfroyd)
(Assignee)

Updated

2 years ago
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+
(Assignee)

Comment 20

2 years ago
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

2 years ago
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

Comment 22

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/d93f890967c0
https://hg.mozilla.org/mozilla-central/rev/00b0dbfee0d6
Status: NEW → RESOLVED
Last Resolved: 2 years ago
status-firefox55: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
You need to log in before you can comment on or make changes to this bug.