GN: Makes GN output deterministic

tools/gn/ninja_target_writer.cc

Index: tools/gn/ninja_target_writer.cc
diff --git a/tools/gn/ninja_target_writer.cc b/tools/gn/ninja_target_writer.cc
index 76413076685207938ec73c2bd9d192ae0efa8f16..2086d47557d32dca50cb8ddb4a19df16863e788c 100644
--- a/tools/gn/ninja_target_writer.cc
+++ b/tools/gn/ninja_target_writer.cc
@@ -207,14 +207,13 @@ OutputFile NinjaTargetWriter::WriteInputDepsStampAndGetDep(
   }
 
   // The different souces of input deps may duplicate some targets, so uniquify
-  // them (ordering doesn't matter for this case).
+  // them. Note that the order matters, or the output is non-deterministic.
   std::set<const Target*> unique_deps;
 
   // Hard dependencies that are direct or indirect dependencies.
   const std::set<const Target*>& hard_deps = target_->recursive_hard_deps();

[M-A Ruel, 2015/12/07 15:09:50]

Use the copy-constructor to save an empty initialization.
std::set<const Target*> unique_deps(target_->recursive_hard_deps());

But then I read http://stackoverflow.com/a/1041939/1939810 and made me wonder a
bit. STL is weird, e.g. "Convert to set (manually)" vs "Convert to set (using a
constructor)".

But I do hope the set(set) copy constructor is better than set(vector).

I don't know what scale (especially with number of duplicates) we want to
optimize for.

[brettw, 2015/12/07 18:48:54]

We don't have to micro-optimize, but in the GN code I try to be pretty careful
since this will be called several thousand times in ~900ms.

In this case, the extra_hard_deps and toolchaion_deps are almost always empty
and if they aren't, they will be small. In contrast, the recursive_hard_deps can
be several hundred items.

I would do something like this:

std::vector<const Target*> sorted_deps;
for (dep : extra_hard_deps) {
  if (hard_deps doesn't contain dep)
    sorted_deps.push_back(dep)
}
<Same thing for toolchain deps>
sorted_deps.insert(hard_deps);
sort(sorted_deps)

This will prevent the extra set construction just to merge with extra_hard_deps.

[Zachary Forman, 2015/12/08 09:40:42]

Nice approach, and probably scales better too. Pretty similar base runtime,
however.

-  for (const auto& dep : hard_deps)
-    unique_deps.insert(dep);
 
+  unique_deps.insert(hard_deps.begin(), hard_deps.end());
   // Extra hard dependencies passed in.
   unique_deps.insert(extra_hard_deps.begin(), extra_hard_deps.end());
 
@@ -226,7 +225,15 @@ OutputFile NinjaTargetWriter::WriteInputDepsStampAndGetDep(
   for (const auto& toolchain_dep : toolchain_deps)
     unique_deps.insert(toolchain_dep.ptr);
 
-  for (const auto& dep : unique_deps) {
+  // Sort the dependencies so they're in deterministic order.
+  std::vector<const Target*> sorted_deps(unique_deps.begin(),
+                                         unique_deps.end());
+
+  std::sort(
+      sorted_deps.begin(), sorted_deps.end(),
+      [](const Target* a, const Target* b) { return a->label() < b->label(); });
+
+  for (const auto& dep : sorted_deps) {
     DCHECK(!dep->dependency_output_file().value().empty());
     out_ << " ";
     path_output_.WriteFile(out_, dep->dependency_output_file());