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)
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.
Created attachment 401146 [details] [diff] [review] Patch #2 Revised version of first patch, correcting flaw that Edwin pointed out.
Attachment #401146 - Flags: superreview?(lhansen) → superreview+
pushed in anticipation of tommy's review: changeset: 2509:487374fca2c3
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
Last Resolved: 9 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.