412238 - Investigate use of Sparsehash as a replacement for PLDHash

Status: NEW

(Core :: XPCOM, defect)

Description

[Mike Schroepfer]

Bug 406810 shows hashtable operations showing up reasonably high in the profile:

#7 JS_DHashTableOperate
#8 SearchTable
#10 PL_DHashTableOperate
HashString further down

We are pretty sure the profile is causing an unintended GC/CC which you wouldn't see during a normal start up.  But it sparked a thought about replacing and/or updating the hash implementations with something faster and/or more space efficient. 

Obviously a small win in the grand scheme of things so likely not for Gecko 1.9 but wanted to capture the thoughts permanently.

Sparsehash at the URL listed looks promising.  Good place to start would be to run some basic benchmarks on pldhash and spareshash.

Comment 1

[Brendan Eich [:brendan]]

Graydon made this point in email, it deserves mention here:

"I wouldn't be surprised if this tangles up "benign / sane use of hashtables" with "cycle collector use of hashtables". The latter is a decidedly special case, may well benefit from its own container type. Digital tries spring to mind, and/or some sort of locality optimizations. Dbaron already did some, but perhaps more could be done. The graph it builds is *supposed* to be a compact mirror of the XPCOM pointer graph; the structure is not random."

/be

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Though the performance issues in cycle collector's use of pldhash may be common to other users that use pldhash/jsdhash with pointers as keys (never mind plhash/jshash).  (The JS root hash comes to mind, although we're using that much less than we used to.)  It may be useful to figure out a common type to use for generic maps from pointers to structs of which that pointer is a member (on top of which a slightly more specialized map from pointers to other simple types could easily be built).

(I could even imagine the best choice varying between systems with 32-bit and 64-bit pointers.)