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 344936 7e6204be142a74d93a66bb17758fa9fcfe08afb6
parent 344935 d82cdc1a1bf3fd95325e9b3132e3cfc6ce531dd1
child 344937 85e40ef81409ff7f4188407b160aa80a3745a7d3
push id37977
push userphilringnalda@gmail.com
push dateSat, 25 Feb 2017 21:34:46 +0000
treeherderautoland@10bfa931c92f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjonco
bugs1342345
milestone54.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 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: