Change resolution algorithm to reduce edge walks
This CL changes how state changes are propagated during
resolution. It reduces the number of notifications
from dependencies to dependents, but ensuring that
each record is resolved and finalized as soon as possible
before notifying its dependents.
For example, let's consider a simple A -> B -> C
dependency chain, where:
- A is defined and waiting for B to resolve.
- B is defined and waiting for C to resolve.
- C is not defined yet (loader still evaluating its BUILD.gn file).
Once the new C item definition arrives, before this
CL, the following events would happen:
- C is defined (can resolve)
C is resolved (can finalize)
C notifies B
B is resolved (cannot finalize)
B notifies A
A waits (cannot resolve)
B waits (cannot finalize)
C finalizes -> writes C
C notifies B
B finalizes -> writes B
B notifies A
A finalizes -> writes A
With this CL, this becomes shorter and writes
are performed earlier:
- C is defined
C is resolved
C is finalized -> writes C
C notifies B
B is resolved
B is finalized -> writes B
B notifies A
A is resolved
A is finalized -> writes A
The conditions blocking state changes are not modified,
only the notifications are delayed, preserving the
correctness of the algorithm. However, this will change
the order of writes when validations are used, because
their dependents can be finalized before them, consider
the following:
A --validation--> B ---> C
Before this CL (when C is not defined yet), A was finalized
(written) before B
- C is defined + resolved
C notifies B
B is resolved
B notifies A
A resolves
A finalizes --> writes A
B waits (cannot finalize)
C finalizes --> writes C
C notifies B
B finalizes --> writes B
After this CL, A is finalized after B:
- C is defined
C is resolved
C is finalized --> writes C
C notifies B
B resolves + finalizes --> writes B
B notifies A
A finalizes --> writes A
Since B is a validation dependency in the Ninja build plan, this doesn't
change its overall graph, only the order in which the corresponding
build statements are defined.
Benchmarking shows a slight benefit in `gn gen` time
(-2% on a medium Fuchsia graph)
+ Change debug log message to use 'dependent --> dependency' instead
of 'dependency --> dependent' for clarity.
+ Minor type change for ItemType and RecordState (char -> unsigned char)
to avoid any potential platform-specific signess issues.
Change-Id: I6a5d19e251e5ca982cd6a64f21bdc96efbf62fc8
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/23141
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Commit-Queue: David Turner <digit@google.com>
diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index cc4d6ff..aca80d7 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -92,19 +92,6 @@
record->SetDefined(std::move(item));
- // Notify anyone waiting on this item's definition, and resolve those
- // that are no longer waiting.
- if (!record->NotifyDependentsWaitingOnValidationDefinition(
- [&](BuilderRecord* waiting) {
- DEBUG_BUILDER_RECORD_LOG(" VALDEFNOTIFY %s -> %s\n",
- record->ToDebugString().c_str(),
- waiting->ToDebugString().c_str());
- return ResolveItem(waiting, &err);
- })) {
- g_scheduler->FailWithError(err);
- return;
- }
-
// Do target-specific dependency setup. This will also schedule dependency
// loads for targets that are required.
switch (type) {
@@ -125,13 +112,31 @@
return;
}
- if (record->can_resolve()) {
- if (!ResolveItem(record, &err)) {
- g_scheduler->FailWithError(err);
- return;
- }
- }
DEBUG_BUILDER_RECORD_LOG("END_DEFINED %s\n", record->ToDebugString().c_str());
+
+ if (!UpdateItem(record, BuilderRecord::STATE_INIT, &err)) {
+ g_scheduler->FailWithError(err);
+ return;
+ }
+}
+
+bool Builder::UpdateItem(BuilderRecord* record,
+ BuilderRecord::RecordState prev_state,
+ Err* err) {
+ DCHECK(record->is_defined());
+
+ if (record->can_resolve()) {
+ if (!ResolveItem(record, err))
+ return false;
+ }
+ if (record->can_finalize()) {
+ if (!FinalizeItem(record, err))
+ return false;
+ }
+ return record->NotifyDependentsOfStateChange(
+ prev_state, [this, err](BuilderRecord* dependent) {
+ return UpdateItem(dependent, dependent->state(), err);
+ });
}
const Item* Builder::GetItem(const Label& label) const {
@@ -581,33 +586,7 @@
bool Builder::CompleteItemResolution(BuilderRecord* record, Err* err) {
record->SetResolved();
-
- // Recursively update everybody waiting on this item to be resolved.
- if (!record->NotifyDependentsWaitingOnResolution([&](BuilderRecord* waiting) {
- DEBUG_BUILDER_RECORD_LOG(" RESOLVE DEP %s -> %s\n",
- record->ToDebugString().c_str(),
- waiting->ToDebugString().c_str());
- return ResolveItem(waiting, err);
- })) {
- return false;
- }
-
- if (!record->NotifyDependentsWaitingOnValidationResolution(
- [&](BuilderRecord* waiting) {
- DEBUG_BUILDER_RECORD_LOG(" VALRESOLVE DEP %s -> %s\n",
- record->ToDebugString().c_str(),
- waiting->ToDebugString().c_str());
- return FinalizeItem(waiting, err);
- })) {
- return false;
- }
-
- if (record->can_finalize()) {
- return FinalizeItem(record, err);
- }
-
DEBUG_BUILDER_RECORD_LOG("END_RESOLVE %s\n", record->ToDebugString().c_str());
-
return true;
}
@@ -618,16 +597,6 @@
record->ToDebugString().c_str());
CheckAndTriggerWrite(record);
- if (!record->NotifyDependentsWaitingOnFinalization(
- [&](BuilderRecord* waiting) {
- DEBUG_BUILDER_RECORD_LOG(" FINALIZE DEP %s -> %s\n",
- record->ToDebugString().c_str(),
- waiting->ToDebugString().c_str());
- return FinalizeItem(waiting, err);
- })) {
- return false;
- }
-
DEBUG_BUILDER_RECORD_LOG("END_FINALIZE %s\n",
record->ToDebugString().c_str());
return true;
diff --git a/src/gn/builder.h b/src/gn/builder.h
index 5e6c88a..542b751 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -121,6 +121,13 @@
void ScheduleItemLoadIfNecessary(BuilderRecord* record);
+ // Update the state of a BuilderRecord and triggers subsequent steps
+ // like dependency resolution or finalization based on the state change.
+ // |prev_state| is the state of the record before the update.
+ bool UpdateItem(BuilderRecord* record,
+ BuilderRecord::RecordState prev_state,
+ Err* err);
+
// This takes a BuilderRecord with resolved dependencies, and fills in the
// target's Label*Vectors with the resolved pointers.
bool ResolveItem(BuilderRecord* record, Err* err);
diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index 8896925..6feb3af 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -62,6 +62,24 @@
return ITEM_UNKNOWN;
}
+#if DEBUG_BUILDER_RECORD
+// static
+const char* BuilderRecord::ToDebugCString(RecordState state) {
+ switch (state) {
+ case STATE_INIT:
+ return "INIT";
+ case STATE_DEFINED:
+ return "DEFINED";
+ case STATE_RESOLVED:
+ return "RESOLVED";
+ case STATE_FINALIZED:
+ return "FINALIZED";
+ default:
+ return "<<<<UNKNOWN STATE>>>>>>";
+ }
+}
+#endif // DEBUG_BUILDER_RECORD
+
void BuilderRecord::SetDefined(std::unique_ptr<Item> item) {
DCHECK(state_ == STATE_INIT);
state_ = STATE_DEFINED;
@@ -80,9 +98,9 @@
if (!info->wait_resolved) {
info->wait_resolved = true;
unresolved_count_++;
- DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_resolution %s -> %s\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str());
+ DEBUG_BUILDER_RECORD_LOG("-- AddDep %s -wait_resolved-> %s\n",
+ this->ToDebugString().c_str(),
+ dep->ToDebugString().c_str());
}
}
if (!dep->is_finalized()) {
@@ -93,9 +111,9 @@
if (!info->wait_finalized) {
info->wait_finalized = true;
unfinalized_count_++;
- DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_finalization %s -> %s\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str());
+ DEBUG_BUILDER_RECORD_LOG("-- AddDep %s -wait_finalized-> %s\n",
+ this->ToDebugString().c_str(),
+ dep->ToDebugString().c_str());
}
}
}
@@ -126,8 +144,8 @@
info->wait_validation_defined = true;
unresolved_count_++;
DEBUG_BUILDER_RECORD_LOG(
- "-- AddValidationDep waiting_on_validation_definition %s -> %s\n",
- dep->ToDebugString().c_str(), this->ToDebugString().c_str());
+ "-- AddValidationDep %s -wait_validation_defined-> %s\n",
+ this->ToDebugString().c_str(), dep->ToDebugString().c_str());
}
}
if (!dep->is_resolved()) {
@@ -139,19 +157,60 @@
info->wait_validation_resolved = true;
unfinalized_count_++;
DEBUG_BUILDER_RECORD_LOG(
- "-- AddValidationDep waiting_on_validation_resolution %s -> %s\n",
- dep->ToDebugString().c_str(), this->ToDebugString().c_str());
+ "-- AddValidationDep %s -wait_validation_resolved-> %s\n",
+ this->ToDebugString().c_str(), dep->ToDebugString().c_str());
}
}
}
-bool BuilderRecord::OnDefinedValidationDep(const BuilderRecord* dep) {
- DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
- DCHECK(unresolved_count_ > 0);
- bool result = (--unresolved_count_ == 0);
- DEBUG_BUILDER_RECORD_LOG("-- OnDefinedValidationDep %s -> %s result=%d\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str(), result);
+bool BuilderRecord::OnDepStateChange(BuilderRecord* dep,
+ RecordState from_state,
+ RecordState to_state,
+ BuilderRecord::WaitInfo& info) {
+ bool result = false;
+
+ DCHECK(all_deps_.contains(dep));
+
+ DEBUG_BUILDER_RECORD_LOG(
+ "-- OnDepStateChange %s -> %s (%s->%s)\n", this->ToDebugString().c_str(),
+ dep->ToDebugString().c_str(), ToDebugCString(from_state),
+ ToDebugCString(to_state));
+ if (to_state >= STATE_DEFINED && info.wait_validation_defined) {
+ info.wait_validation_defined = false;
+ DCHECK(state_ < STATE_RESOLVED);
+ DCHECK(unresolved_count_ > 0);
+ if (--unresolved_count_ == 0) {
+ DEBUG_BUILDER_RECORD_LOG(" CAN RESOLVE (validation)\n");
+ result = true;
+ }
+ }
+ if (to_state >= STATE_RESOLVED && info.wait_resolved) {
+ info.wait_resolved = false;
+ DCHECK(state_ < STATE_RESOLVED);
+ DCHECK(unresolved_count_ > 0);
+ if (--unresolved_count_ == 0) {
+ DEBUG_BUILDER_RECORD_LOG(" CAN RESOLVE\n");
+ result = true;
+ }
+ }
+ if (to_state >= STATE_RESOLVED && info.wait_validation_resolved) {
+ info.wait_validation_resolved = false;
+ DCHECK(state_ < STATE_FINALIZED);
+ DCHECK(unfinalized_count_ > 0);
+ if (--unfinalized_count_ == 0) {
+ DEBUG_BUILDER_RECORD_LOG(" CAN FINALIZE (validation)\n");
+ result = true;
+ }
+ }
+ if (to_state >= STATE_FINALIZED && info.wait_finalized) {
+ info.wait_finalized = false;
+ DCHECK(state_ < STATE_FINALIZED);
+ DCHECK(unfinalized_count_ > 0);
+ if (--unfinalized_count_ == 0) {
+ DEBUG_BUILDER_RECORD_LOG(" CAN FINALIZE\n");
+ result = true;
+ }
+ }
return result;
}
@@ -160,41 +219,11 @@
state_ = STATE_RESOLVED;
}
-bool BuilderRecord::OnResolvedDep(const BuilderRecord* dep) {
- DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
- DCHECK(unresolved_count_ > 0);
- bool result = (--unresolved_count_ == 0);
- DEBUG_BUILDER_RECORD_LOG("-- OnResolvedDep %s -> %s result=%d\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str(), result);
- return result;
-}
-
-bool BuilderRecord::OnResolvedValidationDep(const BuilderRecord* dep) {
- DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
- DCHECK(unfinalized_count_ > 0);
- bool result = (--unfinalized_count_ == 0);
- DEBUG_BUILDER_RECORD_LOG("-- OnResolvedValidationDep %s -> %s result=%d\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str(), result);
- return result;
-}
-
void BuilderRecord::SetFinalized() {
DCHECK(can_finalize());
state_ = STATE_FINALIZED;
}
-bool BuilderRecord::OnFinalizedDep(const BuilderRecord* dep) {
- DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
- DCHECK(unfinalized_count_ > 0);
- bool result = (--unfinalized_count_ == 0);
- DEBUG_BUILDER_RECORD_LOG("-- OnFinalizedDep %s -> %s result=%d\n",
- dep->ToDebugString().c_str(),
- this->ToDebugString().c_str(), result);
- return result;
-}
-
std::vector<const BuilderRecord*> BuilderRecord::GetSortedUnresolvedDeps()
const {
std::vector<const BuilderRecord*> result;
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index fd05fd8..52d4816 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -123,7 +123,7 @@
public:
using BuilderRecordSet = PointerSet<BuilderRecord>;
- enum ItemType : char {
+ enum ItemType : unsigned char {
ITEM_UNKNOWN,
ITEM_TARGET,
ITEM_CONFIG,
@@ -131,13 +131,17 @@
ITEM_POOL
};
- enum RecordState : char {
+ enum RecordState : unsigned char {
STATE_INIT,
STATE_DEFINED,
STATE_RESOLVED,
STATE_FINALIZED,
};
+#if DEBUG_BUILDER_RECORD
+ static const char* ToDebugCString(RecordState);
+#endif // DEBUG_BUILDER_RECORD
+
BuilderRecord(ItemType type,
const Label& label,
const ParseNode* originally_referenced_from);
@@ -171,10 +175,7 @@
bool is_defined() const { return state_ >= STATE_DEFINED; }
// Change the record's state to Defined. This only requires
- // a new Item instance to be provided. After this, the caller
- // should call Add{Dep,GenDep,ValidationDep}() for each
- // dependency type for the Item, then call
- // NotifyDependentsWaitingOnValidationDefinition().
+ // a new Item instance to be provided.
void SetDefined(std::unique_ptr<Item> item);
// After a call to SetDefined()call these methods for each dependency
@@ -183,21 +184,8 @@
void AddGenDep(BuilderRecord* dep_record);
void AddValidationDep(BuilderRecord* dep_record);
- // Iterate over all records waiting on this one to be defined, and call
- // |func| on each one that no longer needs to wait. If |func| returns
- // false, stop and return false.
- template <typename Func>
- bool NotifyDependentsWaitingOnValidationDefinition(Func&& func) {
- for (auto& pair : waiting_map_) {
- if (pair.second.wait_validation_defined) {
- pair.second.wait_validation_defined = false;
- BuilderRecord* waiting = pair.first;
- if (waiting->OnDefinedValidationDep(this) && !func(waiting))
- return false;
- }
- }
- return true;
- }
+ // Return current record state.
+ RecordState state() const { return state_; }
// Returns true if the items has been resolved.
bool is_resolved() const { return state_ >= STATE_RESOLVED; }
@@ -211,40 +199,21 @@
// Change the record's state to Resolved. This requires can_resolve()
// to be true.
- //
- // IMPORTANT: Caller should then call Add{Dep,GenDep,ValidationDep}()
- // for each dependency of the current item, then call
- // NotifyDependentsWaitingOnResolution() and
- // NotifyDependentsWaitingOnValidationResolution().
void SetResolved();
- // Iterate over all records waiting on this one to be resolved, and call
- // |func| on each one that no longer needs to wait. If |func| returns false,
- // stop and return false.
- template <typename Func>
- bool NotifyDependentsWaitingOnResolution(Func&& func) {
- for (auto& pair : waiting_map_) {
- if (pair.second.wait_resolved) {
- pair.second.wait_resolved = false;
- BuilderRecord* waiting = pair.first;
- if (waiting->OnResolvedDep(this) && !func(waiting))
- return false;
- }
- }
- return true;
- }
-
- // Iterate over all records waiting on this one to be resolved as a
- // validation, and call |func| on each one that no longer needs to wait. If
- // |func| returns false, stop and return false.
- template <typename Func>
- bool NotifyDependentsWaitingOnValidationResolution(Func&& func) {
- for (auto& pair : waiting_map_) {
- if (pair.second.wait_validation_resolved) {
- pair.second.wait_validation_resolved = false;
- BuilderRecord* waiting = pair.first;
- if (waiting->OnResolvedValidationDep(this) && !func(waiting))
- return false;
+ // Notify all dependents that the current record's item state
+ // has changed. |update_dependent()| will be called for any
+ // dependent whose state may change itself. |from_state| is
+ // the initial state the record had before its current one.
+ // Return true on success, or false in case of error.
+ template <typename UpdateDependent>
+ bool NotifyDependentsOfStateChange(RecordState from_state,
+ UpdateDependent update_dependent) {
+ if (from_state != state_) {
+ for (auto& [dependent, wait_info] : waiting_map_) {
+ if (dependent->OnDepStateChange(this, from_state, state_, wait_info))
+ if (!update_dependent(dependent))
+ return false;
}
}
return true;
@@ -260,25 +229,8 @@
}
// Change the state to Finalized. This requires can_finalize() to be true.
- // Callers should then call NotifyDependentsWaitingOnFinalization().
void SetFinalized();
- // Iterate over all records waiting on this one to be finalized, and call
- // |func| on each one that no longer needs to wait. If |func| returns false,
- // stop and return false.
- template <typename Func>
- bool NotifyDependentsWaitingOnFinalization(Func&& func) {
- for (auto& pair : waiting_map_) {
- if (pair.second.wait_finalized) {
- pair.second.wait_finalized = false;
- BuilderRecord* waiting = pair.first;
- if (waiting->OnFinalizedDep(this) && !func(waiting))
- return false;
- }
- }
- return true;
- }
-
// All records this one is depending on. Note that this includes gen_deps for
// targets, which can have cycles.
BuilderRecordSet& all_deps() { return all_deps_; }
@@ -333,14 +285,6 @@
std::string ToDebugString() const;
private:
- // Called by NotifyDependentsWaitingOnXXX() methods. This should update
- // the counters and return true if the record is no longer waiting for
- // its dependents and can change state.
- bool OnDefinedValidationDep(const BuilderRecord* dep);
- bool OnResolvedDep(const BuilderRecord* dep);
- bool OnResolvedValidationDep(const BuilderRecord* dep);
- bool OnFinalizedDep(const BuilderRecord* dep);
-
RecordState state_ = STATE_INIT;
ItemType type_;
bool should_generate_ = false;
@@ -385,6 +329,16 @@
};
base::flat_map<BuilderRecord*, WaitInfo> waiting_map_;
+ // Called by NotifyDependentsOfStateChange() when a dependency
+ // of the current record has changed its state. Must return
+ // true if the dependent (current record) can now change state
+ // too, or false if it is still waiting for other dependency
+ // changes.
+ bool OnDepStateChange(BuilderRecord* dep,
+ RecordState from_state,
+ RecordState to_state,
+ WaitInfo& info);
+
BuilderRecord(const BuilderRecord&) = delete;
BuilderRecord& operator=(const BuilderRecord&) = delete;
};
diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index 8e08fab..54d9f5e 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -673,20 +673,20 @@
// Due to the way the Builder is implemented, here's what happens:
//
- // E is resolved, notifies B immediately.
- // B is resolved, notifies A immediately.
- // A is finalized, writes, notifies C
- // C writes.
- // A returns from finalization.
- // B returns from resolution.
- // E returns from resolution.
- // E finalizes, notifies B
- // B finalizes.
+ // E is resolved
+ // E is finalized (written)
+ // E notifies B
+ // B is resolved
+ // B is finalized (written)
+ // B notifies A
+ // A is finalized (written)
+ // A notifies C
+ // C is finalized (written)
ASSERT_EQ(written.size(), 4u);
- EXPECT_EQ(written[0], a_record);
- EXPECT_EQ(written[1], c_record);
- EXPECT_EQ(written[2], e_record);
- EXPECT_EQ(written[3], b_record);
+ EXPECT_EQ(written[0], e_record);
+ EXPECT_EQ(written[1], b_record);
+ EXPECT_EQ(written[2], a_record);
+ EXPECT_EQ(written[3], c_record);
}
} // namespace gn_builder_unittest
