1802568 - SpecificParserAtomLookup::equalsEntry is only called with atoms with matching hashes.

Status: ASSIGNED

(Core :: JavaScript Engine, task, P3)

Description

[Matthew Gaudet (he/him) [:mgaudet]]

While looking at something else, I spotted a surprising pair of lines with zero hits in code-coverage.

I haven't quite gotten to the bottom of this, but it appears that for some reason SpecificParserAtomLookup::equalsEntry is only ever called with something that has a matching hash.

I have found only two test cases that fail if you replace these equalsEntry functions with stubs that just return true:

• wasm/name.js fails if the well-known info overload is replaced with return true -- though, this is only true for non-debug builds.
• for-of/strings.js fails if ParserAtom::equalsSeq, which powers the ParserAtom overload, is replaced with return true.

If the hashes aren't being used, it means that every time we call these functions we're using a string-walk: It would potentially be worth figuring out if there's a pre-computable property here that could be used to avoid having to walk the strings each time.

Comment 1

[André Bargull [:anba]]

This seems correct to me. Both SpecificParserAtomLookup::equalsEntry methods are called from the hash-policy structs ParserAtomLookupHasher resp. WellKnownAtomInfoHasher. The hash-policy description doesn't mention that match is never called for objects with the same hash, so it's valid for the hashmap implementation to call the equalsEntry methods with the same hash.

Comment 2

[Tooru Fujisawa [:arai]]

The branch is actually taken with the following testcase (reduced from https://searchfox.org/mozilla-central/source/js/src/tests/non262/Intl/Locale/likely-subtags-generated.js ):

"raa-Deva-NP";
"tfn-Latn-US";

the HashTable doesn't use the passed hash directly, but applies extra operation on it (see below),
and the resulting keyHash there can cause collision for different inputHash.
and the remaining logic only guarantee that keyHash is same for the item passed to match method.
it means inputHash can be different, and we need to check the original hash (inputHash).

in the above testcase, those 2 strings have different hash e354a2e0 and f7a15f69, but keyHash becomes 874593e0 for both hash.

it would be nice to add explicit comment for this behavior.

https://searchfox.org/mozilla-central/rev/47be6b9a0719f4311356695d9eed48de97b432b2/mfbt/HashTable.h#2110

HashNumber keyHash = prepareHash(inputHash);

https://searchfox.org/mozilla-central/rev/47be6b9a0719f4311356695d9eed48de97b432b2/mfbt/HashTable.h#1645-1653

static HashNumber prepareHash(HashNumber aInputHash) {
  HashNumber keyHash = ScrambleHashCode(aInputHash);

  // Avoid reserved hash codes.
  if (!isLiveHash(keyHash)) {
    keyHash -= (sRemovedKey + 1);
  }
  return keyHash & ~sCollisionBit;
}

https://searchfox.org/mozilla-central/rev/47be6b9a0719f4311356695d9eed48de97b432b2/mfbt/HashFunctions.h#83,99-100

constexpr HashNumber ScrambleHashCode(HashNumber h) {
...
  return mozilla::WrappingMultiply(h, kGoldenRatioU32);
}

Comment 3

[Tooru Fujisawa [:arai]]

I've posted a patch to add documentation comment for HashPolicy to bug 1860451.

Then, I'm wondering if we could move the prepareHash operation out of HashTable (maybe conditionally on template parameter),
and store the "hash with prepareHash applied" to ParserAtom and JSAtom.
It will remove some unnecessary/duplicate operations, and also make the situation simpler.