Improve SpiderMonkey hashing functions by using MFBT's HashGeneric more

RESOLVED FIXED in Firefox 56

Status

()

enhancement
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: Ehsan, Assigned: Ehsan)

Tracking

unspecified
mozilla56
Points:
---

Firefox Tracking Flags

(firefox56 fixed)

Details

Attachments

(1 attachment)

There are many places in SpiderMonkey where we attempt to invent hashing functions.  These attempts can go horribly wrong, see bug 1379282 for an example.  It's better to switch these to use MFBT's HashGeneric() facilities.
Comment on attachment 8888025 [details] [diff] [review]
Improve SpiderMonkey hashing functions by using MFBT's HashGeneric more

Review of attachment 8888025 [details] [diff] [review]:
-----------------------------------------------------------------

Another one that's worth fixing, because it's pretty perf-critical: http://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/src/vm/Shape.h#1491

It has this "Accumulate from least to most random so the low bits are most random." comment but it seems a proper hash function should be fine. Note how it starts buggy, converting base from uintptr_t to HashNumber/uint32_t. r=me if you want to rewrite it to something like:

HashNumber hash = mozilla::HashGeneric(base);
... AddToHash calls...

::: js/src/gc/StoreBuffer.h
@@ +340,5 @@
>  
>          typedef struct {
>              typedef SlotsEdge Lookup;
> +            static HashNumber hash(const Lookup& l) {
> +              return mozilla::HashGeneric(l.objectAndKind_, l.start_, l.count_);

Nit: 4 space indent in SpiderMonkey
Attachment #8888025 - Flags: review?(jdemooij) → review+
Actually I just noticed we call ScrambleHashCode in HashTable.h:

http://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/public/Utility.h#510-545

It seems with that in place, calling HashGeneric in the hash() functions won't add much?
Flags: needinfo?(ehsan)
(In reply to Jan de Mooij [:jandem] from comment #3)
> Actually I just noticed we call ScrambleHashCode in HashTable.h:
> 
> http://searchfox.org/mozilla-central/rev/
> 3a3af33f513071ea829debdfbc628caebcdf6996/js/public/Utility.h#510-545
> 
> It seems with that in place, calling HashGeneric in the hash() functions
> won't add much?

See the discussion in bug 1379282 comment 18 onwards.  That isn't an effective way to distribute the bits in the input space randomly over the output space, so it won't address collision issues caused by adjacent memory addresses.
Flags: needinfo?(ehsan)
(In reply to Jan de Mooij [:jandem] from comment #2)
> Another one that's worth fixing, because it's pretty perf-critical:
> http://searchfox.org/mozilla-central/rev/
> 3a3af33f513071ea829debdfbc628caebcdf6996/js/src/vm/Shape.h#1491
> 
> It has this "Accumulate from least to most random so the low bits are most
> random." comment but it seems a proper hash function should be fine. Note
> how it starts buggy, converting base from uintptr_t to HashNumber/uint32_t.
> r=me if you want to rewrite it to something like:
> 
> HashNumber hash = mozilla::HashGeneric(base);
> ... AddToHash calls...

I wanna fix this in a slightly different way, will file a follow-up.
Pushed by eakhgari@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a7a9d51edeeb
Improve SpiderMonkey hashing functions by using MFBT's HashGeneric more; r=jandem
https://hg.mozilla.org/mozilla-central/rev/a7a9d51edeeb
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla56
You need to log in before you can comment on or make changes to this bug.