AU: Cyclebreaker optimization
When using the cycle breaker, we know that operations that are full
(REPLACE, REPLACE_BZ) can't have any incoming edges, and thus can't be
in a cycle.
To help reduce CPU usage, change the cycle breaker to skip nodes that
are REPLACE or REPLACE_BZ.
BUG=7294
TEST=Attached unittests, generated delta update and applied it
Review URL: http://codereview.chromium.org/3618006
diff --git a/cycle_breaker.cc b/cycle_breaker.cc
index 552a54f..266c2df 100644
--- a/cycle_breaker.cc
+++ b/cycle_breaker.cc
@@ -34,8 +34,16 @@
// and looking for the strongly connected component with vertex s.
TarjanAlgorithm tarjan;
+ skipped_ops_ = 0;
for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
+ DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+ if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ skipped_ops_++;
+ continue;
+ }
+
if (i > 0) {
// Erase node (i - 1) from subgraph_. First, erase what it points to
subgraph_[i - 1].out_edges.clear();
@@ -71,6 +79,7 @@
}
out_cut_edges->swap(cut_edges_);
+ LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
DCHECK(stack_.empty());
}
@@ -116,7 +125,7 @@
bool CycleBreaker::StackContainsCutEdge() const {
for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
- e = stack_.end(); it != e; ++it) {
+ e = stack_.end(); it != e; ++it) {
Edge edge = make_pair(*(it - 1), *it);
if (utils::SetContainsKey(cut_edges_, edge)) {
return true;