Bug 1587678 - Part 2: Use FixedLengthVector when the size is known at the allocation. r=Yoric
☠☠ backed out by 31f16b9b5863 ☠ ☠
authorTooru Fujisawa <arai_a@mac.com>
Mon, 21 Oct 2019 14:31:53 +0000
changeset 498380 16e2bc05dda0eca201e9752839d51a86841677b1
parent 498379 0750949021602aed8c36a833c258092522c448ee
child 498381 00eab227096178b7d95e0a375cb25a300095219b
push id36717
push usernbeleuzu@mozilla.com
push dateMon, 21 Oct 2019 21:51:55 +0000
treeherdermozilla-central@563f437f24b9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersYoric
bugs1587678
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 1587678 - Part 2: Use FixedLengthVector when the size is known at the allocation. r=Yoric Differential Revision: https://phabricator.services.mozilla.com/D49564
js/src/frontend/BinASTTokenReaderContext.cpp
js/src/frontend/BinASTTokenReaderContext.h
--- a/js/src/frontend/BinASTTokenReaderContext.cpp
+++ b/js/src/frontend/BinASTTokenReaderContext.cpp
@@ -1,19 +1,20 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  * vim: set ts=8 sts=2 et sw=2 tw=80:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "frontend/BinASTTokenReaderContext.h"
 
-#include "mozilla/IntegerTypeTraits.h"  // mozilla::MaxValue
-#include "mozilla/Result.h"             // MOZ_TRY*
-#include "mozilla/ScopeExit.h"          // mozilla::MakeScopeExit
+#include "mozilla/IntegerTypeTraits.h"      // mozilla::MaxValue
+#include "mozilla/OperatorNewExtensions.h"  // mozilla::KnownNotNull
+#include "mozilla/Result.h"                 // MOZ_TRY*
+#include "mozilla/ScopeExit.h"              // mozilla::MakeScopeExit
 
 #include <string.h>  // memchr, memcmp, memmove
 
 #include "ds/Sort.h"                 // MergeSort
 #include "frontend/BinAST-macros.h"  // BINJS_TRY*, BINJS_MOZ_TRY*
 #include "gc/Rooting.h"              // RootedAtom
 #include "js/AllocPolicy.h"          // SystemAllocPolicy
 #include "js/StableStringChars.h"    // Latin1Char
@@ -721,23 +722,23 @@ class HuffmanPreludeReader {
         // By format invariant, bit lengths are always non-0
         // and always ranked by increasing order.
         return raiseInvalidTableData(entry.identity_);
       }
 
       // Read and add symbol.
       BINJS_MOZ_TRY_DECL(
           symbol, readSymbol<Entry>(entry, i));  // Symbol is read from disk.
-      MOZ_TRY(table.addSymbol(code, bitLength, symbol));
+      MOZ_TRY(table.addSymbol(i, code, bitLength, symbol));
 
       // Prepare next code.
       code = (code + 1) << (nextBitLength - bitLength);
     }
 
-    MOZ_TRY(table.initComplete());
+    MOZ_TRY(table.initComplete(cx_));
     auxStorageLength_.clear();
     return Ok();
   }
 
   template <typename Entry>
   MOZ_MUST_USE JS::Result<typename Entry::Indexed>
   readMultipleValuesTableAndAssignCode(typename Entry::Table& table,
                                        Entry entry, uint32_t numberOfSymbols) {
@@ -813,23 +814,23 @@ class HuffmanPreludeReader {
                                                 // stop before the terminator.
       MOZ_ASSERT(bitLength > 0);
       MOZ_ASSERT(bitLength <= nextBitLength);
 
       // Read symbol from memory and add it.
       BINJS_MOZ_TRY_DECL(symbol,
                          readSymbol<Entry>(entry, auxStorageLength_[i].index_));
 
-      MOZ_TRY(table.addSymbol(code, bitLength, symbol));
+      MOZ_TRY(table.addSymbol(i, code, bitLength, symbol));
 
       // Prepare next code.
       code = (code + 1) << (nextBitLength - bitLength);
     }
 
-    MOZ_TRY(table.initComplete());
+    MOZ_TRY(table.initComplete(cx_));
 
     auxStorageLength_.clear();
     return Ok();
   }
 
   // Single-argument version: lookup the table using `dictionary_.tableForField`
   // then proceed as two-arguments version.
   template <typename Entry>
@@ -1733,32 +1734,32 @@ const BinASTSymbol* GenericHuffmanTable:
       [](const typename ThreeLookupsHuffmanTable::Iterator& iterator) {
         return iterator.operator->();
       });
 }
 
 GenericHuffmanTable::GenericHuffmanTable(JSContext*)
     : implementation_(HuffmanTableUnreachable{}) {}
 
-JS::Result<Ok> GenericHuffmanTable::initComplete() {
+JS::Result<Ok> GenericHuffmanTable::initComplete(JSContext* cx) {
   return implementation_.match(
       [](SingleEntryHuffmanTable& implementation) -> JS::Result<Ok> {
         MOZ_CRASH("SingleEntryHuffmanTable shouldn't have multiple entries!");
       },
-      [](TwoEntriesHuffmanTable& implementation) -> JS::Result<Ok> {
-        return implementation.initComplete();
+      [cx](TwoEntriesHuffmanTable& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete(cx);
       },
-      [](SingleLookupHuffmanTable& implementation) -> JS::Result<Ok> {
-        return implementation.initComplete();
+      [cx](SingleLookupHuffmanTable& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete(cx);
       },
-      [](TwoLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
-        return implementation.initComplete();
+      [cx](TwoLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete(cx);
       },
-      [](ThreeLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
-        return implementation.initComplete();
+      [cx](ThreeLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete(cx);
       },
       [](HuffmanTableUnreachable&) -> JS::Result<Ok> {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
 typename GenericHuffmanTable::Iterator GenericHuffmanTable::begin() const {
   return implementation_.match(
@@ -1863,46 +1864,47 @@ JS::Result<Ok> GenericHuffmanTable::init
   }
 
   // ...otherwise, we'll need three lookups.
   implementation_ = {mozilla::VariantType<ThreeLookupsHuffmanTable>{}, cx};
   return implementation_.template as<ThreeLookupsHuffmanTable>().initStart(
       cx, numberOfSymbols, largestBitLength);
 }
 
-JS::Result<Ok> GenericHuffmanTable::addSymbol(uint32_t bits, uint8_t bitLength,
+JS::Result<Ok> GenericHuffmanTable::addSymbol(size_t index, uint32_t bits,
+                                              uint8_t bitLength,
                                               const BinASTSymbol& value) {
   return implementation_.match(
       [](SingleEntryHuffmanTable&) -> JS::Result<Ok> {
         MOZ_CRASH("SingleEntryHuffmanTable shouldn't have multiple entries!");
         return Ok();
       },
-      [bits, bitLength,
+      [index, bits, bitLength,
        value](TwoEntriesHuffmanTable&
                   implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
-        return implementation.addSymbol(bits, bitLength, value);
+        return implementation.addSymbol(index, bits, bitLength, value);
       },
-      [bits, bitLength,
+      [index, bits, bitLength,
        value](SingleLookupHuffmanTable&
                   implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
-        return implementation.addSymbol(bits, bitLength, value);
+        return implementation.addSymbol(index, bits, bitLength, value);
       },
-      [bits, bitLength,
+      [index, bits, bitLength,
        value](TwoLookupsHuffmanTable&
                   implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
-        return implementation.addSymbol(bits, bitLength, value);
+        return implementation.addSymbol(index, bits, bitLength, value);
       },
-      [bits, bitLength,
+      [index, bits, bitLength,
        value = value](ThreeLookupsHuffmanTable&
                           implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
-        return implementation.addSymbol(bits, bitLength, value);
+        return implementation.addSymbol(index, bits, bitLength, value);
       },
       [](HuffmanTableUnreachable&) -> JS::Result<Ok> {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
         return Ok();
       });
 }
 
 HuffmanLookupResult GenericHuffmanTable::lookup(HuffmanLookup key) const {
@@ -1994,49 +1996,42 @@ bool TwoEntriesHuffmanTable::Iterator::o
 bool TwoEntriesHuffmanTable::Iterator::operator!=(const Iterator& other) const {
   return position_ != other.position_;
 }
 
 JS::Result<Ok> TwoEntriesHuffmanTable::initStart(JSContext* cx,
                                                  size_t numberOfSymbols,
                                                  uint8_t largestBitLength) {
   // Make sure that we're initializing.
-  MOZ_ASSERT(length_ == 0);
   MOZ_ASSERT(numberOfSymbols == 2);
   MOZ_ASSERT(largestBitLength == 1);
   return Ok();
 }
 
-JS::Result<Ok> TwoEntriesHuffmanTable::initComplete() {
-  MOZ_ASSERT(length_ == 2);
+JS::Result<Ok> TwoEntriesHuffmanTable::initComplete(JSContext* cx) {
   return Ok();
 }
 
-JS::Result<Ok> TwoEntriesHuffmanTable::addSymbol(uint32_t bits,
+JS::Result<Ok> TwoEntriesHuffmanTable::addSymbol(size_t index, uint32_t bits,
                                                  uint8_t bitLength,
                                                  const BinASTSymbol& value) {
-  MOZ_ASSERT(length_ < 2);
   // Symbols must be ranked by increasing bits length
-  MOZ_ASSERT_IF(length_ == 0, bits == 0);
-  MOZ_ASSERT_IF(length_ == 1, bits == 1);
+  MOZ_ASSERT_IF(index == 0, bits == 0);
+  MOZ_ASSERT_IF(index == 1, bits == 1);
 
   // FIXME: Throw soft error instead of assert.
   MOZ_ASSERT(bitLength == 1);
 
-  values_[length_] = value;
-
-  ++length_;
+  values_[index] = value;
   return Ok();
 }
 
 HuffmanLookupResult TwoEntriesHuffmanTable::lookup(HuffmanLookup key) const {
-  MOZ_ASSERT(length_ == 2);
   // By invariant, bit lengths are 1.
   const auto index = key.leadingBits(1);
-  MOZ_ASSERT(index < length_);
   return HuffmanLookupResult::found(1, &values_[index]);
 }
 
 SingleLookupHuffmanTable::Iterator::Iterator(const HuffmanEntry* position)
     : position_(position) {}
 
 void SingleLookupHuffmanTable::Iterator::operator++() { position_++; }
 
@@ -2059,36 +2054,36 @@ bool SingleLookupHuffmanTable::Iterator:
 }
 
 JS::Result<Ok> SingleLookupHuffmanTable::initStart(JSContext* cx,
                                                    size_t numberOfSymbols,
                                                    uint8_t largestBitLength) {
   MOZ_ASSERT_IF(largestBitLength != 32,
                 (uint32_t(1) << largestBitLength) - 1 <=
                     mozilla::MaxValue<InternalIndex>::value);
-  MOZ_ASSERT(values_.empty());  // Make sure that we're initializing.
+  MOZ_ASSERT(!values_.initialized());  // Make sure that we're initializing.
 
   largestBitLength_ = largestBitLength;
 
-  if (MOZ_UNLIKELY(!values_.initCapacity(numberOfSymbols))) {
+  if (MOZ_UNLIKELY(!values_.allocate(cx, numberOfSymbols))) {
     return cx->alreadyReportedError();
   }
   const size_t saturatedLength = 1 << largestBitLength_;
-  if (MOZ_UNLIKELY(!saturated_.initCapacity(saturatedLength))) {
+  if (MOZ_UNLIKELY(!saturated_.allocate(cx, 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(InternalIndex(-1));
+    saturated_[i] = InternalIndex(-1);
   }
   return Ok();
 }
 
-JS::Result<Ok> SingleLookupHuffmanTable::initComplete() {
+JS::Result<Ok> SingleLookupHuffmanTable::initComplete(JSContext* cx) {
   // Double-check that we've initialized properly.
   MOZ_ASSERT(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(largestBitLength_ == 0);
@@ -2111,28 +2106,26 @@ JS::Result<Ok> SingleLookupHuffmanTable:
     }
   }
   MOZ_ASSERT(foundMaxBitLength);
 #endif  // DEBUG
 
   return Ok();
 }
 
-JS::Result<Ok> SingleLookupHuffmanTable::addSymbol(uint32_t bits,
+JS::Result<Ok> SingleLookupHuffmanTable::addSymbol(size_t index, uint32_t bits,
                                                    uint8_t bitLength,
                                                    const BinASTSymbol& value) {
   MOZ_ASSERT_IF(largestBitLength_ != 0, bitLength != 0);
   MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
   MOZ_ASSERT(bitLength <= largestBitLength_);
 
-  const size_t index = values_.length();
-
   // First add the value to `values_`.
-  // Memory was reserved in `init()`.
-  values_.infallibleEmplaceBack(bits, bitLength, value);
+  new (mozilla::KnownNotNull, &values_[index])
+      HuffmanEntry(bits, bitLength, value);
 
   // Notation: in the following, unless otherwise specified, we consider
   // values with `largestBitLength_` bits exactly.
   //
   // 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;
@@ -2211,59 +2204,63 @@ bool MultiLookupHuffmanTable<Subtable, P
   return position_ != other.position_;
 }
 
 template <typename Subtable, uint8_t PrefixBitLength>
 JS::Result<Ok> MultiLookupHuffmanTable<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(suffixTables_.empty());
+  MOZ_ASSERT(!values_.initialized());  // Make sure that we're initializing.
+  MOZ_ASSERT(!suffixTables_.initialized());
   largestBitLength_ = largestBitLength;
-  if (MOZ_UNLIKELY(!values_.initCapacity(numberOfSymbols))) {
+  if (MOZ_UNLIKELY(!values_.allocate(cx, numberOfSymbols))) {
     return cx->alreadyReportedError();
   }
-  if (MOZ_UNLIKELY(!suffixTables_.initCapacity(1 << PrefixBitLength))) {
+  if (MOZ_UNLIKELY(!suffixTables_.allocate(cx, 1 << PrefixBitLength))) {
     return cx->alreadyReportedError();
   }
   return Ok();
 }
 
 template <typename Subtable, uint8_t PrefixBitLength>
 JS::Result<Ok> MultiLookupHuffmanTable<Subtable, PrefixBitLength>::addSymbol(
-    uint32_t bits, uint8_t bitLength, const BinASTSymbol& value) {
+    size_t index, uint32_t bits, uint8_t bitLength, const BinASTSymbol& value) {
   MOZ_ASSERT_IF(largestBitLength_ != 0, bitLength != 0);
-  MOZ_ASSERT(values_.empty() || values_.back().key().bitLength_ <= bitLength,
+  MOZ_ASSERT(!values_.initialized() ||
+                 values_[index - 1].key().bitLength_ <= bitLength,
              "Symbols must be ranked by increasing bits length");
   MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
 
-  values_.infallibleEmplaceBack(bits, bitLength, value);
+  new (mozilla::KnownNotNull, &values_[index])
+      HuffmanEntry(bits, bitLength, value);
 
   return Ok();
 }
 
 template <typename Subtable, uint8_t PrefixBitLength>
-JS::Result<Ok>
-MultiLookupHuffmanTable<Subtable, PrefixBitLength>::initComplete() {
+JS::Result<Ok> MultiLookupHuffmanTable<Subtable, PrefixBitLength>::initComplete(
+    JSContext* cx) {
   // 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_;
     void addSymbol(uint8_t bitLength) {
       ++numberOfSymbols_;
       if (bitLength > largestBitLength_) {
         largestBitLength_ = bitLength;
       }
     }
   };
-  Vector<Bucket> buckets{cx_};
-  BINJS_TRY(buckets.resize(1 << PrefixBitLength));
+  FixedLengthVector<Bucket> buckets;
+  if (!buckets.allocate(cx, 1 << PrefixBitLength)) {
+    return cx->alreadyReportedError();
+  }
   Bucket shortKeysBucket;
 
   for (const auto& entry : values_) {
     if (entry.key().bitLength_ <= SingleLookupHuffmanTable::MAX_BIT_LENGTH) {
       // If the key is short, we put it in `shortKeys_` instead of
       // `suffixTables`.
       shortKeysBucket.addSymbol(entry.key().bitLength_);
       continue;
@@ -2278,68 +2275,81 @@ MultiLookupHuffmanTable<Subtable, Prefix
     // 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];
       bucket.addSymbol(split.suffix_.bitLength_);
     }
   }
 
+  FixedLengthVector<size_t> suffixTablesIndices;
+  if (MOZ_UNLIKELY(!suffixTablesIndices.allocate(cx, suffixTables_.length()))) {
+    return cx->alreadyReportedError();
+  }
+
   // We may now create the subtables.
+  size_t i = 0;
   for (auto& bucket : buckets) {
-    Subtable sub(cx_);
+    new (mozilla::KnownNotNull, &suffixTables_[i]) Subtable(cx);
+    suffixTablesIndices[i] = 0;
+
     if (bucket.numberOfSymbols_ != 0) {
       // Often, a subtable will end up empty because all the prefixes end up
       // in `shortKeys_`. In such a case, we want to avoid initializing the
       // table.
-      MOZ_TRY(sub.initStart(cx_,
-                            /* numberOfSymbols = */ bucket.numberOfSymbols_,
-                            /* maxBitLength = */ bucket.largestBitLength_));
+      MOZ_TRY(suffixTables_[i].initStart(
+          cx,
+          /* numberOfSymbols = */ bucket.numberOfSymbols_,
+          /* maxBitLength = */ bucket.largestBitLength_));
     }
-    BINJS_TRY(suffixTables_.append(std::move(sub)));
+
+    i++;
   }
 
   // Also, create the shortKeys_ fast lookup.
-  MOZ_TRY(shortKeys_.initStart(cx_, shortKeysBucket.numberOfSymbols_,
+  MOZ_TRY(shortKeys_.initStart(cx, shortKeysBucket.numberOfSymbols_,
                                shortKeysBucket.largestBitLength_));
 
   // Now that all the subtables are created, let's dispatch the values
   // among these tables.
+  size_t shortKeysIndex = 0;
   for (size_t i = 0; i < values_.length(); ++i) {
     const auto& entry = values_[i];
     if (entry.key().bitLength_ <= SingleLookupHuffmanTable::MAX_BIT_LENGTH) {
       // The key fits in `shortKeys_`, let's use this table.
-      MOZ_TRY(shortKeys_.addSymbol(entry.key().bits_, entry.key().bitLength_,
+      MOZ_TRY(shortKeys_.addSymbol(shortKeysIndex++, entry.key().bits_,
+                                   entry.key().bitLength_,
                                    BinASTSymbol::fromSubtableIndex(i)));
       continue;
     }
 
     // Otherwise, use one of the suffix tables.
     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 = suffixTables_[index];
 
       // We may now add a reference to `entry` into the sybtable.
-      MOZ_TRY(sub.addSymbol(split.suffix_.bits_, split.suffix_.bitLength_,
+      MOZ_TRY(sub.addSymbol(suffixTablesIndices[index]++, split.suffix_.bits_,
+                            split.suffix_.bitLength_,
                             BinASTSymbol::fromSubtableIndex(i)));
     }
   }
 
   // Finally, complete initialization of shortKeys_ and subtables.
-  MOZ_TRY(shortKeys_.initComplete());
+  MOZ_TRY(shortKeys_.initComplete(cx));
   for (size_t i = 0; i < buckets.length(); ++i) {
     if (buckets[i].numberOfSymbols_ == 0) {
       // Again, we don't want to initialize empty subtables.
       continue;
     }
     auto& sub = suffixTables_[i];
-    MOZ_TRY(sub.initComplete());
+    MOZ_TRY(sub.initComplete(cx));
   }
 
   return Ok();
 }
 
 template <typename Subtable, uint8_t PrefixBitLength>
 HuffmanLookupResult MultiLookupHuffmanTable<Subtable, PrefixBitLength>::lookup(
     HuffmanLookup key) const {
--- a/js/src/frontend/BinASTTokenReaderContext.h
+++ b/js/src/frontend/BinASTTokenReaderContext.h
@@ -12,16 +12,17 @@
 #include "mozilla/Attributes.h"    // MOZ_MUST_USE, MOZ_STACK_CLASS
 #include "mozilla/IntegerRange.h"  // mozilla::IntegerRange
 #include "mozilla/Maybe.h"         // mozilla::Maybe
 #include "mozilla/Variant.h"       // mozilla::Variant
 
 #include <stddef.h>  // size_t
 #include <stdint.h>  // uint8_t, uint32_t
 
+#include "ds/FixedLengthVector.h"  // FixedLengthVector
 #include "frontend/BinASTRuntimeSupport.h"  // CharSlice, BinASTVariant, BinASTKind, BinASTField, BinASTSourceMetadata
 #include "frontend/BinASTToken.h"
 #include "frontend/BinASTTokenReaderBase.h"  // BinASTTokenReaderBase, SkippableSubTree
 #include "js/AllocPolicy.h"                  // SystemAllocPolicy
 #include "js/HashTable.h"                    // HashMap, DefaultHasher
 #include "js/Result.h"                       // JS::Result, Ok, Error
 #include "js/Vector.h"                       // js::Vector
 
@@ -295,30 +296,31 @@ class SingleEntryHuffmanTable {
   BinASTSymbol value_;
 
   friend class HuffmanPreludeReader;
 };
 
 // An implementation of Huffman Tables for two-entry table.
 class TwoEntriesHuffmanTable {
  public:
-  TwoEntriesHuffmanTable() : length_(0) {}
+  TwoEntriesHuffmanTable() {}
   TwoEntriesHuffmanTable(TwoEntriesHuffmanTable&& other) noexcept = 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 maxBitLength);
 
-  JS::Result<Ok> initComplete();
+  JS::Result<Ok> initComplete(JSContext* cx);
 
   // Add a symbol to a value.
-  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
+  // The symbol is the `index`-th item in this table.
+  JS::Result<Ok> addSymbol(size_t index, uint32_t bits, uint8_t bitLength,
                            const BinASTSymbol& value);
 
   TwoEntriesHuffmanTable(TwoEntriesHuffmanTable&) = delete;
 
   // Lookup a value in the table.
   //
   // The return of this method contains:
   //
@@ -338,41 +340,26 @@ class TwoEntriesHuffmanTable {
     const BinASTSymbol* operator->() const;
     bool operator==(const Iterator& other) const;
     bool operator!=(const Iterator& other) const;
 
    private:
     const BinASTSymbol* position_;
   };
   Iterator begin() const { return Iterator(std::begin(values_)); }
-  Iterator end() const {
-    MOZ_ASSERT(length_ == 2);
-    return Iterator(std::end(values_));
-  }
+  Iterator end() const { return Iterator(std::end(values_)); }
 
   // The number of values in the table.
-  size_t length() const {
-    MOZ_ASSERT(length_ == 2);
-    return 2;
-  }
+  size_t length() const { return 2; }
 
  private:
   // A buffer for the values added to this table.
-  //
-  // Only the interval 0..length_ is considered
-  // initialized memory.
   BinASTSymbol values_[2] = {BinASTSymbol::fromBool(false),
                              BinASTSymbol::fromBool(false)};
 
-  // The number of elements added to the table.
-  // Invariants:
-  // - during initialization, 0 <= length_ <= 2;
-  // - after initialization, length_ == 2;
-  uint8_t length_;
-
   friend class HuffmanPreludeReader;
 };
 
 // An implementation of Huffman Tables as a vector designed to allow
 // constant-time lookups at the expense of high space complexity.
 //
 // # Time complexity
 //
@@ -461,38 +448,37 @@ class SingleLookupHuffmanTable {
     ShortKeys,
   };
 
   // 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, Use use = Use::LeafOfMultiLookupHuffmanTable)
-      : values_(cx),
-        saturated_(cx),
-        largestBitLength_(-1)
+      : largestBitLength_(-1)
 #ifdef DEBUG
         ,
         use_(use)
 #endif  // DEBUG
   {
   }
   SingleLookupHuffmanTable(SingleLookupHuffmanTable&& 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 maxBitLength);
 
-  JS::Result<Ok> initComplete();
+  JS::Result<Ok> initComplete(JSContext* cx);
 
   // Add a `(bit, bitLength) => value` mapping.
-  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
+  // The symbol is the `index`-th item in this table.
+  JS::Result<Ok> addSymbol(size_t index, uint32_t bits, uint8_t bitLength,
                            const BinASTSymbol& value);
 
   SingleLookupHuffmanTable() = delete;
   SingleLookupHuffmanTable(SingleLookupHuffmanTable&) = delete;
 
   // Lookup a value in the table.
   //
   // The return of this method contains:
@@ -525,24 +511,24 @@ class SingleLookupHuffmanTable {
   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> values_;
+  FixedLengthVector<HuffmanEntry> 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_;
+  FixedLengthVector<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_;
 
 #ifdef DEBUG
@@ -691,32 +677,31 @@ 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),
         shortKeys_(cx, SingleLookupHuffmanTable::Use::ShortKeys),
-        values_(cx),
-        suffixTables_(cx),
         largestBitLength_(-1) {}
   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();
+  JS::Result<Ok> initComplete(JSContext* cx);
 
   // Add a `(bit, bitLength) => value` mapping.
-  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
+  // The symbol is the `index`-th item in this table.
+  JS::Result<Ok> addSymbol(size_t index, uint32_t bits, uint8_t bitLength,
                            const BinASTSymbol& value);
 
   MultiLookupHuffmanTable() = delete;
   MultiLookupHuffmanTable(MultiLookupHuffmanTable&) = delete;
 
   // Lookup a value in the table.
   //
   // The return of this method contains:
@@ -764,26 +749,26 @@ class MultiLookupHuffmanTable {
   // 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_`.
   //
   // FIXME: In a ThreeLookupsHuffmanTable, we currently store each value
   // three times. We could at least get down to twice.
-  Vector<HuffmanEntry> values_;
+  FixedLengthVector<HuffmanEntry> values_;
 
   // 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)`.
   //
   // Note that, to allow the use of smaller tables, keys
   // inside the subtables have been stripped
   // from the prefix `HuffmanKey(i, prefixBitLen)`.
-  Vector<Subtable> suffixTables_;
+  FixedLengthVector<Subtable> suffixTables_;
 
   // 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;
@@ -818,20 +803,21 @@ struct GenericHuffmanTable {
   // 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 maxBitLength);
 
   // Add a `(bit, bitLength) => value` mapping.
-  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
+  // The symbol is the `index`-th item in this table.
+  JS::Result<Ok> addSymbol(size_t index, uint32_t bits, uint8_t bitLength,
                            const BinASTSymbol& value);
 
-  JS::Result<Ok> initComplete();
+  JS::Result<Ok> initComplete(JSContext* cx);
 
   // The number of values in the table.
   size_t length() const;
 
   struct Iterator {
     explicit Iterator(typename SingleEntryHuffmanTable::Iterator&&);
     explicit Iterator(typename TwoEntriesHuffmanTable::Iterator&&);
     explicit Iterator(typename SingleLookupHuffmanTable::Iterator&&);