Bug 1342345 part 2 - Use a Vector for AutoCycleDetector. r=jonco
authorJan de Mooij <jdemooij@mozilla.com>
Sat, 25 Feb 2017 12:23:44 +0100
changeset 373960 7e6204be142a74d93a66bb17758fa9fcfe08afb6
parent 373959 d82cdc1a1bf3fd95325e9b3132e3cfc6ce531dd1
child 373961 85e40ef81409ff7f4188407b160aa80a3745a7d3
push id10863
push userjlorenzo@mozilla.com
push dateMon, 06 Mar 2017 23:02:23 +0000
treeherdermozilla-aurora@0931190cd725 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjonco
bugs1342345
milestone54.0a1
Bug 1342345 part 2 - Use a Vector for AutoCycleDetector. r=jonco
js/public/GCVector.h
js/src/builtin/Object.cpp
js/src/jsapi.cpp
js/src/jscntxt.cpp
js/src/jscntxt.h
--- a/js/public/GCVector.h
+++ b/js/public/GCVector.h
@@ -69,16 +69,17 @@ class GCVector
 
     bool initCapacity(size_t cap) { return vector.initCapacity(cap); }
     MOZ_MUST_USE bool reserve(size_t req) { return vector.reserve(req); }
     void shrinkBy(size_t amount) { return vector.shrinkBy(amount); }
     MOZ_MUST_USE bool growBy(size_t amount) { return vector.growBy(amount); }
     MOZ_MUST_USE bool resize(size_t newLen) { return vector.resize(newLen); }
 
     void clear() { return vector.clear(); }
+    void clearAndFree() { return vector.clearAndFree(); }
 
     template<typename U> bool append(U&& item) { return vector.append(mozilla::Forward<U>(item)); }
 
     template<typename... Args>
     MOZ_MUST_USE bool
     emplaceBack(Args&&... args) {
         return vector.emplaceBack(mozilla::Forward<Args>(args)...);
     }
--- a/js/src/builtin/Object.cpp
+++ b/js/src/builtin/Object.cpp
@@ -167,17 +167,17 @@ ArgsAndBodySubstring(mozilla::Range<cons
     MOZ_ASSERT(*outOffset + *outLen <= chars.length());
     return true;
 }
 
 JSString*
 js::ObjectToSource(JSContext* cx, HandleObject obj)
 {
     /* If outermost, we need parentheses to be an expression, not a block. */
-    bool outermost = (cx->cycleDetectorSet().count() == 0);
+    bool outermost = cx->cycleDetectorVector().empty();
 
     AutoCycleDetector detector(cx, obj);
     if (!detector.init())
         return nullptr;
     if (detector.foundCycle())
         return NewStringCopyZ<CanGC>(cx, "{}");
 
     StringBuffer buf(cx);
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -633,19 +633,16 @@ JS::InitSelfHostedCode(JSContext* cx)
     AutoNoteSingleThreadedRegion anstr;
 
     JSRuntime* rt = cx->runtime();
 
     JSAutoRequest ar(cx);
     if (!rt->initializeAtoms(cx))
         return false;
 
-    if (!cx->cycleDetectorSet().init())
-        return false;
-
     if (!rt->initSelfHosting(cx))
         return false;
 
     if (!rt->parentRuntime && !rt->transformToPermanentAtoms(cx))
         return false;
 
     return true;
 }
--- a/js/src/jscntxt.cpp
+++ b/js/src/jscntxt.cpp
@@ -63,46 +63,46 @@ using namespace js::gc;
 
 using mozilla::DebugOnly;
 using mozilla::PodArrayZero;
 using mozilla::PointerRangeSize;
 
 bool
 js::AutoCycleDetector::init()
 {
-    AutoCycleDetector::Set& set = cx->cycleDetectorSet();
-    hashsetAddPointer = set.lookupForAdd(obj);
-    if (!hashsetAddPointer) {
-        if (!set.add(hashsetAddPointer, obj)) {
-            ReportOutOfMemory(cx);
-            return false;
-        }
-        cyclic = false;
-        hashsetGenerationAtInit = set.generation();
+    MOZ_ASSERT(cyclic);
+
+    AutoCycleDetector::Vector& vector = cx->cycleDetectorVector();
+
+    for (JSObject* obj2 : vector) {
+        if (MOZ_UNLIKELY(obj == obj2))
+            return true;
     }
+
+    if (!vector.append(obj))
+        return false;
+
+    cyclic = false;
     return true;
 }
 
 js::AutoCycleDetector::~AutoCycleDetector()
 {
-    if (!cyclic) {
-        if (hashsetGenerationAtInit == cx->cycleDetectorSet().generation())
-            cx->cycleDetectorSet().remove(hashsetAddPointer);
-        else
-            cx->cycleDetectorSet().remove(obj);
+    if (MOZ_LIKELY(!cyclic)) {
+        AutoCycleDetector::Vector& vec = cx->cycleDetectorVector();
+        MOZ_ASSERT(vec.back() == obj);
+        if (vec.length() > 1) {
+            vec.popBack();
+        } else {
+            // Avoid holding on to unused heap allocations.
+            vec.clearAndFree();
+        }
     }
 }
 
-void
-js::TraceCycleDetectionSet(JSTracer* trc, AutoCycleDetector::Set& set)
-{
-    for (AutoCycleDetector::Set::Enum e(set); !e.empty(); e.popFront())
-        TraceRoot(trc, &e.mutableFront(), "cycle detector table entry");
-}
-
 bool
 JSContext::init(ContextKind kind)
 {
     // Skip most of the initialization if this thread will not be running JS.
     if (kind == ContextKind::Cooperative) {
         // Get a platform-native handle for this thread, used by js::InterruptRunningJitCode.
 #ifdef XP_WIN
         size_t openFlags = THREAD_GET_CONTEXT | THREAD_SET_CONTEXT | THREAD_SUSPEND_RESUME |
@@ -1192,16 +1192,17 @@ JSContext::JSContext(JSRuntime* runtime,
     propagatingForcedReturn_(false),
     liveVolatileJitFrameIterators_(nullptr),
     reportGranularity(JS_DEFAULT_JITREPORT_GRANULARITY),
     resolvingList(nullptr),
 #ifdef DEBUG
     enteredPolicy(nullptr),
 #endif
     generatingError(false),
+    cycleDetectorVector_(this),
     data(nullptr),
     outstandingRequests(0),
     jitIsBroken(false),
     asyncCauseForNewActivations(nullptr),
     asyncCallIsExplicit(false),
     interruptCallbackDisabled(false),
     interrupt_(false),
     handlingJitInterrupt_(false),
@@ -1386,24 +1387,23 @@ JSContext::updateJITEnabled()
 size_t
 JSContext::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
 {
     /*
      * There are other JSContext members that could be measured; the following
      * ones have been found by DMD to be worth measuring.  More stuff may be
      * added later.
      */
-    return cycleDetectorSet().sizeOfExcludingThis(mallocSizeOf);
+    return cycleDetectorVector().sizeOfExcludingThis(mallocSizeOf);
 }
 
 void
 JSContext::trace(JSTracer* trc)
 {
-    if (cycleDetectorSet().initialized())
-        TraceCycleDetectionSet(trc, cycleDetectorSet());
+    cycleDetectorVector().trace(trc);
 
     if (trc->isMarkingTracer() && compartment_)
         compartment_->mark();
 }
 
 void*
 JSContext::stackLimitAddressForJitCode(JS::StackKind kind)
 {
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -36,44 +36,38 @@ class DebugModeOSRVolatileJitFrameIterat
 } // namespace jit
 
 typedef HashSet<Shape*> ShapeSet;
 
 /* Detects cycles when traversing an object graph. */
 class MOZ_RAII AutoCycleDetector
 {
   public:
-    using Set = HashSet<JSObject*, MovableCellHasher<JSObject*>, SystemAllocPolicy>;
+    using Vector = GCVector<JSObject*, 8>;
 
     AutoCycleDetector(JSContext* cx, HandleObject objArg
                       MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
       : cx(cx), obj(cx, objArg), cyclic(true)
     {
         MOZ_GUARD_OBJECT_NOTIFIER_INIT;
     }
 
     ~AutoCycleDetector();
 
     bool init();
 
     bool foundCycle() { return cyclic; }
 
   private:
-    Generation hashsetGenerationAtInit;
     JSContext* cx;
     RootedObject obj;
-    Set::AddPtr hashsetAddPointer;
     bool cyclic;
     MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER
 };
 
-/* Updates references in the cycle detection set if the GC moves them. */
-extern void
-TraceCycleDetectionSet(JSTracer* trc, AutoCycleDetector::Set& set);
-
 struct AutoResolving;
 
 namespace frontend { class CompileError; }
 
 struct HelperThread;
 
 void ReportOverRecursed(JSContext* cx, unsigned errorNumber);
 
@@ -635,21 +629,25 @@ struct JSContext : public JS::RootingCon
     js::ThreadLocalData<js::AutoEnterPolicy*> enteredPolicy;
 #endif
 
     /* True if generating an error, to prevent runaway recursion. */
     js::ThreadLocalData<bool> generatingError;
 
   private:
     /* State for object and array toSource conversion. */
-    js::ThreadLocalData<js::AutoCycleDetector::Set> cycleDetectorSet_;
+    js::ThreadLocalData<js::AutoCycleDetector::Vector> cycleDetectorVector_;
 
   public:
-    js::AutoCycleDetector::Set& cycleDetectorSet() { return cycleDetectorSet_.ref(); }
-    const js::AutoCycleDetector::Set& cycleDetectorSet() const { return cycleDetectorSet_.ref(); }
+    js::AutoCycleDetector::Vector& cycleDetectorVector() {
+        return cycleDetectorVector_.ref();
+    }
+    const js::AutoCycleDetector::Vector& cycleDetectorVector() const {
+        return cycleDetectorVector_.ref();
+    }
 
     /* Client opaque pointer. */
     js::UnprotectedData<void*> data;
 
     void initJitStackLimit();
     void resetJitStackLimit();
 
   public: