1382097 - High collision rate in ShapeTable::searchUnchecked

Status: RESOLVED INVALID

(Core :: JavaScript Engine, enhancement, P3)

Description

[(no longer active)]

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.

Comment 1

[Jan de Mooij [:jandem]]

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.

Comment 2

[Ted Campbell [:tcampbell]]

Lots of work has been done restructuring Shapes over the years.