High collision rate in ShapeTable::searchUnchecked




2 years ago
2 years ago


(Reporter: Ehsan, Unassigned)


(Blocks 1 bug, {triage-deferred})

Firefox Tracking Flags

(Not tracked)




2 years ago
Bas found that there is high collision rate in ShapeTable::searchUnchecked().  I can verify that, I see lots of time spent in the collision cases in the search function.

From IRC today;

<Bas> ehsan: https://searchfox.org/mozilla-central/source/js/src/vm/Shape-inl.h#227
<ehsan> Bas, thanks
<ehsan> Bas, is there a bug on file for it?
<Bas> ehsan: Nope, I only got to a point where I started to get somewhat actionable info this morning.
<Bas> ehsan: So we spend about 0.8% of a speedometer run in the 3 hash computing lines. But we spend about 0.7% in the function passed line 246 (i.e. the collission case)
<Bas> Well, no, actually 0.6% in the two hash computing lines, and 0.4% in just getting the entry off (which from what I can tell is just the memory access)
<Bas> But together that's 1.7% of all of speedometer.
<Bas> (All this stuff is usually inlined in the NativeProperty lookup functions, fwiw, I just made it so I could see where the time is actually spent)

It would be nice to improve the hashing here.
Maybe interesting to investigate things like table size/capacity and the jsid for the tables with most collisions.

Also it might possible to replace the custom hash table with js::HashMap. A while ago I made it so we can purge ShapeTables on compacting GC, so memory usage is less of a concern now. OTOH Hashmap uses more or less the same algorithm I think so it's not clear if it would do any better.


2 years ago
Depends on: 1382435
Keywords: triage-deferred
Priority: -- → P3
You need to log in before you can comment on or make changes to this bug.