<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[211069] trunk/Source/JavaScriptCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/211069">211069</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2017-01-23 16:01:13 -0800 (Mon, 23 Jan 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>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:
* 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:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreCMakeListstxt">trunk/Source/JavaScriptCore/CMakeLists.txt</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeapcpp">trunk/Source/JavaScriptCore/heap/Heap.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeaph">trunk/Source/JavaScriptCore/heap/Heap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapMarkingConstraintSetcpp">trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapMarkingConstraintSeth">trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapMutatorSchedulercpp">trunk/Source/JavaScriptCore/heap/MutatorScheduler.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapMutatorSchedulerh">trunk/Source/JavaScriptCore/heap/MutatorScheduler.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapSlotVisitorcpp">trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeOptionsh">trunk/Source/JavaScriptCore/runtime/Options.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreheapStochasticSpaceTimeMutatorSchedulercpp">trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapStochasticSpaceTimeMutatorSchedulerh">trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/CMakeLists.txt (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -503,6 +503,7 @@
</span><span class="cx"> heap/MutatorState.cpp
</span><span class="cx"> heap/SlotVisitor.cpp
</span><span class="cx"> heap/SpaceTimeMutatorScheduler.cpp
</span><ins>+ heap/StochasticSpaceTimeMutatorScheduler.cpp
</ins><span class="cx"> heap/StopIfNecessaryTimer.cpp
</span><span class="cx"> heap/Subspace.cpp
</span><span class="cx"> heap/SynchronousStopTheWorldMutatorScheduler.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -1,3 +1,124 @@
</span><ins>+2017-01-22 Filip Pizlo <fpizlo@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:
+ * 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:
+
</ins><span class="cx"> 2017-01-23 Mark Lam <mark.lam@apple.com>
</span><span class="cx">
</span><span class="cx"> Added a comment to clarify an assertion.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -410,6 +410,8 @@
</span><span class="cx"> 0F4F29E018B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */; };
</span><span class="cx"> 0F4F82871E2FFDDD0075184C /* JSSegmentedVariableObjectSubspace.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F82851E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.cpp */; };
</span><span class="cx"> 0F4F82881E2FFDE00075184C /* JSSegmentedVariableObjectSubspace.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F82861E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><ins>+ 0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */; };
+ 0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */; };
</ins><span class="cx"> 0F50AF3C193E8B3900674EE8 /* DFGStructureClobberState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */; };
</span><span class="cx"> 0F5513A61D5A682C00C32BD8 /* FreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5513A51D5A682A00C32BD8 /* FreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F5513A81D5A68CD00C32BD8 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5513A71D5A68CB00C32BD8 /* FreeList.cpp */; };
</span><span class="lines">@@ -2863,6 +2865,8 @@
</span><span class="cx"> 0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStaticExecutionCountEstimationPhase.h; path = dfg/DFGStaticExecutionCountEstimationPhase.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F4F82851E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSSegmentedVariableObjectSubspace.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F4F82861E2FFDDB0075184C /* JSSegmentedVariableObjectSubspace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSSegmentedVariableObjectSubspace.h; sourceTree = "<group>"; };
</span><ins>+ 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>"; };
</ins><span class="cx"> 0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStructureClobberState.h; path = dfg/DFGStructureClobberState.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F5513A51D5A682A00C32BD8 /* FreeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FreeList.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F5513A71D5A68CB00C32BD8 /* FreeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FreeList.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -5821,6 +5825,8 @@
</span><span class="cx"> 0FCB408515C0A3C30048932B /* SlotVisitorInlines.h */,
</span><span class="cx"> 0FDE87FA1DFE6E500064C390 /* SpaceTimeMutatorScheduler.cpp */,
</span><span class="cx"> 0FDE87FB1DFE6E500064C390 /* SpaceTimeMutatorScheduler.h */,
</span><ins>+ 0F4F82891E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.cpp */,
+ 0F4F828A1E31B9710075184C /* StochasticSpaceTimeMutatorScheduler.h */,
</ins><span class="cx"> 0F7CF9501DC027D70098CC12 /* StopIfNecessaryTimer.cpp */,
</span><span class="cx"> 0F7CF9511DC027D70098CC12 /* StopIfNecessaryTimer.h */,
</span><span class="cx"> 142E3132134FF0A600AFADB5 /* Strong.h */,
</span><span class="lines">@@ -8194,6 +8200,7 @@
</span><span class="cx"> 0F9D339717FFC4E60073C2BC /* DFGFlushedAt.h in Headers */,
</span><span class="cx"> A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
</span><span class="cx"> 0F2DD8151AB3D8BE00BBB8E8 /* DFGForAllKills.h in Headers */,
</span><ins>+ 0F4F828C1E31B9760075184C /* StochasticSpaceTimeMutatorScheduler.h in Headers */,
</ins><span class="cx"> 0F69CC89193AC60A0045759E /* DFGFrozenValue.h in Headers */,
</span><span class="cx"> 86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
</span><span class="cx"> 86EC9DC81328DF82002B2AD7 /* DFGGraph.h in Headers */,
</span><span class="lines">@@ -9990,6 +9997,7 @@
</span><span class="cx"> 0F2FCCFE18A60070001A27F8 /* DFGThreadData.cpp in Sources */,
</span><span class="cx"> 0FC097A1146B28CA00CF2442 /* DFGThunks.cpp in Sources */,
</span><span class="cx"> 0FD8A32717D51F5700CA2C40 /* DFGTierUpCheckInjectionPhase.cpp in Sources */,
</span><ins>+ 0F4F828B1E31B9740075184C /* StochasticSpaceTimeMutatorScheduler.cpp in Sources */,
</ins><span class="cx"> 0FD8A32917D51F5700CA2C40 /* DFGToFTLDeferredCompilationCallback.cpp in Sources */,
</span><span class="cx"> 0FD8A32B17D51F5700CA2C40 /* DFGToFTLForOSREntryDeferredCompilationCallback.cpp in Sources */,
</span><span class="cx"> 0FE7211D193B9C590031F6ED /* DFGTransition.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.cpp (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.cpp 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/Heap.cpp 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -55,6 +55,7 @@
</span><span class="cx"> #include "ShadowChicken.h"
</span><span class="cx"> #include "SpaceTimeMutatorScheduler.h"
</span><span class="cx"> #include "SuperSampler.h"
</span><ins>+#include "StochasticSpaceTimeMutatorScheduler.h"
</ins><span class="cx"> #include "StopIfNecessaryTimer.h"
</span><span class="cx"> #include "SynchronousStopTheWorldMutatorScheduler.h"
</span><span class="cx"> #include "TypeProfilerLog.h"
</span><span class="lines">@@ -284,15 +285,17 @@
</span><span class="cx"> , m_sharedCollectorMarkStack(std::make_unique<MarkStackArray>())
</span><span class="cx"> , m_sharedMutatorMarkStack(std::make_unique<MarkStackArray>())
</span><span class="cx"> , m_helperClient(&heapHelperPool())
</span><del>- , m_scheduler(std::make_unique<SpaceTimeMutatorScheduler>(*this))
</del><span class="cx"> , m_threadLock(Box<Lock>::create())
</span><span class="cx"> , m_threadCondition(AutomaticThreadCondition::create())
</span><span class="cx"> {
</span><span class="cx"> m_worldState.store(0);
</span><span class="cx">
</span><del>- if (Options::useConcurrentGC())
- m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
- else {
</del><ins>+ if (Options::useConcurrentGC()) {
+ if (Options::useStochasticMutatorScheduler())
+ m_scheduler = std::make_unique<StochasticSpaceTimeMutatorScheduler>(*this);
+ else
+ m_scheduler = std::make_unique<SpaceTimeMutatorScheduler>(*this);
+ } else {
</ins><span class="cx"> // We simulate turning off concurrent GC by making the scheduler say that the world
</span><span class="cx"> // should always be stopped when the collector is running.
</span><span class="cx"> m_scheduler = std::make_unique<SynchronousStopTheWorldMutatorScheduler>();
</span><span class="lines">@@ -570,32 +573,35 @@
</span><span class="cx">
</span><span class="cx"> SlotVisitor& slotVisitor = *m_collectorSlotVisitor;
</span><span class="cx"> slotVisitor.didStartMarking();
</span><del>-
- m_constraintSet->resetStats();
</del><ins>+ m_constraintSet->didStartMarking();
</ins><span class="cx">
</span><span class="cx"> m_scheduler->beginCollection();
</span><span class="cx"> if (Options::logGC())
</span><span class="cx"> m_scheduler->log();
</span><span class="cx">
</span><del>- // Wondering what m_constraintSet->executeXYZ does? It's running the constraints created by
- // Heap::buildConstraintSet().
-
- m_constraintSet->executeBootstrap(slotVisitor, MonotonicTime::infinity());
- m_scheduler->didExecuteConstraints();
-
</del><span class="cx"> // After this, we will almost certainly fall through all of the "slotVisitor.isEmpty()"
</span><span class="cx"> // checks because bootstrap would have put things into the visitor. So, we should fall
</span><span class="cx"> // through to draining.
</span><span class="cx">
</span><del>- unsigned iteration = 1;
</del><ins>+ 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();
+ }
+
</ins><span class="cx"> for (;;) {
</span><span class="cx"> if (Options::logGC())
</span><span class="cx"> dataLog("v=", bytesVisited() / 1024, "kb o=", m_opaqueRoots.size(), " b=", m_barriersExecuted, " ");
</span><span class="cx">
</span><span class="cx"> if (slotVisitor.didReachTermination()) {
</span><del>- if (Options::logGC())
- dataLog("i#", iteration, " ");
-
</del><ins>+ m_scheduler->didReachTermination();
+
</ins><span class="cx"> assertSharedMarkStacksEmpty();
</span><span class="cx">
</span><span class="cx"> slotVisitor.mergeIfNecessary();
</span><span class="lines">@@ -613,6 +619,8 @@
</span><span class="cx"> // when we have deep stacks or a lot of DOM stuff.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=166831
</span><span class="cx">
</span><ins>+ // Wondering what this does? Look at Heap::addCoreConstraints(). The DOM and others can also
+ // add their own using Heap::addMarkingConstraint().
</ins><span class="cx"> bool converged =
</span><span class="cx"> m_constraintSet->executeConvergence(slotVisitor, MonotonicTime::infinity());
</span><span class="cx"> if (converged && slotVisitor.isEmpty()) {
</span><span class="lines">@@ -621,7 +629,6 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> m_scheduler->didExecuteConstraints();
</span><del>- iteration++;
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (Options::logGC())
</span><span class="lines">@@ -632,6 +639,11 @@
</span><span class="cx"> slotVisitor.drainInParallel(m_scheduler->timeToResume());
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ m_scheduler->synchronousDrainingDidStall();
+
+ if (slotVisitor.didReachTermination())
+ continue;
+
</ins><span class="cx"> if (!m_scheduler->shouldResume())
</span><span class="cx"> continue;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.h (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.h 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/Heap.h 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -368,6 +368,7 @@
</span><span class="cx"> friend class MarkedBlock;
</span><span class="cx"> friend class SlotVisitor;
</span><span class="cx"> friend class SpaceTimeMutatorScheduler;
</span><ins>+ friend class StochasticSpaceTimeMutatorScheduler;
</ins><span class="cx"> friend class IncrementalSweeper;
</span><span class="cx"> friend class HeapStatistics;
</span><span class="cx"> friend class VM;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapMarkingConstraintSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.cpp (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.cpp 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.cpp 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -86,7 +86,7 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void MarkingConstraintSet::resetStats()
</del><ins>+void MarkingConstraintSet::didStartMarking()
</ins><span class="cx"> {
</span><span class="cx"> m_unexecutedRoots.clearAll();
</span><span class="cx"> m_unexecutedOutgrowths.clearAll();
</span><span class="lines">@@ -103,6 +103,7 @@
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+ m_iteration = 1;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MarkingConstraintSet::add(CString abbreviatedName, CString name, Function<void(SlotVisitor&, const VisitingTimeout&)> function, ConstraintVolatility volatility)
</span><span class="lines">@@ -129,22 +130,6 @@
</span><span class="cx"> m_set.append(WTFMove(constraint));
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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;
-}
-
</del><span class="cx"> bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor, MonotonicTime timeout)
</span><span class="cx"> {
</span><span class="cx"> bool result = executeConvergenceImpl(visitor, timeout);
</span><span class="lines">@@ -166,13 +151,21 @@
</span><span class="cx"> {
</span><span class="cx"> ExecutionContext executionContext(*this, visitor, timeout);
</span><span class="cx">
</span><ins>+ unsigned iteration = m_iteration++;
+
</ins><span class="cx"> if (Options::logGC())
</span><del>- dataLog("converge:");
</del><ins>+ dataLog("i#", iteration, ":");
</ins><span class="cx">
</span><span class="cx"> // If there are any constraints that we have not executed at all during this cycle, then
</span><span class="cx"> // we should execute those now.
</span><span class="cx"> if (!executionContext.drain(m_unexecutedRoots))
</span><span class="cx"> return false;
</span><ins>+
+ // First iteration is before any visitor draining, so it's unlikely to trigger any constraints other
+ // than roots.
+ if (iteration == 1)
+ return false;
+
</ins><span class="cx"> if (!executionContext.drain(m_unexecutedOutgrowths))
</span><span class="cx"> return false;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapMarkingConstraintSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.h (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.h 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/MarkingConstraintSet.h 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -36,7 +36,7 @@
</span><span class="cx"> MarkingConstraintSet();
</span><span class="cx"> ~MarkingConstraintSet();
</span><span class="cx">
</span><del>- void resetStats();
</del><ins>+ void didStartMarking();
</ins><span class="cx">
</span><span class="cx"> void add(
</span><span class="cx"> CString abbreviatedName,
</span><span class="lines">@@ -58,10 +58,6 @@
</span><span class="cx"> bool isWavefrontAdvancing(SlotVisitor&);
</span><span class="cx"> bool isWavefrontRetreating(SlotVisitor& visitor) { return !isWavefrontAdvancing(visitor); }
</span><span class="cx">
</span><del>- // 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());
-
</del><span class="cx"> // Returns true if this executed all constraints and none of them produced new work. This
</span><span class="cx"> // assumes that you've alraedy visited roots and drained from there.
</span><span class="cx"> bool executeConvergence(
</span><span class="lines">@@ -84,6 +80,7 @@
</span><span class="cx"> Vector<std::unique_ptr<MarkingConstraint>> m_set;
</span><span class="cx"> Vector<MarkingConstraint*> m_ordered;
</span><span class="cx"> Vector<MarkingConstraint*> m_outgrowths;
</span><ins>+ unsigned m_iteration { 1 };
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace JSC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapMutatorSchedulercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/MutatorScheduler.cpp (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/MutatorScheduler.cpp 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/MutatorScheduler.cpp 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -46,10 +46,18 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void MutatorScheduler::didReachTermination()
+{
+}
+
</ins><span class="cx"> void MutatorScheduler::didExecuteConstraints()
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void MutatorScheduler::synchronousDrainingDidStall()
+{
+}
+
</ins><span class="cx"> void MutatorScheduler::log()
</span><span class="cx"> {
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapMutatorSchedulerh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/MutatorScheduler.h (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/MutatorScheduler.h 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/MutatorScheduler.h 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -50,8 +50,17 @@
</span><span class="cx">
</span><span class="cx"> virtual void didStop();
</span><span class="cx"> virtual void willResume();
</span><ins>+
+ // 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.
</ins><span class="cx"> virtual void didExecuteConstraints();
</span><span class="cx">
</span><ins>+ // 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();
+
</ins><span class="cx"> virtual MonotonicTime timeToStop() = 0; // Call while resumed, to ask when to stop.
</span><span class="cx"> virtual MonotonicTime timeToResume() = 0; // Call while stopped, to ask when to resume.
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapSlotVisitorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -492,12 +492,13 @@
</span><span class="cx"> bool SlotVisitor::didReachTermination()
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(m_heap.m_markingMutex);
</span><del>- return isEmpty() && didReachTermination(locker);
</del><ins>+ return didReachTermination(locker);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool SlotVisitor::didReachTermination(const LockHolder&)
</span><span class="cx"> {
</span><del>- return !m_heap.m_numberOfActiveParallelMarkers
</del><ins>+ return isEmpty()
+ && !m_heap.m_numberOfActiveParallelMarkers
</ins><span class="cx"> && m_heap.m_sharedCollectorMarkStack->isEmpty()
</span><span class="cx"> && m_heap.m_sharedMutatorMarkStack->isEmpty();
</span><span class="cx"> }
</span><span class="lines">@@ -514,14 +515,12 @@
</span><span class="cx">
</span><span class="cx"> ASSERT(Options::numberOfGCMarkers());
</span><span class="cx">
</span><del>- {
- LockHolder locker(m_heap.m_markingMutex);
- m_heap.m_numberOfActiveParallelMarkers++;
- }
</del><ins>+ bool isActive = false;
</ins><span class="cx"> while (true) {
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(m_heap.m_markingMutex);
</span><del>- m_heap.m_numberOfActiveParallelMarkers--;
</del><ins>+ if (isActive)
+ m_heap.m_numberOfActiveParallelMarkers--;
</ins><span class="cx"> m_heap.m_numberOfWaitingParallelMarkers++;
</span><span class="cx">
</span><span class="cx"> if (sharedDrainMode == MasterDrain) {
</span><span class="lines">@@ -568,6 +567,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> drain(timeout);
</span><ins>+ isActive = true;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapStochasticSpaceTimeMutatorSchedulercpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.cpp (0 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.cpp 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -0,0 +1,222 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapStochasticSpaceTimeMutatorSchedulerh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.h (0 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.h (rev 0)
+++ trunk/Source/JavaScriptCore/heap/StochasticSpaceTimeMutatorScheduler.h 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -0,0 +1,92 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeOptionsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/Options.h (211068 => 211069)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/Options.h 2017-01-23 23:37:42 UTC (rev 211068)
+++ trunk/Source/JavaScriptCore/runtime/Options.h 2017-01-24 00:01:13 UTC (rev 211069)
</span><span class="lines">@@ -198,11 +198,13 @@
</span><span class="cx"> v(double, mediumHeapRAMFraction, 0.5, Normal, nullptr) \
</span><span class="cx"> v(double, mediumHeapGrowthFactor, 1.5, Normal, nullptr) \
</span><span class="cx"> v(double, largeHeapGrowthFactor, 1.24, Normal, nullptr) \
</span><del>- v(bool, useCollectorTimeslicing, true, Normal, nullptr) \
</del><span class="cx"> v(double, minimumMutatorUtilization, 0, Normal, nullptr) \
</span><span class="cx"> v(double, maximumMutatorUtilization, 0.7, Normal, nullptr) \
</span><span class="cx"> v(double, concurrentGCMaxHeadroom, 1.5, Normal, nullptr) \
</span><span class="cx"> v(double, concurrentGCPeriodMS, 2, Normal, nullptr) \
</span><ins>+ v(bool, useStochasticMutatorScheduler, false, Normal, nullptr) \
+ v(double, minimumGCPauseMS, 0.3, Normal, nullptr) \
+ v(double, gcPauseScale, 0.3, Normal, nullptr) \
</ins><span class="cx"> v(bool, scribbleFreeCells, false, Normal, nullptr) \
</span><span class="cx"> v(double, sizeClassProgression, 1.4, Normal, nullptr) \
</span><span class="cx"> v(unsigned, largeAllocationCutoff, 100000, Normal, nullptr) \
</span></span></pre>
</div>
</div>
</body>
</html>