934718 - Simplify some HashTable internal maths, kill some JS_STATIC_ASSERT usage

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jeff Walden [:Waldo]]

Attachment: Patch

Some of the current static-asserts of hash table constants are 1) not ever tested, because staticAsserts is never called (and therefore never instantiated), and 2) crazy, because the constants involved are scaled in offsetting ways by 2**7, 2**8, 2, and similar, but not at all in obviously corresponding ways.  Rewrite the math to be significantly clearer about what it does, by splitting alpha fractions into numerator-denominator constant pairs, and replace the relevant JS_STATIC_ASSERT with C++11 static_asserts to the same effect (if not in the same ways).

Comment 1

[Nicholas Nethercote [inactive]]

Bug 929620 comment 1 might be worth considering as part of this bug.

Comment 3

[Luke Wagner [:luke]]

Comment on attachment 827060 [details] [diff] [review]
Patch

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

Nice.

::: js/public/HashTable.h
@@ +926,5 @@
> +    // Hash-table alpha is conceptually a fraction, but to avoid floating-point
> +    // math we implement it as a ratio of integers.
> +    static const uint8_t sAlphaDenominator = 4;
> +    static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
> +    static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4

Whoa, I can like, totally wrap my ahead around this the first time.

@@ +994,5 @@
> +                      "numerator calculation below could potentially overflow");
> +
> +        // Compute the smallest capacity allowing |length| elements to be
> +        // inserted without rehashing: ceil(length / max-alpha).  (Ceiling
> +        // integral division: <http://stackoverflow.com/a/2745086/115698>.)

Is stack overflow the best URL we can embed here?  Also, to make it more readable, perhaps you'd consider factoring this out into some JS_ALWAYS_INLINE function (either in HashTable or a mfbt math helper .h).

Comment 4

[Jeff Walden [:Waldo]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/bbbeb0e593ec

I assume you mean like the Stanford bits algorithms page, or something -- no, I didn't find anything elsewhere for ceiling division.

As for abstracting it, might be nice, but I don't think *this* case is going to look any nicer, given that max-alpha is a fraction, requiring its being split into two parts to gunk up *both* halves of the division.  Next time there's a use for ceiling division, with non-fugly operands, it seems like a good idea to add the helper.

Comment 5

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/bbbeb0e593ec