⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 211069 in webkit


Ignore:
Timestamp:
Jan 23, 2017, 4:01:13 PM (10 years ago)
Author:
fpizlo@apple.com
Message:

Land the stochastic space-time scheduler disabled
​https://bugs.webkit.org/show_bug.cgi?id=167249

Reviewed by Saam Barati.

The space-time scheduler is pretty weird. It uses a periodic scheduler where the next period is
simply determined by an integer multiple of time since when the scheduler last snapped phase. It
snaps phase after constraint solving. Both the snapping of the phase after constraint solving and
the periodicity appear to be necessary for good performance. For example, if the space-time
scheduler decided that it was in the resume part of the phase just by virtue of having just
resumed, then it would be empirically worse than our scheduler which asks "what time is it?" to
decide whether it should be suspended or resumed even if it just suspended or resumed. I've spent
a lot of time wondering why these two features are essential, and I think I found a reason.

What's happening is that sometimes the GC has an overrun and its increment takes longer than it
should have. The current scheduler forgives overruns when constraint solving, which seems to
make sense because it cannot control whether constraint solving runs with the mutator resumed or
suspended. It has to be suspended currently. Snapping phase after constraint solving accomplishes
this. What's more surprising is how important it is to manage deadline misses during draining.
The relevant kind of deadline miss is when doing mutator-suspended draining to catch up to the
retreating wavefront. Deadline misses while doing this can happen systematically in some
workloads, like JetStream/hash-map and some test in Speedometer. It's because they have some
ginormous object and it takes like ~3ms+-1.5ms just to scan it. The space-time scheduler's use
of time to decide what to do saves the day here: after the deadline miss, the scheduler will
initially realize that it missed its deadline to resume the mutator. But as soon as it does this
it asks: "based on current time since phase snap, what should I do?". In the case of a deadline
miss, this question is essentially a weighted coin flip because of the high noise in the amount
of time that it takes to do things in the GC. If you overrun, you will probably overrun by
multiple milliseconds, which is enough that where you land in the space-time scheduler's timeline
is random. The likelihood that you land in the "resume mutator" part of the timeline has a
probability that is roughly the same as what the space-time scheduler calls mutator utilization.
This is a super weird property. I did not intend for it to have this property, but it appears to
be the most important property of this scheduler.

Based on this, it seems that the fact that the space-time scheduler could suspend the mutator
before draining runs out of work doesn't accomplish anything. As soon as you resume the
mutator, you have a retreating wavefront to worry about. But if the collector is happily scanning
things then it's almost certain that the collector will outpace the mutator. Also, anything that
the mutator asks us to revisit is deferred anyway.

In the past I've tried to replace the scheduler in one patch and this turned out to be annoying
because even a poorly conceived scheduler should be iterated on. This patch lands a new scheduler
called the StochasticSpaceTime scheduler. It replaces two of the known-good features of the old
scheduler: (1) it forgives constraint pauses and (2) after deadline overrun its choice is random,
weighted by the mutator utilization target. Unlike the old scheduler, this one will only suspend
the mutator when the draining terminates, but it may pause for any amount of time after an
iteration of constraint solving. It computes the targetPause by measuring constraint solving time
and multiplying by the pauseScale (0.3 by default). If smaller then minimumPause (0.3ms by
default), then it uses minimumPause instead. The stochastic scheduler will then definitely do at
least targetPause worth of suspended draining after the constraint solving iteration, and then
it will decide whether or not to do another one at random. The probability that it will choose to
resume is exactly mutatorUtilization, which is computed exactly as before. Therefore, the
probability of resumption starts at 0.7 and goes down as memory usage rises. Conversely, the
probability that we will stay suspended starts at 0.3 and goes up from there.

This new scheduler looks like it might be a 25% improvement on splay-latency. It also looks like
a small progression on hash-map. Hash-map is a great test of one of the worst cases of retreating
wavefront, since it is repeatedly storing to a ginormous array. This array is sure to take a
while to scan, and to complete, the GC must be smart enough to visit any new objects it finds
while scanning the array immediately after scanning that array. This new scheduler means that
after scanning the array, the probability that you will scan whatever you found in it starts at
0.3 and rises as the program allocates. It's sure to be 0.3, and not 0.3k, because after the
wavefront stops advancing, the only object on the mark stack after a constraint iteration will be
that array. Since there is sure to be a 0.3ms or longer pause, the GC will be sure to start
visiting this object. The GC can then complete if it just allows enough time after this to scan
whatever new objects it finds. If scanning the array overruns the deadline (and it almost
certainly will) then the probability that the GC keeps the mutator suspended is simply
1 - mutatorUtilization.

This scheduler is disabled by default. You can enable it with
--useStochasticMutatorScheduler=true.

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

(JSC::Heap::Heap):
(JSC::Heap::markToFixpoint):

  • heap/Heap.h:
  • heap/MarkingConstraintSet.cpp:

(JSC::MarkingConstraintSet::didStartMarking):
(JSC::MarkingConstraintSet::executeConvergenceImpl):
(JSC::MarkingConstraintSet::resetStats): Deleted.
(JSC::MarkingConstraintSet::executeBootstrap): Deleted.

  • heap/MarkingConstraintSet.h:
  • heap/MutatorScheduler.cpp:

(JSC::MutatorScheduler::didReachTermination):
(JSC::MutatorScheduler::synchronousDrainingDidStall):

  • heap/MutatorScheduler.h:
  • heap/SlotVisitor.cpp:

(JSC::SlotVisitor::didReachTermination):
(JSC::SlotVisitor::drainFromShared):

  • heap/StochasticSpaceTimeMutatorScheduler.cpp: Added.

(JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::Snapshot):
(JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::now):
(JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::bytesAllocatedThisCycle):
(JSC::StochasticSpaceTimeMutatorScheduler::StochasticSpaceTimeMutatorScheduler):
(JSC::StochasticSpaceTimeMutatorScheduler::~StochasticSpaceTimeMutatorScheduler):
(JSC::StochasticSpaceTimeMutatorScheduler::state):
(JSC::StochasticSpaceTimeMutatorScheduler::beginCollection):
(JSC::StochasticSpaceTimeMutatorScheduler::didStop):
(JSC::StochasticSpaceTimeMutatorScheduler::willResume):
(JSC::StochasticSpaceTimeMutatorScheduler::didReachTermination):
(JSC::StochasticSpaceTimeMutatorScheduler::didExecuteConstraints):
(JSC::StochasticSpaceTimeMutatorScheduler::synchronousDrainingDidStall):
(JSC::StochasticSpaceTimeMutatorScheduler::timeToStop):
(JSC::StochasticSpaceTimeMutatorScheduler::timeToResume):
(JSC::StochasticSpaceTimeMutatorScheduler::log):
(JSC::StochasticSpaceTimeMutatorScheduler::endCollection):
(JSC::StochasticSpaceTimeMutatorScheduler::setResumeTime):
(JSC::StochasticSpaceTimeMutatorScheduler::bytesAllocatedThisCycleImpl):
(JSC::StochasticSpaceTimeMutatorScheduler::bytesSinceBeginningOfCycle):
(JSC::StochasticSpaceTimeMutatorScheduler::maxHeadroom):
(JSC::StochasticSpaceTimeMutatorScheduler::headroomFullness):
(JSC::StochasticSpaceTimeMutatorScheduler::mutatorUtilization):

  • heap/StochasticSpaceTimeMutatorScheduler.h: Added.
  • runtime/Options.cpp:

(JSC::overrideDefaults):

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

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r210912 r211069  
    504504    heap/SlotVisitor.cpp
    505505    heap/SpaceTimeMutatorScheduler.cpp
     506    heap/StochasticSpaceTimeMutatorScheduler.cpp
    506507    heap/StopIfNecessaryTimer.cpp
    507508    heap/Subspace.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r211066 r211069  
     12017-01-22  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Land the stochastic space-time scheduler disabled
     4        https://bugs.webkit.org/show_bug.cgi?id=167249
     5
     6        Reviewed by Saam Barati.
     7       
     8        The space-time scheduler is pretty weird. It uses a periodic scheduler where the next period is
     9        simply determined by an integer multiple of time since when the scheduler last snapped phase. It
     10        snaps phase after constraint solving. Both the snapping of the phase after constraint solving and
     11        the periodicity appear to be necessary for good performance. For example, if the space-time
     12        scheduler decided that it was in the resume part of the phase just by virtue of having just
     13        resumed, then it would be empirically worse than our scheduler which asks "what time is it?" to
     14        decide whether it should be suspended or resumed even if it just suspended or resumed. I've spent
     15        a lot of time wondering why these two features are essential, and I think I found a reason.
     16       
     17        What's happening is that sometimes the GC has an overrun and its increment takes longer than it
     18        should have. The current scheduler forgives overruns when constraint solving, which seems to
     19        make sense because it cannot control whether constraint solving runs with the mutator resumed or
     20        suspended. It has to be suspended currently. Snapping phase after constraint solving accomplishes
     21        this. What's more surprising is how important it is to manage deadline misses during draining.
     22        The relevant kind of deadline miss is when doing mutator-suspended draining to catch up to the
     23        retreating wavefront. Deadline misses while doing this can happen systematically in some
     24        workloads, like JetStream/hash-map and some test in Speedometer. It's because they have some
     25        ginormous object and it takes like ~3ms+-1.5ms just to scan it. The space-time scheduler's use
     26        of time to decide what to do saves the day here: after the deadline miss, the scheduler will
     27        initially realize that it missed its deadline to resume the mutator. But as soon as it does this
     28        it asks: "based on current time since phase snap, what should I do?". In the case of a deadline
     29        miss, this question is essentially a weighted coin flip because of the high noise in the amount
     30        of time that it takes to do things in the GC. If you overrun, you will probably overrun by
     31        multiple milliseconds, which is enough that where you land in the space-time scheduler's timeline
     32        is random. The likelihood that you land in the "resume mutator" part of the timeline has a
     33        probability that is roughly the same as what the space-time scheduler calls mutator utilization.
     34        This is a super weird property. I did not intend for it to have this property, but it appears to
     35        be the most important property of this scheduler.
     36       
     37        Based on this, it seems that the fact that the space-time scheduler could suspend the mutator
     38        before draining runs out of work doesn't accomplish anything. As soon as you resume the
     39        mutator, you have a retreating wavefront to worry about. But if the collector is happily scanning
     40        things then it's almost certain that the collector will outpace the mutator. Also, anything that
     41        the mutator asks us to revisit is deferred anyway.
     42       
     43        In the past I've tried to replace the scheduler in one patch and this turned out to be annoying
     44        because even a poorly conceived scheduler should be iterated on. This patch lands a new scheduler
     45        called the StochasticSpaceTime scheduler. It replaces two of the known-good features of the old
     46        scheduler: (1) it forgives constraint pauses and (2) after deadline overrun its choice is random,
     47        weighted by the mutator utilization target. Unlike the old scheduler, this one will only suspend
     48        the mutator when the draining terminates, but it may pause for any amount of time after an
     49        iteration of constraint solving. It computes the targetPause by measuring constraint solving time
     50        and multiplying by the pauseScale (0.3 by default). If smaller then minimumPause (0.3ms by
     51        default), then it uses minimumPause instead. The stochastic scheduler will then definitely do at
     52        least targetPause worth of suspended draining after the constraint solving iteration, and then
     53        it will decide whether or not to do another one at random. The probability that it will choose to
     54        resume is exactly mutatorUtilization, which is computed exactly as before. Therefore, the
     55        probability of resumption starts at 0.7 and goes down as memory usage rises. Conversely, the
     56        probability that we will stay suspended starts at 0.3 and goes up from there.
     57       
     58        This new scheduler looks like it might be a 25% improvement on splay-latency. It also looks like
     59        a small progression on hash-map. Hash-map is a great test of one of the worst cases of retreating
     60        wavefront, since it is repeatedly storing to a ginormous array. This array is sure to take a
     61        while to scan, and to complete, the GC must be smart enough to visit any new objects it finds
     62        while scanning the array immediately after scanning that array. This new scheduler means that
     63        after scanning the array, the probability that you will scan whatever you found in it starts at
     64        0.3 and rises as the program allocates. It's sure to be 0.3, and not 0.3^k, because after the
     65        wavefront stops advancing, the only object on the mark stack after a constraint iteration will be
     66        that array. Since there is sure to be a 0.3ms or longer pause, the GC will be sure to start
     67        visiting this object. The GC can then complete if it just allows enough time after this to scan
     68        whatever new objects it finds. If scanning the array overruns the deadline (and it almost
     69        certainly will) then the probability that the GC keeps the mutator suspended is simply
     70        1 - mutatorUtilization.
     71       
     72        This scheduler is disabled by default. You can enable it with
     73        --useStochasticMutatorScheduler=true.
     74
     75        * CMakeLists.txt:
     76        * JavaScriptCore.xcodeproj/project.pbxproj:
     77        * heap/Heap.cpp:
     78        (JSC::Heap::Heap):
     79        (JSC::Heap::markToFixpoint):
     80        * heap/Heap.h:
     81        * heap/MarkingConstraintSet.cpp:
     82        (JSC::MarkingConstraintSet::didStartMarking):
     83        (JSC::MarkingConstraintSet::executeConvergenceImpl):
     84        (JSC::MarkingConstraintSet::resetStats): Deleted.
     85        (JSC::MarkingConstraintSet::executeBootstrap): Deleted.
     86        * heap/MarkingConstraintSet.h:
     87        * heap/MutatorScheduler.cpp:
     88        (JSC::MutatorScheduler::didReachTermination):
     89        (JSC::MutatorScheduler::synchronousDrainingDidStall):
     90        * heap/MutatorScheduler.h:
     91        * heap/SlotVisitor.cpp:
     92        (JSC::SlotVisitor::didReachTermination):
     93        (JSC::SlotVisitor::drainFromShared):
     94        * heap/StochasticSpaceTimeMutatorScheduler.cpp: Added.
     95        (JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::Snapshot):
     96        (JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::now):
     97        (JSC::StochasticSpaceTimeMutatorScheduler::Snapshot::bytesAllocatedThisCycle):
     98        (JSC::StochasticSpaceTimeMutatorScheduler::StochasticSpaceTimeMutatorScheduler):
     99        (JSC::StochasticSpaceTimeMutatorScheduler::~StochasticSpaceTimeMutatorScheduler):
     100        (JSC::StochasticSpaceTimeMutatorScheduler::state):
     101        (JSC::StochasticSpaceTimeMutatorScheduler::beginCollection):
     102        (JSC::StochasticSpaceTimeMutatorScheduler::didStop):
     103        (JSC::StochasticSpaceTimeMutatorScheduler::willResume):
     104        (JSC::StochasticSpaceTimeMutatorScheduler::didReachTermination):
     105        (JSC::StochasticSpaceTimeMutatorScheduler::didExecuteConstraints):
     106        (JSC::StochasticSpaceTimeMutatorScheduler::synchronousDrainingDidStall):
     107        (JSC::StochasticSpaceTimeMutatorScheduler::timeToStop):
     108        (JSC::StochasticSpaceTimeMutatorScheduler::timeToResume):
     109        (JSC::StochasticSpaceTimeMutatorScheduler::log):
     110        (JSC::StochasticSpaceTimeMutatorScheduler::endCollection):
     111        (JSC::StochasticSpaceTimeMutatorScheduler::setResumeTime):
     112        (JSC::StochasticSpaceTimeMutatorScheduler::bytesAllocatedThisCycleImpl):
     113        (JSC::StochasticSpaceTimeMutatorScheduler::bytesSinceBeginningOfCycle):
     114        (JSC::StochasticSpaceTimeMutatorScheduler::maxHeadroom):
     115        (JSC::StochasticSpaceTimeMutatorScheduler::headroomFullness):
     116        (JSC::StochasticSpaceTimeMutatorScheduler::mutatorUtilization):
     117        * heap/StochasticSpaceTimeMutatorScheduler.h: Added.
     118        * runtime/Options.cpp:
     119        (JSC::overrideDefaults):
     120        * runtime/Options.h:
     121
    11222017-01-23  Mark Lam  <mark.lam@apple.com>
    2123

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

    r210912 r211069  
    411411                0F4F82871E2FFDDD0075184C /* JSSegmentedVariableObjectSubspace.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F82851E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.cpp */; };
    412412                0F4F82881E2FFDE00075184C /* JSSegmentedVariableObjectSubspace.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F82861E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.h */; settings = {ATTRIBUTES = (Private, ); }; };
     413                0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */; };
     414                0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */; };
    413415                0F50AF3C193E8B3900674EE8 /* DFGStructureClobberState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */; };
    414416                0F5513A61D5A682C00C32BD8 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5513A51D5A682A00C32BD8 /* FreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    28642866                0F4F82851E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSSegmentedVariableObjectSubspace.cpp; sourceTree = "<group>"; };
    28652867                0F4F82861E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSSegmentedVariableObjectSubspace.h; sourceTree = "<group>"; };
     2868                0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StochasticSpaceTimeMutatorScheduler.cpp; sourceTree = "<group>"; };
     2869                0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StochasticSpaceTimeMutatorScheduler.h; sourceTree = "<group>"; };
    28662870                0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStructureClobberState.h; path = dfg/DFGStructureClobberState.h; sourceTree = "<group>"; };
    28672871                0F5513A51D5A682A00C32BD8 /* FreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FreeList.h; sourceTree = "<group>"; };
    … …  
    58225826                                0FDE87FA1DFE6E500064C390 /* SpaceTimeMutatorScheduler.cpp */,
    58235827                                0FDE87FB1DFE6E500064C390 /* SpaceTimeMutatorScheduler.h */,
     5828                                0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */,
     5829                                0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */,
    58245830                                0F7CF9501DC027D70098CC12 /* StopIfNecessaryTimer.cpp */,
    58255831                                0F7CF9511DC027D70098CC12 /* StopIfNecessaryTimer.h */,
    … …  
    81958201                                A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
    81968202                                0F2DD8151AB3D8BE00BBB8E8 /* DFGForAllKills.h in Headers */,
     8203                                0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */,
    81978204                                0F69CC89193AC60A0045759E /* DFGFrozenValue.h in Headers */,
    81988205                                86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
    … …  
    99919998                                0FC097A1146B28CA00CF2442 /* DFGThunks.cpp in Sources */,
    99929999                                0FD8A32717D51F5700CA2C40 /* DFGTierUpCheckInjectionPhase.cpp in Sources */,
     10000                                0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */,
    999310001                                0FD8A32917D51F5700CA2C40 /* DFGToFTLDeferredCompilationCallback.cpp in Sources */,
    999410002                                0FD8A32B17D51F5700CA2C40 /* DFGToFTLForOSREntryDeferredCompilationCallback.cpp in Sources */,

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

    r210891 r211069  
    5656#include "SpaceTimeMutatorScheduler.h"
    5757#include "SuperSampler.h"
     58#include "StochasticSpaceTimeMutatorScheduler.h"
    5859#include "StopIfNecessaryTimer.h"
    5960#include "SynchronousStopTheWorldMutatorScheduler.h"
    … …  
    285286    , m_sharedMutatorMarkStack(std::make_unique<MarkStackArray>())
    286287    , m_helperClient(&heapHelperPool())
    287     , m_scheduler(std::make_unique<SpaceTimeMutatorScheduler>(*this))
    288288    , m_threadLock(Box<Lock>::create())
    289289    , m_threadCondition(AutomaticThreadCondition::create())
    … …  
    291291    m_worldState.store(0);
    292292   
    293     if (Options::useConcurrentGC())
    294         m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
    295     else {
     293    if (Options::useConcurrentGC()) {
     294        if (Options::useStochasticMutatorScheduler())
     295            m_scheduler = std::make_unique<StochasticSpaceTimeMutatorScheduler>(*this);
     296        else
     297            m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
     298    } else {
    296299        // We simulate turning off concurrent GC by making the scheduler say that the world
    297300        // should always be stopped when the collector is running.
    … …  
    571574    SlotVisitor& slotVisitor = *m_collectorSlotVisitor;
    572575    slotVisitor.didStartMarking();
    573 
    574     m_constraintSet->resetStats();
     576    m_constraintSet->didStartMarking();
    575577   
    576578    m_scheduler->beginCollection();
    … …  
    578580        m_scheduler->log();
    579581   
    580     // Wondering what m_constraintSet->executeXYZ does? It's running the constraints created by
    581     // Heap::buildConstraintSet().
    582    
    583     m_constraintSet->executeBootstrap(slotVisitor, MonotonicTime::infinity());
    584     m_scheduler->didExecuteConstraints();
    585 
    586582    // After this, we will almost certainly fall through all of the "slotVisitor.isEmpty()"
    587583    // checks because bootstrap would have put things into the visitor. So, we should fall
    588584    // through to draining.
    589585   
    590     unsigned iteration = 1;
     586    if (!slotVisitor.didReachTermination()) {
     587        dataLog("Fatal: SlotVisitor should think that GC should terminate before constraint solving, but it does not think this.\n");
     588        dataLog("slotVisitor.isEmpty(): ", slotVisitor.isEmpty(), "\n");
     589        dataLog("slotVisitor.collectorMarkStack().isEmpty(): ", slotVisitor.collectorMarkStack().isEmpty(), "\n");
     590        dataLog("slotVisitor.mutatorMarkStack().isEmpty(): ", slotVisitor.mutatorMarkStack().isEmpty(), "\n");
     591        dataLog("m_numberOfActiveParallelMarkers: ", m_numberOfActiveParallelMarkers, "\n");
     592        dataLog("m_sharedCollectorMarkStack->isEmpty(): ", m_sharedCollectorMarkStack->isEmpty(), "\n");
     593        dataLog("m_sharedMutatorMarkStack->isEmpty(): ", m_sharedMutatorMarkStack->isEmpty(), "\n");
     594        dataLog("slotVisitor.didReachTermination(): ", slotVisitor.didReachTermination(), "\n");
     595        RELEASE_ASSERT_NOT_REACHED();
     596    }
     597   
    591598    for (;;) {
    592599        if (Options::logGC())
    … …  
    594601       
    595602        if (slotVisitor.didReachTermination()) {
    596             if (Options::logGC())
    597                 dataLog("i#", iteration, " ");
    598        
     603            m_scheduler->didReachTermination();
     604           
    599605            assertSharedMarkStacksEmpty();
    600606           
    … …  
    614620            // https://bugs.webkit.org/show_bug.cgi?id=166831
    615621           
     622            // Wondering what this does? Look at Heap::addCoreConstraints(). The DOM and others can also
     623            // add their own using Heap::addMarkingConstraint().
    616624            bool converged =
    617625                m_constraintSet->executeConvergence(slotVisitor, MonotonicTime::infinity());
    … …  
    622630           
    623631            m_scheduler->didExecuteConstraints();
    624             iteration++;
    625632        }
    626633       
    … …  
    632639            slotVisitor.drainInParallel(m_scheduler->timeToResume());
    633640        }
     641       
     642        m_scheduler->synchronousDrainingDidStall();
     643
     644        if (slotVisitor.didReachTermination())
     645            continue;
    634646       
    635647        if (!m_scheduler->shouldResume())

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

    r210844 r211069  
    369369    friend class SlotVisitor;
    370370    friend class SpaceTimeMutatorScheduler;
     371    friend class StochasticSpaceTimeMutatorScheduler;
    371372    friend class IncrementalSweeper;
    372373    friend class HeapStatistics;

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

    r210844 r211069  
    8787}
    8888
    89 void MarkingConstraintSet::resetStats()
     89void MarkingConstraintSet::didStartMarking()
    9090{
    9191    m_unexecutedRoots.clearAll();
    … …  
    104104        }
    105105    }
     106    m_iteration = 1;
    106107}
    107108
    … …  
    130131}
    131132
    132 bool MarkingConstraintSet::executeBootstrap(SlotVisitor& visitor, MonotonicTime timeout)
    133 {
    134     // Bootstrap means that we haven't done any object visiting yet. This means that we want to
    135     // only execute root constraints (which also happens to be those that we say are greyed by
    136     // resumption), since the other constraints are super unlikely to trigger without some object
    137     // visiting. The expectation is that the caller will go straight to object visiting after
    138     // this.
    139     ExecutionContext executionContext(*this, visitor, timeout);
    140     if (Options::logGC())
    141         dataLog("boot:");
    142     bool result = executionContext.drain(m_unexecutedRoots);
    143     if (Options::logGC())
    144         dataLog(" ");
    145     return result;
    146 }
    147 
    148133bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor, MonotonicTime timeout)
    149134{
    … …  
    167152    ExecutionContext executionContext(*this, visitor, timeout);
    168153   
     154    unsigned iteration = m_iteration++;
     155   
    169156    if (Options::logGC())
    170         dataLog("converge:");
     157        dataLog("i#", iteration, ":");
    171158
    172159    // If there are any constraints that we have not executed at all during this cycle, then
    … …  
    174161    if (!executionContext.drain(m_unexecutedRoots))
    175162        return false;
     163   
     164    // First iteration is before any visitor draining, so it's unlikely to trigger any constraints other
     165    // than roots.
     166    if (iteration == 1)
     167        return false;
     168   
    176169    if (!executionContext.drain(m_unexecutedOutgrowths))
    177170        return false;

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

    r210844 r211069  
    3737    ~MarkingConstraintSet();
    3838   
    39     void resetStats();
     39    void didStartMarking();
    4040   
    4141    void add(
    … …  
    5858    bool isWavefrontAdvancing(SlotVisitor&);
    5959    bool isWavefrontRetreating(SlotVisitor& visitor) { return !isWavefrontAdvancing(visitor); }
    60    
    61     // Executes only roots. Returns true if all roots have been executed. It's expected
    62     // that you'll do some draining after this and then use executeConvergence().
    63     bool executeBootstrap(SlotVisitor&, MonotonicTime timeout = MonotonicTime::infinity());
    6460   
    6561    // Returns true if this executed all constraints and none of them produced new work. This
    … …  
    8581    Vector<MarkingConstraint*> m_ordered;
    8682    Vector<MarkingConstraint*> m_outgrowths;
     83    unsigned m_iteration { 1 };
    8784};
    8885

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

    r210521 r211069  
    4747}
    4848
     49void MutatorScheduler::didReachTermination()
     50{
     51}
     52
    4953void MutatorScheduler::didExecuteConstraints()
     54{
     55}
     56
     57void MutatorScheduler::synchronousDrainingDidStall()
    5058{
    5159}

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

    r210521 r211069  
    5151    virtual void didStop();
    5252    virtual void willResume();
     53   
     54    // At the top of an iteration, the GC will may call didReachTermination.
     55    virtual void didReachTermination();
     56   
     57    // If it called didReachTermination, it will then later call didExecuteConstraints.
    5358    virtual void didExecuteConstraints();
     59   
     60    // After doing that, it will do synchronous draining. When this stalls - either due to timeout or
     61    // just 'cause, it will call this.
     62    virtual void synchronousDrainingDidStall();
    5463   
    5564    virtual MonotonicTime timeToStop() = 0; // Call while resumed, to ask when to stop.

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

    r210844 r211069  
    493493{
    494494    LockHolder locker(m_heap.m_markingMutex);
    495     return isEmpty() && didReachTermination(locker);
     495    return didReachTermination(locker);
    496496}
    497497
    498498bool SlotVisitor::didReachTermination(const LockHolder&)
    499499{
    500     return !m_heap.m_numberOfActiveParallelMarkers
     500    return isEmpty()
     501        && !m_heap.m_numberOfActiveParallelMarkers
    501502        && m_heap.m_sharedCollectorMarkStack->isEmpty()
    502503        && m_heap.m_sharedMutatorMarkStack->isEmpty();
    … …  
    515516    ASSERT(Options::numberOfGCMarkers());
    516517   
    517     {
    518         LockHolder locker(m_heap.m_markingMutex);
    519         m_heap.m_numberOfActiveParallelMarkers++;
    520     }
     518    bool isActive = false;
    521519    while (true) {
    522520        {
    523521            LockHolder locker(m_heap.m_markingMutex);
    524             m_heap.m_numberOfActiveParallelMarkers--;
     522            if (isActive)
     523                m_heap.m_numberOfActiveParallelMarkers--;
    525524            m_heap.m_numberOfWaitingParallelMarkers++;
    526525
    … …  
    569568       
    570569        drain(timeout);
     570        isActive = true;
    571571    }
    572572}

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

    r210971 r211069  
    199199    v(double, mediumHeapGrowthFactor, 1.5, Normal, nullptr) \
    200200    v(double, largeHeapGrowthFactor, 1.24, Normal, nullptr) \
    201     v(bool, useCollectorTimeslicing, true, Normal, nullptr) \
    202201    v(double, minimumMutatorUtilization, 0, Normal, nullptr) \
    203202    v(double, maximumMutatorUtilization, 0.7, Normal, nullptr) \
    204203    v(double, concurrentGCMaxHeadroom, 1.5, Normal, nullptr) \
    205204    v(double, concurrentGCPeriodMS, 2, Normal, nullptr) \
     205    v(bool, useStochasticMutatorScheduler, false, Normal, nullptr) \
     206    v(double, minimumGCPauseMS, 0.3, Normal, nullptr) \
     207    v(double, gcPauseScale, 0.3, Normal, nullptr) \
    206208    v(bool, scribbleFreeCells, false, Normal, nullptr) \
    207209    v(double, sizeClassProgression, 1.4, Normal, nullptr) \
Note: See TracChangeset for help on using the changeset viewer.