Bug 1581875 - Introducing MultiLookupHuffmanTable;r=arai
authorDavid Teller <dteller@mozilla.com>
Mon, 30 Sep 2019 08:29:34 +0000
changeset 495651 1e1f1ab54bd89cff28ea876c3d26a571a87b9dbc
parent 495650 455940bf79772434906badfad4e29fe08d3bdad2
child 495652 1afa24c955835d0682e7af01af53861ee7cded94
push id114140
push userdvarga@mozilla.com
push dateWed, 02 Oct 2019 18:04:51 +0000
treeherdermozilla-inbound@32eb0ea893f3 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersarai
bugs1581875
milestone71.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1581875 - Introducing MultiLookupHuffmanTable;r=arai The MultiLookupHuffmanTable is designed to allow fast lookup in tables that have a max bit length too large for the SingleLookupHuffmanTable. We will probably need to tune the bit lengths at which we switch from SingleLookup to TwoLookups or ThreeLookups in followup patches. Differential Revision: https://phabricator.services.mozilla.com/D46806
js/src/frontend/BinASTTokenReaderContext.cpp
js/src/frontend/BinASTTokenReaderContext.h
--- a/js/src/frontend/BinASTTokenReaderContext.cpp
+++ b/js/src/frontend/BinASTTokenReaderContext.cpp
@@ -610,36 +610,36 @@ class HuffmanPreludeReader {
 
     // Data is presented in an order that doesn't match our memory
     // representation, so we need to copy `numberOfSymbols` entries.
     // We use an auxiliary vector to avoid allocating each time.
     MOZ_ASSERT(
         auxStorageLength.empty());  // We must have cleaned it up properly.
     BINJS_TRY(auxStorageLength.reserve(numberOfSymbols + 1));
 
-    uint8_t maxBitLength = 0;
+    uint8_t largestBitLength = 0;
 
     // First read and store the bit lengths for all symbols.
     for (size_t i = 0; i < numberOfSymbols; ++i) {
       BINJS_MOZ_TRY_DECL(bitLength, reader.readByte<Compression::No>());
       if (bitLength == 0) {
         return raiseInvalidTableData(entry.identity);
       }
-      if (bitLength > maxBitLength) {
-        maxBitLength = bitLength;
+      if (bitLength > largestBitLength) {
+        largestBitLength = bitLength;
       }
       BINJS_TRY(auxStorageLength.append(BitLengthAndIndex(bitLength, i)));
     }
     // Append a terminator.
     BINJS_TRY(auxStorageLength.append(
         BitLengthAndIndex(MAX_CODE_BIT_LENGTH, numberOfSymbols)));
 
     // Now read the symbols and assign bits.
     uint32_t code = 0;
-    MOZ_TRY(table.initStart(cx_, numberOfSymbols, maxBitLength));
+    MOZ_TRY(table.initStart(cx_, numberOfSymbols, largestBitLength));
 
     for (size_t i = 0; i < numberOfSymbols; ++i) {
       const auto bitLength = auxStorageLength[i].bitLength;
       const auto nextBitLength =
           auxStorageLength[i + 1]
               .bitLength;  // Guaranteed to exist, as we have a terminator.
 
       if (bitLength > nextBitLength) {
@@ -673,28 +673,28 @@ class HuffmanPreludeReader {
         auxStorageLength.empty());  // We must have cleaned it up properly.
     BINJS_TRY(auxStorageLength.reserve(numberOfSymbols + 1));
 
     // Implicit entry:
     // - Symbols are known statically.
     // - Lengths MAY be 0.
     // - Lengths are not sorted on disk.
 
-    uint8_t maxBitLength = 0;
+    uint8_t largestBitLength = 0;
 
     // First read the length for all symbols, only store non-0 lengths.
     for (size_t i = 0; i < numberOfSymbols; ++i) {
       BINJS_MOZ_TRY_DECL(bitLength, reader.readByte<Compression::No>());
       if (bitLength > MAX_CODE_BIT_LENGTH) {
         MOZ_CRASH("FIXME: Implement error");
       }
       if (bitLength > 0) {
         BINJS_TRY(auxStorageLength.append(BitLengthAndIndex(bitLength, i)));
-        if (bitLength > maxBitLength) {
-          maxBitLength = bitLength;
+        if (bitLength > largestBitLength) {
+          largestBitLength = bitLength;
         }
       }
     }
 
     // Sort by length then webidl order (which is also the index).
     std::sort(auxStorageLength.begin(), auxStorageLength.end(),
               [&entry](const BitLengthAndIndex& a,
                        const BitLengthAndIndex& b) -> bool {
@@ -711,17 +711,18 @@ class HuffmanPreludeReader {
               });
 
     // Append a terminator.
     BINJS_TRY(
         auxStorageLength.emplaceBack(MAX_CODE_BIT_LENGTH, numberOfSymbols));
 
     // Now read the symbols and assign bits.
     uint32_t code = 0;
-    MOZ_TRY(table.initStart(cx_, auxStorageLength.length() - 1, maxBitLength));
+    MOZ_TRY(
+        table.initStart(cx_, auxStorageLength.length() - 1, largestBitLength));
 
     for (size_t i = 0; i < auxStorageLength.length() - 1; ++i) {
       const auto bitLength = auxStorageLength[i].bitLength;
       const auto nextBitLength =
           auxStorageLength[i + 1].bitLength;  // Guaranteed to exist, as we stop
                                               // before the terminator.
       MOZ_ASSERT(bitLength > 0);
       MOZ_ASSERT(bitLength <= nextBitLength);
@@ -1631,116 +1632,148 @@ FlatHuffmanKey::FlatHuffmanKey(const Huf
 
 template <typename T>
 GenericHuffmanTable<T>::Iterator::Iterator(
     typename SingleLookupHuffmanTable<T>::Iterator&& iterator)
     : implementation(std::move(iterator)) {}
 
 template <typename T>
 GenericHuffmanTable<T>::Iterator::Iterator(
-    typename MapBasedHuffmanTable<T>::Iterator&& iterator)
+    typename TwoLookupsHuffmanTable<T>::Iterator&& iterator)
+    : implementation(std::move(iterator)) {}
+
+template <typename T>
+GenericHuffmanTable<T>::Iterator::Iterator(
+    typename ThreeLookupsHuffmanTable<T>::Iterator&& iterator)
     : implementation(std::move(iterator)) {}
 
 template <typename T>
 void GenericHuffmanTable<T>::Iterator::operator++() {
   implementation.match(
       [](typename SingleLookupHuffmanTable<T>::Iterator& iterator) {
         iterator.operator++();
       },
-      [](typename MapBasedHuffmanTable<T>::Iterator& iterator) {
+      [](typename TwoLookupsHuffmanTable<T>::Iterator& iterator) {
+        iterator.operator++();
+      },
+      [](typename ThreeLookupsHuffmanTable<T>::Iterator& iterator) {
         iterator.operator++();
       });
 }
 
 template <typename T>
 bool GenericHuffmanTable<T>::Iterator::operator==(
     const GenericHuffmanTable<T>::Iterator& other) const {
   return implementation.match(
       [other](const typename SingleLookupHuffmanTable<T>::Iterator& iterator) {
         return iterator ==
                other.implementation.template as<
                    typename SingleLookupHuffmanTable<T>::Iterator>();
       },
-      [other](const typename MapBasedHuffmanTable<T>::Iterator& iterator) {
+      [other](const typename TwoLookupsHuffmanTable<T>::Iterator& iterator) {
         return iterator ==
                other.implementation
-                   .template as<typename MapBasedHuffmanTable<T>::Iterator>();
+                   .template as<typename TwoLookupsHuffmanTable<T>::Iterator>();
+      },
+      [other](const typename ThreeLookupsHuffmanTable<T>::Iterator& iterator) {
+        return iterator ==
+               other.implementation.template as<
+                   typename ThreeLookupsHuffmanTable<T>::Iterator>();
       });
 }
 
 template <typename T>
 bool GenericHuffmanTable<T>::Iterator::operator!=(
     const GenericHuffmanTable<T>::Iterator& other) const {
   return implementation.match(
       [other](const typename SingleLookupHuffmanTable<T>::Iterator& iterator) {
         return iterator !=
                other.implementation.template as<
                    typename SingleLookupHuffmanTable<T>::Iterator>();
       },
-      [other](const typename MapBasedHuffmanTable<T>::Iterator& iterator) {
+      [other](const typename TwoLookupsHuffmanTable<T>::Iterator& iterator) {
         return iterator !=
                other.implementation
-                   .template as<typename MapBasedHuffmanTable<T>::Iterator>();
+                   .template as<typename TwoLookupsHuffmanTable<T>::Iterator>();
+      },
+      [other](const typename ThreeLookupsHuffmanTable<T>::Iterator& iterator) {
+        return iterator !=
+               other.implementation.template as<
+                   typename ThreeLookupsHuffmanTable<T>::Iterator>();
       });
 }
 
 template <typename T>
 const T* GenericHuffmanTable<T>::Iterator::operator*() const {
   return implementation.match(
       [](const typename SingleLookupHuffmanTable<T>::Iterator& iterator) {
         return iterator.operator*();
       },
-      [](const typename MapBasedHuffmanTable<T>::Iterator& iterator) {
+      [](const typename TwoLookupsHuffmanTable<T>::Iterator& iterator) {
+        return iterator.operator*();
+      },
+      [](const typename ThreeLookupsHuffmanTable<T>::Iterator& iterator) {
         return iterator.operator*();
       });
 }
 
 template <typename T>
 GenericHuffmanTable<T>::GenericHuffmanTable(JSContext*)
     : implementation(HuffmanTableUnreachable{}) {}
 
 template <typename T>
 JS::Result<Ok> GenericHuffmanTable<T>::initComplete() {
   return this->implementation.match(
-      [](SingleLookupHuffmanTable<T>& implementation) {
+      [](SingleLookupHuffmanTable<T>& implementation) -> JS::Result<Ok> {
         return implementation.initComplete();
       },
-      [](MapBasedHuffmanTable<T>& implementation) {
+      [](TwoLookupsHuffmanTable<T>& implementation) -> JS::Result<Ok> {
         return implementation.initComplete();
       },
-      [](HuffmanTableUnreachable&) {
+      [](ThreeLookupsHuffmanTable<T>& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete();
+      },
+      [](HuffmanTableUnreachable&) -> JS::Result<Ok> {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
 template <typename T>
 typename GenericHuffmanTable<T>::Iterator GenericHuffmanTable<T>::begin()
     const {
   return this->implementation.match(
       [](const SingleLookupHuffmanTable<T>& implementation)
           -> GenericHuffmanTable<T>::Iterator {
         return Iterator(implementation.begin());
       },
-      [](const MapBasedHuffmanTable<T>& implementation)
+      [](const TwoLookupsHuffmanTable<T>& implementation)
+          -> GenericHuffmanTable<T>::Iterator {
+        return Iterator(implementation.begin());
+      },
+      [](const ThreeLookupsHuffmanTable<T>& implementation)
           -> GenericHuffmanTable<T>::Iterator {
         return Iterator(implementation.begin());
       },
       [](const HuffmanTableUnreachable&) -> GenericHuffmanTable<T>::Iterator {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
 template <typename T>
 typename GenericHuffmanTable<T>::Iterator GenericHuffmanTable<T>::end() const {
   return this->implementation.match(
       [](const SingleLookupHuffmanTable<T>& implementation)
           -> GenericHuffmanTable<T>::Iterator {
         return Iterator(implementation.end());
       },
-      [](const MapBasedHuffmanTable<T>& implementation)
+      [](const TwoLookupsHuffmanTable<T>& implementation)
+          -> GenericHuffmanTable<T>::Iterator {
+        return Iterator(implementation.end());
+      },
+      [](const ThreeLookupsHuffmanTable<T>& implementation)
           -> GenericHuffmanTable<T>::Iterator {
         return Iterator(implementation.end());
       },
       [](const HuffmanTableUnreachable&) -> GenericHuffmanTable<T>::Iterator {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
@@ -1757,71 +1790,87 @@ JS::Result<Ok> GenericHuffmanTable<T>::i
   MOZ_TRY(this->implementation.template as<SingleLookupHuffmanTable<T>>()
               .initWithSingleValue(cx, std::move(value)));
   return Ok();
 }
 
 template <typename T>
 JS::Result<Ok> GenericHuffmanTable<T>::initStart(JSContext* cx,
                                                  size_t numberOfSymbols,
-                                                 uint8_t maxBitLength) {
-  MOZ_ASSERT(this->implementation.template is<
-             HuffmanTableUnreachable>());  // Make sure that we're initializing.
-  if (
-      // If the bit length is too large, don't put it in a saturated table
-      // as this would need too much space.
-      maxBitLength > MAX_BIT_LENGTH_IN_SATURATED_TABLE ||
-      // If there are too many symbols, don't put it in a saturated table
-      // as indices  wouldn't fit into `InternalIndex` .
-      numberOfSymbols >
-          mozilla::MaxValue<
-              typename SingleLookupHuffmanTable<T>::InternalIndex>::value) {
-    this->implementation = {mozilla::VariantType<MapBasedHuffmanTable<T>>{},
-                            cx};
-    MOZ_TRY(
-        this->implementation.template as<MapBasedHuffmanTable<T>>().initStart(
-            cx, numberOfSymbols, maxBitLength));
-  } else {
+                                                 uint8_t largestBitLength) {
+  // Make sure that we have a way to represent all legal bit lengths.
+  static_assert(
+      MAX_CODE_BIT_LENGTH <= ThreeLookupsHuffmanTable<T>::MAX_BIT_LENGTH,
+      "ThreeLookupsHuffmanTable cannot hold all bit lengths");
+  // Make sure that we're initializing.
+  MOZ_ASSERT(this->implementation.template is<HuffmanTableUnreachable>());
+
+  // Find the (hopefully) fastest implementation of HuffmanTable for
+  // `largestBitLength`.
+  // ...hopefully, only one lookup.
+  if (largestBitLength <= SingleLookupHuffmanTable<T>::MAX_BIT_LENGTH) {
     this->implementation = {mozilla::VariantType<SingleLookupHuffmanTable<T>>{},
                             cx};
-    MOZ_TRY(this->implementation.template as<SingleLookupHuffmanTable<T>>()
-                .initStart(cx, numberOfSymbols, maxBitLength));
+    return this->implementation.template as<SingleLookupHuffmanTable<T>>()
+        .initStart(cx, numberOfSymbols, largestBitLength);
   }
-  return Ok();
+
+  // ...if a single-lookup table would be too large, let's see if
+  // we can fit in a two-lookup table.
+  if (largestBitLength <= TwoLookupsHuffmanTable<T>::MAX_BIT_LENGTH) {
+    this->implementation = {mozilla::VariantType<TwoLookupsHuffmanTable<T>>{},
+                            cx};
+    return this->implementation.template as<TwoLookupsHuffmanTable<T>>()
+        .initStart(cx, numberOfSymbols, largestBitLength);
+  }
+
+  // ...otherwise, we'll need three lookups.
+  this->implementation = {mozilla::VariantType<ThreeLookupsHuffmanTable<T>>{},
+                          cx};
+  return this->implementation.template as<ThreeLookupsHuffmanTable<T>>()
+      .initStart(cx, numberOfSymbols, largestBitLength);
 }
 
 template <typename T>
 JS::Result<Ok> GenericHuffmanTable<T>::addSymbol(uint32_t bits,
                                                  uint8_t bitLength, T&& value) {
   return this->implementation.match(
       [bits, bitLength, value = std::move(value)](
           SingleLookupHuffmanTable<T>&
               implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
         return implementation.addSymbol(bits, bitLength, std::move(value));
       },
       [bits, bitLength, value = std::move(value)](
-          MapBasedHuffmanTable<T>&
+          TwoLookupsHuffmanTable<T>&
+              implementation) mutable /* discard implicit const */
+      -> JS::Result<Ok> {
+        return implementation.addSymbol(bits, bitLength, std::move(value));
+      },
+      [bits, bitLength, value = std::move(value)](
+          ThreeLookupsHuffmanTable<T>&
               implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
         return implementation.addSymbol(bits, bitLength, std::move(value));
       },
       [](HuffmanTableUnreachable&) -> JS::Result<Ok> {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
         return Ok();
       });
 }
 
 template <typename T>
 HuffmanEntry<const T*> GenericHuffmanTable<T>::lookup(
     HuffmanLookup lookup) const {
   return this->implementation.match(
       [lookup](const SingleLookupHuffmanTable<T>& implementation)
           -> HuffmanEntry<const T*> { return implementation.lookup(lookup); },
-      [lookup](const MapBasedHuffmanTable<T>& implementation)
+      [lookup](const TwoLookupsHuffmanTable<T>& implementation)
+          -> HuffmanEntry<const T*> { return implementation.lookup(lookup); },
+      [lookup](const ThreeLookupsHuffmanTable<T>& implementation)
           -> HuffmanEntry<const T*> { return implementation.lookup(lookup); },
       [](const HuffmanTableUnreachable&) -> HuffmanEntry<const T*> {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
 template <typename T, int N>
 JS::Result<Ok> NaiveHuffmanTable<T, N>::initWithSingleValue(JSContext* cx,
@@ -1929,18 +1978,16 @@ JS::Result<Ok> MapBasedHuffmanTable<T>::
 #endif  // DEBUG
   return Ok();
 }
 
 template <typename T>
 JS::Result<Ok> MapBasedHuffmanTable<T>::addSymbol(uint32_t bits,
                                                   uint8_t bitLength,
                                                   T&& value) {
-  MOZ_ASSERT(bitLength != 0,
-             "Adding a symbol with a bitLength of 0 doesn't make sense.");
   MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
   const HuffmanKey key(bits, bitLength);
   const FlatHuffmanKey flat(key);
   values.putNewInfallible(
       flat, std::move(value));  // Memory was reserved in `init()`.
   keys.infallibleAppend(std::move(key));
 
   return Ok();
@@ -1994,123 +2041,305 @@ JS::Result<Ok> SingleLookupHuffmanTable<
                                                                 T&& value) {
   MOZ_ASSERT(values.empty());  // Make sure that we're initializing.
   if (!values.emplaceBack(0, 0, std::move(value))) {
     return cx->alreadyReportedError();
   }
   if (!saturated.emplaceBack(0)) {
     return cx->alreadyReportedError();
   }
-  this->maxBitLength = 0;
+  this->largestBitLength = 0;
   return Ok();
 }
 
 template <typename T>
 JS::Result<Ok> SingleLookupHuffmanTable<T>::initStart(JSContext* cx,
                                                       size_t numberOfSymbols,
-                                                      uint8_t maxBitLength) {
-  MOZ_ASSERT(maxBitLength <= MAX_BIT_LENGTH_IN_SATURATED_TABLE);
+                                                      uint8_t largestBitLength) {
+  MOZ_ASSERT(largestBitLength <= MAX_BIT_LENGTH_IN_SATURATED_TABLE);
   MOZ_ASSERT(values.empty());  // Make sure that we're initializing.
 
-  this->maxBitLength = maxBitLength;
+  this->largestBitLength = largestBitLength;
 
   if (!values.initCapacity(numberOfSymbols)) {
     return cx->alreadyReportedError();
   }
-  const size_t saturatedLength = 1 << maxBitLength;
+  const size_t saturatedLength = 1 << largestBitLength;
   if (!saturated.initCapacity(saturatedLength)) {
     return cx->alreadyReportedError();
   }
   // Enlarge `saturated`, as we're going to fill it in random order.
   for (size_t i = 0; i < saturatedLength; ++i) {
     // Capacity reserved in this method.
-    saturated.infallibleAppend(uint8_t(-1));
+    saturated.infallibleAppend(InternalIndex(-1));
   }
   return Ok();
 }
 
 template <typename T>
 JS::Result<Ok> SingleLookupHuffmanTable<T>::initComplete() {
   // Double-check that we've initialized properly.
-  MOZ_ASSERT(this->maxBitLength <= MAX_CODE_BIT_LENGTH);
+  MOZ_ASSERT(this->largestBitLength <= MAX_CODE_BIT_LENGTH);
+
+  // We can end up with empty tables, if this `SingleLookupHuffmanTable`
+  // is used to store suffixes in a `MultiLookupHuffmanTable` and
+  // the corresponding prefix is never used.
+  if (values.length() == 0) {
+    MOZ_ASSERT(this->largestBitLength == 0);
+    return Ok();
+  }
 #ifdef DEBUG
   bool foundMaxBitLength = false;
   for (size_t i = 0; i < saturated.length(); ++i) {
-    // Check that all indices have been properly initialized.
-    // Note: this is an explicit `for(;;)` loop instead of
-    // a `for(:)` range loop, as knowing `i` should simplify
-    // debugging.
     const uint8_t index = saturated[i];
-    MOZ_ASSERT(index < values.length());
-    if (values[index].key.bitLength == maxBitLength) {
+    MOZ_ASSERT(values[index].key.bitLength <= largestBitLength);
+    if (values[index].key.bitLength == largestBitLength) {
       foundMaxBitLength = true;
     }
   }
   MOZ_ASSERT(foundMaxBitLength);
 #endif  // DEBUG
   return Ok();
 }
 
 template <typename T>
 JS::Result<Ok> SingleLookupHuffmanTable<T>::addSymbol(uint32_t bits,
                                                       uint8_t bitLength,
                                                       T&& value) {
-  MOZ_ASSERT(bitLength != 0,
-             "Adding a symbol with a bitLength of 0 doesn't make sense.");
-  MOZ_ASSERT(values.empty() || values.back().key.bitLength <= bitLength,
-             "Symbols must be ranked by increasing bits length");
+  MOZ_ASSERT_IF(largestBitLength != 0, bitLength != 0);
   MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
-  MOZ_ASSERT(bitLength <= maxBitLength);
+  MOZ_ASSERT(bitLength <= largestBitLength);
 
   const size_t index = values.length();
 
   // First add the value to `values`.
-  if (!values.emplaceBack(bits, bitLength, std::move(value))) {
-    // Memory was reserved in `init()`.
-    MOZ_CRASH();
-  }
+  // Memory was reserved in `init()`.
+  values.infallibleEmplaceBack(bits, bitLength, std::move(value));
 
   // Notation: in the following, unless otherwise specified, we consider
-  // values with `maxBitLength` bits exactly.
+  // values with `largestBitLength` bits exactly.
   //
-  // When we perform lookup, we will extract `maxBitLength` bits from the key
-  // into a value `0bB...B`. We have a match for `value` if and only if
+  // When we perform lookup, we will extract `largestBitLength` bits from the
+  // key into a value `0bB...B`. We have a match for `value` if and only if
   // `0bB...B` may be decomposed into `0bC...CX...X` such that
   //    - `0bC...C` is `bitLength` bits long;
   //    - `0bC...C == bits`.
   //
   // To perform a fast lookup, we precompute all possible values of `0bB...B`
   // for which this condition is true. That's all the values of segment
   // `[0bC...C0...0, 0bC...C1...1]`.
   const HuffmanLookup base(bits, bitLength);
-  for (size_t i : base.suffixes(maxBitLength)) {
+  for (size_t i : base.suffixes(largestBitLength)) {
     saturated[i] = index;
   }
 
   return Ok();
 }
 
 template <typename T>
 HuffmanEntry<const T*> SingleLookupHuffmanTable<T>::lookup(
     HuffmanLookup key) const {
-  // Take the `maxBitLength` highest weight bits of `key`.
+  if (values.length() == 0) {
+    // If the table is empty, any lookup fails.
+    return HuffmanEntry<const T*>(0, 0, nullptr);
+  }
+  // ...otherwise, all lookups succeed.
+
+  // Take the `largestBitLength` highest weight bits of `key`.
   // In the documentation of `addSymbol`, this is
   // `0bB...B`.
-  const uint32_t bits = key.leadingBits(maxBitLength);
-
-  // Invariants: `saturated.length() == 1 << maxBitLength`
-  // and `bits <= 1 << maxBitLength`.
+  const uint32_t bits = key.leadingBits(largestBitLength);
+
+  // Invariants: `saturated.length() == 1 << largestBitLength`
+  // and `bits <= 1 << largestBitLength`.
   const size_t index = saturated[bits];
 
   // Invariants: `saturated[i] < values.length()`.
   const auto& entry = values[index];
   return HuffmanEntry<const T*>(entry.key.bits, entry.key.bitLength,
                                 &entry.value);
 }
 
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::Iterator::Iterator(
+    const HuffmanEntry<T>* position)
+    : position(position) {}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+void MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::Iterator::
+operator++() {
+  position++;
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+const T* MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::Iterator::
+operator*() const {
+  return &position->value;
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+bool MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::Iterator::
+operator==(const Iterator& other) const {
+  return position == other.position;
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+bool MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::Iterator::
+operator!=(const Iterator& other) const {
+  return position != other.position;
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+JS::Result<Ok> MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::initStart(
+    JSContext* cx, size_t numberOfSymbols, uint8_t largestBitLength) {
+  static_assert(PrefixBitLength < MAX_CODE_BIT_LENGTH,
+                "Invalid PrefixBitLength");
+  MOZ_ASSERT(values.empty());  // Make sure that we're initializing.
+  MOZ_ASSERT(subTables.empty());
+  this->largestBitLength = largestBitLength;
+  if (!values.initCapacity(numberOfSymbols)) {
+    return cx->alreadyReportedError();
+  }
+  if (!subTables.initCapacity(1 << PrefixBitLength)) {
+    return cx->alreadyReportedError();
+  }
+#ifdef DEBUG
+  MOZ_TRY(control.initStart(cx, numberOfSymbols, largestBitLength));
+#endif  // DEBUG
+  return Ok();
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+JS::Result<Ok> MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::addSymbol(
+    uint32_t bits, uint8_t bitLength, T&& value) {
+  MOZ_ASSERT_IF(largestBitLength != 0, bitLength != 0);
+  MOZ_ASSERT(values.empty() || values.back().key.bitLength <= bitLength,
+             "Symbols must be ranked by increasing bits length");
+  MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
+
+#ifdef DEBUG
+  T valueCopy = value;
+  MOZ_TRY(control.addSymbol(bits, bitLength, std::move(valueCopy)));
+#endif  // DEBUG
+
+  values.infallibleEmplaceBack(bits, bitLength, std::move(value));
+
+  return Ok();
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+JS::Result<Ok>
+MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::initComplete() {
+#ifdef DEBUG
+  MOZ_TRY(control.initComplete());
+#endif  // DEBUG
+
+  // First, we need to collect the `largestBitLength`
+  // and `numberofSymbols` for each subtable.
+  struct Bucket {
+    Bucket() : largestBitLength(0), numberOfSymbols(0){};
+    uint8_t largestBitLength;
+    uint32_t numberOfSymbols;
+  };
+  Vector<Bucket> buckets{cx_};
+  BINJS_TRY(buckets.resize(1 << PrefixBitLength));
+
+  for (const auto& entry : values) {
+    const HuffmanLookup lookup(entry.key.bits, entry.key.bitLength);
+    const auto split = lookup.split(PrefixBitLength);
+    MOZ_ASSERT_IF(split.suffix.bitLength != 32,
+                  split.suffix.bits >> split.suffix.bitLength == 0);
+
+    // Entries that have a sufficient number of bits will be dispatched
+    // to a single subtable (e.g. A, B, C, D, E, F in the documentation).
+    // Other entries need to be dispatched to several subtables
+    // (e.g. G, H in the documentation).
+    for (const auto index : lookup.suffixes(PrefixBitLength)) {
+      Bucket& bucket = buckets[index];
+      if (split.suffix.bitLength >= bucket.largestBitLength) {
+        bucket.largestBitLength = split.suffix.bitLength;
+      }
+      bucket.numberOfSymbols++;
+    }
+  }
+
+  // We may now create the subtables.
+  for (auto& bucket : buckets) {
+    Subtable sub(cx_);
+    MOZ_TRY(sub.initStart(cx_,
+                          /* numberOfSymbols = */ bucket.numberOfSymbols,
+                          /* largestBitLength = */ bucket.largestBitLength));
+    BINJS_TRY(subTables.append(std::move(sub)));
+  }
+
+  // Now that the subtables are created, let's dispatch the values
+  // among these tables.
+  for (size_t i = 0; i < values.length(); ++i) {
+    const auto& entry = values[i];
+
+    // Find the relevant subtables.
+    const HuffmanLookup lookup(entry.key.bits, entry.key.bitLength);
+    const auto split = lookup.split(PrefixBitLength);
+    MOZ_ASSERT_IF(split.suffix.bitLength != 32,
+                  split.suffix.bits >> split.suffix.bitLength == 0);
+    for (const auto index : lookup.suffixes(PrefixBitLength)) {
+      auto& sub = subTables[index];
+
+      // We may now add a reference to `entry` into the sybtable.
+      MOZ_TRY(sub.addSymbol(split.suffix.bits, split.suffix.bitLength,
+                            std::move(i)));
+    }
+  }
+
+  // Finally, complete initialization of subtables.
+  for (auto& sub : subTables) {
+    MOZ_TRY(sub.initComplete());
+  }
+
+  return Ok();
+}
+
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+HuffmanEntry<const T*>
+MultiLookupHuffmanTable<T, Subtable, PrefixBitLength>::lookup(
+    HuffmanLookup key) const {
+#ifdef DEBUG
+  const auto controlResult = control.lookup(key);
+#endif  // DEBUG
+
+  const auto split = key.split(PrefixBitLength);
+  if (split.prefix.bits >= subTables.length()) {
+    return HuffmanEntry<const T*>(0, 0, nullptr);
+  }
+  const Subtable& subtable = subTables[split.prefix.bits];
+
+  auto found = subtable.lookup(split.suffix);
+
+  if (found.value == nullptr) {
+    // Propagate "not found".
+#ifdef DEBUG
+    MOZ_ASSERT(controlResult.value == nullptr);
+#endif  // DEBUG
+    return {0, 0, nullptr};
+  }
+
+  // Otherwise, restore the entire `HuffmanEntry`.
+  const auto& result = values[*found.value];
+
+#ifdef DEBUG
+  MOZ_ASSERT(controlResult.value != nullptr);
+  MOZ_ASSERT(result.key.bits == controlResult.key.bits);
+  MOZ_ASSERT(result.key.bitLength == controlResult.key.bitLength);
+  MOZ_ASSERT(result.value == *controlResult.value);
+#endif  // DEBUG
+  return /* HuffmanEntry */ {/* bits */ result.key.bits,
+                             /* bitLength */ result.key.bitLength,
+                             /* value */ std::move(&result.value)};
+}
+
 // -----
 
 // The number of possible interfaces in each sum, indexed by
 // `static_cast<size_t>(BinASTSum)`.
 const size_t SUM_LIMITS[]{
 #define WITH_SUM(_ENUM_NAME, _HUMAN_NAME, MACRO_NAME, _TYPE_NAME) \
   BINAST_SUM_##MACRO_NAME##_LIMIT,
     FOR_EACH_BIN_SUM(WITH_SUM)
@@ -2586,16 +2815,48 @@ HuffmanTableListLength& HuffmanDictionar
 uint32_t HuffmanLookup::leadingBits(const uint8_t aBitLength) const {
   MOZ_ASSERT(aBitLength <= this->bitLength);
   const uint32_t result =
       (aBitLength == 0) ? 0  // Shifting a uint32_t by 32 bits is UB.
                         : this->bits >> uint32_t(this->bitLength - aBitLength);
   return result;
 }
 
+Split<HuffmanLookup> HuffmanLookup::split(const uint8_t prefixLength) const {
+  if (bitLength <= prefixLength) {
+    // Not enough bits, pad with zeros.
+    return {
+        /* prefix: HuffmanLookup */ {bits << (prefixLength - bitLength),
+                                     prefixLength},
+        /* suffix: HuffmanLookup */ {0, 0},
+    };
+  }
+
+  // Keep `prefixLength` bits from `bits`.
+  // Pad the rest with 0s to build the suffix.
+  const uint8_t shift = bitLength - prefixLength;
+  switch (shift) {
+    case 0:  // Special case, as we can't >> 32
+      return {
+          /* prefix: HuffmanLookup */ {bits, prefixLength},
+          /* suffix: HuffmanLookup */ {0, 0},
+      };
+    case 32:  // Special case, as we can't >> 32
+      return {
+          /* prefix: HuffmanLookup */ {0, prefixLength},
+          /* suffix: HuffmanLookup */ {bits, shift},
+      };
+  }
+  return {
+      /* prefix: HuffmanLookup */ {bits >> shift, prefixLength},
+      /* suffix: HuffmanLookup */
+      {bits & (mozilla::MaxValue<uint32_t>::value >> (32 - shift)), shift},
+  };
+}
+
 mozilla::detail::IntegerRange<size_t> HuffmanLookup::suffixes(
     uint8_t expectedBitLength) const {
   if (expectedBitLength <= bitLength) {
     // We have too many bits, we need to truncate the HuffmanLookup,
     // then return a single element.
     const uint8_t shearing = bitLength - expectedBitLength;
     const size_t first = size_t(bits) >> shearing;
     const size_t last = first;
--- a/js/src/frontend/BinASTTokenReaderContext.h
+++ b/js/src/frontend/BinASTTokenReaderContext.h
@@ -45,16 +45,22 @@ struct NormalizedInterfaceAndField {
   const BinASTInterfaceAndField identity;
   explicit NormalizedInterfaceAndField(BinASTInterfaceAndField identity)
       : identity(identity == BinASTInterfaceAndField::
                                  StaticMemberAssignmentTarget__Property
                      ? BinASTInterfaceAndField::StaticMemberExpression__Property
                      : identity) {}
 };
 
+template <typename T>
+struct Split {
+  T prefix;
+  T suffix;
+};
+
 // A bunch of bits used to lookup a value in a Huffman table. In most cases,
 // these are the 32 leading bits of the underlying bit stream.
 //
 // In a Huffman table, keys have variable bitlength. Consequently, we only know
 // the bitlength of the key *after* we have performed the lookup. A
 // `HuffmanLookup` is a data structure contained at least as many bits as
 // needed to perform the lookup.
 //
@@ -78,16 +84,24 @@ struct HuffmanLookup {
   //
   // Note: This only makes sense if `bitLength <= this.bitLength`.
   //
   // So, for instance, if `leadingBits(4)` returns
   // `0b_0000_0000__0000_0000__0000_0000__0000_0100`, this is
   // equal to Huffman Key `0100`.
   uint32_t leadingBits(const uint8_t bitLength) const;
 
+  // Split a HuffmanLookup into a prefix of `prefixBitLength` bits
+  // and a suffix containing the remaining buts.
+  //
+  // If the prefix contains fewer than `prefixBitLength`, it is
+  // padded with lower-weight 0s into a `prefixBitLength`
+  // HuffmanLookup.
+  Split<HuffmanLookup> split(const uint8_t prefixBitLength) const;
+
   // The buffer holding the bits. At this stage, bits are stored
   // in the same order as `HuffmanKey`. See the implementation of
   // `BitBuffer` methods for more details about how this order
   // is implemented.
   //
   // If `bitLength < 32`, the unused highest bits are guaranteed
   // to be 0.
   const uint32_t bits;
@@ -345,19 +359,19 @@ class MapBasedHuffmanTable {
 //
 // # Space complexity
 //
 // After initialization, a `SingleLookupHuffmanTable`
 // requires O(2 ^ max bit length in the table) space:
 //
 // - A vector `values` containing one entry per symbol.
 // - A vector `saturated` containing exactly 2 ^ (max bit length in the
-//   table) entries, which we use to map any combination of `maxBitLength`
+//   table) entries, which we use to map any combination of `largestBitLength`
 //   bits onto the only `HuffmanEntry` that may be reached by a prefix
-//   of these `maxBitLength` bits. See below for more details.
+//   of these `largestBitLength` bits. See below for more details.
 //
 // # Algorithm
 //
 // Consider the following Huffman table
 //
 // Symbol | Binary Code  | Int value of Code | Bit Length
 // ------ | ------------ | ----------------- | ----------
 // A      | 11000        | 24                | 5
@@ -405,19 +419,27 @@ class MapBasedHuffmanTable {
 //
 // In the current implementation, to save some space, we have
 // two distinct arrays, one (`values`) with a single instance of each
 // symbols bit length, and one (`saturated`) with indices into that
 // array.
 template <typename T>
 class SingleLookupHuffmanTable {
  public:
+  // An index into table `values`.
+  // We use `uint8_t` instead of `size_t` to limit the space
+  // used by the table.
+  using InternalIndex = uint8_t;
+
+  // The largest bit length that may be represented by this table.
+  static const uint8_t MAX_BIT_LENGTH = sizeof(InternalIndex) * 8;
+
   explicit SingleLookupHuffmanTable(JSContext* cx)
-      : values(cx), saturated(cx), maxBitLength(-1) {}
-  SingleLookupHuffmanTable(SingleLookupHuffmanTable&& other) noexcept = default;
+      : values(cx), saturated(cx), largestBitLength(-1) {}
+  SingleLookupHuffmanTable(SingleLookupHuffmanTable&& other) = default;
 
   // Initialize a Huffman table containing a single value.
   JS::Result<Ok> initWithSingleValue(JSContext* cx, T&& value);
 
   // Initialize a Huffman table containing `numberOfSymbols`.
   // Symbols must be added with `addSymbol`.
   // If you initialize with `initStart`, you MUST call `initComplete()`
   // at the end of initialization.
@@ -454,46 +476,273 @@ class SingleLookupHuffmanTable {
     bool operator!=(const Iterator& other) const;
 
    private:
     const HuffmanEntry<T>* position;
   };
   Iterator begin() const { return Iterator(values.begin()); }
   Iterator end() const { return Iterator(values.end()); }
 
+ private:
+  // The entries in this Huffman Table, sorted in the order of insertion.
+  //
+  // Invariant (once `init*` has been called):
+  // - Length is the number of values inserted in the table.
+  // - for all i, `values[i].bitLength <= largestBitLength`.
+  Vector<HuffmanEntry<T>> values;
+
+  // The entries in this Huffman table, prepared for lookup.
+  //
+  // Invariant (once `init*` has been called):
+  // - Length is `1 << largestBitLength`.
+  // - for all i, `saturated[i] < values.length()`
+  Vector<InternalIndex> saturated;
+
+  // The maximal bitlength of a value in this table.
+  //
+  // Invariant (once `init*` has been called):
+  // - `largestBitLength <= MAX_CODE_BIT_LENGTH`
+  uint8_t largestBitLength;
+
+  friend class HuffmanPreludeReader;
+};
+
+/// A table designed to support fast lookup in large sets of data.
+/// In most cases, lookup will be slower than a `SingleLookupHuffmanTable`
+/// but, particularly in heavily unbalanced trees, the table will
+/// take ~2^prefix_len fewer internal entries than a `SingleLookupHuffmanTable`.
+///
+/// Typically, use this table whenever codes range between 10 and 20 bits.
+///
+/// # Time complexity
+///
+/// A lookup in `MultiLookupHuffmanTable` will also take constant time:
+///
+/// - a constant-time lookup to determine into which sub-table to perform the
+/// lookup;
+/// - a constant-time lookup into the sub-table;
+/// - a constant-time lookup into the array of values.
+///
+///
+/// # Space complexity
+///
+/// TBD. Highly dependent on the shape of the Huffman Tree.
+///
+///
+/// # Algorithm
+///
+/// Consider the following Huffman table
+///
+/// Symbol | Binary Code  | Bit Length
+/// ------ | ------------ | ----------
+/// A      | 11000        | 5
+/// B      | 11001        | 5
+/// C      | 1101         | 4
+/// D      | 100          | 3
+/// E      | 101          | 3
+/// F      | 111          | 3
+/// G      | 00           | 2
+/// H      | 01           | 2
+///
+/// With a prefix length of 3, we will precompute all possible 3-bit prefixes
+/// and split the table across such prefixes. Note that we have picked a
+/// length of 3 bits arbitrarily – in this case it is larger than the
+/// bit length of some symbols.
+///
+/// Prefix | Int Value of Prefix | Symbols   | Max bit length
+/// ------ | ------------------- | --------- | --------------
+/// 000    | 0                   | G         | 0
+/// 001    | 1                   | G         | 0
+/// 010    | 2                   | H         | 0
+/// 011    | 3                   | H         | 0
+/// 100    | 4                   | D         | 0
+/// 101    | 5                   | E         | 0
+/// 110    | 6                   | A, B, C   | 2
+/// 111    | 7                   | F         | 0
+///
+/// For each prefix, we build the table containing the Symbols,
+/// stripping prefix from the Binary Code.
+///
+/// - Prefix 000
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// G      | (none)      | 0          | 2
+///
+/// - Prefix 001
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// G      | (none)      | 0          | 2
+///
+/// - Prefix 010
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | --------------
+/// H      | (none)      | 0          | 2
+///
+/// - Prefix 11
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// H      | (none)      | 0          | 2
+///
+/// - Prefix 100
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// D      | (none)      | 0          | 3
+///
+/// - Prefix 101
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// E      | (none)      | 0          | 3
+///
+/// - Prefix 110
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// A      | 00          | 2          | 5
+/// B      | 01          | 2          | 5
+/// C      | 1           | 1          | 4
+///
+/// - Prefix 111
+///
+/// Symbol | Binary Code | Bit Length | Total Bit Length
+/// ------ | ----------- | ---------- | ----------------
+/// F      | (none)      | 0          | 3
+///
+/// With this transformation, we have represented one table
+/// with an initial max bit length of 5 as:
+///
+/// - 1 table with a max bit length of 2;
+/// - 7 tables with a max bit length of 0.
+///
+/// Consequently, instead of storing 2^5 = 32 internal references,
+/// as we would have done with a SingleLookupHuffmanTable, we only
+/// need to store:
+///
+/// - 7 subtables with 1 reference each;
+/// - 1 subtable with 2^2 = 4 references.
+template <typename T, typename Subtable, uint8_t PrefixBitLength>
+class MultiLookupHuffmanTable {
+ public:
+  // The largest bit length that may be represented by this table.
+  static const uint8_t MAX_BIT_LENGTH =
+      PrefixBitLength + Subtable::MAX_BIT_LENGTH;
+
+  explicit MultiLookupHuffmanTable(JSContext* cx)
+      : cx_(cx),
+        values(cx),
+        subTables(cx),
+        largestBitLength(-1)
+#ifdef DEBUG
+        ,
+        control(cx)
+#endif  // DEBUG
+  {
+  }
+  MultiLookupHuffmanTable(MultiLookupHuffmanTable&& other) = default;
+
+  // Initialize a Huffman table containing `numberOfSymbols`.
+  // Symbols must be added with `addSymbol`.
+  // If you initialize with `initStart`, you MUST call `initComplete()`
+  // at the end of initialization.
+  JS::Result<Ok> initStart(JSContext* cx, size_t numberOfSymbols,
+                           uint8_t largestBitLength);
+
+  JS::Result<Ok> initComplete();
+
+  // Add a `(bit, bits_length) => value` mapping.
+  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bits_length, T&& value);
+
+  MultiLookupHuffmanTable() = delete;
+  MultiLookupHuffmanTable(MultiLookupHuffmanTable&) = delete;
+
+  // Lookup a value in the table.
+  //
+  // Return an entry with a value of `nullptr` if the value is not in the table.
+  //
+  // The lookup may advance `key` by `[0, key.bitLength]` bits. Typically, in a
+  // table with a single instance, or if the value is not in the table, it
+  // will advance by 0 bits. The caller is responsible for advancing its
+  // bitstream by `result.key.bitLength` bits.
+  HuffmanEntry<const T*> lookup(HuffmanLookup key) const;
+
+  // The number of values in the table.
+  size_t length() const { return values.length(); }
+
+  // Iterating in the order of insertion.
+  struct Iterator {
+    explicit Iterator(const HuffmanEntry<T>* position);
+    void operator++();
+    const T* operator*() const;
+    bool operator==(const Iterator& other) const;
+    bool operator!=(const Iterator& other) const;
+
+   private:
+    const HuffmanEntry<T>* position;
+  };
+  Iterator begin() const { return Iterator(values.begin()); }
+  Iterator end() const { return Iterator(values.end()); }
+
  public:
   // An index into table `values`.
   // We use `uint8_t` instead of `size_t` to limit the space
   // used by the table.
   using InternalIndex = uint8_t;
 
  private:
+  JSContext* cx_;
+
   // The entries in this Huffman Table, sorted in the order of insertion.
   //
   // Invariant (once `init*` has been called):
   // - Length is the number of values inserted in the table.
-  // - for all i, `values[i].bitLength <= maxBitLength`.
+  // - for all i, `values[i].bitLength <= largestBitLength`.
+  //
+  // FIXME: In a ThreeLookupsHuffmanTable, we currently store each value
+  // three times. We could at least get down to twice.
   Vector<HuffmanEntry<T>> values;
 
-  // The entries in this Huffman table, prepared for lookup.
+  // A mapping from 0..2^prefixBitLen such that index `i`
+  // maps to a subtable that holds all values associated
+  // with a key that starts with `HuffmanKey(i, prefixBitLen)`.
   //
-  // Invariant (once `init*` has been called):
-  // - Length is `1 << maxBitLength`.
-  // - for all i, `saturated[i] < values.length()`
-  Vector<InternalIndex> saturated;
+  // Note that, to allow the use of smaller tables, keys
+  // inside the subtables have been stripped
+  // from the prefix `HuffmanKey(i, prefixBitLen)`.
+  Vector<Subtable> subTables;
 
   // The maximal bitlength of a value in this table.
   //
   // Invariant (once `init*` has been called):
-  // - `maxBitLength <= MAX_CODE_BIT_LENGTH`
-  uint8_t maxBitLength;
+  // - `largestBitLength <= MAX_CODE_BIT_LENGTH`
+  uint8_t largestBitLength;
+
+#ifdef DEBUG
+  MapBasedHuffmanTable<T> control;
+#endif  // DEBUG
 
   friend class HuffmanPreludeReader;
 };
 
+/// A Huffman table suitable for max bit lengths in [8, 14]
+template <typename T>
+using TwoLookupsHuffmanTable = MultiLookupHuffmanTable<
+    T,
+    SingleLookupHuffmanTable</* external index */ size_t>,
+    6>;
+
+/// A Huffman table suitable for max bit lengths in [15, 20]
+template <typename T>
+using ThreeLookupsHuffmanTable = MultiLookupHuffmanTable<
+    T, TwoLookupsHuffmanTable</* external index */ size_t>, 6>;
+
 // An empty Huffman table. Attempting to get a value from this table is a syntax
 // error. This is the default value for `HuffmanTableValue` and represents all
 // states that may not be reached.
 //
 // Part of variants `HuffmanTableValue`, `HuffmanTableListLength` and
 // `GenericHuffmanTable::implementation`.
 struct HuffmanTableUnreachable {};
 
@@ -520,27 +769,29 @@ struct GenericHuffmanTable {
 
   JS::Result<Ok> initComplete();
 
   // The number of values in the table.
   size_t length() const;
 
   struct Iterator {
     explicit Iterator(typename SingleLookupHuffmanTable<T>::Iterator&&);
-    explicit Iterator(typename MapBasedHuffmanTable<T>::Iterator&&);
+    explicit Iterator(typename TwoLookupsHuffmanTable<T>::Iterator&&);
+    explicit Iterator(typename ThreeLookupsHuffmanTable<T>::Iterator&&);
     Iterator(Iterator&&) = default;
     Iterator(const Iterator&) = default;
     void operator++();
     const T* operator*() const;
     bool operator==(const Iterator& other) const;
     bool operator!=(const Iterator& other) const;
 
    private:
     mozilla::Variant<typename SingleLookupHuffmanTable<T>::Iterator,
-                     typename MapBasedHuffmanTable<T>::Iterator>
+                     typename TwoLookupsHuffmanTable<T>::Iterator,
+                     typename ThreeLookupsHuffmanTable<T>::Iterator>
         implementation;
   };
 
   // Iterating in the order of insertion.
   Iterator begin() const;
   Iterator end() const;
 
   // Lookup a value in the table.
@@ -549,18 +800,18 @@ struct GenericHuffmanTable {
   //
   // The lookup may advance `key` by `[0, key.bitLength]` bits. Typically, in a
   // table with a single instance, or if the value is not in the table, it
   // will advance by 0 bits. The caller is responsible for advancing its
   // bitstream by `result.key.bitLength` bits.
   HuffmanEntry<const T*> lookup(HuffmanLookup key) const;
 
  private:
-  mozilla::Variant<SingleLookupHuffmanTable<T>, MapBasedHuffmanTable<T>,
-                   HuffmanTableUnreachable>
+  mozilla::Variant<SingleLookupHuffmanTable<T>, TwoLookupsHuffmanTable<T>,
+                   ThreeLookupsHuffmanTable<T>, HuffmanTableUnreachable>
       implementation;
 };
 
 // While reading the Huffman prelude, whenever we first encounter a
 // `HuffmanTableUnreachable`, we replace it with a `HuffmanTableInitializing`
 // to mark that we should not attempt to read/initialize it again.
 //
 // Attempting to get a value from this table is an internal error.