From 4b6f10cfff8ab99a17fe5de79966248c3ccf1806 Mon Sep 17 00:00:00 2001
From: janakr <janakr@google.com>
Date: Sun, 24 Dec 2017 13:57:22 -0800
Subject: Memoize equals and hashCode operations for BuildOptions. Currently,
 equality is so slow that if we have to compare many of them, the build can
 basically never finish. This is needed for a follow-up in which BuildOptions
 are part of many SkyKeys.

PiperOrigin-RevId: 180056834
---
 .../build/lib/analysis/config/BuildOptions.java    | 51 ++++++++++++++++++++--
 1 file changed, 48 insertions(+), 3 deletions(-)

(limited to 'src/main/java/com/google/devtools/build/lib/analysis/config')

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
index ae0a7f66dd..024c33748a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
@@ -19,26 +19,34 @@ import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.InvocationPolicy;
+import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.common.options.InvocationPolicyEnforcer;
 import com.google.devtools.common.options.OptionsBase;
 import com.google.devtools.common.options.OptionsClassProvider;
 import com.google.devtools.common.options.OptionsParser;
 import com.google.devtools.common.options.OptionsParsingException;
 import java.io.Serializable;
+import java.util.Arrays;
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeMap;
 import java.util.TreeSet;
+import javax.annotation.Nullable;
 
 /**
  * Stores the command-line options from a set of configuration fragments.
  */
 public final class BuildOptions implements Cloneable, Serializable {
+  private static final Comparator<Class<? extends FragmentOptions>>
+      lexicalFragmentOptionsComparator = Comparator.comparing(Class::getName);
+
   /**
    * Creates a BuildOptions object with all options set to their default values, processed by the
    * given {@code invocationPolicy}.
@@ -220,6 +228,35 @@ public final class BuildOptions implements Cloneable, Serializable {
     return new BuildOptions(builder.build());
   }
 
+  /**
+   * Lazily initialize {@link #fingerprint} and {@link #hashCode}. Keeps computation off critical
+   * path of build, while still avoiding expensive computation for equality and hash code each time.
+   *
+   * <p>We check for nullity of {@link #fingerprint} to see if this method has already been called.
+   * Using {@link #hashCode} after this method is called is safe because it is set here before
+   * {@link #fingerprint} is set, so if {@link #fingerprint} is non-null then {@link #hashCode} is
+   * definitely set.
+   */
+  private void maybeInitializeFingerprintAndHashCode() {
+    if (fingerprint != null) {
+      return;
+    }
+    synchronized (this) {
+      if (fingerprint != null) {
+        return;
+      }
+      Fingerprint fingerprint = new Fingerprint();
+      for (Map.Entry<Class<? extends FragmentOptions>, FragmentOptions> entry :
+          fragmentOptionsMap.entrySet()) {
+        fingerprint.addString(entry.getKey().getName());
+        fingerprint.addString(entry.getValue().cacheKey());
+      }
+      byte[] computedFingerprint = fingerprint.digestAndReset();
+      hashCode = Arrays.hashCode(computedFingerprint);
+      this.fingerprint = computedFingerprint;
+    }
+  }
+
   @Override
   public boolean equals(Object other) {
     if (this == other) {
@@ -227,16 +264,23 @@ public final class BuildOptions implements Cloneable, Serializable {
     } else if (!(other instanceof BuildOptions)) {
       return false;
     } else {
+      maybeInitializeFingerprintAndHashCode();
       BuildOptions otherOptions = (BuildOptions) other;
-      return fragmentOptionsMap.equals(otherOptions.fragmentOptionsMap);
+      otherOptions.maybeInitializeFingerprintAndHashCode();
+      return Arrays.equals(this.fingerprint, otherOptions.fingerprint);
     }
   }
 
   @Override
   public int hashCode() {
-    return fragmentOptionsMap.hashCode();
+    maybeInitializeFingerprintAndHashCode();
+    return hashCode;
   }
 
+  // Lazily initialized.
+  @Nullable private volatile byte[] fingerprint;
+  private volatile int hashCode;
+
   /**
    * Maps options class definitions to FragmentOptions objects.
    */
@@ -268,7 +312,8 @@ public final class BuildOptions implements Cloneable, Serializable {
     }
 
     public BuildOptions build() {
-      return new BuildOptions(ImmutableMap.copyOf(builderMap));
+      return new BuildOptions(
+          ImmutableSortedMap.copyOf(builderMap, lexicalFragmentOptionsComparator));
     }
 
     private Map<Class<? extends FragmentOptions>, FragmentOptions> builderMap;
-- 
cgit v1.2.3