Closed
Bug 517050
Opened 15 years ago
Closed 15 years ago
GCHashtable performance issue
Categories
(Tamarin Graveyard :: Virtual Machine, defect, P3)
Tamarin Graveyard
Virtual Machine
Tracking
(Not tracked)
VERIFIED
FIXED
flash10.1
People
(Reporter: stejohns, Unassigned)
Details
Attachments
(1 file, 1 obsolete file)
7.32 KB,
patch
|
treilly
:
review-
lhansen
:
superreview+
|
Details | Diff | Splinter Review |
currently, GCHashtable never rehashes itself unless the table needs shrinking, so if the table stays a similar size but there are many insertions/deletions, many hash chains can fill up with DELETED items, causing pathological performance problems. Patch has a simple change which makes a dramatic improvment: allow put() to replace the first DELETED item it finds. In one testcase, this dropped average probe depth from ~74 to ~1. Patch also includes a few other cleanup items: -- uniformly make indices unsigned (except for the nextIndex() call, which relies on it being signed); this allows us to take out the now-pointless masking of the high bit when calculating hash, since it can't go negative -- inline -> REALLY_INLINE -- Iterator::remove was unused, so remove it -- Iterator::ht made volatile to ensure it doesn't get optimized away (see previous bugs re iterators) -- adapt rot-by-3 code in pointer hash (from nanojit) since most pointers we get are 8-aligned)
Attachment #401086 -
Flags: superreview?(lhansen)
Attachment #401086 -
Flags: review?(treilly)
Comment 1•15 years ago
|
||
is that change legal? i could see letting put replace the last DELETED item it finds, but if it replaces the first then it could end up putting duplicate keys into the table.
Reporter | ||
Comment 2•15 years ago
|
||
(In reply to comment #1) > is that change legal? i could see letting put replace the last DELETED item it > finds, but if it replaces the first then it could end up putting duplicate keys > into the table. Eek. Good catch. Let me try smartening it up.
Reporter | ||
Comment 3•15 years ago
|
||
Revised version of first patch, correcting flaw that Edwin pointed out.
Attachment #401086 -
Attachment is obsolete: true
Attachment #401146 -
Flags: superreview?(lhansen)
Attachment #401146 -
Flags: review?(treilly)
Attachment #401086 -
Flags: superreview?(lhansen)
Attachment #401086 -
Flags: review?(treilly)
Updated•15 years ago
|
Attachment #401146 -
Flags: superreview?(lhansen) → superreview+
Reporter | ||
Comment 4•15 years ago
|
||
pushed in anticipation of tommy's review: changeset: 2509:487374fca2c3
Updated•15 years ago
|
Priority: -- → P3
Target Milestone: --- → flash10.1
Comment 5•15 years ago
|
||
Comment on attachment 401146 [details] [diff] [review] Patch #2 I think I'm supposed to reject this and ask for GCHashtable-inlines.h?
Attachment #401146 -
Flags: review?(treilly) → review-
Comment 6•15 years ago
|
||
I haven't converted that file yet so it's OK with me for now. (Anyway it's landed already.)
Updated•15 years ago
|
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
Comment 7•15 years ago
|
||
Resolved fixed engineering / work item that has been pushed. Setting status to verified.
Status: RESOLVED → VERIFIED
You need to log in
before you can comment on or make changes to this bug.
Description
•