commit ec938ddaa276646eb8f1ab33e160c156011d8217
author David 'Digit' Turner <digit@google.com> Tue Mar 31 10:27:10 2020 +0200
committer Commit Bot <commit-bot@chromium.org> Tue Apr 07 15:28:42 2020 +0000
tree 2c8ce7a06ad36e2794ed513bd3d47cd3ab852bad
parent d6131075f75ba4e7ae1ba62a5f4a57eb7f6122ba

Speed up label comparison

The Label::operator< function appears high in the profile of "gn gen"
for the Chromium and Fuchsia build, so this CL optimizes its
implementation by using the fact that StringAtom and SourceDir are
both unique/interned string pointer values, with very fast equality
comparison.

This saves about 1s from the Fuchsia 'gn gen' step.

Measurements:

/work/chromium0/src$ repeat_cmd 5 /tmp/gn-master gen --check out/Release
Done. Made 13413 targets from 2220 files in 6620ms
Done. Made 13413 targets from 2220 files in 6552ms
Done. Made 13413 targets from 2220 files in 6450ms
Done. Made 13413 targets from 2220 files in 6532ms
Done. Made 13413 targets from 2220 files in 6346ms (best)

/work/chromium0/src$ repeat_cmd 5 /tmp/gn-fast-label gen --check out/Release
Done. Made 13413 targets from 2220 files in 6785ms
Done. Made 13413 targets from 2220 files in 6369ms
Done. Made 13413 targets from 2220 files in 6285ms (best)
Done. Made 13413 targets from 2220 files in 6285ms
Done. Made 13413 targets from 2220 files in 6391ms

/work/fx-gn$ GN=prebuilt/third_party/gn/linux-x64/gn
/work/fx-gn$ cp -f /tmp/gn-master $GN
/work/fx-gn$ repeat_cmd 5 $GN gen --check out/default
Done. Made 42114 targets from 3695 files in 12574ms (best)
Done. Made 42114 targets from 3695 files in 12932ms
Done. Made 42114 targets from 3695 files in 13155ms
Done. Made 42114 targets from 3695 files in 13238ms
Done. Made 42114 targets from 3695 files in 13108ms

/work/fx-gn$ cp -f /tmp/gn-fast-label $GN
/work/fx-gn$ repeat_cmd 5 $GN gen --check out/default
Done. Made 42114 targets from 3695 files in 12252ms
Done. Made 42114 targets from 3695 files in 12336ms
Done. Made 42114 targets from 3695 files in 12438ms
Done. Made 42114 targets from 3695 files in 11938ms
Done. Made 42114 targets from 3695 files in 11601ms (best)

Change-Id: I80c0bd47e89c101c7c42fe57cc71592b2b27713e
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/8000
Reviewed-by: Brett Wilson <brettw@chromium.org>
Commit-Queue: Brett Wilson <brettw@chromium.org>

src/gn/label.h

diff --git a/src/gn/label.h b/src/gn/label.h
index 95234c9..dc9813b 100644
--- a/src/gn/label.h
+++ b/src/gn/label.h
@@ -75,9 +75,19 @@
   }
   bool operator!=(const Label& other) const { return !operator==(other); }
   bool operator<(const Label& other) const {
-    return std::tie(dir_, name_, toolchain_dir_, toolchain_name_) <
-           std::tie(other.dir_, other.name_, other.toolchain_dir_,
-                    other.toolchain_name_);
+    // This custom comparison function uses the fact that SourceDir and
+    // StringAtom values have very fast equality comparison to avoid
+    // un-necessary string comparisons when components are equal.
+    if (dir_ != other.dir_)
+      return dir_ < other.dir_;
+
+    if (!name_.SameAs(other.name_))
+      return name_ < other.name_;
+
+    if (toolchain_dir_ != other.toolchain_dir_)
+      return toolchain_dir_ < other.toolchain_dir_;
+
+    return toolchain_name_ < other.toolchain_name_;
   }
 
   // Returns true if the toolchain dir/name of this object matches some

src/gn/string_atom.h

diff --git a/src/gn/string_atom.h b/src/gn/string_atom.h
index fa92ac2..29d4e41 100644
--- a/src/gn/string_atom.h
+++ b/src/gn/string_atom.h
@@ -109,6 +109,10 @@
   }
 
   bool operator<(const StringAtom& other) const {
+    // Avoid one un-necessary string comparison if values are equal.
+    if (SameAs(other))
+      return false;
+
     return value_ < other.value_;
   }