Closed
Bug 1352888
Opened 7 years ago
Closed 7 years ago
Don't set the collision flag when adding to PLDHashTable if we've already found the entry we're going to add
Categories
(Core :: XPCOM, enhancement)
Core
XPCOM
Tracking
()
RESOLVED
FIXED
mozilla55
Tracking | Status | |
---|---|---|
firefox55 | --- | fixed |
People
(Reporter: dbaron, Assigned: dbaron)
References
(Blocks 1 open bug)
Details
Attachments
(1 file)
2.93 KB,
patch
|
n.nethercote
:
review+
|
Details | Diff | Splinter Review |
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
Assignee | ||
Comment 1•7 years ago
|
||
Attachment #8853816 -
Flags: review?(n.nethercote)
Updated•7 years ago
|
Attachment #8853816 -
Flags: review?(n.nethercote) → review+
Assignee | ||
Comment 2•7 years ago
|
||
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•7 years ago
|
||
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.
Assignee | ||
Comment 4•7 years ago
|
||
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•7 years ago
|
||
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
Flags: needinfo?(dbaron)
Backout by cbook@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/0cdde80fed22 Backed out changeset 8f8e8cd713ad
Assignee | ||
Updated•7 years ago
|
Blocks: FastReflows
Assignee | ||
Updated•7 years ago
|
Flags: needinfo?(dbaron)
Assignee | ||
Comment 7•7 years ago
|
||
https://treeherder.mozilla.org/#/jobs?repo=try&revision=50f3c56e5af5be0e01c02a67496ae5da91f7a8ac&group_state=expanded looks pretty green (though not *quite* done yet).
Assignee | ||
Comment 8•7 years ago
|
||
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•7 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/e4ac2148c920
Status: ASSIGNED → RESOLVED
Closed: 7 years ago
status-firefox55:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Assignee | ||
Comment 10•7 years ago
|
||
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.
Assignee | ||
Updated•7 years ago
|
Status: RESOLVED → REOPENED
Flags: needinfo?(dbaron)
Resolution: FIXED → ---
Comment 11•7 years ago
|
||
Merge of backout: https://hg.mozilla.org/mozilla-central/rev/705f18f41c8e
status-firefox55:
fixed → ---
Target Milestone: mozilla55 → ---
Assignee | ||
Comment 12•7 years ago
|
||
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•7 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/d8c7a5c7cb77
Status: REOPENED → RESOLVED
Closed: 7 years ago → 7 years ago
status-firefox55:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Assignee | ||
Updated•7 years ago
|
Flags: needinfo?(dbaron)
You need to log in
before you can comment on or make changes to this bug.
Description
•