1352888 - Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

PLDHashTable's entry store has two types of unoccupied entries:  free
entries and removed entries.  The search of a chain of entries
(determined by the hash value) in the entry store to search for an entry
can stop at free entries, but it continues across removed entries,
because removed entries are entries that may have been skipped over when
we were adding the value we're searching for to the hash, but have since
been removed.  For live entries, we also maintain this distinction by
using one bit of storage for a collision flag, which notes that if the
hashtable entry is removed, its place in the entry store must become a
removed entry rather than a free entry.

When we add a new entry to the table, Add's semantics require that we
return an existing entry if there is one, and only create a new entry if
no existing entry exists.  (Bug 1352198 suggests the possibility of a
faster alternative Add API where the caller guarantees that the key is
not already in the hashtable.)  When we search for the existing entry,
we must thus continue the search across removed entries, even though we
record the first removed entry found to return if the search for an
existing entry fails.

The existing code adds the collision flag through the entire table
search during an Add.  This patch changes that behavior so that we only
add the collision flag prior to finding the first removed entry.  Adding
it after we find the first removed entry is unnecessary, since we are
not making that entry part of a path to a new entry.  If it is part of a
path to an existing entry, it will already have the collision flag set.

This patch effectively puts an if (!firstRemoved) around the else branch
of the if (MOZ_UNLIKELY(EntryIsRemoved(entry))), and then refactors that
condition outwards since it is now around the contents of both the if
and else branches.

MozReview-Commit-ID: CsXnMYttHVy

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I did a try run:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=9b9959ff44298ddea0e9ae5fd809eba0d99d1ec6&group_state=expanded
but didn't get anything substantive out of perfherder:
https://treeherder.mozilla.org/perf.html#/compare?originalProject=mozilla-central&originalRevision=03d602fd723a&newProject=try&newRevision=9b9959ff44298ddea0e9ae5fd809eba0d99d1ec6&framework=1&filter=linux64%20opt%20e10s&showOnlyImportant=0

Comment 3

[Nicholas Nethercote [inactive]]

If I were analyzing this change I would probably insert some printfs for various cases and then do some post-processing to see if the frequencies of those cases had changed.

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8f8e8cd713ad1d08e756c329b45004fa9cea1946
Bug 1352888 - Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add.  r=njn

Comment 5

[Carsten Book [:Tomcat]]

backed this out in https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=2ba7fac730edb476a51a732011872e95d34d82c8&filter-searchStr=OS+X+10.10+debug+XPCShell+(X) for failing xpcshell tests like https://treeherder.mozilla.org/logviewer.html#?job_id=88513551&repo=mozilla-inbound&lineNumber=7989 even after backout of the other patches.

to keep the tree clear backing out this changes

Comment 6

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/0cdde80fed22
Backed out changeset 8f8e8cd713ad

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=50f3c56e5af5be0e01c02a67496ae5da91f7a8ac&group_state=expanded looks pretty green (though not *quite* done yet).

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e4ac2148c9204c4a61f572b947a9e998b83ccfc9
Bug 1352888 - Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add.  r=njn

Comment 9

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e4ac2148c920

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/705f18f41c8eb994eaa977c82aeb0da639065887
Backed out changeset e4ac2148c920 (bug 1352888) to see if it is responsible for input latency regression bug 1362094.

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/705f18f41c8e

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d8c7a5c7cb77f8fc3527a4b020291b920a7afda2
Bug 1352888 - Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add.  r=njn

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/d8c7a5c7cb77