Changeset 209727 in webkit


Ignore:
Timestamp:
Dec 12, 2016, 2:06:41 PM (9 years ago)
Author:
fpizlo@apple.com
Message:

GC scheduler should avoid consecutive pauses
​https://bugs.webkit.org/show_bug.cgi?id=165758

Reviewed by Michael Saboff.

This factors out the scheduler from lambdas in Heap::markToFixpoint to an actual class.
It's called the SpaceTimeScheduler because it is a linear controller that ties the
amount of time you spend on things to the amount of space you are using.

This patch uses this refactoring to fix a bug where the GC would pause even though we
still had time during a mutator timeslice. This is a 15% improvement on
JetStream/splay-latency. Seems neutral on everything else. However, it's not at all
clear if this is the right policy or not since retreating wavefront can sometimes be so
sensitive to scheduling decisions. For this reason, there is a tunable option that lets
you decide how long the GC will sit idle before the start of its timeslice.

So, we can revert this policy change in this patch without reverting the patch.

  • CMakeLists.txt:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • heap/Heap.cpp:

(JSC::Heap::markToFixpoint):

  • heap/Heap.h:
  • heap/SpaceTimeScheduler.cpp: Added.

(JSC::SpaceTimeScheduler::Decision::targetMutatorUtilization):
(JSC::SpaceTimeScheduler::Decision::targetCollectorUtilization):
(JSC::SpaceTimeScheduler::Decision::elapsedInPeriod):
(JSC::SpaceTimeScheduler::Decision::phase):
(JSC::SpaceTimeScheduler::Decision::shouldBeResumed):
(JSC::SpaceTimeScheduler::Decision::timeToResume):
(JSC::SpaceTimeScheduler::Decision::timeToStop):
(JSC::SpaceTimeScheduler::SpaceTimeScheduler):
(JSC::SpaceTimeScheduler::snapPhase):
(JSC::SpaceTimeScheduler::currentDecision):

  • heap/SpaceTimeScheduler.h: Added.

(JSC::SpaceTimeScheduler::Decision::Decision):
(JSC::SpaceTimeScheduler::Decision::operator bool):

  • runtime/Options.h:
Location:
trunk/Source/JavaScriptCore
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r209691 r209727  
    498498    heap/MutatorState.cpp
    499499    heap/SlotVisitor.cpp
     500    heap/SpaceTimeScheduler.cpp
    500501    heap/StopIfNecessaryTimer.cpp
    501502    heap/VisitRaceKey.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r209725 r209727  
     12016-12-12  Filip Pizlo  <fpizlo@apple.com>
     2
     3        GC scheduler should avoid consecutive pauses
     4        https://bugs.webkit.org/show_bug.cgi?id=165758
     5
     6        Reviewed by Michael Saboff.
     7       
     8        This factors out the scheduler from lambdas in Heap::markToFixpoint to an actual class.
     9        It's called the SpaceTimeScheduler because it is a linear controller that ties the
     10        amount of time you spend on things to the amount of space you are using.
     11       
     12        This patch uses this refactoring to fix a bug where the GC would pause even though we
     13        still had time during a mutator timeslice. This is a 15% improvement on
     14        JetStream/splay-latency. Seems neutral on everything else. However, it's not at all
     15        clear if this is the right policy or not since retreating wavefront can sometimes be so
     16        sensitive to scheduling decisions. For this reason, there is a tunable option that lets
     17        you decide how long the GC will sit idle before the start of its timeslice.
     18       
     19        So, we can revert this policy change in this patch without reverting the patch.
     20
     21        * CMakeLists.txt:
     22        * JavaScriptCore.xcodeproj/project.pbxproj:
     23        * heap/Heap.cpp:
     24        (JSC::Heap::markToFixpoint):
     25        * heap/Heap.h:
     26        * heap/SpaceTimeScheduler.cpp: Added.
     27        (JSC::SpaceTimeScheduler::Decision::targetMutatorUtilization):
     28        (JSC::SpaceTimeScheduler::Decision::targetCollectorUtilization):
     29        (JSC::SpaceTimeScheduler::Decision::elapsedInPeriod):
     30        (JSC::SpaceTimeScheduler::Decision::phase):
     31        (JSC::SpaceTimeScheduler::Decision::shouldBeResumed):
     32        (JSC::SpaceTimeScheduler::Decision::timeToResume):
     33        (JSC::SpaceTimeScheduler::Decision::timeToStop):
     34        (JSC::SpaceTimeScheduler::SpaceTimeScheduler):
     35        (JSC::SpaceTimeScheduler::snapPhase):
     36        (JSC::SpaceTimeScheduler::currentDecision):
     37        * heap/SpaceTimeScheduler.h: Added.
     38        (JSC::SpaceTimeScheduler::Decision::Decision):
     39        (JSC::SpaceTimeScheduler::Decision::operator bool):
     40        * runtime/Options.h:
     41
    1422016-12-12  Michael Saboff  <msaboff@apple.com>
    243

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r209725 r209727  
    754754                0FDDBFB61666EEDA00C55FEF /* DFGVariableAccessDataDump.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFB31666EED500C55FEF /* DFGVariableAccessDataDump.h */; };
    755755                0FDE87F91DFD0C760064C390 /* CellContainer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDE87F81DFD0C6D0064C390 /* CellContainer.cpp */; };
     756                0FDE87FC1DFE6E510064C390 /* SpaceTimeScheduler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDE87FB1DFE6E500064C390 /* SpaceTimeScheduler.h */; };
     757                0FDE87FD1DFE6E540064C390 /* SpaceTimeScheduler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDE87FA1DFE6E500064C390 /* SpaceTimeScheduler.cpp */; };
    756758                0FDF67D21D9C6D27001B9825 /* B3Kind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDF67D11D9C6086001B9825 /* B3Kind.h */; };
    757759                0FDF67D31D9C6D2A001B9825 /* B3Kind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDF67D01D9C6086001B9825 /* B3Kind.cpp */; };
    … …  
    31823184                0FDDBFB31666EED500C55FEF /* DFGVariableAccessDataDump.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGVariableAccessDataDump.h; path = dfg/DFGVariableAccessDataDump.h; sourceTree = "<group>"; };
    31833185                0FDE87F81DFD0C6D0064C390 /* CellContainer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CellContainer.cpp; sourceTree = "<group>"; };
     3186                0FDE87FA1DFE6E500064C390 /* SpaceTimeScheduler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SpaceTimeScheduler.cpp; sourceTree = "<group>"; };
     3187                0FDE87FB1DFE6E500064C390 /* SpaceTimeScheduler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpaceTimeScheduler.h; sourceTree = "<group>"; };
    31843188                0FDF67D01D9C6086001B9825 /* B3Kind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3Kind.cpp; path = b3/B3Kind.cpp; sourceTree = "<group>"; };
    31853189                0FDF67D11D9C6086001B9825 /* B3Kind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Kind.h; path = b3/B3Kind.h; sourceTree = "<group>"; };
    … …  
    57385742                                14BA78F013AAB88F005B7C2C /* SlotVisitor.h */,
    57395743                                0FCB408515C0A3C30048932B /* SlotVisitorInlines.h */,
     5744                                0FDE87FA1DFE6E500064C390 /* SpaceTimeScheduler.cpp */,
     5745                                0FDE87FB1DFE6E500064C390 /* SpaceTimeScheduler.h */,
    57405746                                0F7CF9501DC027D70098CC12 /* StopIfNecessaryTimer.cpp */,
    57415747                                0F7CF9511DC027D70098CC12 /* StopIfNecessaryTimer.h */,
    … …  
    86238629                                43AB26C61C1A535900D82AE6 /* B3MathExtras.h in Headers */,
    86248630                                AD2FCBF31DB58DAD00B3E736 /* WebAssemblyInstancePrototype.h in Headers */,
     8631                                0FDE87FC1DFE6E510064C390 /* SpaceTimeScheduler.h in Headers */,
    86258632                                BC18C4290E16F5CD00B34460 /* JSStringRefCF.h in Headers */,
    86268633                                E350708A1DC49BBF0089BCD6 /* DOMJITSignature.h in Headers */,
    … …  
    97939800                                0FC09791146A6F7100CF2442 /* DFGOSRExit.cpp in Sources */,
    97949801                                0F235BEB17178E7300690C7F /* DFGOSRExitBase.cpp in Sources */,
     9802                                0FDE87FD1DFE6E540064C390 /* SpaceTimeScheduler.cpp in Sources */,
    97959803                                0FC09792146A6F7300CF2442 /* DFGOSRExitCompiler.cpp in Sources */,
    97969804                                0F4DE1D11C4D764B004D6C11 /* B3OriginDump.cpp in Sources */,

  • trunk/Source/JavaScriptCore/heap/Heap.cpp

    r209683 r209727  
    5353#include "SamplingProfiler.h"
    5454#include "ShadowChicken.h"
     55#include "SpaceTimeScheduler.h"
    5556#include "SuperSampler.h"
    5657#include "StopIfNecessaryTimer.h"
    … …  
    561562    m_collectorSlotVisitor->didStartMarking();
    562563
    563     MonotonicTime initialTime = MonotonicTime::now();
    564    
    565     const Seconds period = Seconds::fromMilliseconds(Options::concurrentGCPeriodMS());
    566    
    567     const double bytesAllocatedThisCycleAtTheBeginning = m_bytesAllocatedThisCycle;
    568     const double bytesAllocatedThisCycleAtTheEnd =
    569         Options::concurrentGCMaxHeadroom() *
    570         std::max(
    571             bytesAllocatedThisCycleAtTheBeginning,
    572             static_cast<double>(m_maxEdenSize));
    573     double bytesAllocatedThisCycle;
    574     MonotonicTime nowForScheduling;
    575    
    576     auto cacheSchedulingStats = [&] () {
    577         bytesAllocatedThisCycle = m_bytesAllocatedThisCycle;
    578         nowForScheduling = MonotonicTime::now();
    579     };
    580    
    581     cacheSchedulingStats();
    582    
    583     auto targetMutatorUtilization = [&] () -> double {
    584         double headroomFullness =
    585             (bytesAllocatedThisCycle - bytesAllocatedThisCycleAtTheBeginning) /
    586             (bytesAllocatedThisCycleAtTheEnd - bytesAllocatedThisCycleAtTheBeginning);
    587        
    588         // headroomFullness can be NaN and other interesting things if
    589         // bytesAllocatedThisCycleAtTheBeginning is zero. We see that in debug tests. This code
    590         // defends against all floating point dragons.
    591        
    592         if (!(headroomFullness >= 0))
    593             headroomFullness = 0;
    594         if (!(headroomFullness <= 1))
    595             headroomFullness = 1;
    596        
    597         double mutatorUtilization = 1 - headroomFullness;
    598        
    599         // Scale the mutator utilization into the permitted window.
    600         mutatorUtilization =
    601             Options::minimumMutatorUtilization() +
    602             mutatorUtilization * (
    603                 Options::maximumMutatorUtilization() -
    604                 Options::minimumMutatorUtilization());
    605        
    606         return mutatorUtilization;
    607     };
    608    
    609     auto targetCollectorUtilization = [&] () -> double {
    610         return 1 - targetMutatorUtilization();
    611     };
    612    
    613     auto elapsedInPeriod = [&] () -> Seconds {
    614         return (nowForScheduling - initialTime) % period;
    615     };
    616    
    617     auto phase = [&] () -> double {
    618         return elapsedInPeriod() / period;
    619     };
    620    
    621     auto shouldBeResumed = [&] () -> bool {
    622         if (Options::collectorShouldResumeFirst())
    623             return phase() <= targetMutatorUtilization();
    624         return phase() > targetCollectorUtilization();
    625     };
    626    
    627     auto timeToResume = [&] () -> MonotonicTime {
    628         ASSERT(!shouldBeResumed());
    629         if (Options::collectorShouldResumeFirst())
    630             return nowForScheduling - elapsedInPeriod() + period;
    631         return nowForScheduling - elapsedInPeriod() + period * targetCollectorUtilization();
    632     };
    633    
    634     auto timeToStop = [&] () -> MonotonicTime {
    635         ASSERT(shouldBeResumed());
    636         if (Options::collectorShouldResumeFirst())
    637             return nowForScheduling - elapsedInPeriod() + period * targetMutatorUtilization();
    638         return nowForScheduling - elapsedInPeriod() + period;
    639     };
    640    
    641     // Adjust the target extra pause ratio as necessary.
    642     double rateOfCollection =
    643         (m_lastGCEndTime - m_lastGCStartTime) /
    644         (m_currentGCStartTime - m_lastGCStartTime);
    645    
    646     if (Options::logGC())
    647         dataLog("cr=", rateOfCollection, " ");
    648    
    649     // FIXME: Determine if this is useful or get rid of it.
    650     // https://bugs.webkit.org/show_bug.cgi?id=164940
    651     double extraPauseRatio = Options::initialExtraPauseRatio();
     564    SpaceTimeScheduler scheduler(*this);
    652565   
    653566    for (unsigned iteration = 1; ; ++iteration) {
    654567        if (Options::logGC())
    655568            dataLog("i#", iteration, " ");
    656         MonotonicTime topOfLoop = MonotonicTime::now();
    657569        {
    658570            TimingScope preConvergenceTimingScope(*this, "Heap::markToFixpoint conservative scan");
    … …  
    717629       
    718630        if (Options::logGC()) {
    719             cacheSchedulingStats();
    720             dataLog(m_collectorSlotVisitor->collectorMarkStack().size(), "+", m_mutatorMarkStack->size() + m_collectorSlotVisitor->mutatorMarkStack().size(), ", a=", m_bytesAllocatedThisCycle / 1024, " kb, b=", m_barriersExecuted, ", mu=", targetMutatorUtilization(), " ");
     631            dataLog(m_collectorSlotVisitor->collectorMarkStack().size(), "+", m_mutatorMarkStack->size() + m_collectorSlotVisitor->mutatorMarkStack().size(), ", a=", m_bytesAllocatedThisCycle / 1024, " kb, b=", m_barriersExecuted, ", mu=", scheduler.currentDecision().targetMutatorUtilization(), " ");
    721632        }
    722633       
    … …  
    740651            dataLog("Live Weak Handles:\n", *m_collectorSlotVisitor);
    741652       
    742         MonotonicTime beforeConvergence = MonotonicTime::now();
    743        
    744653        {
    745654            TimingScope traceTimingScope(*this, "Heap::markToFixpoint tracing");
    … …  
    747656           
    748657            if (Options::useCollectorTimeslicing()) {
    749                 // Before we yield to the mutator, we should do GC work proportional to the time we
    750                 // spent paused. We initialize the timeslicer to start after this "mandatory" pause
    751                 // completes.
     658                scheduler.snapPhase();
    752659               
    753660                SlotVisitor::SharedDrainResult drainResult;
    754                
    755                 Seconds extraPause = (beforeConvergence - topOfLoop) * extraPauseRatio;
    756                 initialTime = beforeConvergence + extraPause;
    757                 drainResult = m_collectorSlotVisitor->drainInParallel(initialTime);
    758                
    759                 while (drainResult != SlotVisitor::SharedDrainResult::Done) {
    760                     cacheSchedulingStats();
    761                     if (shouldBeResumed()) {
     661                do {
     662                    auto decision = scheduler.currentDecision();
     663                    if (decision.shouldBeResumed()) {
    762664                        ResumeTheWorldScope resumeTheWorldScope(*this);
    763                         drainResult = m_collectorSlotVisitor->drainInParallelPassively(timeToStop());
     665                        drainResult = m_collectorSlotVisitor->drainInParallelPassively(decision.timeToStop());
     666                        if (drainResult == SlotVisitor::SharedDrainResult::Done) {
     667                            // At this point we will stop. But maybe the scheduler does not want
     668                            // that.
     669                            Seconds scheduledIdle = decision.timeToStop() - MonotonicTime::now();
     670                            // It's totally unclear what the value of collectPermittedIdleRatio
     671                            // should be, other than it should be greater than 0. You could even
     672                            // argue for it being greater than 1. We should tune it.
     673                            sleep(scheduledIdle * Options::collectorPermittedIdleRatio());
     674                        }
    764675                    } else
    765                         drainResult = m_collectorSlotVisitor->drainInParallel(timeToResume());
    766                 }
     676                        drainResult = m_collectorSlotVisitor->drainInParallel(decision.timeToResume());
     677                } while (drainResult != SlotVisitor::SharedDrainResult::Done);
    767678            } else {
    768679                // Disabling collector timeslicing is meant to be used together with
    … …  
    772683            }
    773684        }
    774        
    775         extraPauseRatio *= Options::extraPauseRatioIterationGrowthRate();
    776685    }
    777686

  • trunk/Source/JavaScriptCore/heap/Heap.h

    r209683 r209727  
    7676class MarkedArgumentBuffer;
    7777class SlotVisitor;
     78class SpaceTimeScheduler;
    7879class StopIfNecessaryTimer;
    7980class VM;
    … …  
    377378    friend class MarkedBlock;
    378379    friend class SlotVisitor;
     380    friend class SpaceTimeScheduler;
    379381    friend class IncrementalSweeper;
    380382    friend class HeapStatistics;

  • trunk/Source/JavaScriptCore/runtime/Options.h

    r209692 r209727  
    203203    v(double, concurrentGCMaxHeadroom, 1.5, Normal, nullptr) \
    204204    v(double, concurrentGCPeriodMS, 2, Normal, nullptr) \
    205     v(double, initialExtraPauseRatio, 0, Normal, nullptr) \
    206     v(double, extraPauseRatioIterationGrowthRate, 1.1, Normal, nullptr) \
    207205    v(bool, collectorShouldResumeFirst, false, Normal, nullptr) \
     206    v(double, collectorPermittedIdleRatio, 1, Normal, nullptr) \
    208207    v(bool, scribbleFreeCells, false, Normal, nullptr) \
    209208    v(double, sizeClassProgression, 1.4, Normal, nullptr) \
Note: See TracChangeset for help on using the changeset viewer.