Closed Bug 517050 Opened 15 years ago Closed 15 years ago

GCHashtable performance issue

Categories

(Tamarin Graveyard :: Virtual Machine, defect, P3)

defect

Tracking

(Not tracked)

VERIFIED FIXED
flash10.1

People

(Reporter: stejohns, Unassigned)

Details

Attachments

(1 file, 1 obsolete file)

Attached patch Patch (obsolete) — 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)
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.
(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.
Attached patch Patch #2Splinter Review
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)
Attachment #401146 - Flags: superreview?(lhansen) → superreview+
pushed in anticipation of tommy's review: changeset:   2509:487374fca2c3
Priority: -- → P3
Target Milestone: --- → flash10.1
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-
I haven't converted that file yet so it's OK with me for now.  (Anyway it's landed already.)
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
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.

Attachment

General

Creator:
Created:
Updated:
Size: