GC constraint solving should be parallel
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkingConstraintSet.cpp
1 /*
2  * Copyright (C) 2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "MarkingConstraintSet.h"
28
29 #include "JSCInlines.h"
30 #include "MarkingConstraintSolver.h"
31 #include "Options.h"
32 #include "SimpleMarkingConstraint.h"
33 #include "SuperSampler.h"
34 #include <wtf/Function.h>
35 #include <wtf/TimeWithDynamicClockType.h>
36
37 namespace JSC {
38
39 MarkingConstraintSet::MarkingConstraintSet(Heap& heap)
40     : m_heap(heap)
41 {
42 }
43
44 MarkingConstraintSet::~MarkingConstraintSet()
45 {
46 }
47
48 void MarkingConstraintSet::didStartMarking()
49 {
50     m_unexecutedRoots.clearAll();
51     m_unexecutedOutgrowths.clearAll();
52     for (auto& constraint : m_set) {
53         constraint->resetStats();
54         switch (constraint->volatility()) {
55         case ConstraintVolatility::GreyedByExecution:
56             m_unexecutedRoots.set(constraint->index());
57             break;
58         case ConstraintVolatility::GreyedByMarking:
59             m_unexecutedOutgrowths.set(constraint->index());
60             break;
61         case ConstraintVolatility::SeldomGreyed:
62             break;
63         }
64     }
65     m_iteration = 1;
66 }
67
68 void MarkingConstraintSet::add(CString abbreviatedName, CString name, ::Function<void(SlotVisitor&)> function, ConstraintVolatility volatility, ConstraintConcurrency concurrency)
69 {
70     add(std::make_unique<SimpleMarkingConstraint>(WTFMove(abbreviatedName), WTFMove(name), WTFMove(function), volatility, concurrency));
71 }
72
73 void MarkingConstraintSet::add(
74     std::unique_ptr<MarkingConstraint> constraint)
75 {
76     constraint->m_index = m_set.size();
77     m_ordered.append(constraint.get());
78     if (constraint->volatility() == ConstraintVolatility::GreyedByMarking)
79         m_outgrowths.append(constraint.get());
80     m_set.append(WTFMove(constraint));
81 }
82
83 bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor)
84 {
85     bool result = executeConvergenceImpl(visitor);
86     if (Options::logGC())
87         dataLog(" ");
88     return result;
89 }
90
91 bool MarkingConstraintSet::isWavefrontAdvancing(SlotVisitor& visitor)
92 {
93     for (MarkingConstraint* outgrowth : m_outgrowths) {
94         if (outgrowth->workEstimate(visitor))
95             return true;
96     }
97     return false;
98 }
99
100 bool MarkingConstraintSet::executeConvergenceImpl(SlotVisitor& visitor)
101 {
102     SuperSamplerScope superSamplerScope(false);
103     MarkingConstraintSolver solver(*this);
104     
105     unsigned iteration = m_iteration++;
106     
107     if (Options::logGC())
108         dataLog("i#", iteration, ":");
109
110     if (iteration == 1) {
111         // First iteration is before any visitor draining, so it's unlikely to trigger any constraints
112         // other than roots.
113         solver.drain(m_unexecutedRoots);
114         return false;
115     }
116     
117     if (iteration == 2) {
118         solver.drain(m_unexecutedOutgrowths);
119         return false;
120     }
121     
122     // We want to keep preferring the outgrowth constraints - the ones that need to be fixpointed
123     // even in a stop-the-world GC - until they stop producing. They have a tendency to go totally
124     // silent at some point during GC, at which point it makes sense not to run them again until
125     // the end. Outgrowths producing new information corresponds almost exactly to the wavefront
126     // advancing: it usually means that we are marking objects that should be marked based on
127     // other objects that we would have marked anyway. Once the wavefront is no longer advancing,
128     // we want to run mostly the root constraints (based on their predictions of how much work
129     // they will have) because at this point we are just trying to outpace the retreating
130     // wavefront.
131     //
132     // Note that this function (executeConvergenceImpl) only returns true if it runs all
133     // constraints. So, all we are controlling are the heuristics that say which constraints to
134     // run first. Choosing the constraints that are the most likely to produce means running fewer
135     // constraints before returning.
136     bool isWavefrontAdvancing = this->isWavefrontAdvancing(visitor);
137     
138     std::sort(
139         m_ordered.begin(), m_ordered.end(),
140         [&] (MarkingConstraint* a, MarkingConstraint* b) -> bool {
141             // Remember: return true if a should come before b.
142             
143             auto volatilityScore = [] (MarkingConstraint* constraint) -> unsigned {
144                 return constraint->volatility() == ConstraintVolatility::GreyedByMarking ? 1 : 0;
145             };
146             
147             unsigned aVolatilityScore = volatilityScore(a);
148             unsigned bVolatilityScore = volatilityScore(b);
149             
150             if (aVolatilityScore != bVolatilityScore) {
151                 if (isWavefrontAdvancing)
152                     return aVolatilityScore > bVolatilityScore;
153                 else
154                     return aVolatilityScore < bVolatilityScore;
155             }
156             
157             double aWorkEstimate = a->workEstimate(visitor);
158             double bWorkEstimate = b->workEstimate(visitor);
159             
160             if (aWorkEstimate != bWorkEstimate)
161                 return aWorkEstimate > bWorkEstimate;
162             
163             // This causes us to use SeldomGreyed vs GreyedByExecution as a final tie-breaker.
164             return a->volatility() > b->volatility();
165         });
166     
167     solver.converge(m_ordered);
168     
169     // Return true if we've converged. That happens if we did not visit anything.
170     return !solver.didVisitSomething();
171 }
172
173 void MarkingConstraintSet::executeAll(SlotVisitor& visitor)
174 {
175     for (auto& constraint : m_set)
176         constraint->execute(visitor);
177     if (Options::logGC())
178         dataLog(" ");
179 }
180
181 } // namespace JSC
182