Skip to content

Commit 20c541c

Browse files
justinhorvitzcopybara-github
justinhorvitz
authored and
copybara-github
committed
Implement NonIncrementalInMemoryNodeEntry separately from IncrementalInMemoryNodeEntry.
This reduces the shallow heap of `NonIncrementalInMemoryNodeEntry` from 40 to 24 bytes, which is especially good because users often opt for non-incremental builds to save memory. The overall savings are somewhat lessened by existing optimizations which already reduce the number of retained nodes in non-incremental builds: * `--heuristically_drop_nodes` which discards nodes on the fly. * `GlobbingStrategy#NON_SKYFRAME`, which is used to reduce the number of nodes in the glob subgraph on non-incremental builds since we don't need incremental correctness. Some of the state checks for the "force rebuild" lifecycle are loosened to allow `NonIncrementalInMemoryNodeEntry` to act as if it has never been built before, as opposed to supporting some special incremental building state only for rewinding. I left a couple `TODO`s to tighten this up as I work on incremental rewinding support. PiperOrigin-RevId: 555934542 Change-Id: Ie9600706c7f34b41a11401812534571e516e5a3b
1 parent 7bcd5cc commit 20c541c

8 files changed

Lines changed: 324 additions & 92 deletions

File tree

‎src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryNodeEntry.java‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -58,8 +58,12 @@
5858
* the ALREADY_EVALUATING state until it is DONE.
5959
*
6060
* <p>From the DONE state, the node can go back to the "marked as affected" state.
61+
*
62+
* @param <D> the type of {@link DirtyBuildingState} used by the {@link AbstractInMemoryNodeEntry}
63+
* subclass
6164
*/
62-
abstract class AbstractInMemoryNodeEntry implements InMemoryNodeEntry {
65+
abstract class AbstractInMemoryNodeEntry<D extends DirtyBuildingState>
66+
implements InMemoryNodeEntry {
6367

6468
private final SkyKey key;
6569

@@ -70,7 +74,7 @@ abstract class AbstractInMemoryNodeEntry implements InMemoryNodeEntry {
7074
* Tracks state of this entry while it is evaluating (either on its initial build or after being
7175
* marked dirty).
7276
*/
73-
@Nullable protected volatile DirtyBuildingState dirtyBuildingState;
77+
@Nullable protected volatile D dirtyBuildingState;
7478

7579
AbstractInMemoryNodeEntry(SkyKey key) {
7680
this.key = checkNotNull(key);

‎src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java‎

Lines changed: 17 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,9 @@
3232
* <p>If the node has previously been built, {@link #isIncremental} returns true. Deps are checked
3333
* to see if re-evaluation is needed, and the node will either marked clean or re-evaluated.
3434
*
35+
* <p>This class does not attempt to synchronize operations. It is assumed that the calling {@link
36+
* InMemoryNodeEntry} performs the appropriate synchronization when necessary.
37+
*
3538
* <p>This class is public only for the benefit of alternative graph implementations outside of the
3639
* package.
3740
*/
@@ -165,14 +168,21 @@ final void markForceRebuild() {
165168
}
166169
}
167170

171+
// TODO(b/228090759): Tighten up state checks for the force rebuild lifecycle.
168172
final void forceRebuild(int numTemporaryDirectDeps) {
169173
checkState(numTemporaryDirectDeps + externalDeps == signaledDeps, this);
170-
checkState(
171-
(dirtyState == DirtyState.CHECK_DEPENDENCIES
172-
&& getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex)
173-
|| dirtyState == DirtyState.NEEDS_FORCED_REBUILDING,
174-
this);
175-
dirtyState = DirtyState.REBUILDING;
174+
switch (dirtyState) {
175+
case CHECK_DEPENDENCIES:
176+
checkState(getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex, this);
177+
dirtyState = DirtyState.REBUILDING;
178+
break;
179+
case NEEDS_REBUILDING: // Valid for NonIncrementalInMemoryNodeEntry.
180+
case NEEDS_FORCED_REBUILDING: // Valid for IncrementalInMemoryNodeEntry.
181+
dirtyState = DirtyState.REBUILDING;
182+
break;
183+
default:
184+
throw new IllegalStateException("Unexpected dirty state " + dirtyState + ": " + this);
185+
}
176186
}
177187

178188
final boolean isEvaluating() {
@@ -202,12 +212,10 @@ private void checkFinishedBuildingWhenAboutToSetValue() {
202212
* DirtyBuildingState#getNumOfGroupsInLastBuildDirectDeps()}.
203213
*/
204214
final void signalDep(
205-
AbstractInMemoryNodeEntry entry,
215+
AbstractInMemoryNodeEntry<?> entry,
206216
NodeVersion version,
207217
Version childVersion,
208218
@Nullable SkyKey childForDebugging) {
209-
// Synchronization isn't needed here because the only caller is InMemoryNodeEntry, which does it
210-
// through the synchronized method signalDep.
211219
checkState(isEvaluating(), "%s %s", entry, childForDebugging);
212220
signaledDeps++;
213221
if (isChanged()) {

‎src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java‎

Lines changed: 14 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,6 @@
1313
// limitations under the License.
1414
package com.google.devtools.build.skyframe;
1515

16-
import static com.google.common.base.Preconditions.checkArgument;
1716
import static com.google.common.base.Preconditions.checkNotNull;
1817
import static com.google.common.base.Preconditions.checkState;
1918

@@ -29,7 +28,7 @@
2928
import javax.annotation.Nullable;
3029

3130
/** An {@link InMemoryNodeEntry} that {@link #keepsEdges} for use in incremental evaluations. */
32-
public class IncrementalInMemoryNodeEntry extends AbstractInMemoryNodeEntry {
31+
public class IncrementalInMemoryNodeEntry extends AbstractInMemoryNodeEntry<DirtyBuildingState> {
3332

3433
protected volatile NodeVersion version = Version.minimal();
3534

@@ -38,8 +37,8 @@ public class IncrementalInMemoryNodeEntry extends AbstractInMemoryNodeEntry {
3837
* requested them that way. It contains either the in-progress direct deps, stored as a {@link
3938
* GroupedDeps} (constructed via {@link GroupedDeps.WithHashSet} if {@code
4039
* key.supportsPartialReevaluation()}) before the node is finished building, or the full direct
41-
* deps, compressed in a memory-efficient way (via {@link GroupedDeps#compress}, after the node is
42-
* done.
40+
* deps, compressed in a memory-efficient way (via {@link GroupedDeps#compress}), after the node
41+
* is done.
4342
*
4443
* <p>It is initialized lazily in getTemporaryDirectDeps() to save a little memory.
4544
*/
@@ -84,7 +83,7 @@ public IncrementalInMemoryNodeEntry(SkyKey key) {
8483
}
8584

8685
@Override
87-
public boolean keepsEdges() {
86+
public final boolean keepsEdges() {
8887
return true;
8988
}
9089

@@ -123,7 +122,6 @@ public boolean hasAtLeastOneDep() {
123122

124123
@Override
125124
public final synchronized @GroupedDeps.Compressed Object getCompressedDirectDepsForDoneEntry() {
126-
assertKeepEdges();
127125
checkState(isDone(), "no deps until done. NodeEntry: %s", this);
128126
checkNotNull(directDeps, "deps can't be null: %s", this);
129127
return GroupedDeps.castAsCompressed(directDeps);
@@ -140,7 +138,7 @@ protected void markDone() {
140138

141139
protected final synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
142140
Set<SkyKey> reverseDepsToSignal = ReverseDepsUtility.consolidateDataAndReturnNewElements(this);
143-
directDeps = keepsEdges() ? getTemporaryDirectDeps().compress() : null;
141+
directDeps = getTemporaryDirectDeps().compress();
144142
markDone();
145143
return reverseDepsToSignal;
146144
}
@@ -162,10 +160,6 @@ public synchronized Set<SkyKey> getInProgressReverseDeps() {
162160
public synchronized Set<SkyKey> setValue(
163161
SkyValue value, Version graphVersion, @Nullable Version maxTransitiveSourceVersion)
164162
throws InterruptedException {
165-
checkArgument(
166-
keepsEdges() || graphVersion.equals(ConstantVersion.INSTANCE),
167-
"Non-incremental evaluations must use a constant graph version, got %s",
168-
graphVersion);
169163
checkState(!hasUnsignaledDeps(), "Has unsignaled deps (this=%s, value=%s)", this, value);
170164
checkState(
171165
version.lastChanged().atMost(graphVersion) && version.lastEvaluated().atMost(graphVersion),
@@ -192,7 +186,7 @@ public synchronized Set<SkyKey> setValue(
192186
@Override
193187
@CanIgnoreReturnValue
194188
public DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
195-
if ((reverseDep == null || !keepsEdges()) && isDone()) {
189+
if (reverseDep == null && isDone()) {
196190
return DependencyState.DONE;
197191
}
198192

@@ -203,21 +197,19 @@ public DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
203197
}
204198
if (reverseDep != null) {
205199
if (done) {
206-
if (keepsEdges()) {
207-
ReverseDepsUtility.addReverseDep(this, reverseDep);
208-
}
200+
ReverseDepsUtility.addReverseDep(this, reverseDep);
209201
} else {
210202
appendToReverseDepOperations(reverseDep, Op.ADD);
211203
}
212204
}
213205
if (done) {
214206
return DependencyState.DONE;
215207
}
216-
boolean wasEvaluating = dirtyBuildingState.isEvaluating();
217-
if (!wasEvaluating) {
218-
dirtyBuildingState.startEvaluating();
208+
if (dirtyBuildingState.isEvaluating()) {
209+
return DependencyState.ALREADY_EVALUATING;
219210
}
220-
return wasEvaluating ? DependencyState.ALREADY_EVALUATING : DependencyState.NEEDS_SCHEDULING;
211+
dirtyBuildingState.startEvaluating();
212+
return DependencyState.NEEDS_SCHEDULING;
221213
}
222214
}
223215

@@ -252,7 +244,6 @@ private synchronized void appendToReverseDepOperations(SkyKey reverseDep, Op op)
252244
@Override
253245
public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
254246
checkNotNull(reverseDep, this);
255-
checkState(keepsEdges(), "Incremental means keeping edges %s %s", reverseDep, this);
256247
if (isDone()) {
257248
return DependencyState.DONE;
258249
}
@@ -262,9 +253,6 @@ public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverse
262253

263254
@Override
264255
public synchronized void removeReverseDep(SkyKey reverseDep) {
265-
if (!keepsEdges()) {
266-
return;
267-
}
268256
if (isDone()) {
269257
ReverseDepsUtility.removeReverseDep(this, reverseDep);
270258
} else {
@@ -276,7 +264,6 @@ public synchronized void removeReverseDep(SkyKey reverseDep) {
276264

277265
@Override
278266
public synchronized void removeReverseDepsFromDoneEntryDueToDeletion(Set<SkyKey> deletedKeys) {
279-
assertKeepEdges();
280267
checkState(isDone(), this);
281268
ReverseDepsUtility.removeReverseDepsMatching(this, deletedKeys);
282269
}
@@ -288,14 +275,12 @@ public synchronized void removeInProgressReverseDep(SkyKey reverseDep) {
288275

289276
@Override
290277
public synchronized Collection<SkyKey> getReverseDepsForDoneEntry() {
291-
assertKeepEdges();
292278
checkState(isDone(), "Called on not done %s", this);
293279
return ReverseDepsUtility.getReverseDeps(this, /* checkConsistency= */ true);
294280
}
295281

296282
@Override
297283
public synchronized Collection<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
298-
assertKeepEdges();
299284
if (!isDone()) {
300285
// This consolidation loses information about pending reverse deps to signal, but that is
301286
// unimportant since this node is being deleted.
@@ -313,11 +298,6 @@ public synchronized boolean signalDep(Version childVersion, @Nullable SkyKey chi
313298
return !hasUnsignaledDeps();
314299
}
315300

316-
/** Checks that a caller is not trying to access not-stored graph edges. */
317-
private void assertKeepEdges() {
318-
checkState(keepsEdges(), "Not keeping edges: %s", this);
319-
}
320-
321301
/**
322302
* Creates a {@link DirtyBuildingState} for the case where this node is done and is being marked
323303
* dirty.
@@ -328,25 +308,16 @@ protected DirtyBuildingState createDirtyBuildingStateForDoneNode(
328308
return new IncrementalDirtyBuildingState(dirtyType, getKey(), directDeps, value);
329309
}
330310

331-
private static final GroupedDeps EMPTY_LIST = new GroupedDeps();
332-
333311
@Nullable
334312
@Override
335313
public synchronized MarkedDirtyResult markDirty(DirtyType dirtyType) {
336-
if (!DirtyType.FORCE_REBUILD.equals(dirtyType)) {
337-
// A node can't be found to be dirty without deps unless it's force-rebuilt.
338-
assertKeepEdges();
339-
}
340314
if (isDone()) {
341-
GroupedDeps directDeps =
342-
keepsEdges() ? GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry()) : EMPTY_LIST;
315+
GroupedDeps directDeps = GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry());
343316
dirtyBuildingState = createDirtyBuildingStateForDoneNode(dirtyType, directDeps, value);
344317
value = null;
345318
this.directDeps = null;
346319
return MarkedDirtyResult.withReverseDeps(
347-
keepsEdges()
348-
? ReverseDepsUtility.getReverseDeps(this, /* checkConsistency= */ true)
349-
: ImmutableList.of());
320+
ReverseDepsUtility.getReverseDeps(this, /* checkConsistency= */ true));
350321
}
351322
if (dirtyType.equals(DirtyType.FORCE_REBUILD)) {
352323
if (dirtyBuildingState != null) {
@@ -420,9 +391,7 @@ protected synchronized MoreObjects.ToStringHelper toStringHelper() {
420391
.add("version", version)
421392
.add(
422393
"directDeps",
423-
isDone() && keepsEdges()
424-
? GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry())
425-
: directDeps)
394+
isDone() ? GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry()) : directDeps)
426395
.add("reverseDeps", ReverseDepsUtility.toString(this));
427396
}
428397

‎src/main/java/com/google/devtools/build/skyframe/InitialBuildingState.java‎

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -16,32 +16,35 @@
1616
import com.google.devtools.build.skyframe.NodeEntry.DirtyType;
1717
import javax.annotation.Nullable;
1818

19-
/** {@link DirtyBuildingState} for a node on its initial build. */
20-
final class InitialBuildingState extends DirtyBuildingState {
19+
/**
20+
* {@link DirtyBuildingState} for a node on its initial build or a {@link
21+
* NonIncrementalInMemoryNodeEntry} being {@linkplain NodeEntry#forceRebuild force rebuilt}.
22+
*/
23+
class InitialBuildingState extends DirtyBuildingState {
2124

2225
InitialBuildingState(boolean hasLowFanout) {
2326
super(DirtyType.CHANGE, hasLowFanout);
2427
}
2528

2629
@Nullable
2730
@Override
28-
public GroupedDeps getLastBuildDirectDeps() {
31+
public final GroupedDeps getLastBuildDirectDeps() {
2932
return null;
3033
}
3134

3235
@Override
33-
protected int getNumOfGroupsInLastBuildDirectDeps() {
36+
protected final int getNumOfGroupsInLastBuildDirectDeps() {
3437
return 0;
3538
}
3639

3740
@Nullable
3841
@Override
39-
public SkyValue getLastBuildValue() {
42+
public final SkyValue getLastBuildValue() {
4043
return null;
4144
}
4245

4346
@Override
44-
protected boolean isIncremental() {
47+
protected final boolean isIncremental() {
4548
return false;
4649
}
4750
}

0 commit comments

Comments
 (0)