--- a/js/src/gc/NurseryAwareHashMap.h
+++ b/js/src/gc/NurseryAwareHashMap.h
@@ -65,171 +65,101 @@ class UnsafeBareReadBarriered : public R
 template <typename Key,
           typename Value,
           typename HashPolicy = DefaultHasher<Key>,
           typename AllocPolicy = TempAllocPolicy>
 class NurseryAwareHashMap
 {
     using BarrieredValue = detail::UnsafeBareReadBarriered<Value>;
     using MapType = GCRekeyableHashMap<Key, BarrieredValue, HashPolicy, AllocPolicy>;
-
-    // Contains entries that have a nursery-allocated key or value (or both).
-    MapType nurseryMap_;
+    MapType map;
 
-    // All entries in this map have a tenured key and value.
-    MapType tenuredMap_;
-
-    // Keys and values usually have the same lifetime (for the WrapperMap we
-    // ensure this when we allocate the wrapper object). If this flag is set,
-    // it means nurseryMap_ contains a tenured key with a nursery allocated
-    // value.
-    bool nurseryMapContainsTenuredKeys_;
+    // Keep a list of all keys for which JS::GCPolicy<Key>::isTenured is false.
+    // This lets us avoid a full traveral of the map on each minor GC, keeping
+    // the minor GC times proportional to the nursery heap size.
+    Vector<Key, 0, AllocPolicy> nurseryEntries;
 
   public:
     using Lookup = typename MapType::Lookup;
-
-    class Ptr {
-        friend class NurseryAwareHashMap;
-
-        typename MapType::Ptr ptr_;
-        bool isNurseryMap_;
-
-      public:
-        Ptr(typename MapType::Ptr ptr, bool isNurseryMap)
-          : ptr_(ptr), isNurseryMap_(isNurseryMap)
-        {}
+    using Ptr = typename MapType::Ptr;
+    using Range = typename MapType::Range;
 
-        const typename MapType::Entry& operator*() const { return *ptr_; }
-        const typename MapType::Entry* operator->() const { return &*ptr_; }
-
-        bool found() const { return ptr_.found(); }
-        explicit operator bool() const { return bool(ptr_); }
-    };
+    explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy()) : map(a) {}
 
-    explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy())
-      : nurseryMap_(a), tenuredMap_(a), nurseryMapContainsTenuredKeys_(false)
-    {}
-
-    MOZ_MUST_USE bool init(uint32_t len = 16) {
-        return nurseryMap_.init(len) && tenuredMap_.init(len);
-    }
-
-    bool empty() const { return nurseryMap_.empty() && tenuredMap_.empty(); }
+    MOZ_MUST_USE bool init(uint32_t len = 16) { return map.init(len); }
 
-    Ptr lookup(const Lookup& l) const {
-        if (JS::GCPolicy<Key>::isTenured(l)) {
-            // If we find the key in the tenuredMap_, we're done. If we don't
-            // find it there and we know nurseryMap_ contains tenured keys
-            // (hopefully uncommon), we have to try nurseryMap_ as well.
-            typename MapType::Ptr p = tenuredMap_.lookup(l);
-            if (p || !nurseryMapContainsTenuredKeys_)
-                return Ptr(p, /* isNurseryMap = */ false);
-        }
-        return Ptr(nurseryMap_.lookup(l), /* isNurseryMap = */ true);
-    }
-
-    void remove(Ptr p) {
-        if (p.isNurseryMap_)
-            nurseryMap_.remove(p.ptr_);
-        else
-            tenuredMap_.remove(p.ptr_);
-    }
-
-    class Enum {
-        // First iterate over the nursery map. When nurseryEnum_ becomes
-        // empty() we switch to tenuredEnum_.
-        typename MapType::Enum nurseryEnum_;
-        typename MapType::Enum tenuredEnum_;
-
-        const typename MapType::Enum& currentEnum() const {
-            return nurseryEnum_.empty() ? tenuredEnum_ : nurseryEnum_;
-        }
-        typename MapType::Enum& currentEnum() {
-            return nurseryEnum_.empty() ? tenuredEnum_ : nurseryEnum_;
-        }
-
-      public:
-        explicit Enum(NurseryAwareHashMap& namap)
-          : nurseryEnum_(namap.nurseryMap_), tenuredEnum_(namap.tenuredMap_)
-        {}
-
-        typename MapType::Entry& front() const { return currentEnum().front(); }
-        void popFront() { currentEnum().popFront(); }
-        void removeFront() { currentEnum().removeFront(); }
-
-        bool empty() const { return nurseryEnum_.empty() && tenuredEnum_.empty(); }
+    bool empty() const { return map.empty(); }
+    Ptr lookup(const Lookup& l) const { return map.lookup(l); }
+    void remove(Ptr p) { map.remove(p); }
+    Range all() const { return map.all(); }
+    struct Enum : public MapType::Enum {
+        explicit Enum(NurseryAwareHashMap& namap) : MapType::Enum(namap.map) {}
     };
-
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
-        size_t size = nurseryMap_.sizeOfExcludingThis(mallocSizeOf);
-        size += tenuredMap_.sizeOfExcludingThis(mallocSizeOf);
-        return size;
+        return map.sizeOfExcludingThis(mallocSizeOf);
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
-        size_t size = nurseryMap_.sizeOfIncludingThis(mallocSizeOf);
-        size += tenuredMap_.sizeOfIncludingThis(mallocSizeOf);
-        return size;
-    }
-
-    MOZ_MUST_USE bool putNew(const Key& k, const Value& v) {
-        MOZ_ASSERT(!tenuredMap_.has(k));
-        MOZ_ASSERT(!nurseryMap_.has(k));
-
-        bool tenuredKey = JS::GCPolicy<Key>::isTenured(k);
-        if (tenuredKey && JS::GCPolicy<Value>::isTenured(v))
-            return tenuredMap_.putNew(k, v);
-
-        if (tenuredKey)
-            nurseryMapContainsTenuredKeys_ = true;
-
-        return nurseryMap_.putNew(k, v);
+        return map.sizeOfIncludingThis(mallocSizeOf);
     }
 
     MOZ_MUST_USE bool put(const Key& k, const Value& v) {
-        // For simplicity, just remove the entry and forward to putNew for now.
-        // Performance-sensitive callers should prefer putNew.
-        if (Ptr p = lookup(k))
-            remove(p);
-        return putNew(k, v);
+        auto p = map.lookupForAdd(k);
+        if (p) {
+            if (!JS::GCPolicy<Key>::isTenured(k) || !JS::GCPolicy<Value>::isTenured(v)) {
+                if (!nurseryEntries.append(k))
+                    return false;
+            }
+            p->value() = v;
+            return true;
+        }
+
+        bool ok = map.add(p, k, v);
+        if (!ok)
+            return false;
+
+        if (!JS::GCPolicy<Key>::isTenured(k) || !JS::GCPolicy<Value>::isTenured(v)) {
+            if (!nurseryEntries.append(k)) {
+                map.remove(k);
+                return false;
+            }
+        }
+
+        return true;
     }
 
     void sweepAfterMinorGC(JSTracer* trc) {
-        for (typename MapType::Enum e(nurseryMap_); !e.empty(); e.popFront()) {
-            auto& key = e.front().key();
-            auto& value = e.front().value();
+        for (auto& key : nurseryEntries) {
+            auto p = map.lookup(key);
+            if (!p)
+                continue;
 
             // Drop the entry if the value is not marked.
-            if (JS::GCPolicy<BarrieredValue>::needsSweep(&value))
+            if (JS::GCPolicy<BarrieredValue>::needsSweep(&p->value())) {
+                map.remove(key);
                 continue;
+            }
 
-            // Insert the key/value in the tenured map, if the value is still
-            // needed.
+            // Update and relocate the key, if the value is still needed.
             //
-            // Note that this currently assumes that each Value will contain a
+            // Note that this currently assumes that all Value will contain a
             // strong reference to Key, as per its use as the
             // CrossCompartmentWrapperMap. We may need to make the following
             // behavior more dynamic if we use this map in other nursery-aware
             // contexts.
-
-            Key keyCopy(key);
-            mozilla::DebugOnly<bool> sweepKey = JS::GCPolicy<Key>::needsSweep(&keyCopy);
+            Key copy(key);
+            mozilla::DebugOnly<bool> sweepKey = JS::GCPolicy<Key>::needsSweep(&copy);
             MOZ_ASSERT(!sweepKey);
-
-            AutoEnterOOMUnsafeRegion oomUnsafe;
-            if (!tenuredMap_.putNew(keyCopy, value))
-                oomUnsafe.crash("NurseryAwareHashMap sweepAfterMinorGC");
+            map.rekeyIfMoved(key, copy);
         }
-
-        nurseryMap_.clear();
-        nurseryMapContainsTenuredKeys_ = false;
+        nurseryEntries.clear();
     }
 
     void sweep() {
-        MOZ_ASSERT(nurseryMap_.empty());
-        tenuredMap_.sweep();
+        MOZ_ASSERT(nurseryEntries.empty());
+        map.sweep();
     }
 };
 
 } // namespace js
 
 namespace JS {
 template <typename T>
 struct GCPolicy<js::detail::UnsafeBareReadBarriered<T>>

--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -921,21 +921,18 @@ JS_TransplantObject(JSContext* cx, Handl
     if (origobj->compartment() != destination) {
         RootedObject newIdentityWrapper(cx, newIdentity);
         AutoCompartment ac(cx, origobj);
         if (!JS_WrapObject(cx, &newIdentityWrapper))
             MOZ_CRASH();
         MOZ_ASSERT(Wrapper::wrappedObject(newIdentityWrapper) == newIdentity);
         if (!JSObject::swap(cx, origobj, newIdentityWrapper))
             MOZ_CRASH();
-        if (!origobj->compartment()->putWrapperMaybeUpdate(cx, CrossCompartmentKey(newIdentity),
-                                                           origv))
-        {
+        if (!origobj->compartment()->putWrapper(cx, CrossCompartmentKey(newIdentity), origv))
             MOZ_CRASH();
-        }
     }
 
     // The new identity object might be one of several things. Return it to avoid
     // ambiguity.
     return newIdentity;
 }
 
 /*

--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -246,33 +246,18 @@ JSCompartment::checkWrapperMapAfterMovin
 
         WrapperMap::Ptr ptr = crossCompartmentWrappers.lookup(e.front().key());
         MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
     }
 }
 #endif
 
 bool
-JSCompartment::putNewWrapper(JSContext* cx, const CrossCompartmentKey& wrapped,
-                             const js::Value& wrapper)
-{
-    MOZ_ASSERT(wrapped.is<JSString*>() == wrapper.isString());
-    MOZ_ASSERT_IF(!wrapped.is<JSString*>(), wrapper.isObject());
-
-    if (!crossCompartmentWrappers.putNew(wrapped, wrapper)) {
-        ReportOutOfMemory(cx);
-        return false;
-    }
-
-    return true;
-}
-
-bool
-JSCompartment::putWrapperMaybeUpdate(JSContext* cx, const CrossCompartmentKey& wrapped,
-                                     const js::Value& wrapper)
+JSCompartment::putWrapper(JSContext* cx, const CrossCompartmentKey& wrapped,
+                          const js::Value& wrapper)
 {
     MOZ_ASSERT(wrapped.is<JSString*>() == wrapper.isString());
     MOZ_ASSERT_IF(!wrapped.is<JSString*>(), wrapper.isObject());
 
     if (!crossCompartmentWrappers.put(wrapped, wrapper)) {
         ReportOutOfMemory(cx);
         return false;
     }
@@ -353,17 +338,17 @@ JSCompartment::wrap(JSContext* cx, Mutab
         strp.set(p->value().get().toString());
         return true;
     }
 
     /* No dice. Make a copy, and cache it. */
     JSString* copy = CopyStringPure(cx, str);
     if (!copy)
         return false;
-    if (!putNewWrapper(cx, CrossCompartmentKey(key), StringValue(copy)))
+    if (!putWrapper(cx, CrossCompartmentKey(key), StringValue(copy)))
         return false;
 
     strp.set(copy);
     return true;
 }
 
 bool
 JSCompartment::getNonWrapperObjectForCurrentCompartment(JSContext* cx, MutableHandleObject obj)
@@ -443,17 +428,17 @@ JSCompartment::getOrCreateWrapper(JSCont
     RootedObject wrapper(cx, wrap(cx, existing, obj));
     if (!wrapper)
         return false;
 
     // We maintain the invariant that the key in the cross-compartment wrapper
     // map is always directly wrapped by the value.
     MOZ_ASSERT(Wrapper::wrappedObject(wrapper) == &key.get().toObject());
 
-    if (!putNewWrapper(cx, CrossCompartmentKey(key), ObjectValue(*wrapper))) {
+    if (!putWrapper(cx, CrossCompartmentKey(key), ObjectValue(*wrapper))) {
         // Enforce the invariant that all cross-compartment wrapper object are
         // in the map by nuking the wrapper if we couldn't add it.
         // Unfortunately it's possible for the wrapper to still be marked if we
         // took this path, for example if the object metadata callback stashes a
         // reference to it.
         if (wrapper->is<CrossCompartmentWrapperObject>())
             NukeCrossCompartmentWrapper(cx, wrapper);
         return false;

--- a/js/src/jscompartment.h
+++ b/js/src/jscompartment.h
@@ -474,16 +474,19 @@ struct JSCompartment
 
   private:
     const js::AllocationMetadataBuilder *allocationMetadataBuilder;
 
     js::SavedStacks              savedStacks_;
 
     js::WrapperMap               crossCompartmentWrappers;
 
+    using CCKeyVector = mozilla::Vector<js::CrossCompartmentKey, 0, js::SystemAllocPolicy>;
+    CCKeyVector                  nurseryCCKeys;
+
     // The global environment record's [[VarNames]] list that contains all
     // names declared using FunctionDeclaration, GeneratorDeclaration, and
     // VariableDeclaration declarations in global code in this compartment.
     // Names are only removed from this list by a |delete IdentifierReference|
     // that successfully removes that global property.
     JS::GCHashSet<JSAtom*,
                   js::DefaultHasher<JSAtom*>,
                   js::SystemAllocPolicy> varNames_;
@@ -637,20 +640,18 @@ struct JSCompartment
     MOZ_MUST_USE inline bool wrap(JSContext* cx, JS::MutableHandleValue vp);
 
     MOZ_MUST_USE bool wrap(JSContext* cx, js::MutableHandleString strp);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandleObject obj);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandle<js::PropertyDescriptor> desc);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandle<JS::GCVector<JS::Value>> vec);
     MOZ_MUST_USE bool rewrap(JSContext* cx, JS::MutableHandleObject obj, JS::HandleObject existing);
 
-    MOZ_MUST_USE bool putNewWrapper(JSContext* cx, const js::CrossCompartmentKey& wrapped,
-                                    const js::Value& wrapper);
-    MOZ_MUST_USE bool putWrapperMaybeUpdate(JSContext* cx, const js::CrossCompartmentKey& wrapped,
-                                            const js::Value& wrapper);
+    MOZ_MUST_USE bool putWrapper(JSContext* cx, const js::CrossCompartmentKey& wrapped,
+                                 const js::Value& wrapper);
 
     js::WrapperMap::Ptr lookupWrapper(const js::Value& wrapped) const {
         return crossCompartmentWrappers.lookup(js::CrossCompartmentKey(wrapped));
     }
 
     void removeWrapper(js::WrapperMap::Ptr p) {
         crossCompartmentWrappers.remove(p);
     }

--- a/js/src/proxy/CrossCompartmentWrapper.cpp
+++ b/js/src/proxy/CrossCompartmentWrapper.cpp
@@ -615,21 +615,18 @@ js::RemapWrapper(JSContext* cx, JSObject
 
     // Before swapping, this wrapper came out of wrap(), which enforces the
     // invariant that the wrapper in the map points directly to the key.
     MOZ_ASSERT(Wrapper::wrappedObject(wobj) == newTarget);
 
     // Update the entry in the compartment's wrapper map to point to the old
     // wrapper, which has now been updated (via reuse or swap).
     MOZ_ASSERT(wobj->is<WrapperObject>());
-    if (!wcompartment->putWrapperMaybeUpdate(cx, CrossCompartmentKey(newTarget),
-                                             ObjectValue(*wobj)))
-    {
+    if (!wcompartment->putWrapper(cx, CrossCompartmentKey(newTarget), ObjectValue(*wobj)))
         MOZ_CRASH();
-    }
 }
 
 // Remap all cross-compartment wrappers pointing to |oldTarget| to point to
 // |newTarget|. All wrappers are recomputed.
 JS_FRIEND_API(bool)
 js::RemapAllWrappersForObject(JSContext* cx, JSObject* oldTargetArg,
                               JSObject* newTargetArg)
 {

--- a/js/src/vm/Debugger.cpp
+++ b/js/src/vm/Debugger.cpp
@@ -1133,17 +1133,17 @@ Debugger::wrapEnvironment(JSContext* cx,
             return false;
 
         if (!p.add(cx, environments, env, envobj)) {
             NukeDebuggerWrapper(envobj);
             return false;
         }
 
         CrossCompartmentKey key(object, env, CrossCompartmentKey::DebuggerEnvironment);
-        if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*envobj))) {
+        if (!object->compartment()->putWrapper(cx, key, ObjectValue(*envobj))) {
             NukeDebuggerWrapper(envobj);
             environments.remove(env);
             return false;
         }
 
         result.set(envobj);
     }
 
@@ -1220,17 +1220,17 @@ Debugger::wrapDebuggeeObject(JSContext* 
 
         if (!p.add(cx, objects, obj, dobj)) {
             NukeDebuggerWrapper(dobj);
             return false;
         }
 
         if (obj->compartment() != object->compartment()) {
             CrossCompartmentKey key(object, obj, CrossCompartmentKey::DebuggerObject);
-            if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*dobj))) {
+            if (!object->compartment()->putWrapper(cx, key, ObjectValue(*dobj))) {
                 NukeDebuggerWrapper(dobj);
                 objects.remove(obj);
                 ReportOutOfMemory(cx);
                 return false;
             }
         }
 
         result.set(dobj);
@@ -5515,17 +5515,17 @@ Debugger::wrapVariantReferent(JSContext*
         if (!wrapper)
             return nullptr;
 
         if (!p.add(cx, map, untaggedReferent, wrapper)) {
             NukeDebuggerWrapper(wrapper);
             return nullptr;
         }
 
-        if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*wrapper))) {
+        if (!object->compartment()->putWrapper(cx, key, ObjectValue(*wrapper))) {
             NukeDebuggerWrapper(wrapper);
             map.remove(untaggedReferent);
             ReportOutOfMemory(cx);
             return nullptr;
         }
 
     }