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 442254 7141a7da10208223603df9d309e1d738dbf91892
parent 442253 a83370778faf43b69e9a3b3540d25ce8b51da6a8
child 442255 ff70442b73b376bc5f135aab4390ac1b5b3a662c
push id34894
push userbtara@mozilla.com
push dateSat, 20 Oct 2018 21:56:37 +0000
treeherdermozilla-central@3872ebc4799b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjonco
bugs1500064, 1481998
milestone64.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 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) {