The concurrent GC should have a timeslicing controller
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Nov 2016 21:15:04 +0000 (21:15 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Nov 2016 21:15:04 +0000 (21:15 +0000)
https://bugs.webkit.org/show_bug.cgi?id=164783

Reviewed by Geoffrey Garen.
Source/JavaScriptCore:

This adds a simple control system for deciding when the collector should let the mutator run
and when it should stop the mutator. We definitely have to stop the mutator during certain
collector phases, but during marking - which takes the most time - we can go either way.
Normally we want to let the mutator run, but if the heap size starts to grow then we have to
stop the mutator just to make sure it doesn't get too far ahead of the collector. That could
lead to memory exhaustion, so it's better to just stop in that case.

The controller tries to never stop the mutator for longer than short timeslices. It slices on
a 2ms period (configurable via Options). The amount of that period that the collector spends
with the mutator stopped is determined by the fraction of the collector's concurrent headroom
that has been allocated over. The headroom is currently configured at 50% of what was
allocated before the collector started.

This moves a bunch of parameters into Options so that it's easier to play with different
configurations.

I tried these different values for the period:

1ms: 30% worse than 2ms on splay-latency.
2ms: best score on splay-latency: the tick time above the 99.5% percentile is <2ms.
3ms: 40% worse than 2ms on splay-latency.
4ms: 40% worse than 2ms on splay-latency.

I also tried 100% headroom as an alternate to 50% and found it to be a worse.

This patch is a 2x improvement on splay-latency with the default parameters and concurrent GC
enabled. Prior to this change, the GC didn't have a good bound on its pause times, which
would cause these problems. Concurrent GC is now 5.6x better on splay-latency than no
concurrent GC.

* heap/Heap.cpp:
(JSC::Heap::ResumeTheWorldScope::ResumeTheWorldScope):
(JSC::Heap::markToFixpoint):
(JSC::Heap::collectInThread):
* runtime/Options.h:

Source/WTF:

* wtf/LockAlgorithm.h: Added some comments.
* wtf/Seconds.h: Added support for modulo. It's necessary for timeslicing.
(WTF::Seconds::operator%):
(WTF::Seconds::operator%=):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@208750 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/runtime/Options.h
Source/WTF/ChangeLog
Source/WTF/wtf/LockAlgorithm.h
Source/WTF/wtf/Seconds.h

index 1adf2ea..d94145b 100644 (file)
@@ -1,3 +1,46 @@
+2016-11-15  Filip Pizlo  <fpizlo@apple.com>
+
+        The concurrent GC should have a timeslicing controller
+        https://bugs.webkit.org/show_bug.cgi?id=164783
+
+        Reviewed by Geoffrey Garen.
+        
+        This adds a simple control system for deciding when the collector should let the mutator run
+        and when it should stop the mutator. We definitely have to stop the mutator during certain
+        collector phases, but during marking - which takes the most time - we can go either way.
+        Normally we want to let the mutator run, but if the heap size starts to grow then we have to
+        stop the mutator just to make sure it doesn't get too far ahead of the collector. That could
+        lead to memory exhaustion, so it's better to just stop in that case.
+        
+        The controller tries to never stop the mutator for longer than short timeslices. It slices on
+        a 2ms period (configurable via Options). The amount of that period that the collector spends
+        with the mutator stopped is determined by the fraction of the collector's concurrent headroom
+        that has been allocated over. The headroom is currently configured at 50% of what was
+        allocated before the collector started.
+        
+        This moves a bunch of parameters into Options so that it's easier to play with different
+        configurations.
+        
+        I tried these different values for the period:
+        
+        1ms: 30% worse than 2ms on splay-latency.
+        2ms: best score on splay-latency: the tick time above the 99.5% percentile is <2ms.
+        3ms: 40% worse than 2ms on splay-latency.
+        4ms: 40% worse than 2ms on splay-latency.
+        
+        I also tried 100% headroom as an alternate to 50% and found it to be a worse.
+        
+        This patch is a 2x improvement on splay-latency with the default parameters and concurrent GC
+        enabled. Prior to this change, the GC didn't have a good bound on its pause times, which
+        would cause these problems. Concurrent GC is now 5.6x better on splay-latency than no
+        concurrent GC.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::ResumeTheWorldScope::ResumeTheWorldScope):
+        (JSC::Heap::markToFixpoint):
+        (JSC::Heap::collectInThread):
+        * runtime/Options.h:
+
 2016-11-15  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Unreviewed, build fix for CLoop after r208738
index cb03b59..41d6cff 100644 (file)
@@ -78,6 +78,16 @@ using namespace std;
 
 namespace JSC {
 
+namespace {
+
+double maxPauseMS(double thisPauseMS)
+{
+    static double maxPauseMS = std::max(thisPauseMS, maxPauseMS);
+    return maxPauseMS;
+}
+
+} // anonymous namespace
+
 class Heap::ResumeTheWorldScope {
 public:
     ResumeTheWorldScope(Heap& heap)
@@ -86,8 +96,10 @@ public:
         if (!Options::useConcurrentGC())
             return;
         
-        if (Options::logGC())
-            dataLog((MonotonicTime::now() - m_heap.m_stopTime).milliseconds(), " ms...]\n");
+        if (Options::logGC()) {
+            double thisPauseMS = (MonotonicTime::now() - m_heap.m_stopTime).milliseconds();
+            dataLog(thisPauseMS, " ms (max ", maxPauseMS(thisPauseMS), ")...]\n");
+        }
         
         m_heap.resumeTheWorld();
     }
@@ -109,24 +121,24 @@ private:
 
 namespace {
 
-static const size_t largeHeapSize = 32 * MB; // About 1.5X the average webpage.
-const size_t smallHeapSize = 1 * MB; // Matches the FastMalloc per-thread cache.
-
 size_t minHeapSize(HeapType heapType, size_t ramSize)
 {
-    if (heapType == LargeHeap)
-        return min(largeHeapSize, ramSize / 4);
-    return smallHeapSize;
+    if (heapType == LargeHeap) {
+        double result = min(
+            static_cast<double>(Options::largeHeapSize()),
+            ramSize * Options::smallHeapRAMFraction());
+        return static_cast<size_t>(result);
+    }
+    return Options::smallHeapSize();
 }
 
 size_t proportionalHeapSize(size_t heapSize, size_t ramSize)
 {
-    // Try to stay under 1/2 RAM size to leave room for the DOM, rendering, networking, etc.
-    if (heapSize < ramSize / 4)
-        return 2 * heapSize;
-    if (heapSize < ramSize / 2)
-        return 1.5 * heapSize;
-    return 1.25 * heapSize;
+    if (heapSize < ramSize * Options::smallHeapRAMFraction())
+        return Options::smallHeapGrowthFactor() * heapSize;
+    if (heapSize < ramSize * Options::mediumHeapRAMFraction())
+        return Options::mediumHeapGrowthFactor() * heapSize;
+    return Options::largeHeapGrowthFactor() * heapSize;
 }
 
 bool isValidSharedInstanceThreadState(VM* vm)
@@ -525,16 +537,53 @@ void Heap::markToFixpoint(double gcStartTime)
 
     m_collectorSlotVisitor->didStartMarking();
 
-    Seconds concurrentTime;
-    double stoppedOverConcurrentRatio = 0.1;
-    const double ratioStep = 1.3;
     MonotonicTime initialTime = MonotonicTime::now();
-    MonotonicTime topOfLoopTime = initialTime;
+    
+    const Seconds period = Seconds::fromMilliseconds(Options::concurrentGCPeriodMS());
+    
+    const double bytesAllocatedThisCycleAtTheBeginning = m_bytesAllocatedThisCycle;
+    const double bytesAllocatedThisCycleAtTheEnd = bytesAllocatedThisCycleAtTheBeginning * Options::concurrentGCHeadroomRatio();
+    
+    auto targetCollectorUtilization = [&] () -> double {
+        double headroomFullness =
+            (m_bytesAllocatedThisCycle - bytesAllocatedThisCycleAtTheBeginning) /
+            (bytesAllocatedThisCycleAtTheEnd - bytesAllocatedThisCycleAtTheBeginning);
+        
+        ASSERT(headroomFullness >= 0);
+        if (!(headroomFullness >= 0))
+            headroomFullness = 0;
+        ASSERT(headroomFullness <= 1);
+        if (!(headroomFullness <= 1))
+            headroomFullness = 1;
+        
+        return headroomFullness;
+    };
+    
+    auto elapsedInPeriod = [&] (MonotonicTime now) -> Seconds {
+        return (now - initialTime) % period;
+    };
+    
+    auto phase = [&] (MonotonicTime now) -> double {
+        return elapsedInPeriod(now) / period;
+    };
+    
+    auto shouldBeResumed = [&] (MonotonicTime now) -> bool {
+        return phase(now) > targetCollectorUtilization();
+    };
+    
+    auto timeToResume = [&] (MonotonicTime now) -> MonotonicTime {
+        ASSERT(!shouldBeResumed(now));
+        return now - elapsedInPeriod(now) + period * targetCollectorUtilization();
+    };
+    
+    auto timeToStop = [&] (MonotonicTime now) -> MonotonicTime {
+        ASSERT(shouldBeResumed(now));
+        return now - elapsedInPeriod(now) + period;
+    };
+    
     for (unsigned iteration = 1; ; ++iteration) {
         if (Options::logGC())
             dataLog("i#", iteration, " ");
-        MonotonicTime timeToResume = topOfLoopTime + concurrentTime * stoppedOverConcurrentRatio;
-        stoppedOverConcurrentRatio *= ratioStep;
         {
             TimingScope preConvergenceTimingScope(*this, "Heap::markToFixpoint conservative scan");
             ConservativeRoots conservativeRoots(*this);
@@ -615,24 +664,28 @@ void Heap::markToFixpoint(double gcStartTime)
             dataLog("Live Weak Handles:\n", *m_collectorSlotVisitor);
         
         if (Options::logGC())
-            dataLog(m_collectorSlotVisitor->collectorMarkStack().size(), "+", m_collectorSlotVisitor->mutatorMarkStack().size(), " ");
-
+            dataLog(m_collectorSlotVisitor->collectorMarkStack().size(), "+", m_collectorSlotVisitor->mutatorMarkStack().size(), " mu=", 1 - targetCollectorUtilization(), " ");
+        
         {
             TimingScope traceTimingScope(*this, "Heap::markToFixpoint tracing");
             ParallelModeEnabler enabler(*m_collectorSlotVisitor);
-            m_collectorSlotVisitor->donateAndDrain(timeToResume);
-            SlotVisitor::SharedDrainResult drainResult =
-                m_collectorSlotVisitor->drainFromShared(SlotVisitor::MasterDrain, timeToResume);
-            if (drainResult != SlotVisitor::SharedDrainResult::Done) {
-                ResumeTheWorldScope resumeTheWorldScope(*this);
-                m_collectorSlotVisitor->donateAndDrain();
-                m_collectorSlotVisitor->drainFromShared(SlotVisitor::MasterDrain);
+            for (;;) {
+                MonotonicTime now = MonotonicTime::now();
+                SlotVisitor::SharedDrainResult drainResult;
+                if (shouldBeResumed(now)) {
+                    ResumeTheWorldScope resumeTheWorldScope(*this);
+                    m_collectorSlotVisitor->donateAndDrain(timeToStop(now));
+                    drainResult = m_collectorSlotVisitor->drainFromShared(
+                        SlotVisitor::MasterDrain, timeToStop(now));
+                } else {
+                    m_collectorSlotVisitor->donateAndDrain(timeToResume(now));
+                    drainResult = m_collectorSlotVisitor->drainFromShared(
+                        SlotVisitor::MasterDrain, timeToResume(now));
+                }
+                if (drainResult == SlotVisitor::SharedDrainResult::Done)
+                    break;
             }
         }
-        
-        MonotonicTime timeOfStop = MonotonicTime::now();
-        concurrentTime = timeOfStop - timeToResume;
-        topOfLoopTime = timeOfStop;
     }
 
     {
@@ -1112,7 +1165,8 @@ void Heap::collectInThread()
     
     if (Options::logGC()) {
         MonotonicTime after = MonotonicTime::now();
-        dataLog((after - m_stopTime).milliseconds(), " ms, cycle ", (after - before).milliseconds(), " ms END]\n");
+        double thisPauseMS = (after - m_stopTime).milliseconds();
+        dataLog(thisPauseMS, " ms (max ", maxPauseMS(thisPauseMS), "), cycle ", (after - before).milliseconds(), " ms END]\n");
     }
     
     {
index ba1c6d2..4b26fb8 100644 (file)
@@ -187,6 +187,15 @@ typedef const char* optionString;
     v(bool, useConcurrentGC, false, Normal, nullptr) \
     v(bool, collectContinuously, false, Normal, nullptr) \
     v(bool, forceFencedBarrier, false, Normal, nullptr) \
+    v(unsigned, largeHeapSize, 32 * 1024 * 1024, Normal, nullptr) \
+    v(unsigned, smallHeapSize, 1 * 1024 * 1024, Normal, nullptr) \
+    v(double, smallHeapRAMFraction, 0.25, Normal, nullptr) \
+    v(double, smallHeapGrowthFactor, 2, Normal, nullptr) \
+    v(double, mediumHeapRAMFraction, 0.5, Normal, nullptr) \
+    v(double, mediumHeapGrowthFactor, 1.5, Normal, nullptr) \
+    v(double, largeHeapGrowthFactor, 1.24, Normal, nullptr) \
+    v(double, concurrentGCHeadroomRatio, 1.5, Normal, nullptr) \
+    v(double, concurrentGCPeriodMS, 2, Normal, nullptr) \
     v(bool, scribbleFreeCells, false, Normal, nullptr) \
     v(double, sizeClassProgression, 1.4, Normal, nullptr) \
     v(unsigned, largeAllocationCutoff, 100000, Normal, nullptr) \
index 3087d5b..11caa83 100644 (file)
@@ -1,3 +1,15 @@
+2016-11-15  Filip Pizlo  <fpizlo@apple.com>
+
+        The concurrent GC should have a timeslicing controller
+        https://bugs.webkit.org/show_bug.cgi?id=164783
+
+        Reviewed by Geoffrey Garen.
+
+        * wtf/LockAlgorithm.h: Added some comments.
+        * wtf/Seconds.h: Added support for modulo. It's necessary for timeslicing.
+        (WTF::Seconds::operator%):
+        (WTF::Seconds::operator%=):
+
 2016-11-11  Filip Pizlo  <fpizlo@apple.com>
 
         The GC should be optionally concurrent and disabled by default
index a4e5e97..1b46979 100644 (file)
@@ -33,7 +33,9 @@
 
 namespace WTF {
 
-// This is the algorithm used by WTF::Lock.
+// This is the algorithm used by WTF::Lock. You can use it to project one lock onto any atomic
+// field. The limit of one lock is due to the use of the field's address as a key to find the lock's
+// queue.
 
 template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
 class LockAlgorithm {
index 1a59424..c3914cb 100644 (file)
@@ -26,6 +26,8 @@
 #ifndef WTF_Seconds_h
 #define WTF_Seconds_h
 
+#include <wtf/MathExtras.h>
+
 namespace WTF {
 
 class MonotonicTime;
@@ -104,6 +106,21 @@ public:
         return value() / other.value();
     }
     
+    Seconds operator%(double scalar) const
+    {
+        return Seconds(fmod(value(), scalar));
+    }
+    
+    // This solves for r, where:
+    //
+    //     floor(this / other) + r / other = this / other
+    //
+    // Therefore, if this is Seconds then r is Seconds.
+    Seconds operator%(Seconds other) const
+    {
+        return Seconds(fmod(value(), other.value()));
+    }
+    
     Seconds& operator+=(Seconds other)
     {
         return *this = *this + other;
@@ -124,6 +141,16 @@ public:
         return *this = *this / scalar;
     }
     
+    Seconds& operator%=(double scalar)
+    {
+        return *this = *this % scalar;
+    }
+    
+    Seconds& operator%=(Seconds other)
+    {
+        return *this = *this % other;
+    }
+    
     WTF_EXPORT_PRIVATE WallTime operator+(WallTime) const;
     WTF_EXPORT_PRIVATE MonotonicTime operator+(MonotonicTime) const;
     WTF_EXPORT_PRIVATE TimeWithDynamicClockType operator+(const TimeWithDynamicClockType&) const;