1371928 - Add nsTHashtable::EnsureInserted/EnsureRemoved methods that indicates whether an existing entry was found

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement, P2)

Description

[Mats Palmgren (inactive)]

I've observed this recurring pattern when removing unnecessary hashtable lookups:

  auto oldCount = hashtable.Count();
  hashtable.RemoveEntry(key);  // or PutEntry
  if (oldCount != hashtable.Count()) {
    // we removed an existing entry  (or inserted a new entry for PutEntry)
    ...
  }

We should pave this cow path with methods to make this more convenient:

  if (hashtable.RemoveEntry(key, nsTHashtable::ReturnTrueIfFound)) {
    ...
  }

or something like that...

Comment 1

[Mats Palmgren (inactive)]

Attachment: Add a new EnsureInserted() method that return true if a new entry was created, and EnsureRemoved() that return true if an existing entry was removed.

I tried a few variations of overloading PutEntry/RemoveEntry but I think
I prefer using new names.  This is to avoid errors like this:

  if (PutEntry(key)) {
    // Code for when we insert a new entry here... oops we used
    // the existing "EntryType* PutEntry(KeyType aKey)" which always
    // return non-null...
  }

Using new names emphasizes the new functionality, and the common
prefix (Ensure) emphasizes the bool return value.

Let me know if you have better ideas...

I'll attach an example use in bug 1371925.

Comment 2

[Mats Palmgren (inactive)]

Alternatively, EnsureRemoved could be implemented as:

auto* entry = GetEntry(aKey)
if (entry) {
  RemoveEntry(entry);
  return true;
}
return false;

I guess that would be a few cycles faster, if we assume GetEntry+RemoveEntry(Entry*)
is exactly what RemoveEntry(Key) would do, which it appears to be currently:
http://searchfox.org/mozilla-central/rev/61054508641ee76f9c49bcf7303ef3cfb6b410d2/xpcom/ds/PLDHashTable.cpp#626-629,631-632,643-644
http://searchfox.org/mozilla-central/rev/61054508641ee76f9c49bcf7303ef3cfb6b410d2/xpcom/ds/PLDHashTable.cpp#530-533

Comment 3

[Nathan Froyd [:froydnj]]

Comment on attachment 8876423 [details] [diff] [review]
Add a new EnsureInserted() method that return true if a new entry was created, and EnsureRemoved() that return true if an existing entry was removed.

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

I like this idea; I'm a little concerned that we are introducing lots of primitives that do *almost* the same thing.  Let's chat about the suggestions below.

::: xpcom/ds/nsTHashtable.h
@@ +171,5 @@
> +   * @return    true if a new entry was created, or false if an existing entry
> +   *            was found
> +   */
> +  MOZ_MUST_USE
> +  bool EnsureInserted(KeyType aKey, EntryType** aEntry = nullptr)

Do we really want to hand out references to the entry here?  For nsBaseHashtable and derivatives, the entry type is a private implementation detail and I think we'd want to hand out some reference to the value instead.

@@ +197,5 @@
> +   * @return    true if an entry was found and removed, or false if no entry
> +   *            was found for aKey
> +   */
> +  MOZ_MUST_USE
> +  bool EnsureRemoved(KeyType aKey)

I think we could legitimately change the original RemoveEntry to return bool; that would be more in line with things like nsTArray::RemoveElement.  It would add overhead to read Count() twice, but I bet we could just change the underlying PLDHashTable methods to return true or false depending on whether something was removed, and propagate that up through the hashtable wrappers.  Then we'd only be adding a single instruction, which seems inexpensive enough.

It does have the downside that RemoveEntry could not be MOZ_MUST_USE, as you have done here.

Comment 4

[Mats Palmgren (inactive)]

(In reply to Nathan Froyd [:froydnj] from comment #3)
> +  bool EnsureInserted(KeyType aKey, EntryType** aEntry = nullptr)

Yes.  It's no different than PutEntry really, only you get to know
if an entry already existed or not.

> For nsBaseHashtable and derivatives, the entry type is a private implementation
> detail and I think we'd want to hand out some reference to the value instead.

Right, I think that is the fundamental flaw that led to these performance
issues.  This is now being corrected by LookupForAdd/LookupRemoveIf.
The other methods are bad for performance when you need to do more than
operation on the entry, which isn't uncommon as we've seen.

But yes, I agree we shouldn't expose these nsTHashtable methods on
the subclasses.  For nsTHashtable though, handing out the EntryType* is
how the rest of its API works so I think it's appropriate here.

> I think we could legitimately change the original RemoveEntry to return
> bool; that would be more in line with things like nsTArray::RemoveElement.

Sure, although I do think we should use a different name than RemoveEntry
to avoid the EntryType*/KeyType overload confusion (bug 1370573).  I've
found ~10 places where authors mistakenly used the KeyType version even
though they had the entry at hand from an earlier GetEntry call.  I wanted
to avoid introducing a similar confusion for PutEntry, i.e. we could add
"bool PutEntry(KeyType aKey, EntryType** aEntry = nullptr)" but then
people might mistakenly write:
  if (PutEntry(key))
    // oops, that call returns an EntryPtr* and is always true
so this is why I chose to use new names, with a common prefix.
Granted, RemoveEntry is void at the moment, so it's not a problem there,
but I think the prefix helps understanding the API:
bool EnsureInserted(KeyType aKey, EntryType** aEntry = nullptr)
bool EnsureRemoved(KeyType aKey)

I don't feel strongly about the names though, as long as we're not
overloading any existing methods like PutEntry/RemoveEntry.  I guess
we could use those names as a prefix, something like:
PutEntryReturnTrueIfCreatedNew
RemoveEntryReturnTrueIfFound
would be clear enough, but they are a bit long...

> Then we'd only be adding a single instruction, which seems
> inexpensive enough.

I ran a micro-benchmark comparing the Count() version and the entry-
null-check version above and I couldn't detect any difference at all.
I also compared with simply "return true" and saw no difference
there either so I don't think we need to worry about performance.
(clang Opt build on Linux64; could be different on other platforms)

Intuitively though, it seems like the null-check version *should* be
faster since PLDHashTable::Remove does that internally, so I'll
update the patch to do that instead.

> It does have the downside that RemoveEntry could not be MOZ_MUST_USE, as you
> have done here.

We might want to drop that on the Remove-operation anyway so that we can
replace the existing RemoveEntry(KeyType) calls with it, and then remove
that confusing method overload.

Comment 5

[Nathan Froyd [:froydnj]]

OK, let's try the Ensure* names and your proposed changes from comment 4, then.

Comment 6

[Mats Palmgren (inactive)]

Attachment: Add a new EnsureInserted() method that return true if a new entry was created, and EnsureRemoved() that return true if an existing entry was removed.

Comment 7

[Nathan Froyd [:froydnj]]

Comment on attachment 8877823 [details] [diff] [review]
Add a new EnsureInserted() method that return true if a new entry was created, and EnsureRemoved() that return true if an existing entry was removed.

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

r=me with the below addressed.

::: xpcom/ds/nsTHashtable.h
@@ +171,5 @@
> +   * @return    true if a new entry was created, or false if an existing entry
> +   *            was found
> +   */
> +  MOZ_MUST_USE
> +  bool EnsureInserted(KeyType aKey, EntryType** aEntry = nullptr)

The nsTHashtable API does indeed return EntryType to external consumers, but I think that derived classes probably shouldn't expose EntryType.  WDYT about having this, but then having nsBaseHashtable::EnsureInserted that simply forwards to this one?  C++ name lookup rules will ensure that nsTHashtable::EnsureInserted isn't visible in subclasses; we can even add commentary to that effect in our wrapper function.

I looked at all of the patches you've posted using EnsureInserted, and AFAICT, none of them use aEntry anyway.

Comment 8

[Mats Palmgren (inactive)]

But nsBaseHashtable inherits nsTHashtable protected so these methods
aren't visible on those classes at all (unless we want to; but I don't
see a reason to do that since Lookup/LookupForAdd fills that role):
http://searchfox.org/mozilla-central/rev/20d16dadd336e0c6b97e3e19dc4ff907744b5734/xpcom/ds/nsBaseHashtable.h#53

Comment 9

[Nathan Froyd [:froydnj]]

Ah, right.  OK, then, commit away!

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3cd8b9859ac2
Add a new EnsureInserted() method that return true if a new entry was created, and EnsureRemoved() that return true if an existing entry was removed.  r=froydnj

Comment 11

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/3cd8b9859ac2