Bug 1500064 - Use GCHashSet in property enumeration code. r=jonco
authorJan de Mooij <jdemooij@mozilla.com>
Fri, 19 Oct 2018 10:24:17 +0200
changeset 490576 7141a7da10208223603df9d309e1d738dbf91892
parent 490575 a83370778faf43b69e9a3b3540d25ce8b51da6a8
child 490577 ff70442b73b376bc5f135aab4390ac1b5b3a662c
push id247
push userfmarier@mozilla.com
push dateSat, 27 Oct 2018 01:06:44 +0000
reviewersjonco
bugs1500064, 1481998
milestone64.0a1
Bug 1500064 - Use GCHashSet in property enumeration code. r=jonco This changes Maybe<IdSet> to Rooted<IdSet>. I think the Maybe<> is not buying us much because HashTable's storage is now lazily allocated (bug 1481998). I didn't notice any regressions in micro-benchmarks; this patch might be a small improvement actually. Differential Revision: https://phabricator.services.mozilla.com/D9225
js/src/vm/Iteration.cpp
--- a/js/src/vm/Iteration.cpp
+++ b/js/src/vm/Iteration.cpp
@@ -94,43 +94,38 @@ NativeIterator::trace(JSTracer* trc)
                       // Properties begin life non-null and never *become*
                       // null.  (Deletion-suppression will shift trailing
                       // properties over a deleted property in the properties
                       // array, but it doesn't null them out.)
                       TraceEdge(trc, &prop, "prop");
                   });
 }
 
-typedef HashSet<jsid, DefaultHasher<jsid>> IdSet;
+using IdSet = GCHashSet<jsid, DefaultHasher<jsid>>;
 
 template <bool CheckForDuplicates>
 static inline bool
 Enumerate(JSContext* cx, HandleObject pobj, jsid id,
-          bool enumerable, unsigned flags, Maybe<IdSet>& ht, AutoIdVector* props)
+          bool enumerable, unsigned flags, MutableHandle<IdSet> visited, AutoIdVector* props)
 {
     if (CheckForDuplicates) {
-        if (!ht) {
-            // Most of the time there are only a handful of entries.
-            ht.emplace(cx, 5);
-        }
-
         // If we've already seen this, we definitely won't add it.
-        IdSet::AddPtr p = ht->lookupForAdd(id);
+        IdSet::AddPtr p = visited.lookupForAdd(id);
         if (MOZ_UNLIKELY(!!p)) {
             return true;
         }
 
-        // It's not necessary to add properties to the hash table at the end of
+        // It's not necessary to add properties to the hash set at the end of
         // the prototype chain, but custom enumeration behaviors might return
         // duplicated properties, so always add in such cases.
         if (pobj->is<ProxyObject>() ||
             pobj->staticPrototype() ||
             pobj->getClass()->getNewEnumerate())
         {
-            if (!ht->add(p, id)) {
+            if (!visited.add(p, id)) {
                 return false;
             }
         }
     }
 
     if (!enumerable && !(flags & JSITER_HIDDEN)) {
         return true;
     }
@@ -142,18 +137,18 @@ Enumerate(JSContext* cx, HandleObject po
         return true;
     }
 
     return props->append(id);
 }
 
 template <bool CheckForDuplicates>
 static bool
-EnumerateExtraProperties(JSContext* cx, HandleObject obj, unsigned flags, Maybe<IdSet>& ht,
-                         AutoIdVector* props)
+EnumerateExtraProperties(JSContext* cx, HandleObject obj, unsigned flags,
+                         MutableHandle<IdSet> visited, AutoIdVector* props)
 {
     MOZ_ASSERT(obj->getClass()->getNewEnumerate());
 
     AutoIdVector properties(cx);
     bool enumerableOnly = !(flags & JSITER_HIDDEN);
     if (!obj->getClass()->getNewEnumerate()(cx, obj, properties, enumerableOnly)) {
         return false;
     }
@@ -162,17 +157,17 @@ EnumerateExtraProperties(JSContext* cx, 
     for (size_t n = 0; n < properties.length(); n++) {
         id = properties[n];
 
         // The enumerate hook does not indicate whether the properties
         // it returns are enumerable or not. Since we already passed
         // `enumerableOnly` to the hook to filter out non-enumerable
         // properties, it doesn't really matter what we pass here.
         bool enumerable = true;
-        if (!Enumerate<CheckForDuplicates>(cx, obj, id, enumerable, flags, ht, props)) {
+        if (!Enumerate<CheckForDuplicates>(cx, obj, id, enumerable, flags, visited, props)) {
             return false;
         }
     }
 
     return true;
 }
 
 static bool
@@ -182,47 +177,48 @@ SortComparatorIntegerIds(jsid a, jsid b,
     MOZ_ALWAYS_TRUE(IdIsIndex(a, &indexA));
     MOZ_ALWAYS_TRUE(IdIsIndex(b, &indexB));
     *lessOrEqualp = (indexA <= indexB);
     return true;
 }
 
 template <bool CheckForDuplicates>
 static bool
-EnumerateNativeProperties(JSContext* cx, HandleNativeObject pobj, unsigned flags, Maybe<IdSet>& ht,
-                          AutoIdVector* props, Handle<UnboxedPlainObject*> unboxed = nullptr)
+EnumerateNativeProperties(JSContext* cx, HandleNativeObject pobj, unsigned flags,
+                          MutableHandle<IdSet> visited, AutoIdVector* props,
+                          Handle<UnboxedPlainObject*> unboxed = nullptr)
 {
     bool enumerateSymbols;
     if (flags & JSITER_SYMBOLSONLY) {
         enumerateSymbols = true;
     } else {
         /* Collect any dense elements from this object. */
         size_t firstElemIndex = props->length();
         size_t initlen = pobj->getDenseInitializedLength();
         const Value* vp = pobj->getDenseElements();
         bool hasHoles = false;
         for (size_t i = 0; i < initlen; ++i, ++vp) {
             if (vp->isMagic(JS_ELEMENTS_HOLE)) {
                 hasHoles = true;
             } else {
                 /* Dense arrays never get so large that i would not fit into an integer id. */
                 if (!Enumerate<CheckForDuplicates>(cx, pobj, INT_TO_JSID(i),
-                                                   /* enumerable = */ true, flags, ht, props))
+                                                   /* enumerable = */ true, flags, visited, props))
                 {
                     return false;
                 }
             }
         }
 
         /* Collect any typed array or shared typed array elements from this object. */
         if (pobj->is<TypedArrayObject>()) {
             size_t len = pobj->as<TypedArrayObject>().length();
             for (size_t i = 0; i < len; i++) {
                 if (!Enumerate<CheckForDuplicates>(cx, pobj, INT_TO_JSID(i),
-                                                   /* enumerable = */ true, flags, ht, props))
+                                                   /* enumerable = */ true, flags, visited, props))
                 {
                     return false;
                 }
             }
         }
 
         // Collect any sparse elements from this object.
         bool isIndexed = pobj->isIndexed();
@@ -233,18 +229,18 @@ EnumerateNativeProperties(JSContext* cx,
                 firstElemIndex = props->length();
             }
 
             for (Shape::Range<NoGC> r(pobj->lastProperty()); !r.empty(); r.popFront()) {
                 Shape& shape = r.front();
                 jsid id = shape.propid();
                 uint32_t dummy;
                 if (IdIsIndex(id, &dummy)) {
-                    if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags, ht,
-                                                       props))
+                    if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags,
+                                                       visited, props))
                     {
                         return false;
                     }
                 }
             }
 
             MOZ_ASSERT(firstElemIndex <= props->length());
 
@@ -263,17 +259,19 @@ EnumerateNativeProperties(JSContext* cx,
         }
 
         if (unboxed) {
             // If |unboxed| is set then |pobj| is the expando for an unboxed
             // plain object we are enumerating. Add the unboxed properties
             // themselves here since they are all property names that were
             // given to the object before any of the expando's properties.
             MOZ_ASSERT(pobj->is<UnboxedExpandoObject>());
-            if (!EnumerateExtraProperties<CheckForDuplicates>(cx, unboxed, flags, ht, props)) {
+            if (!EnumerateExtraProperties<CheckForDuplicates>(cx, unboxed, flags, visited,
+                                                              props))
+            {
                 return false;
             }
         }
 
         size_t initialLength = props->length();
 
         /* Collect all unique property names from this object's shape. */
         bool symbolsFound = false;
@@ -287,17 +285,19 @@ EnumerateNativeProperties(JSContext* cx,
                 continue;
             }
 
             uint32_t dummy;
             if (isIndexed && IdIsIndex(id, &dummy)) {
                 continue;
             }
 
-            if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags, ht, props)) {
+            if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags, visited,
+                                               props))
+            {
                 return false;
             }
         }
         ::Reverse(props->begin() + initialLength, props->end());
 
         enumerateSymbols = symbolsFound && (flags & JSITER_SYMBOLS);
     }
 
@@ -305,44 +305,44 @@ EnumerateNativeProperties(JSContext* cx,
         // Do a second pass to collect symbols. ES6 draft rev 25 (2014 May 22)
         // 9.1.12 requires that all symbols appear after all strings in the
         // result.
         size_t initialLength = props->length();
         for (Shape::Range<NoGC> r(pobj->lastProperty()); !r.empty(); r.popFront()) {
             Shape& shape = r.front();
             jsid id = shape.propid();
             if (JSID_IS_SYMBOL(id)) {
-                if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags, ht,
-                                                   props))
+                if (!Enumerate<CheckForDuplicates>(cx, pobj, id, shape.enumerable(), flags,
+                                                   visited, props))
                 {
                     return false;
                 }
             }
         }
         ::Reverse(props->begin() + initialLength, props->end());
     }
 
     return true;
 }
 
 static bool
-EnumerateNativeProperties(JSContext* cx, HandleNativeObject pobj, unsigned flags, Maybe<IdSet>& ht,
-                          AutoIdVector* props, bool checkForDuplicates,
-                          Handle<UnboxedPlainObject*> unboxed = nullptr)
+EnumerateNativeProperties(JSContext* cx, HandleNativeObject pobj, unsigned flags,
+                          MutableHandle<IdSet> visited, AutoIdVector* props,
+                          bool checkForDuplicates, Handle<UnboxedPlainObject*> unboxed = nullptr)
 {
     if (checkForDuplicates) {
-        return EnumerateNativeProperties<true>(cx, pobj, flags, ht, props, unboxed);
+        return EnumerateNativeProperties<true>(cx, pobj, flags, visited, props, unboxed);
     }
-    return EnumerateNativeProperties<false>(cx, pobj, flags, ht, props, unboxed);
+    return EnumerateNativeProperties<false>(cx, pobj, flags, visited, props, unboxed);
 }
 
 template <bool CheckForDuplicates>
 static bool
-EnumerateProxyProperties(JSContext* cx, HandleObject pobj, unsigned flags, Maybe<IdSet>& ht,
-                         AutoIdVector* props)
+EnumerateProxyProperties(JSContext* cx, HandleObject pobj, unsigned flags,
+                         MutableHandle<IdSet> visited, AutoIdVector* props)
 {
     MOZ_ASSERT(pobj->is<ProxyObject>());
 
     AutoIdVector proxyProps(cx);
 
     if (flags & JSITER_HIDDEN || flags & JSITER_SYMBOLS) {
         // This gets all property keys, both strings and symbols. The call to
         // Enumerate in the loop below will filter out unwanted keys, per the
@@ -358,33 +358,33 @@ EnumerateProxyProperties(JSContext* cx, 
             // We need to filter, if the caller just wants enumerable symbols.
             if (!(flags & JSITER_HIDDEN)) {
                 if (!Proxy::getOwnPropertyDescriptor(cx, pobj, proxyProps[n], &desc)) {
                     return false;
                 }
                 enumerable = desc.enumerable();
             }
 
-            if (!Enumerate<CheckForDuplicates>(cx, pobj, proxyProps[n], enumerable, flags, ht,
+            if (!Enumerate<CheckForDuplicates>(cx, pobj, proxyProps[n], enumerable, flags, visited,
                                                props))
             {
                 return false;
             }
         }
 
         return true;
     }
 
     // Returns enumerable property names (no symbols).
     if (!Proxy::getOwnEnumerablePropertyKeys(cx, pobj, proxyProps)) {
         return false;
     }
 
     for (size_t n = 0, len = proxyProps.length(); n < len; n++) {
-        if (!Enumerate<CheckForDuplicates>(cx, pobj, proxyProps[n], true, flags, ht, props)) {
+        if (!Enumerate<CheckForDuplicates>(cx, pobj, proxyProps[n], true, flags, visited, props)) {
             return false;
         }
     }
 
     return true;
 }
 
 #ifdef JS_MORE_DETERMINISTIC
@@ -458,19 +458,17 @@ struct SortComparatorIds
     }
 };
 
 #endif /* JS_MORE_DETERMINISTIC */
 
 static bool
 Snapshot(JSContext* cx, HandleObject pobj_, unsigned flags, AutoIdVector* props)
 {
-    // We initialize |ht| lazily (in Enumerate()) because it ends up unused
-    // anywhere from 67--99.9% of the time.
-    Maybe<IdSet> ht;
+    Rooted<IdSet> visited(cx, IdSet(cx));
     RootedObject pobj(cx, pobj_);
 
     // Don't check for duplicates if we're only interested in own properties.
     // This does the right thing for most objects: native objects don't have
     // duplicate property ids and we allow the [[OwnPropertyKeys]] proxy trap to
     // return duplicates.
     //
     // The only special case is when the object has a newEnumerate hook: it
@@ -478,65 +476,65 @@ Snapshot(JSContext* cx, HandleObject pob
     // handled below.
     bool checkForDuplicates = !(flags & JSITER_OWNONLY);
 
     do {
         if (pobj->getClass()->getNewEnumerate()) {
             if (pobj->is<UnboxedPlainObject>() && pobj->as<UnboxedPlainObject>().maybeExpando()) {
                 // Special case unboxed objects with an expando object.
                 RootedNativeObject expando(cx, pobj->as<UnboxedPlainObject>().maybeExpando());
-                if (!EnumerateNativeProperties(cx, expando, flags, ht, props, checkForDuplicates,
-                                               pobj.as<UnboxedPlainObject>()))
+                if (!EnumerateNativeProperties(cx, expando, flags, &visited, props,
+                                               checkForDuplicates, pobj.as<UnboxedPlainObject>()))
                 {
                     return false;
                 }
             } else {
                 // The newEnumerate hook may return duplicates. Whitelist the
                 // unboxed object hooks because we know they are well-behaved.
                 if (!pobj->is<UnboxedPlainObject>()) {
                     checkForDuplicates = true;
                 }
 
                 if (checkForDuplicates) {
-                    if (!EnumerateExtraProperties<true>(cx, pobj, flags, ht, props)) {
+                    if (!EnumerateExtraProperties<true>(cx, pobj, flags, &visited, props)) {
                         return false;
                     }
                 } else {
-                    if (!EnumerateExtraProperties<false>(cx, pobj, flags, ht, props)) {
+                    if (!EnumerateExtraProperties<false>(cx, pobj, flags, &visited, props)) {
                         return false;
                     }
                 }
 
                 if (pobj->isNative()) {
-                    if (!EnumerateNativeProperties(cx, pobj.as<NativeObject>(), flags, ht, props,
-                                                   checkForDuplicates))
+                    if (!EnumerateNativeProperties(cx, pobj.as<NativeObject>(), flags, &visited,
+                                                   props, checkForDuplicates))
                     {
                         return false;
                     }
                 }
             }
         } else if (pobj->isNative()) {
             // Give the object a chance to resolve all lazy properties
             if (JSEnumerateOp enumerate = pobj->getClass()->getEnumerate()) {
                 if (!enumerate(cx, pobj.as<NativeObject>())) {
                     return false;
                 }
             }
-            if (!EnumerateNativeProperties(cx, pobj.as<NativeObject>(), flags, ht, props,
+            if (!EnumerateNativeProperties(cx, pobj.as<NativeObject>(), flags, &visited, props,
                                            checkForDuplicates))
             {
                 return false;
             }
         } else if (pobj->is<ProxyObject>()) {
             if (checkForDuplicates) {
-                if (!EnumerateProxyProperties<true>(cx, pobj, flags, ht, props)) {
+                if (!EnumerateProxyProperties<true>(cx, pobj, flags, &visited, props)) {
                     return false;
                 }
             } else {
-                if (!EnumerateProxyProperties<false>(cx, pobj, flags, ht, props)) {
+                if (!EnumerateProxyProperties<false>(cx, pobj, flags, &visited, props)) {
                     return false;
                 }
             }
         } else {
             MOZ_CRASH("non-native objects must have an enumerate op");
         }
 
         if (flags & JSITER_OWNONLY) {