5.9.6 Node Restart Cost

A restart re-invokes one internal Java SkyFunction.compute method. It does not restart the Bazel server. 5.9.2 Evaluation Model explains the full lookup and restart protocol. The detail needed here is that returning null ends the current invocation and releases its evaluator thread. A later invocation starts the method again, so serial dependency discovery can replay progressively more work.^1,2

N restarts can produce quadratic work

Suppose an internal function processes N dependency keys, but stops at the first missing value on every invocation:

for (SkyKey key : keys) {
  SkyValue value = env.getValue(key);
  if (env.valuesMissing()) {
    return null;
  }
  consume(value);
}

If none of the values is initially ready, the first invocation reaches key 1. The next replays key 1 and reaches key 2. Later invocations replay progressively longer prefixes. This trace assumes dependencies complete successfully. Code that needs to recover from or enrich a dependency error uses the appropriate getValueOrThrow form rather than assigning every null lookup the meaning “not ready.” The node may restart N times, while the number of loop visits grows like 1 + 2 + ... + N: O(N²) repeated work. It is the time cost, not the number of restarts, that is quadratic.^2,3

Previously requested values are generally available on the later invocation, so this pattern still makes progress. That does not make the replay cheap: key construction, validation, transformation, event preparation, and other work before the next missing lookup may all run again.^1,4

Request independent dependencies as one group

When all keys are known and one result cannot change which other keys are needed, request them as a dependency group. The public Skyframe documentation calls this operation env.getValues(). In current Bazel Java source, the corresponding SkyFunction.LookupEnvironment entry point is getValuesAndExceptions(Iterable<SkyKey>), which returns a SkyframeLookupResult. The exact Java interface is internal and may evolve. The durable design rule is to group independent lookups.^1,3

SkyframeLookupResult results = env.getValuesAndExceptions(keys);

List<SkyValue> values = new ArrayList<>();
for (SkyKey key : keys) {
  values.add(results.get(key));
}
if (env.valuesMissing()) {
  return null;
}
for (SkyValue value : values) {
  consume(value);
}

This compact example again assumes successful dependencies. An implementation that handles dependency failures queries each result with the matching getOrThrow overload and declared exception type.³

This first invocation declares the whole group, allowing its missing members to be evaluated in parallel. Once all values requested in that invocation are ready, the function can restart and consume them. “At most one restart” is a useful model for this simple case, not a universal guarantee: errors, partial re-evaluation, external futures, and later data-dependent lookups can require more evaluation passes.^1,3

Bulk lookup is not correct when an earlier result determines whether a later key is needed. Requesting every possible key would record dependencies the computation did not actually require. Current source documentation gives this decision rule: group lookups that are independent of one another. Keep truly data-dependent discovery in separate groups.³

When discovery is genuinely sequential

Some computations cannot know the next key in advance, such as following a chain of symbolic links. In internal Bazel Java code, the alternatives are to reduce replay by splitting the computation into smaller Skyframe nodes, or to checkpoint temporary computation with SkyKeyComputeState and structured Skyframe state machines. Cached state is a performance optimization rather than a correctness requirement: Skyframe may discard it, so the function must still be able to recompute correctly.^1,4,3

That yields a practical internal review sequence:

1. Group every set of keys already known to be independently required.
2. Separate discovery into smaller nodes when that gives each node a bounded restart path.
3. Use compute state or state machines when expensive sequential work must span restarts, while preserving correct behavior if the state is dropped.

This is internal Java guidance, not a Starlark rule pattern

Starlark rule implementations do not receive SkyFunction.Environment, cannot call getValue, getValues, or getValuesAndExceptions, and do not manually checkpoint a SkyFunction. Their dependency targets and providers arrive through declared attributes before the implementation registers the actions described in 4.2.2 Actions. The public rules API still presents loading, analysis, and execution concepts rather than exposing Skyframe's dependency discovery protocol.²

Consequently, the restart mechanism does not directly imply that a Starlark rule author should “collect SkyKeys” or avoid conditionals over provider data. For Starlark, use the supported declarative interfaces: declare attributes and action inputs, consume providers, and preserve transitive collections as depsets where appropriate. The separate O(N²) problem caused by repeatedly flattening or copying transitive collections is covered by 4.1.5 depset vs list. It should not be confused with SkyFunction restart replay.²