Use static creation method for SkyKey. This allows interning SkyKeys as they are created, as opposed to when they are requested from the ParallelEvaluator. That delay can lead to large memory spikes and churn.

--
MOS_MIGRATED_REVID=116224565
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
index c3b755c..dd5a350 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
@@ -37,7 +37,7 @@
 
   public static SkyKey key(String serverName) {
     Preconditions.checkNotNull(serverName);
-    return new SkyKey(MavenServerFunction.NAME, serverName);
+    return SkyKey.create(MavenServerFunction.NAME, serverName);
   }
 
   public static MavenServerValue createFromUrl(String url) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 62fa681..25d65ea 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -94,7 +94,7 @@
  */
 public class GenQuery implements RuleConfiguredTargetFactory {
   public static final Precomputed<ImmutableList<OutputFormatter>> QUERY_OUTPUT_FORMATTERS =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "query_output_formatters"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "query_output_formatters"));
 
   @Override
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
index 6b43297..5756d51 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
@@ -89,6 +89,6 @@
    * Creates a key from the given repository name.
    */
   public static SkyKey key(RepositoryName repository) {
-    return new SkyKey(SkyFunctions.REPOSITORY_DIRECTORY, repository);
+    return SkyKey.create(SkyFunctions.REPOSITORY_DIRECTORY, repository);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
index fa0f175..27430e9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
@@ -95,6 +95,6 @@
   }
 
   static SkyKey key(Label astFileLabel) {
-    return new SkyKey(SkyFunctions.AST_FILE_LOOKUP, astFileLabel);
+    return SkyKey.create(SkyFunctions.AST_FILE_LOOKUP, astFileLabel);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
index b0b9c51..25a4339 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
@@ -129,7 +129,7 @@
   @ThreadSafe
   @VisibleForTesting
   public static SkyKey key(Action action) {
-    return new SkyKey(SkyFunctions.ACTION_EXECUTION, action);
+    return SkyKey.create(SkyFunctions.ACTION_EXECUTION, action);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
index 27418c5..a78b6a4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
@@ -105,7 +105,7 @@
      * <p>Subclasses may override if the value key contents should not be the key itself.
      */
     SkyKey getSkyKey() {
-      return new SkyKey(getType(), this);
+      return SkyKey.create(getType(), this);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
index 8114ba9..d9a5150 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
@@ -41,9 +41,11 @@
 
   @ThreadSafe
   public static SkyKey key(Artifact artifact, boolean isMandatory) {
-    return new SkyKey(SkyFunctions.ARTIFACT, artifact.isSourceArtifact()
-        ? new OwnedArtifact(artifact, isMandatory)
-        : new OwnedArtifact(artifact));
+    return SkyKey.create(
+        SkyFunctions.ARTIFACT,
+        artifact.isSourceArtifact()
+            ? new OwnedArtifact(artifact, isMandatory)
+            : new OwnedArtifact(artifact));
   }
 
   private static final Function<Artifact, SkyKey> TO_MANDATORY_KEY =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
index 5f008f7..22b0ee0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
@@ -40,7 +40,7 @@
         new Function<AspectValue, SkyKey>() {
           @Override
           public SkyKey apply(AspectValue aspectValue) {
-            return new SkyKey(SkyFunctions.ASPECT_COMPLETION, aspectValue.getKey());
+            return SkyKey.create(SkyFunctions.ASPECT_COMPLETION, aspectValue.getKey());
           }
         });
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index f67ae19..43bc287 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -280,14 +280,14 @@
       BuildConfiguration baseConfiguration,
       AspectClass aspectFactory,
       AspectParameters additionalConfiguration) {
-    return new SkyKey(
+    return SkyKey.create(
         SkyFunctions.ASPECT,
         new AspectKey(
             label, aspectConfiguration, baseConfiguration, aspectFactory, additionalConfiguration));
   }
 
   public static SkyKey key(AspectValueKey aspectKey) {
-    return new SkyKey(aspectKey.getType(), aspectKey);
+    return SkyKey.create(aspectKey.getType(), aspectKey);
   }
 
   public static AspectKey createAspectKey(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
index 99d954d..b5c9420 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
@@ -26,7 +26,7 @@
   private final ImmutableSet<PathFragment> patterns;
 
   private static final SkyKey BLACKLIST_KEY =
-      new SkyKey(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES, "");
+      SkyKey.create(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES, "");
 
   public BlacklistedPackagePrefixesValue(ImmutableSet<PathFragment> exclusions) {
     this.patterns = Preconditions.checkNotNull(exclusions);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java
index 8591dbd..9bd14e8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java
@@ -51,8 +51,7 @@
   @ThreadSafe
   public static SkyKey key(Set<Class<? extends BuildConfiguration.Fragment>> fragments,
       BuildOptions buildOptions) {
-    return new SkyKey(SkyFunctions.BUILD_CONFIGURATION,
-        new Key(fragments, buildOptions, true));
+    return SkyKey.create(SkyFunctions.BUILD_CONFIGURATION, new Key(fragments, buildOptions, true));
   }
 
   /**
@@ -66,8 +65,7 @@
   public static SkyKey disabledActionsKey(
       Set<Class<? extends BuildConfiguration.Fragment>> fragments,
       BuildOptions buildOptions) {
-    return new SkyKey(SkyFunctions.BUILD_CONFIGURATION,
-        new Key(fragments, buildOptions, false));
+    return SkyKey.create(SkyFunctions.BUILD_CONFIGURATION, new Key(fragments, buildOptions, false));
   }
 
   static final class Key implements Serializable {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
index 82f4c55..dfff250 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
@@ -33,7 +33,7 @@
    */
   static SkyKey key(SkyFunctionName functionName, ImmutableList<? extends Object> chain) {
     Preconditions.checkState(!chain.isEmpty());
-    return new SkyKey(functionName, canonicalize(chain));
+    return SkyKey.create(functionName, canonicalize(chain));
   }
 
   private static ImmutableList<Object> canonicalize(ImmutableList<? extends Object> cycle) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
index f015509..1a431e2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
@@ -115,6 +115,6 @@
   }
 
   static SkyKey key(RecursivePkgKey recursivePkgKey) {
-    return new SkyKey(SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY, recursivePkgKey);
+    return SkyKey.create(SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY, recursivePkgKey);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationCollectionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationCollectionValue.java
index 90c200c..eb5f173 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationCollectionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationCollectionValue.java
@@ -44,7 +44,8 @@
 
   @ThreadSafe
   public static SkyKey key(BuildOptions buildOptions, ImmutableSet<String> multiCpu) {
-    return new SkyKey(SkyFunctions.CONFIGURATION_COLLECTION, 
+    return SkyKey.create(
+        SkyFunctions.CONFIGURATION_COLLECTION,
         new ConfigurationCollectionKey(buildOptions, multiCpu));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationFragmentValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationFragmentValue.java
index 9db7f72..43d6c27 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationFragmentValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfigurationFragmentValue.java
@@ -56,7 +56,8 @@
             BuildConfiguration.getOptionsClasses(
                 ImmutableList.<Class<? extends BuildConfiguration.Fragment>>of(fragmentType),
                 ruleClassProvider));
-    return new SkyKey(SkyFunctions.CONFIGURATION_FRAGMENT,
+    return SkyKey.create(
+        SkyFunctions.CONFIGURATION_FRAGMENT,
         new ConfigurationFragmentKey(optionsKey, fragmentType));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
index 0653f33..ffee11c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
@@ -39,7 +39,7 @@
 
   public static SkyKey key(PackageIdentifier id) {
     Preconditions.checkArgument(!id.getPackageFragment().isAbsolute(), id);
-    return new SkyKey(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, id);
+    return SkyKey.create(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, id);
   }
 
   public static ContainingPackage withContainingPackage(PackageIdentifier pkgId, Path root) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
index 66dc169..44722b5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
@@ -29,7 +29,8 @@
   private final ImmutableSet<Artifact> coverageReportArtifacts;
 
   // There should only ever be one CoverageReportValue value in the graph.
-  public static final SkyKey SKY_KEY = new SkyKey(SkyFunctions.COVERAGE_REPORT, "COVERAGE_REPORT");
+  public static final SkyKey SKY_KEY =
+      SkyKey.create(SkyFunctions.COVERAGE_REPORT, "COVERAGE_REPORT");
   public static final ArtifactOwner ARTIFACT_OWNER = new CoverageReportKey();
 
   public CoverageReportValue(ImmutableSet<Artifact> coverageReportArtifacts,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
index cf94b59..34b2022 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
@@ -57,7 +57,7 @@
 
   @ThreadSafe
   public static SkyKey key(RootedPath rootedPath) {
-    return new SkyKey(SkyFunctions.DIRECTORY_LISTING_STATE, rootedPath);
+    return SkyKey.create(SkyFunctions.DIRECTORY_LISTING_STATE, rootedPath);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
index 8822cdc..fd02f4c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
@@ -56,7 +56,7 @@
    */
   @ThreadSafe
   static SkyKey key(RootedPath directoryUnderRoot) {
-    return new SkyKey(SkyFunctions.DIRECTORY_LISTING, directoryUnderRoot);
+    return SkyKey.create(SkyFunctions.DIRECTORY_LISTING, directoryUnderRoot);
   }
 
   static DirectoryListingValue value(RootedPath dirRootedPath, FileValue dirFileValue,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
index 283e1a6..eae3ac7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
@@ -60,6 +60,6 @@
    * Returns a SkyKey to find the WORKSPACE file at the given path.
    */
   public static SkyKey key(RootedPath workspacePath) {
-    return new SkyKey(SkyFunctions.EXTERNAL_PACKAGE, workspacePath);
+    return SkyKey.create(SkyFunctions.EXTERNAL_PACKAGE, workspacePath);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
index 459d1ca..4e90846 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
@@ -103,7 +103,7 @@
   @VisibleForTesting
   @ThreadSafe
   public static SkyKey key(RootedPath rootedPath) {
-    return new SkyKey(SkyFunctions.FILE_STATE, rootedPath);
+    return SkyKey.create(SkyFunctions.FILE_STATE, rootedPath);
   }
 
   public abstract Type getType();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
index e10cf77..d4ce6ca 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
@@ -119,7 +119,7 @@
    */
   @ThreadSafe
   public static SkyKey key(RootedPath rootedPath) {
-    return new SkyKey(SkyFunctions.FILE, rootedPath);
+    return SkyKey.create(SkyFunctions.FILE, rootedPath);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryValue.java
index c72a4ac..d628da2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryValue.java
@@ -44,7 +44,7 @@
   }
 
   public static SkyKey key(FilesetTraversalParams params) {
-    return new SkyKey(SkyFunctions.FILESET_ENTRY, params);
+    return SkyKey.create(SkyFunctions.FILESET_ENTRY, params);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
index 5e877bd..5f8eaa9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
@@ -102,7 +102,8 @@
   @ThreadSafe
   static SkyKey internalKey(PackageIdentifier packageId, Path packageRoot, PathFragment subdir,
       String pattern, boolean excludeDirs) {
-    return new SkyKey(SkyFunctions.GLOB,
+    return SkyKey.create(
+        SkyFunctions.GLOB,
         new GlobDescriptor(packageId, packageRoot, subdir, pattern, excludeDirs));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
index e265e44..b277321 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
@@ -39,7 +39,7 @@
  */
 public class PackageErrorFunction implements SkyFunction {
   public static SkyKey key(PackageIdentifier packageIdentifier) {
-    return new SkyKey(SkyFunctions.PACKAGE_ERROR, packageIdentifier);
+    return SkyKey.create(SkyFunctions.PACKAGE_ERROR, packageIdentifier);
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
index d6fdcc0..816ab4f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
@@ -97,7 +97,7 @@
   }
 
   public static SkyKey key(PackageIdentifier pkgIdentifier) {
-    return new SkyKey(SkyFunctions.PACKAGE_LOOKUP, pkgIdentifier);
+    return SkyKey.create(SkyFunctions.PACKAGE_LOOKUP, pkgIdentifier);
   }
 
   private static class SuccessfulPackageLookupValue extends PackageLookupValue {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
index 01e4af5..840a4c8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
@@ -54,7 +54,7 @@
   }
 
   public static SkyKey key(PackageIdentifier pkgIdentifier) {
-    return new SkyKey(SkyFunctions.PACKAGE, pkgIdentifier);
+    return SkyKey.create(SkyFunctions.PACKAGE, pkgIdentifier);
   }
 
   public static List<SkyKey> keys(Iterable<PackageIdentifier> pkgIdentifiers) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
index 8e2551f..4ef9ae3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
@@ -40,7 +40,7 @@
   }
 
   public static SkyKey key(ConfiguredTargetKey lac) {
-    return new SkyKey(SkyFunctions.POST_CONFIGURED_TARGET, lac);
+    return SkyKey.create(SkyFunctions.POST_CONFIGURED_TARGET, lac);
   }
 
   public ConfiguredTarget getCt() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
index 5ae849c..9aab8b1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
@@ -74,38 +74,38 @@
   }
 
   public static final Precomputed<String> DEFAULTS_PACKAGE_CONTENTS =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "default_pkg"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "default_pkg"));
 
   public static final Precomputed<PathFragment> BLACKLISTED_PACKAGE_PREFIXES_FILE =
-          new Precomputed<>(
-              new SkyKey(SkyFunctions.PRECOMPUTED, "blacklisted_package_prefixes_file"));
+      new Precomputed<>(
+          SkyKey.create(SkyFunctions.PRECOMPUTED, "blacklisted_package_prefixes_file"));
 
   public static final Precomputed<RuleVisibility> DEFAULT_VISIBILITY =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "default_visibility"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "default_visibility"));
 
   static final Precomputed<UUID> BUILD_ID =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "build_id"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "build_id"));
 
   static final Precomputed<WorkspaceStatusAction> WORKSPACE_STATUS_KEY =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "workspace_status_action"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "workspace_status_action"));
 
-  static final Precomputed<ImmutableList <Action>> COVERAGE_REPORT_KEY =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "coverage_report_actions"));
+  static final Precomputed<ImmutableList<Action>> COVERAGE_REPORT_KEY =
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "coverage_report_actions"));
 
   static final Precomputed<TopLevelArtifactContext> TOP_LEVEL_CONTEXT =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "top_level_context"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "top_level_context"));
 
   public static final Precomputed<Map<BuildInfoKey, BuildInfoFactory>> BUILD_INFO_FACTORIES =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "build_info_factories"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "build_info_factories"));
 
   static final Precomputed<BlazeDirectories> BLAZE_DIRECTORIES =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "blaze_directories"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "blaze_directories"));
 
   static final Precomputed<ImmutableMap<Action, ConflictException>> BAD_ACTIONS =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "bad_actions"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "bad_actions"));
 
   public static final Precomputed<PathPackageLocator> PATH_PACKAGE_LOCATOR =
-      new Precomputed<>(new SkyKey(SkyFunctions.PRECOMPUTED, "path_package_locator"));
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "path_package_locator"));
 
   private final Object value;
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
index 48ef204..423d07e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
@@ -206,7 +206,7 @@
 
     @Override
     public SkyKey getSkyKey() throws TargetParsingException {
-      return new SkyKey(SkyFunctions.PREPARE_DEPS_OF_PATTERN, targetPatternKey);
+      return SkyKey.create(SkyFunctions.PREPARE_DEPS_OF_PATTERN, targetPatternKey);
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
index 5d73904..81a65d3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
@@ -55,8 +55,8 @@
 
   @ThreadSafe
   public static SkyKey key(ImmutableList<String> patterns, String offset) {
-    return new SkyKey(SkyFunctions.PREPARE_DEPS_OF_PATTERNS,
-        new TargetPatternSequence(patterns, offset));
+    return SkyKey.create(
+        SkyFunctions.PREPARE_DEPS_OF_PATTERNS, new TargetPatternSequence(patterns, offset));
   }
 
   /** The argument value for {@link SkyKey}s of {@link PrepareDepsOfPatternsFunction}. */
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
index 136a94b..c937263 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
@@ -61,10 +61,10 @@
   @ThreadSafe
   public static SkyKey key(RepositoryName repository, RootedPath rootedPath,
       ImmutableSet<PathFragment> excludedPaths, FilteringPolicy filteringPolicy) {
-    return new SkyKey(SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
+    return SkyKey.create(
+        SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
         new PrepareDepsOfTargetsUnderDirectoryKey(
-            new RecursivePkgKey(repository, rootedPath, excludedPaths),
-            filteringPolicy));
+            new RecursivePkgKey(repository, rootedPath, excludedPaths), filteringPolicy));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
index d79f7b9..7f2777c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
@@ -105,7 +105,7 @@
   }
 
   public static SkyKey key(TraversalRequest traversal) {
-    return new SkyKey(SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, traversal);
+    return SkyKey.create(SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, traversal);
   }
 
   /** The parameters of a file or directory traversal. */
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
index 8919578..b318519 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
@@ -58,8 +58,8 @@
   @ThreadSafe
   public static SkyKey key(RepositoryName repositoryName, RootedPath rootedPath,
       ImmutableSet<PathFragment> excludedPaths) {
-    return new SkyKey(SkyFunctions.RECURSIVE_PKG,
-        new RecursivePkgKey(repositoryName, rootedPath, excludedPaths));
+    return SkyKey.create(
+        SkyFunctions.RECURSIVE_PKG, new RecursivePkgKey(repositoryName, rootedPath, excludedPaths));
   }
 
   public NestedSet<String> getPackages() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
index 2f8da11..a33e4e0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
@@ -63,6 +63,6 @@
   }
 
   static SkyKey key(RepositoryName repositoryName) {
-    return new SkyKey(SkyFunctions.REPOSITORY, repositoryName);
+    return SkyKey.create(SkyFunctions.REPOSITORY, repositoryName);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
index 278c597..2fbaf10 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
@@ -93,7 +93,7 @@
   }
 
   static SkyKey key(Label importLabel, boolean inWorkspace) {
-    return new SkyKey(
+    return SkyKey.create(
         SkyFunctions.SKYLARK_IMPORTS_LOOKUP, new SkylarkImportLookupKey(importLabel, inWorkspace));
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetCompletionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetCompletionValue.java
index c9bc04a..94eda0e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetCompletionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetCompletionValue.java
@@ -37,15 +37,17 @@
   }
 
   public static SkyKey key(LabelAndConfiguration labelAndConfiguration) {
-    return new SkyKey(SkyFunctions.TARGET_COMPLETION, labelAndConfiguration);
+    return SkyKey.create(SkyFunctions.TARGET_COMPLETION, labelAndConfiguration);
   }
 
   public static Iterable<SkyKey> keys(Collection<ConfiguredTarget> targets) {
-    return Iterables.transform(targets, new Function<ConfiguredTarget, SkyKey>() {
-      @Override
-      public SkyKey apply(ConfiguredTarget ct) {
-        return new SkyKey(SkyFunctions.TARGET_COMPLETION, new LabelAndConfiguration(ct));
-      }
-    });
+    return Iterables.transform(
+        targets,
+        new Function<ConfiguredTarget, SkyKey>() {
+          @Override
+          public SkyKey apply(ConfiguredTarget ct) {
+            return SkyKey.create(SkyFunctions.TARGET_COMPLETION, new LabelAndConfiguration(ct));
+          }
+        });
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
index 91f7afb..9c39849 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
@@ -45,6 +45,6 @@
 
   @ThreadSafe
   public static SkyKey key(Label label) {
-    return new SkyKey(SkyFunctions.TARGET_MARKER, label);
+    return SkyKey.create(SkyFunctions.TARGET_MARKER, label);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
index f319e77..0e43191 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
@@ -125,8 +125,15 @@
   public static SkyKey key(ImmutableList<String> targetPatterns, String offset,
       boolean compileOneDependency, boolean buildTestsOnly, boolean determineTests,
       @Nullable TestFilter testFilter) {
-    return new SkyKey(SkyFunctions.TARGET_PATTERN_PHASE, new TargetPatternList(
-        targetPatterns, offset, compileOneDependency, buildTestsOnly, determineTests, testFilter));
+    return SkyKey.create(
+        SkyFunctions.TARGET_PATTERN_PHASE,
+        new TargetPatternList(
+            targetPatterns,
+            offset,
+            compileOneDependency,
+            buildTestsOnly,
+            determineTests,
+            testFilter));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
index bbf9277..f247bde 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
@@ -144,7 +144,7 @@
               !positive,
               offset,
               ImmutableSet.<PathFragment>of());
-      SkyKey skyKey = new SkyKey(SkyFunctions.TARGET_PATTERN, targetPatternKey);
+      SkyKey skyKey = SkyKey.create(SkyFunctions.TARGET_PATTERN, targetPatternKey);
       builder.add(new TargetPatternSkyKeyValue(skyKey));
     }
     return builder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
index eb2cfd4..4cb8998 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
@@ -32,18 +32,21 @@
   private TestCompletionValue() { }
 
   public static SkyKey key(LabelAndConfiguration lac, boolean exclusive) {
-    return new SkyKey(SkyFunctions.TEST_COMPLETION, new TestCompletionKey(lac, exclusive));
+    return SkyKey.create(SkyFunctions.TEST_COMPLETION, new TestCompletionKey(lac, exclusive));
   }
 
   public static Iterable<SkyKey> keys(Collection<ConfiguredTarget> targets,
                                       final boolean exclusive) {
-    return Iterables.transform(targets, new Function<ConfiguredTarget, SkyKey>() {
-      @Override
-      public SkyKey apply(ConfiguredTarget ct) {
-        return new SkyKey(SkyFunctions.TEST_COMPLETION, 
-            new TestCompletionKey(new LabelAndConfiguration(ct), exclusive));
-      }
-    });
+    return Iterables.transform(
+        targets,
+        new Function<ConfiguredTarget, SkyKey>() {
+          @Override
+          public SkyKey apply(ConfiguredTarget ct) {
+            return SkyKey.create(
+                SkyFunctions.TEST_COMPLETION,
+                new TestCompletionKey(new LabelAndConfiguration(ct), exclusive));
+          }
+        });
   }
   
   static class TestCompletionKey {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
index 0714f2d..a7a330f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
@@ -70,7 +70,8 @@
    */
   @ThreadSafe
   public static SkyKey key(Collection<Label> targets) {
-    return new SkyKey(SkyFunctions.TEST_SUITE_EXPANSION,
+    return SkyKey.create(
+        SkyFunctions.TEST_SUITE_EXPANSION,
         new TestSuiteExpansion(ImmutableSortedSet.copyOf(targets)));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
index 81b9346..0267f4a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
@@ -68,8 +68,7 @@
   @ThreadSafe
   public static SkyKey key(Target testSuite, boolean strict) {
     Preconditions.checkState(TargetUtils.isTestSuiteRule(testSuite));
-    return new SkyKey(SkyFunctions.TESTS_IN_SUITE,
-        new TestsInSuite((Rule) testSuite, strict));
+    return SkyKey.create(SkyFunctions.TESTS_IN_SUITE, new TestsInSuite((Rule) testSuite, strict));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
index d7e9358..d8e9b26 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
@@ -170,6 +170,6 @@
 
   @ThreadSafe
   public static SkyKey key(Label label) {
-    return new SkyKey(SkyFunctions.TRANSITIVE_TARGET, label);
+    return SkyKey.create(SkyFunctions.TRANSITIVE_TARGET, label);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
index 1de546d..59252d8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
@@ -13,8 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import static com.google.devtools.build.skyframe.SkyKeyInterner.SKY_KEY_INTERNER;
-
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -127,7 +125,6 @@
 
   @ThreadSafe
   public static SkyKey key(Label label) {
-    // Intern in order to save memory.
-    return SKY_KEY_INTERNER.intern(new SkyKey(SkyFunctions.TRANSITIVE_TRAVERSAL, label));
+    return SkyKey.create(SkyFunctions.TRANSITIVE_TRAVERSAL, label);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
index 35479fc..e002765 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
@@ -57,7 +57,7 @@
   }
 
   public static SkyKey key(RootedPath path) {
-    return new SkyKey(SkyFunctions.WORKSPACE_AST, path);
+    return SkyKey.create(SkyFunctions.WORKSPACE_AST, path);
   }
 }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
index cb49728..daf578e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
@@ -135,7 +135,7 @@
   }
 
   static SkyKey key(RootedPath path, int idx) {
-    return new SkyKey(SkyFunctions.WORKSPACE_FILE, new WorkspaceFileKey(path, idx));
+    return SkyKey.create(SkyFunctions.WORKSPACE_FILE, new WorkspaceFileKey(path, idx));
   }
 
   public static SkyKey key(RootedPath path) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
index 6379b56..fca72db 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
@@ -30,7 +30,7 @@
   private final Artifact volatileArtifact;
 
   // There should only ever be one BuildInfo value in the graph.
-  public static final SkyKey SKY_KEY = new SkyKey(SkyFunctions.BUILD_INFO, "BUILD_INFO");
+  public static final SkyKey SKY_KEY = SkyKey.create(SkyFunctions.BUILD_INFO, "BUILD_INFO");
   static final ArtifactOwner ARTIFACT_OWNER = new BuildInfoKey();
 
   public WorkspaceStatusValue(Artifact stableArtifact, Artifact volatileArtifact,
diff --git a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
index 3d5ede4..c0544df 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
@@ -22,7 +22,7 @@
  */
 public final class ErrorTransienceValue implements SkyValue {
   public static final SkyFunctionName FUNCTION_NAME = SkyFunctionName.create("ERROR_TRANSIENCE");
-  public static final SkyKey KEY = new SkyKey(FUNCTION_NAME, "ERROR_TRANSIENCE");
+  public static final SkyKey KEY = SkyKey.create(FUNCTION_NAME, "ERROR_TRANSIENCE");
   public static final ErrorTransienceValue INSTANCE = new ErrorTransienceValue();
 
   private ErrorTransienceValue() {}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index 1899bcc..25c3215 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -13,8 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import static com.google.devtools.build.skyframe.SkyKeyInterner.SKY_KEY_INTERNER;
-
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Predicate;
 import com.google.common.base.Supplier;
@@ -414,12 +412,6 @@
     protected ImmutableMap<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(
         Set<SkyKey> depKeys) {
       checkActive();
-      Set<SkyKey> keys = Sets.newLinkedHashSetWithExpectedSize(depKeys.size());
-      for (SkyKey depKey : depKeys) {
-        // Canonicalize SkyKeys to save memory.
-        keys.add(SKY_KEY_INTERNER.intern(depKey));
-      }
-      depKeys = keys;
       Map<SkyKey, ValueWithMetadata> values = getValuesMaybeFromError(depKeys, bubbleErrorInfo);
       ImmutableMap.Builder<SkyKey, ValueOrUntypedException> builder = ImmutableMap.builder();
       for (SkyKey depKey : depKeys) {
@@ -1637,7 +1629,7 @@
    * ArrayDeque does not permit null elements.
    */
   private static final SkyKey CHILDREN_FINISHED =
-      new SkyKey(SkyFunctionName.create("MARKER"), "MARKER");
+      SkyKey.create(SkyFunctionName.create("MARKER"), "MARKER");
 
   /** The max number of cycles we will report to the user for a given root, to avoid OOMing. */
   private static final int MAX_CYCLES = 20;
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyKey.java b/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
index 482940d..bc15bf8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
@@ -14,6 +14,8 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.common.base.Function;
+import com.google.common.collect.Interner;
+import com.google.common.collect.Interners;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.io.Serializable;
@@ -22,6 +24,8 @@
  * A {@link SkyKey} is effectively a pair (type, name) that identifies a Skyframe value.
  */
 public final class SkyKey implements Serializable {
+  private static final Interner<SkyKey> SKY_KEY_INTERNER = Interners.newWeakInterner();
+
   private final SkyFunctionName functionName;
 
   /**
@@ -39,15 +43,20 @@
    */
   private transient int hashCode;
 
-  public SkyKey(SkyFunctionName functionName, Object valueName) {
+  private SkyKey(SkyFunctionName functionName, Object argument) {
     this.functionName = Preconditions.checkNotNull(functionName);
-    this.argument = Preconditions.checkNotNull(valueName);
+    this.argument = Preconditions.checkNotNull(argument);
     // 'hashCode' is non-volatile and non-final, so this write may in fact *not* be visible to other
     // threads. But this isn't a concern from a correctness perspective. See the comments in
     // #hashCode for more details.
     this.hashCode = computeHashCode();
   }
 
+  public static SkyKey create(SkyFunctionName functionName, Object argument) {
+    // Intern to save memory.
+    return SKY_KEY_INTERNER.intern(new SkyKey(functionName, argument));
+  }
+
   public SkyFunctionName functionName() {
     return functionName;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyKeyInterner.java b/src/main/java/com/google/devtools/build/skyframe/SkyKeyInterner.java
deleted file mode 100644
index bc8a950..0000000
--- a/src/main/java/com/google/devtools/build/skyframe/SkyKeyInterner.java
+++ /dev/null
@@ -1,27 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.skyframe;
-
-import com.google.common.collect.Interner;
-import com.google.common.collect.Interners;
-
-/**
- * A holder class for SkyKey interning.
- */
-public class SkyKeyInterner {
-  public static final Interner<SkyKey> SKY_KEY_INTERNER =  Interners.newWeakInterner();
-
-  private SkyKeyInterner() {
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index 2f75f40..1a93420 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -49,7 +49,7 @@
 import java.util.concurrent.atomic.AtomicReference;
 
 abstract class ArtifactFunctionTestCase {
-  protected static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  protected static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, "OWNER");
   protected static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
 
   protected Predicate<PathFragment> allowedMissingInputsPredicate = Predicates.alwaysFalse();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 2218684..9ddfcb5 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -88,7 +88,7 @@
  */
 public abstract class TimestampBuilderTestCase extends FoundationTestCase {
 
-  private static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  private static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, "OWNER");
   protected static final ActionLookupValue.ActionLookupKey ALL_OWNER =
       new SingletonActionLookupKey();
   protected static final Predicate<Action> ALWAYS_EXECUTE_FILTER = Predicates.alwaysTrue();
diff --git a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
index 8179d13..ab17456 100644
--- a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
@@ -29,7 +29,7 @@
 @RunWith(JUnit4.class)
 public class CyclesReporterTest {
 
-  private static final SkyKey DUMMY_KEY = new SkyKey(SkyFunctionName.create("func"), "key");
+  private static final SkyKey DUMMY_KEY = SkyKey.create(SkyFunctionName.create("func"), "key");
 
   @Test
   public void nullEventHandler() {
diff --git a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
index 3e15000..4b04614 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
@@ -49,7 +49,7 @@
 
   private void runTestFromException(boolean isDirectlyTransient, boolean isTransitivelyTransient) {
     Exception exception = new IOException("ehhhhh");
-    SkyKey causeOfException = new SkyKey(SkyFunctionName.create("CAUSE"), 1234);
+    SkyKey causeOfException = SkyKey.create(SkyFunctionName.create("CAUSE"), 1234);
     DummySkyFunctionException dummyException =
         new DummySkyFunctionException(exception, isDirectlyTransient, /*isCatastrophic=*/ false);
 
@@ -87,9 +87,10 @@
 
   @Test
   public void testFromCycle() {
-    CycleInfo cycle = new CycleInfo(
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("PATH"), 1234)),
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("CYCLE"), 4321)));
+    CycleInfo cycle =
+        new CycleInfo(
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("PATH"), 1234)),
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
 
     ErrorInfo errorInfo = ErrorInfo.fromCycle(cycle);
 
@@ -102,13 +103,14 @@
 
   @Test
   public void testFromChildErrors() {
-    CycleInfo cycle = new CycleInfo(
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("PATH"), 1234)),
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("CYCLE"), 4321)));
+    CycleInfo cycle =
+        new CycleInfo(
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("PATH"), 1234)),
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
     ErrorInfo cycleErrorInfo = ErrorInfo.fromCycle(cycle);
 
     Exception exception1 = new IOException("ehhhhh");
-    SkyKey causeOfException1 = new SkyKey(SkyFunctionName.create("CAUSE1"), 1234);
+    SkyKey causeOfException1 = SkyKey.create(SkyFunctionName.create("CAUSE1"), 1234);
     DummySkyFunctionException dummyException1 =
         new DummySkyFunctionException(exception1, /*isTransient=*/ true, /*isCatastrophic=*/ false);
     ErrorInfo exceptionErrorInfo1 = ErrorInfo.fromException(
@@ -117,14 +119,14 @@
 
     // N.B this ErrorInfo will be catastrophic.
     Exception exception2 = new IOException("blahhhhh");
-    SkyKey causeOfException2 = new SkyKey(SkyFunctionName.create("CAUSE2"), 5678);
+    SkyKey causeOfException2 = SkyKey.create(SkyFunctionName.create("CAUSE2"), 5678);
     DummySkyFunctionException dummyException2 =
         new DummySkyFunctionException(exception2, /*isTransient=*/ false, /*isCatastrophic=*/ true);
     ErrorInfo exceptionErrorInfo2 = ErrorInfo.fromException(
         new ReifiedSkyFunctionException(dummyException2, causeOfException2),
         /*isTransitivelyTransient=*/ false);
 
-    SkyKey currentKey = new SkyKey(SkyFunctionName.create("CURRENT"), 9876);
+    SkyKey currentKey = SkyKey.create(SkyFunctionName.create("CURRENT"), 9876);
 
     ErrorInfo errorInfo = ErrorInfo.fromChildErrors(
         currentKey, ImmutableList.of(cycleErrorInfo, exceptionErrorInfo1, exceptionErrorInfo2));
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
index 68e3046..c10277f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -72,7 +72,7 @@
   }
 
   protected SkyKey key(String name) {
-    return new SkyKey(SKY_FUNCTION_NAME, name);
+    return SkyKey.create(SKY_FUNCTION_NAME, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
index 70dbe80..76759af 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -157,7 +157,7 @@
   }
 
   public static SkyKey skyKey(String key) {
-    return new SkyKey(NODE_TYPE, key);
+    return SkyKey.create(NODE_TYPE, key);
   }
 
   /**
@@ -260,7 +260,7 @@
   public static SkyKey[] toSkyKeys(String... names) {
     SkyKey[] result = new SkyKey[names.length];
     for (int i = 0; i < names.length; i++) {
-      result[i] = new SkyKey(GraphTester.NODE_TYPE, names[i]);
+      result[i] = SkyKey.create(GraphTester.NODE_TYPE, names[i]);
     }
     return result;
   }
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 1298c48..4170c54 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -54,7 +54,7 @@
       NestedSetBuilder.<TaggedEvents>emptySet(Order.STABLE_ORDER);
 
   private static SkyKey key(String name) {
-    return new SkyKey(NODE_TYPE, name);
+    return SkyKey.create(NODE_TYPE, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 2fcd1a9..27ca052 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -145,7 +145,7 @@
   }
 
   protected static SkyKey toSkyKey(String name) {
-    return new SkyKey(NODE_TYPE, name);
+    return SkyKey.create(NODE_TYPE, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index 172efd5..41d9cdc 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -1434,7 +1434,7 @@
     class ParentFunction implements SkyFunction {
       @Override
       public SkyValue compute(SkyKey skyKey, Environment env) {
-        SkyValue dep = env.getValue(new SkyKey(childType, "billy the kid"));
+        SkyValue dep = env.getValue(SkyKey.create(childType, "billy the kid"));
         if (dep == null) {
           return null;
         }
@@ -1451,7 +1451,7 @@
         skyFunctions, false);
 
     try {
-      evaluator.eval(ImmutableList.of(new SkyKey(parentType, "octodad")));
+      evaluator.eval(ImmutableList.of(SkyKey.create(parentType, "octodad")));
       fail();
     } catch (RuntimeException e) {
       assertEquals("I WANT A PONY!!!", e.getCause().getMessage());
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
index 4c2d9c6f..7c5e476 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
@@ -99,13 +99,14 @@
     for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
       Example example = new Example();
       for (int j = 0; j < numElements; j++) {
-        REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, j)));
+        REVERSE_DEPS_UTIL.addReverseDeps(
+            example, Collections.singleton(SkyKey.create(NODE_TYPE, j)));
       }
       // Not a big test but at least check that it does not blow up.
       assertThat(REVERSE_DEPS_UTIL.toString(example)).isNotEmpty();
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
+        REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.dataToConsolidate).isNull();
@@ -119,12 +120,12 @@
       Example example = new Example();
       List<SkyKey> toAdd = new ArrayList<>();
       for (int j = 0; j < numElements; j++) {
-        toAdd.add(new SkyKey(NODE_TYPE, j));
+        toAdd.add(SkyKey.create(NODE_TYPE, j));
       }
       REVERSE_DEPS_UTIL.addReverseDeps(example, toAdd);
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
+        REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.dataToConsolidate).isNull();
@@ -135,10 +136,10 @@
   public void testDuplicateCheckOnGetReverseDeps() {
     Example example = new Example();
     for (int i = 0; i < numElements; i++) {
-      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, i)));
+      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
     }
     // Should only fail when we call getReverseDeps().
-    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, 0)));
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0)));
     try {
       REVERSE_DEPS_UTIL.getReverseDeps(example);
       assertThat(numElements).isEqualTo(0);
@@ -149,7 +150,7 @@
   @Test
   public void doubleAddThenRemove() {
     Example example = new Example();
-    SkyKey key = new SkyKey(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 0);
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
     // Should only fail when we call getReverseDeps().
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -164,8 +165,8 @@
   @Test
   public void doubleAddThenRemoveCheckedOnSize() {
     Example example = new Example();
-    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
-    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 1);
     REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     // Should only fail when we reach the limit.
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -181,8 +182,8 @@
   @Test
   public void addRemoveAdd() {
     Example example = new Example();
-    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
-    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 1);
     REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     REVERSE_DEPS_UTIL.removeReverseDep(example, key);
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -193,12 +194,12 @@
   public void testMaybeCheck() {
     Example example = new Example();
     for (int i = 0; i < numElements; i++) {
-      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, i)));
+      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
       // This should always succeed, since the next element is still not present.
-      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, new SkyKey(NODE_TYPE, i + 1));
+      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1));
     }
     try {
-      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, new SkyKey(NODE_TYPE, 0));
+      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0));
       // Should only fail if empty or above the checking threshold.
       assertThat(numElements == 0 || numElements >= ReverseDepsUtilImpl.MAYBE_CHECK_THRESHOLD)
           .isTrue();
diff --git a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
index 8f7b247..0e22db3 100644
--- a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
@@ -36,7 +36,7 @@
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(0);
 
     // When a SkyKey is constructed with that HashCodeSpy as its argument,
-    SkyKey originalKey = new SkyKey(SkyFunctionName.create("TEMP"), hashCodeSpy);
+    SkyKey originalKey = SkyKey.create(SkyFunctionName.create("TEMP"), hashCodeSpy);
 
     // Then the HashCodeSpy reports that its hashcode method was called once.
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(1);