Diff
Modified: branches/safari-603-branch/Source/_javascript_Core/CMakeLists.txt (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/CMakeLists.txt 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/CMakeLists.txt 2017-01-24 23:29:25 UTC (rev 211115)
@@ -503,6 +503,7 @@
heap/MutatorState.cpp
heap/SlotVisitor.cpp
heap/SpaceTimeMutatorScheduler.cpp
+ heap/StochasticSpaceTimeMutatorScheduler.cpp
heap/StopIfNecessaryTimer.cpp
heap/Subspace.cpp
heap/SynchronousStopTheWorldMutatorScheduler.cpp
Modified: branches/safari-603-branch/Source/_javascript_Core/ChangeLog (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/ChangeLog 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/ChangeLog 2017-01-24 23:29:25 UTC (rev 211115)
@@ -1,5 +1,130 @@
2017-01-24 Matthew Hanson <matthew_han...@apple.com>
+ Merge r211069. rdar://problem/30173274
+
+ 2017-01-22 Filip Pizlo <fpi...@apple.com>
+
+ 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.3^k, 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:
+ * _javascript_Core.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:
+
+2017-01-24 Matthew Hanson <matthew_han...@apple.com>
+
Merge r211065. rdar://problem/29784295
2017-01-23 Filip Pizlo <fpi...@apple.com>
Modified: branches/safari-603-branch/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-01-24 23:29:25 UTC (rev 211115)
@@ -408,6 +408,8 @@
0F4DE1D11C4D764B004D6C11 /* B3OriginDump.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4DE1D01C4D764B004D6C11 /* B3OriginDump.cpp */; };
0F4F29DF18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */; };
0F4F29E018B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */; };
+ 0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */; };
+ 0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */; };
0F50AF3C193E8B3900674EE8 /* DFGStructureClobberState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */; };
0F5513A61D5A682C00C32BD8 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5513A51D5A682A00C32BD8 /* FreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F5513A81D5A68CD00C32BD8 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5513A71D5A68CB00C32BD8 /* FreeList.cpp */; };
@@ -2846,6 +2848,8 @@
0F4DE1D01C4D764B004D6C11 /* B3OriginDump.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3OriginDump.cpp; path = b3/B3OriginDump.cpp; sourceTree = "<group>"; };
0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStaticExecutionCountEstimationPhase.cpp; path = dfg/DFGStaticExecutionCountEstimationPhase.cpp; sourceTree = "<group>"; };
0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStaticExecutionCountEstimationPhase.h; path = dfg/DFGStaticExecutionCountEstimationPhase.h; sourceTree = "<group>"; };
+ 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StochasticSpaceTimeMutatorScheduler.cpp; sourceTree = "<group>"; };
+ 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StochasticSpaceTimeMutatorScheduler.h; sourceTree = "<group>"; };
0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStructureClobberState.h; path = dfg/DFGStructureClobberState.h; sourceTree = "<group>"; };
0F5513A51D5A682A00C32BD8 /* FreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FreeList.h; sourceTree = "<group>"; };
0F5513A71D5A68CB00C32BD8 /* FreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FreeList.cpp; sourceTree = "<group>"; };
@@ -5791,6 +5795,8 @@
0FCB408515C0A3C30048932B /* SlotVisitorInlines.h */,
0FDE87FA1DFE6E500064C390 /* SpaceTimeMutatorScheduler.cpp */,
0FDE87FB1DFE6E500064C390 /* SpaceTimeMutatorScheduler.h */,
+ 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */,
+ 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */,
0F7CF9501DC027D70098CC12 /* StopIfNecessaryTimer.cpp */,
0F7CF9511DC027D70098CC12 /* StopIfNecessaryTimer.h */,
142E3132134FF0A600AFADB5 /* Strong.h */,
@@ -8147,6 +8153,7 @@
0F9D339717FFC4E60073C2BC /* DFGFlushedAt.h in Headers */,
A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
0F2DD8151AB3D8BE00BBB8E8 /* DFGForAllKills.h in Headers */,
+ 0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */,
0F69CC89193AC60A0045759E /* DFGFrozenValue.h in Headers */,
86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
86EC9DC81328DF82002B2AD7 /* DFGGraph.h in Headers */,
@@ -9936,6 +9943,7 @@
0F2FCCFE18A60070001A27F8 /* DFGThreadData.cpp in Sources */,
0FC097A1146B28CA00CF2442 /* DFGThunks.cpp in Sources */,
0FD8A32717D51F5700CA2C40 /* DFGTierUpCheckInjectionPhase.cpp in Sources */,
+ 0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */,
0FD8A32917D51F5700CA2C40 /* DFGToFTLDeferredCompilationCallback.cpp in Sources */,
0FD8A32B17D51F5700CA2C40 /* DFGToFTLForOSREntryDeferredCompilationCallback.cpp in Sources */,
0FE7211D193B9C590031F6ED /* DFGTransition.cpp in Sources */,
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/Heap.cpp (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/Heap.cpp 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/Heap.cpp 2017-01-24 23:29:25 UTC (rev 211115)
@@ -55,6 +55,7 @@
#include "ShadowChicken.h"
#include "SpaceTimeMutatorScheduler.h"
#include "SuperSampler.h"
+#include "StochasticSpaceTimeMutatorScheduler.h"
#include "StopIfNecessaryTimer.h"
#include "SynchronousStopTheWorldMutatorScheduler.h"
#include "TypeProfilerLog.h"
@@ -284,15 +285,17 @@
, m_sharedCollectorMarkStack(std::make_unique<MarkStackArray>())
, m_sharedMutatorMarkStack(std::make_unique<MarkStackArray>())
, m_helperClient(&heapHelperPool())
- , m_scheduler(std::make_unique<SpaceTimeMutatorScheduler>(*this))
, m_threadLock(Box<Lock>::create())
, m_threadCondition(AutomaticThreadCondition::create())
{
m_worldState.store(0);
- if (Options::useConcurrentGC())
- m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
- else {
+ if (Options::useConcurrentGC()) {
+ if (Options::useStochasticMutatorScheduler())
+ m_scheduler = std::make_unique<StochasticSpaceTimeMutatorScheduler>(*this);
+ else
+ m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
+ } else {
// We simulate turning off concurrent GC by making the scheduler say that the world
// should always be stopped when the collector is running.
m_scheduler = std::make_unique<SynchronousStopTheWorldMutatorScheduler>();
@@ -570,32 +573,35 @@
SlotVisitor& slotVisitor = *m_collectorSlotVisitor;
slotVisitor.didStartMarking();
-
- m_constraintSet->resetStats();
+ m_constraintSet->didStartMarking();
m_scheduler->beginCollection();
if (Options::logGC())
m_scheduler->log();
- // Wondering what m_constraintSet->executeXYZ does? It's running the constraints created by
- // Heap::buildConstraintSet().
-
- m_constraintSet->executeBootstrap(slotVisitor, MonotonicTime::infinity());
- m_scheduler->didExecuteConstraints();
-
// After this, we will almost certainly fall through all of the "slotVisitor.isEmpty()"
// checks because bootstrap would have put things into the visitor. So, we should fall
// through to draining.
- unsigned iteration = 1;
+ if (!slotVisitor.didReachTermination()) {
+ dataLog("Fatal: SlotVisitor should think that GC should terminate before constraint solving, but it does not think this.\n");
+ dataLog("slotVisitor.isEmpty(): ", slotVisitor.isEmpty(), "\n");
+ dataLog("slotVisitor.collectorMarkStack().isEmpty(): ", slotVisitor.collectorMarkStack().isEmpty(), "\n");
+ dataLog("slotVisitor.mutatorMarkStack().isEmpty(): ", slotVisitor.mutatorMarkStack().isEmpty(), "\n");
+ dataLog("m_numberOfActiveParallelMarkers: ", m_numberOfActiveParallelMarkers, "\n");
+ dataLog("m_sharedCollectorMarkStack->isEmpty(): ", m_sharedCollectorMarkStack->isEmpty(), "\n");
+ dataLog("m_sharedMutatorMarkStack->isEmpty(): ", m_sharedMutatorMarkStack->isEmpty(), "\n");
+ dataLog("slotVisitor.didReachTermination(): ", slotVisitor.didReachTermination(), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+
for (;;) {
if (Options::logGC())
dataLog("v=", bytesVisited() / 1024, "kb o=", m_opaqueRoots.size(), " b=", m_barriersExecuted, " ");
if (slotVisitor.didReachTermination()) {
- if (Options::logGC())
- dataLog("i#", iteration, " ");
-
+ m_scheduler->didReachTermination();
+
assertSharedMarkStacksEmpty();
slotVisitor.mergeIfNecessary();
@@ -613,6 +619,8 @@
// when we have deep stacks or a lot of DOM stuff.
// https://bugs.webkit.org/show_bug.cgi?id=166831
+ // Wondering what this does? Look at Heap::addCoreConstraints(). The DOM and others can also
+ // add their own using Heap::addMarkingConstraint().
bool converged =
m_constraintSet->executeConvergence(slotVisitor, MonotonicTime::infinity());
if (converged && slotVisitor.isEmpty()) {
@@ -621,7 +629,6 @@
}
m_scheduler->didExecuteConstraints();
- iteration++;
}
if (Options::logGC())
@@ -632,6 +639,11 @@
slotVisitor.drainInParallel(m_scheduler->timeToResume());
}
+ m_scheduler->synchronousDrainingDidStall();
+
+ if (slotVisitor.didReachTermination())
+ continue;
+
if (!m_scheduler->shouldResume())
continue;
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/Heap.h (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/Heap.h 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/Heap.h 2017-01-24 23:29:25 UTC (rev 211115)
@@ -368,6 +368,7 @@
friend class MarkedBlock;
friend class SlotVisitor;
friend class SpaceTimeMutatorScheduler;
+ friend class StochasticSpaceTimeMutatorScheduler;
friend class IncrementalSweeper;
friend class HeapStatistics;
friend class VM;
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.cpp (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.cpp 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.cpp 2017-01-24 23:29:25 UTC (rev 211115)
@@ -86,7 +86,7 @@
{
}
-void MarkingConstraintSet::resetStats()
+void MarkingConstraintSet::didStartMarking()
{
m_unexecutedRoots.clearAll();
m_unexecutedOutgrowths.clearAll();
@@ -103,6 +103,7 @@
break;
}
}
+ m_iteration = 1;
}
void MarkingConstraintSet::add(CString abbreviatedName, CString name, Function<void(SlotVisitor&, const VisitingTimeout&)> function, ConstraintVolatility volatility)
@@ -129,22 +130,6 @@
m_set.append(WTFMove(constraint));
}
-bool MarkingConstraintSet::executeBootstrap(SlotVisitor& visitor, MonotonicTime timeout)
-{
- // Bootstrap means that we haven't done any object visiting yet. This means that we want to
- // only execute root constraints (which also happens to be those that we say are greyed by
- // resumption), since the other constraints are super unlikely to trigger without some object
- // visiting. The expectation is that the caller will go straight to object visiting after
- // this.
- ExecutionContext executionContext(*this, visitor, timeout);
- if (Options::logGC())
- dataLog("boot:");
- bool result = executionContext.drain(m_unexecutedRoots);
- if (Options::logGC())
- dataLog(" ");
- return result;
-}
-
bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor, MonotonicTime timeout)
{
bool result = executeConvergenceImpl(visitor, timeout);
@@ -166,13 +151,21 @@
{
ExecutionContext executionContext(*this, visitor, timeout);
+ unsigned iteration = m_iteration++;
+
if (Options::logGC())
- dataLog("converge:");
+ dataLog("i#", iteration, ":");
// If there are any constraints that we have not executed at all during this cycle, then
// we should execute those now.
if (!executionContext.drain(m_unexecutedRoots))
return false;
+
+ // First iteration is before any visitor draining, so it's unlikely to trigger any constraints other
+ // than roots.
+ if (iteration == 1)
+ return false;
+
if (!executionContext.drain(m_unexecutedOutgrowths))
return false;
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.h (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.h 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/MarkingConstraintSet.h 2017-01-24 23:29:25 UTC (rev 211115)
@@ -36,7 +36,7 @@
MarkingConstraintSet();
~MarkingConstraintSet();
- void resetStats();
+ void didStartMarking();
void add(
CString abbreviatedName,
@@ -58,10 +58,6 @@
bool isWavefrontAdvancing(SlotVisitor&);
bool isWavefrontRetreating(SlotVisitor& visitor) { return !isWavefrontAdvancing(visitor); }
- // Executes only roots. Returns true if all roots have been executed. It's expected
- // that you'll do some draining after this and then use executeConvergence().
- bool executeBootstrap(SlotVisitor&, MonotonicTime timeout = MonotonicTime::infinity());
-
// Returns true if this executed all constraints and none of them produced new work. This
// assumes that you've alraedy visited roots and drained from there.
bool executeConvergence(
@@ -84,6 +80,7 @@
Vector<std::unique_ptr<MarkingConstraint>> m_set;
Vector<MarkingConstraint*> m_ordered;
Vector<MarkingConstraint*> m_outgrowths;
+ unsigned m_iteration { 1 };
};
} // namespace JSC
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.cpp (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.cpp 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.cpp 2017-01-24 23:29:25 UTC (rev 211115)
@@ -46,10 +46,18 @@
{
}
+void MutatorScheduler::didReachTermination()
+{
+}
+
void MutatorScheduler::didExecuteConstraints()
{
}
+void MutatorScheduler::synchronousDrainingDidStall()
+{
+}
+
void MutatorScheduler::log()
{
}
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.h (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.h 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/MutatorScheduler.h 2017-01-24 23:29:25 UTC (rev 211115)
@@ -50,8 +50,17 @@
virtual void didStop();
virtual void willResume();
+
+ // At the top of an iteration, the GC will may call didReachTermination.
+ virtual void didReachTermination();
+
+ // If it called didReachTermination, it will then later call didExecuteConstraints.
virtual void didExecuteConstraints();
+ // After doing that, it will do synchronous draining. When this stalls - either due to timeout or
+ // just 'cause, it will call this.
+ virtual void synchronousDrainingDidStall();
+
virtual MonotonicTime timeToStop() = 0; // Call while resumed, to ask when to stop.
virtual MonotonicTime timeToResume() = 0; // Call while stopped, to ask when to resume.
Modified: branches/safari-603-branch/Source/_javascript_Core/heap/SlotVisitor.cpp (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/SlotVisitor.cpp 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/SlotVisitor.cpp 2017-01-24 23:29:25 UTC (rev 211115)
@@ -492,12 +492,13 @@
bool SlotVisitor::didReachTermination()
{
LockHolder locker(m_heap.m_markingMutex);
- return isEmpty() && didReachTermination(locker);
+ return didReachTermination(locker);
}
bool SlotVisitor::didReachTermination(const LockHolder&)
{
- return !m_heap.m_numberOfActiveParallelMarkers
+ return isEmpty()
+ && !m_heap.m_numberOfActiveParallelMarkers
&& m_heap.m_sharedCollectorMarkStack->isEmpty()
&& m_heap.m_sharedMutatorMarkStack->isEmpty();
}
@@ -514,14 +515,12 @@
ASSERT(Options::numberOfGCMarkers());
- {
- LockHolder locker(m_heap.m_markingMutex);
- m_heap.m_numberOfActiveParallelMarkers++;
- }
+ bool isActive = false;
while (true) {
{
LockHolder locker(m_heap.m_markingMutex);
- m_heap.m_numberOfActiveParallelMarkers--;
+ if (isActive)
+ m_heap.m_numberOfActiveParallelMarkers--;
m_heap.m_numberOfWaitingParallelMarkers++;
if (sharedDrainMode == MasterDrain) {
@@ -568,6 +567,7 @@
}
drain(timeout);
+ isActive = true;
}
}
Added: branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.cpp (0 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.cpp (rev 0)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.cpp 2017-01-24 23:29:25 UTC (rev 211115)
@@ -0,0 +1,222 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "StochasticSpaceTimeMutatorScheduler.h"
+
+#include "JSCInlines.h"
+
+namespace JSC {
+
+// The scheduler will often make decisions based on state that is in flux. It will be fine so
+// long as multiple uses of the same value all see the same value. We wouldn't get this for free,
+// since our need to modularize the calculation results in a tendency to access the same mutable
+// field in Heap multiple times, and to access the current time multiple times.
+class StochasticSpaceTimeMutatorScheduler::Snapshot {
+public:
+ Snapshot(StochasticSpaceTimeMutatorScheduler& scheduler)
+ {
+ m_now = MonotonicTime::now();
+ m_bytesAllocatedThisCycle = scheduler.bytesAllocatedThisCycleImpl();
+ }
+
+ MonotonicTime now() const { return m_now; }
+
+ double bytesAllocatedThisCycle() const { return m_bytesAllocatedThisCycle; }
+
+private:
+ MonotonicTime m_now;
+ double m_bytesAllocatedThisCycle;
+};
+
+StochasticSpaceTimeMutatorScheduler::StochasticSpaceTimeMutatorScheduler(Heap& heap)
+ : m_heap(heap)
+ , m_minimumPause(Seconds::fromMilliseconds(Options::minimumGCPauseMS()))
+ , m_pauseScale(Options::gcPauseScale())
+{
+}
+
+StochasticSpaceTimeMutatorScheduler::~StochasticSpaceTimeMutatorScheduler()
+{
+}
+
+MutatorScheduler::State StochasticSpaceTimeMutatorScheduler::state() const
+{
+ return m_state;
+}
+
+void StochasticSpaceTimeMutatorScheduler::beginCollection()
+{
+ RELEASE_ASSERT(m_state == Normal);
+ m_state = Stopped;
+
+ m_bytesAllocatedThisCycleAtTheBeginning = m_heap.m_bytesAllocatedThisCycle;
+ m_bytesAllocatedThisCycleAtTheEnd =
+ Options::concurrentGCMaxHeadroom() *
+ std::max<double>(m_bytesAllocatedThisCycleAtTheBeginning, m_heap.m_maxEdenSize);
+ m_beforeConstraints = MonotonicTime::now();
+}
+
+void StochasticSpaceTimeMutatorScheduler::didStop()
+{
+ RELEASE_ASSERT(m_state == Stopped || m_state == Resumed);
+ m_state = Stopped;
+}
+
+void StochasticSpaceTimeMutatorScheduler::willResume()
+{
+ RELEASE_ASSERT(m_state == Stopped || m_state == Resumed);
+ m_state = Resumed;
+}
+
+void StochasticSpaceTimeMutatorScheduler::didReachTermination()
+{
+ m_beforeConstraints = MonotonicTime::now();
+}
+
+void StochasticSpaceTimeMutatorScheduler::didExecuteConstraints()
+{
+ Snapshot snapshot(*this);
+
+ Seconds constraintExecutionDuration = snapshot.now() - m_beforeConstraints;
+
+ m_targetPause = std::max(
+ constraintExecutionDuration * m_pauseScale,
+ m_minimumPause);
+
+ if (Options::logGC())
+ dataLog("tp=", m_targetPause.milliseconds(), "ms ");
+
+ m_plannedResumeTime = snapshot.now() + m_targetPause;
+}
+
+void StochasticSpaceTimeMutatorScheduler::synchronousDrainingDidStall()
+{
+ Snapshot snapshot(*this);
+
+ double resumeProbability = mutatorUtilization(snapshot);
+ bool shouldResume = m_random.get() < resumeProbability;
+
+ if (shouldResume) {
+ m_plannedResumeTime = snapshot.now();
+ return;
+ }
+
+ m_plannedResumeTime = snapshot.now() + m_targetPause;
+}
+
+MonotonicTime StochasticSpaceTimeMutatorScheduler::timeToStop()
+{
+ switch (m_state) {
+ case Normal:
+ return MonotonicTime::infinity();
+ case Stopped:
+ return MonotonicTime::now();
+ case Resumed: {
+ // Once we're running, we keep going.
+ // FIXME: Maybe force stop when we run out of headroom?
+ return MonotonicTime::infinity();
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return MonotonicTime();
+}
+
+MonotonicTime StochasticSpaceTimeMutatorScheduler::timeToResume()
+{
+ switch (m_state) {
+ case Normal:
+ case Resumed:
+ return MonotonicTime::now();
+ case Stopped:
+ return m_plannedResumeTime;
+ }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return MonotonicTime();
+}
+
+void StochasticSpaceTimeMutatorScheduler::log()
+{
+ ASSERT(Options::logGC());
+ Snapshot snapshot(*this);
+ dataLog(
+ "a=", format("%.0lf", bytesSinceBeginningOfCycle(snapshot) / 1024), " kb ",
+ "hf=", format("%.3lf", headroomFullness(snapshot)), " ",
+ "mu=", format("%.3lf", mutatorUtilization(snapshot)), " ");
+}
+
+void StochasticSpaceTimeMutatorScheduler::endCollection()
+{
+ m_state = Normal;
+}
+
+double StochasticSpaceTimeMutatorScheduler::bytesAllocatedThisCycleImpl()
+{
+ return m_heap.m_bytesAllocatedThisCycle;
+}
+
+double StochasticSpaceTimeMutatorScheduler::bytesSinceBeginningOfCycle(const Snapshot& snapshot)
+{
+ return snapshot.bytesAllocatedThisCycle() - m_bytesAllocatedThisCycleAtTheBeginning;
+}
+
+double StochasticSpaceTimeMutatorScheduler::maxHeadroom()
+{
+ return m_bytesAllocatedThisCycleAtTheEnd - m_bytesAllocatedThisCycleAtTheBeginning;
+}
+
+double StochasticSpaceTimeMutatorScheduler::headroomFullness(const Snapshot& snapshot)
+{
+ double result = bytesSinceBeginningOfCycle(snapshot) / maxHeadroom();
+
+ // headroomFullness can be NaN and other interesting things if
+ // bytesAllocatedThisCycleAtTheBeginning is zero. We see that in debug tests. This code
+ // defends against all floating point dragons.
+
+ if (!(result >= 0))
+ result = 0;
+ if (!(result <= 1))
+ result = 1;
+
+ return result;
+}
+
+double StochasticSpaceTimeMutatorScheduler::mutatorUtilization(const Snapshot& snapshot)
+{
+ double mutatorUtilization = 1 - headroomFullness(snapshot);
+
+ // Scale the mutator utilization into the permitted window.
+ mutatorUtilization =
+ Options::minimumMutatorUtilization() +
+ mutatorUtilization * (
+ Options::maximumMutatorUtilization() -
+ Options::minimumMutatorUtilization());
+
+ return mutatorUtilization;
+}
+
+} // namespace JSC
+
Added: branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.h (0 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.h (rev 0)
+++ branches/safari-603-branch/Source/_javascript_Core/heap/StochasticSpaceTimeMutatorScheduler.h 2017-01-24 23:29:25 UTC (rev 211115)
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include "MutatorScheduler.h"
+#include <wtf/Seconds.h>
+#include <wtf/WeakRandom.h>
+
+namespace JSC {
+
+class Heap;
+
+// The JSC concurrent GC sometimes stops the world in order to stay ahead of it. These deliberate,
+// synthetic pauses ensure that the GC won't have to do one huge pause in order to catch up to the
+// retreating wavefront. The scheduler is called "space-time" because it links the amount of time
+// that the world is paused for to the amount of space that the world allocated since the GC cycle
+// began.
+
+class StochasticSpaceTimeMutatorScheduler : public MutatorScheduler {
+public:
+ StochasticSpaceTimeMutatorScheduler(Heap&);
+ ~StochasticSpaceTimeMutatorScheduler();
+
+ State state() const override;
+
+ void beginCollection() override;
+
+ void didStop() override;
+ void willResume() override;
+ void didReachTermination() override;
+ void didExecuteConstraints() override;
+ void synchronousDrainingDidStall() override;
+
+ MonotonicTime timeToStop() override;
+ MonotonicTime timeToResume() override;
+
+ void log() override;
+
+ void endCollection() override;
+
+private:
+ class Snapshot;
+ friend class Snapshot;
+
+ double bytesAllocatedThisCycleImpl();
+
+ double bytesSinceBeginningOfCycle(const Snapshot&);
+ double maxHeadroom();
+ double headroomFullness(const Snapshot&);
+ double mutatorUtilization(const Snapshot&);
+
+ Heap& m_heap;
+ State m_state { Normal };
+
+ WeakRandom m_random;
+
+ Seconds m_minimumPause;
+ double m_pauseScale;
+ Seconds m_targetPause;
+
+ double m_bytesAllocatedThisCycleAtTheBeginning { 0 };
+ double m_bytesAllocatedThisCycleAtTheEnd { 0 };
+
+ MonotonicTime m_beforeConstraints;
+ MonotonicTime m_plannedResumeTime;
+};
+
+} // namespace JSC
+
Modified: branches/safari-603-branch/Source/_javascript_Core/runtime/Options.h (211114 => 211115)
--- branches/safari-603-branch/Source/_javascript_Core/runtime/Options.h 2017-01-24 23:25:38 UTC (rev 211114)
+++ branches/safari-603-branch/Source/_javascript_Core/runtime/Options.h 2017-01-24 23:29:25 UTC (rev 211115)
@@ -198,11 +198,13 @@
v(double, mediumHeapRAMFraction, 0.5, Normal, nullptr) \
v(double, mediumHeapGrowthFactor, 1.5, Normal, nullptr) \
v(double, largeHeapGrowthFactor, 1.24, Normal, nullptr) \
- v(bool, useCollectorTimeslicing, true, Normal, nullptr) \
v(double, minimumMutatorUtilization, 0, Normal, nullptr) \
v(double, maximumMutatorUtilization, 0.7, Normal, nullptr) \
v(double, concurrentGCMaxHeadroom, 1.5, Normal, nullptr) \
v(double, concurrentGCPeriodMS, 2, Normal, nullptr) \
+ v(bool, useStochasticMutatorScheduler, false, Normal, nullptr) \
+ v(double, minimumGCPauseMS, 0.3, Normal, nullptr) \
+ v(double, gcPauseScale, 0.3, Normal, nullptr) \
v(bool, scribbleFreeCells, false, Normal, nullptr) \
v(double, sizeClassProgression, 1.4, Normal, nullptr) \
v(unsigned, largeAllocationCutoff, 100000, Normal, nullptr) \
