1371094 - Implement nsBaseHashtable::LookupForAdd

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement, P2)

Description

[Mats Palmgren (inactive)]

I need a LookupForAdd() method to fix some perf issues in mozilla::dom::ImageTracker

Comment 1

[(no longer active)]

Thank you for doing this!

Comment 2

[Mats Palmgren (inactive)]

Attachment: Introduce a nsBaseHashtable::LookupForAdd() method

This is basically a copy of the nsClassHashtable version, but with
two differences:
1. nsClassHashtable treats null values for an existing entry the same
   as a non-existing entry:
http://searchfox.org/mozilla-central/rev/a798ee4fc323f9387b7576dbed177859d29d09b7/xpcom/ds/nsClassHashtable.h#99,106
   We can't do that here since we don't know if UserDataType is a pointer
   type or not.  Instead, I'm checking Count() before and after the call
   to PutEntry() to determine of an entry was added.  I considered adding
   new API to ferry out this state all the way from PLDHashTable, but it
   doesn't seem worth it to me.  Checking Count() should be as fast and
   accurate.

2. I'm adding a Data() method for easy access to the value in the entry.
   This is needed in multiple places, for example in ImageTracker which
   stores a counter that needs to incremented. (see bug 1371095)

I kept nsClassHashtable::LookupForAdd for now since it treats null values
differently.  I don't know if that's intentional though.  If not, we can
remove it and let it inherit this instead.

Comment 3

[Nathan Froyd [:froydnj]]

Comment on attachment 8876105 [details] [diff] [review]
Introduce a nsBaseHashtable::LookupForAdd() method

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

Checking Count() is probably about as fast as you can get; trying to do it inside PLDHashTable would require altering Add() or similar, which we've found to be very perf-sensitive, or adding an entirely new API...  Maybe we could come up with some inventive specialization that would enable us to use null pointer checks (which should be faster) on pointer-like values, and Count() where that's not available?

Can you add a comment in nsClassHashtable::LookupForAdd about why we're keeping that?  And, come to think of it, if we're going to have a separate nsClassHashtable method, why shouldn't we have one for nsRefPtr/InterfaceHashtable, which behave approximately the same way?

Not opposed to adding this at all, I just think there are a couple more things to get nailed down before we commit this.

Comment 4

[Mats Palmgren (inactive)]

> why shouldn't we have one for nsRefPtr/InterfaceHashtable, which behave approximately the same way?

Good point.  I'm starting to think that the current behavior is simply a bug.
I see no reason why LookupForAdd should have different behavior from Get/GetOrInsert etc.
AFIAK, all three of these classes supports inserting nullptr as a value - it's rather odd
that you can't retrieve that value using nsClassHashtable::LookupForAdd.

Let's see if anything breaks by removing it:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=74b5c21c8daa8167f0d15315554bfa331608880f

Comment 5

[Mats Palmgren (inactive)]

Attachment: Move the nsClassHashtable::LookupForAdd() method to nsBaseHashtable

(I also changed nsClassHashtable::LookupOrAdd to make it consistent.)

Comment 6

[Mats Palmgren (inactive)]

Attachment: Move the nsClassHashtable::LookupForAdd() method to nsBaseHashtable

A minor tweak to the assertion in the dtor:
  MOZ_ASSERT(mEntry.mData, "Entry should have been added by now");
because it makes no sense unless mData is a pointer and we use
null to indicate "not set" (which is dubious in the first place).

I added a DEBUG bool instead to track whether OrInsert was called
in the non-existing entry case.

Comment 7

[Nathan Froyd [:froydnj]]

Comment on attachment 8876454 [details] [diff] [review]
Move the nsClassHashtable::LookupForAdd() method to nsBaseHashtable

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

r=me with the below test added somewhere appropriate under xpcom/tests/gtest/.

::: xpcom/ds/nsBaseHashtable.h
@@ +234,5 @@
> +      MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
> +      if (!mExistingEntry) {
> +        mEntry.mData = func();
> +#ifdef DEBUG
> +        mDidInitNewEntry = true;

We should have an explicit test that:

auto e = ht.LookupForAdd(...);
T& t = e.OrInsert(...);
if (!e) {
}

works, i.e. that the boolean-ness of EntryPtr is not tied to stuff being present in the entry or not.  I saw this pattern in a patch that depends on this code and it threw me a little...and it wouldn't be any fun to track down if somebody accidentally changed said behavior.

Comment 8

[Mats Palmgren (inactive)]

Attachment: part 2 - Add some tests for the LookupForAdd/OrInsert/LookupRemoveIf methods

OK, let me know if I missed something.

Comment 9

[Nathan Froyd [:froydnj]]

Comment on attachment 8876806 [details] [diff] [review]
part 2 - Add some tests for the LookupForAdd/OrInsert/LookupRemoveIf methods

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

Thank you!

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/1b01e6d83f2c
part 1 - Move the nsClassHashtable::LookupForAdd() method to nsBaseHashtable.  r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/fb2197af9bfc
part 2 - Add some tests for the LookupForAdd/OrInsert/LookupRemoveIf methods.  r=froydnj

Comment 11

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/1b01e6d83f2c
https://hg.mozilla.org/mozilla-central/rev/fb2197af9bfc