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

RESOLVED FIXED in Firefox 55

Status

()

enhancement
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: dbaron, Assigned: dbaron)

Tracking

(Blocks 1 bug)

unspecified
mozilla55
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(1 attachment)

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
Attachment #8853816 - Flags: review?(n.nethercote) → review+
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.
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
Flags: needinfo?(dbaron)
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
https://hg.mozilla.org/mozilla-central/rev/e4ac2148c920
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
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.
Status: RESOLVED → REOPENED
Flags: needinfo?(dbaron)
Resolution: FIXED → ---
Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/705f18f41c8e
Target Milestone: mozilla55 → ---
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
https://hg.mozilla.org/mozilla-central/rev/d8c7a5c7cb77
Status: REOPENED → RESOLVED
Closed: 2 years ago2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Flags: needinfo?(dbaron)
You need to log in before you can comment on or make changes to this bug.