Closed Bug 1352888 Opened 4 years ago Closed 4 years ago
Don't set the collision flag when adding to PLDHash
Table if we've already found the entry we're going to add
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+
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
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
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
Backout by firstname.lastname@example.org: https://hg.mozilla.org/integration/mozilla-inbound/rev/0cdde80fed22 Backed out changeset 8f8e8cd713ad
https://treeherder.mozilla.org/#/jobs?repo=try&revision=50f3c56e5af5be0e01c02a67496ae5da91f7a8ac&group_state=expanded looks pretty green (though not *quite* done yet).
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/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
Resolution: FIXED → ---
Merge of backout: https://hg.mozilla.org/mozilla-central/rev/705f18f41c8e
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
You need to log in before you can comment on or make changes to this bug.