[vcpkg] Randomize topological sort in CI plans to allow concurrent builds to more efficiently interact
MODIFY
.clang-format
.clang-format
@@ -30,3 +30,4 @@ KeepEmptyLinesAtTheStartOfBlocks: false
NamespaceIndentation: All
PenaltyReturnTypeOnItsOwnLine: 1000
SpaceAfterTemplateKeyword: false
+SpaceBeforeCpp11BracedList: false

MODIFY
include/vcpkg/base/graphs.h
include/vcpkg/base/graphs.h
@@ -29,13 +29,36 @@ namespace vcpkg::Graphs
virtual U load_vertex_data(const V& vertex) const = 0;
};
+ struct Randomizer
+ {
+ virtual int random(int max_exclusive) = 0;
+
+ protected:
+ ~Randomizer() {}
+ };
+
namespace details
{
+ template<class Container>
+ void shuffle(Container& c, Randomizer* r)
+ {
+ if (!r) return;
+ for (int i = static_cast<int>(c.size()); i > 1; --i)
+ {
+ auto j = r->random(i);
+ if (j != i - 1)
+ {
+ std::swap(c[i - 1], c[j]);
+ }
+ }
+ }
+
template<class V, class U>
void topological_sort_internal(const V& vertex,
const AdjacencyProvider<V, U>& f,
std::unordered_map<V, ExplorationStatus>& exploration_status,
- std::vector<U>& sorted)
+ std::vector<U>& sorted,
+ Randomizer* randomizer)
{
ExplorationStatus& status = exploration_status[vertex];
switch (status)
@@ -43,7 +66,7 @@ namespace vcpkg::Graphs
case ExplorationStatus::FULLY_EXPLORED: return;
case ExplorationStatus::PARTIALLY_EXPLORED:
{
- System::println("Cycle detected within graph:");
+ System::println("Cycle detected within graph at %s:", f.to_string(vertex));
for (auto&& node : exploration_status)
{
if (node.second == ExplorationStatus::PARTIALLY_EXPLORED)
@@ -57,8 +80,10 @@ namespace vcpkg::Graphs
{
status = ExplorationStatus::PARTIALLY_EXPLORED;
U vertex_data = f.load_vertex_data(vertex);
- for (const V& neighbour : f.adjacency_list(vertex_data))
- topological_sort_internal(neighbour, f, exploration_status, sorted);
+ auto neighbours = f.adjacency_list(vertex_data);
+ details::shuffle(neighbours, randomizer);
+ for (const V& neighbour : neighbours)
+ topological_sort_internal(neighbour, f, exploration_status, sorted, randomizer);
sorted.push_back(std::move(vertex_data));
status = ExplorationStatus::FULLY_EXPLORED;
@@ -69,15 +94,19 @@ namespace vcpkg::Graphs
}
}
- template<class VertexRange, class V, class U>
- std::vector<U> topological_sort(const VertexRange& starting_vertices, const AdjacencyProvider<V, U>& f)
+ template<class VertexContainer, class V, class U>
+ std::vector<U> topological_sort(VertexContainer starting_vertices,
+ const AdjacencyProvider<V, U>& f,
+ Randomizer* randomizer)
{
std::vector<U> sorted;
std::unordered_map<V, ExplorationStatus> exploration_status;
+ details::shuffle(starting_vertices, randomizer);
+
for (auto&& vertex : starting_vertices)
{
- details::topological_sort_internal(vertex, f, exploration_status, sorted);
+ details::topological_sort_internal(vertex, f, exploration_status, sorted, randomizer);
}
return sorted;

MODIFY
include/vcpkg/dependencies.h
include/vcpkg/dependencies.h
#include <vcpkg/statusparagraphs.h>
#include <vcpkg/vcpkgpaths.h>
+#include <functional>
#include <vector>
+namespace vcpkg::Graphs
+{
+ struct Randomizer;
+}
+
namespace vcpkg::Dependencies
{
enum class RequestType
@@ -148,6 +154,11 @@ namespace vcpkg::Dependencies
struct ClusterGraph;
struct GraphPlan;
+ struct CreateInstallPlanOptions
+ {
+ Graphs::Randomizer* randomizer = nullptr;
+ };
+
struct PackageGraph
{
PackageGraph(const PortFileProvider& provider, const StatusParagraphs& status_db);
@@ -157,7 +168,7 @@ namespace vcpkg::Dependencies
const std::unordered_set<std::string>& prevent_default_features = {}) const;
void upgrade(const PackageSpec& spec) const;
- std::vector<AnyAction> serialize() const;
+ std::vector<AnyAction> serialize(const CreateInstallPlanOptions& options = {}) const;
private:
std::unique_ptr<GraphPlan> m_graph_plan;
@@ -174,9 +185,14 @@ namespace vcpkg::Dependencies
const std::vector<FeatureSpec>& specs,
const StatusParagraphs& status_db);
+ /// <summary>Figure out which actions are required to install features specifications in `specs`.</summary>
+ /// <param name="provider">Contains the ports of the current environment.</param>
+ /// <param name="specs">Feature specifications to resolve dependencies for.</param>
+ /// <param name="status_db">Status of installed packages in the current environment.</param>
std::vector<AnyAction> create_feature_install_plan(const PortFileProvider& provider,
const std::vector<FeatureSpec>& specs,
- const StatusParagraphs& status_db);
+ const StatusParagraphs& status_db,
+ const CreateInstallPlanOptions& options = {});
void print_plan(const std::vector<AnyAction>& action_plan, const bool is_recursive = true);
}

MODIFY
src/vcpkg/commands.ci.cpp
src/vcpkg/commands.ci.cpp
#include <vcpkg/base/cache.h>
#include <vcpkg/base/files.h>
+#include <vcpkg/base/graphs.h>
#include <vcpkg/base/stringliteral.h>
#include <vcpkg/base/system.h>
#include <vcpkg/base/util.h>
@@ -30,14 +31,16 @@ namespace vcpkg::Commands::CI
static constexpr StringLiteral OPTION_EXCLUDE = "--exclude";
static constexpr StringLiteral OPTION_PURGE_TOMBSTONES = "--purge-tombstones";
static constexpr StringLiteral OPTION_XUNIT = "--x-xunit";
+ static constexpr StringLiteral OPTION_RANDOMIZE = "--x-randomize";
static constexpr std::array<CommandSetting, 2> CI_SETTINGS = {{
{OPTION_EXCLUDE, "Comma separated list of ports to skip"},
{OPTION_XUNIT, "File to output results in XUnit format (internal)"},
}};
- static constexpr std::array<CommandSwitch, 2> CI_SWITCHES = {{
+ static constexpr std::array<CommandSwitch, 3> CI_SWITCHES = {{
{OPTION_DRY_RUN, "Print out plan without execution"},
+ {OPTION_RANDOMIZE, "Randomize the install order"},
{OPTION_PURGE_TOMBSTONES, "Purge failure tombstones and retry building the ports"},
}};
@@ -69,7 +72,7 @@ namespace vcpkg::Commands::CI
std::map<PackageSpec, std::string> abi_tag_map;
std::set<PackageSpec> will_fail;
- const Build::BuildPackageOptions install_plan_options = {
+ const Build::BuildPackageOptions build_options = {
Build::UseHeadVersion::NO,
Build::AllowDownloads::YES,
Build::CleanBuildtrees::YES,
@@ -81,7 +84,9 @@ namespace vcpkg::Commands::CI
vcpkg::Cache<Triplet, Build::PreBuildInfo> pre_build_info_cache;
- auto action_plan = Dependencies::create_feature_install_plan(provider, fspecs, StatusParagraphs {});
+ auto action_plan = Dependencies::create_feature_install_plan(provider, fspecs, {}, {});
+
+ auto timer = Chrono::ElapsedTimer::create_started();
for (auto&& action : action_plan)
{
@@ -94,7 +99,7 @@ namespace vcpkg::Commands::CI
auto triplet = p->spec.triplet();
const Build::BuildPackageConfig build_config {
- *scf, triplet, paths.port_dir(p->spec), install_plan_options, p->feature_list};
+ *scf, triplet, paths.port_dir(p->spec), build_options, p->feature_list};
auto dependency_abis =
Util::fmap(p->computed_dependencies, [&](const PackageSpec& spec) -> Build::AbiEntry {
@@ -174,6 +179,8 @@ namespace vcpkg::Commands::CI
}
}
+ System::print("Time to determine pass/fail: %s\n", timer.elapsed().to_string());
+
return ret;
}
@@ -241,12 +248,31 @@ namespace vcpkg::Commands::CI
for (auto&& fspec : fspecs)
pgraph.install(fspec);
+ Dependencies::CreateInstallPlanOptions serialize_options;
+
+ struct RandomizerInstance : Graphs::Randomizer
+ {
+ virtual int random(int i) override
+ {
+ if (i <= 1) return 0;
+ std::uniform_int_distribution<int> d(0, i - 1);
+ return d(e);
+ }
+
+ std::random_device e;
+ } randomizer_instance;
+
+ if (Util::Sets::contains(options.switches, OPTION_RANDOMIZE))
+ {
+ serialize_options.randomizer = &randomizer_instance;
+ }
+
auto action_plan = [&]() {
int iterations = 0;
do
{
bool inconsistent = false;
- auto action_plan = pgraph.serialize();
+ auto action_plan = pgraph.serialize(serialize_options);
for (auto&& action : action_plan)
{

MODIFY
src/vcpkg/dependencies.cpp
src/vcpkg/dependencies.cpp
@@ -354,7 +354,7 @@ namespace vcpkg::Dependencies
auto installed_ports = get_installed_ports(status_db);
const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
- return Graphs::topological_sort(specs, RemoveAdjacencyProvider{status_db, installed_ports, specs_as_set});
+ return Graphs::topological_sort(specs, RemoveAdjacencyProvider{status_db, installed_ports, specs_as_set}, {});
}
std::vector<ExportPlanAction> create_export_plan(const std::vector<PackageSpec>& specs,
@@ -396,7 +396,7 @@ namespace vcpkg::Dependencies
const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
std::vector<ExportPlanAction> toposort =
- Graphs::topological_sort(specs, ExportAdjacencyProvider{status_db, specs_as_set});
+ Graphs::topological_sort(specs, ExportAdjacencyProvider{status_db, specs_as_set}, {});
return toposort;
}
@@ -605,13 +605,10 @@ namespace vcpkg::Dependencies
}
}
- /// <summary>Figure out which actions are required to install features specifications in `specs`.</summary>
- /// <param name="provider">Contains the ports of the current environment.</param>
- /// <param name="specs">Feature specifications to resolve dependencies for.</param>
- /// <param name="status_db">Status of installed packages in the current environment.</param>
std::vector<AnyAction> create_feature_install_plan(const PortFileProvider& provider,
const std::vector<FeatureSpec>& specs,
- const StatusParagraphs& status_db)
+ const StatusParagraphs& status_db,
+ const CreateInstallPlanOptions& options)
{
std::unordered_set<std::string> prevent_default_features;
for (auto&& spec : specs)
@@ -628,7 +625,7 @@ namespace vcpkg::Dependencies
pgraph.install(spec, prevent_default_features);
}
- return pgraph.serialize();
+ return pgraph.serialize(options);
}
/// <summary>Figure out which actions are required to install features specifications in `specs`.</summary>
@@ -672,13 +669,15 @@ namespace vcpkg::Dependencies
mark_minus(spec_cluster, *m_graph, *m_graph_plan, {});
}
- std::vector<AnyAction> PackageGraph::serialize() const
+ std::vector<AnyAction> PackageGraph::serialize(const CreateInstallPlanOptions& options) const
{
auto remove_vertex_list = m_graph_plan->remove_graph.vertex_list();
- auto remove_toposort = Graphs::topological_sort(remove_vertex_list, m_graph_plan->remove_graph);
+ auto remove_toposort =
+ Graphs::topological_sort(remove_vertex_list, m_graph_plan->remove_graph, options.randomizer);
auto insert_vertex_list = m_graph_plan->install_graph.vertex_list();
- auto insert_toposort = Graphs::topological_sort(insert_vertex_list, m_graph_plan->install_graph);
+ auto insert_toposort =
+ Graphs::topological_sort(insert_vertex_list, m_graph_plan->install_graph, options.randomizer);
std::vector<AnyAction> plan;

[vcpkg] Randomize topological sort in CI plans to allow concurrent builds to more efficiently interact