1058075 - IonMonkey: Improve hashing of MConstants

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

Attachment: gvn-constant-hash.patch

Currently, MConstant::valueHash disregards half of its full 64-bit value. I've observed cases where this leads to huge slowdowns due to excessive hash-table collisions. The attached patch just mixes all 64 bits into a 32-bit value using xor, which sufficient to fix the problems I'm seeing.

Comment 1

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8478329 [details] [diff] [review]
gvn-constant-hash.patch

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

::: js/src/jit/MIR.cpp
@@ +580,5 @@
> +    // Fold all 64 bits into the 32-bit result. It's tempting to just discard
> +    // half of the bits, as this is just a hash, however there are many common
> +    // patterns of values where only the low or the high bits vary, so
> +    // discarding either side would lead to excessive hash collisions.
> +    uint64_t bits = JSVAL_TO_IMPL(value_).asBits;

I think I'd prefer something that dosen't hash -1 and 0 to the same value, but super-minor nit.  Particularly since AIUI, we never actually use a 64-bit -1

Comment 2

[Dan Gohman [:sunfish]]

(In reply to Marty Rosenberg [:mjrosenb] from comment #1)
> Comment on attachment 8478329 [details] [diff] [review]
> gvn-constant-hash.patch
> 
> Review of attachment 8478329 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MIR.cpp
> @@ +580,5 @@
> > +    // Fold all 64 bits into the 32-bit result. It's tempting to just discard
> > +    // half of the bits, as this is just a hash, however there are many common
> > +    // patterns of values where only the low or the high bits vary, so
> > +    // discarding either side would lead to excessive hash collisions.
> > +    uint64_t bits = JSVAL_TO_IMPL(value_).asBits;
> 
> I think I'd prefer something that dosen't hash -1 and 0 to the same value,
> but super-minor nit.  Particularly since AIUI, we never actually use a
> 64-bit -1

That's a good point. However Value doesn't currently support int64; it's only 64 bits itself, and it needs room for a type tag, so I believe we're ok for the foreseeable future.

https://hg.mozilla.org/integration/mozilla-inbound/rev/73d25b34ba67

Comment 3

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/73d25b34ba67