GCHashtable performance issue

VERIFIED FIXED in flash10.1

Status

Tamarin
Virtual Machine
P3
normal
VERIFIED FIXED
9 years ago
9 years ago

People

(Reporter: Steven Johnson, Unassigned)

Tracking

unspecified
flash10.1

Details

Attachments

(1 attachment, 1 obsolete attachment)

7.32 KB, patch
Tommy Reilly
: review-
Lars T Hansen
: superreview+
Details | Diff | Splinter Review
(Reporter)

Description

9 years ago
Created attachment 401086 [details] [diff] [review]
Patch

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

9 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

9 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

9 years ago
Created attachment 401146 [details] [diff] [review]
Patch #2

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

9 years ago
Attachment #401146 - Flags: superreview?(lhansen) → superreview+
(Reporter)

Comment 4

9 years ago
pushed in anticipation of tommy's review: changeset:   2509:487374fca2c3

Updated

9 years ago
Priority: -- → P3
Target Milestone: --- → flash10.1

Comment 5

9 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

9 years ago
I haven't converted that file yet so it's OK with me for now.  (Anyway it's landed already.)

Updated

9 years ago
Status: NEW → RESOLVED
Last Resolved: 9 years ago
Resolution: --- → FIXED

Comment 7

9 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.