Add memory-efficient map for storing nested set -> digest.

Instead of using ConcurrentHashMap, we use a dead-simple open addressed hash hable with a giant byte array with 16-byte slots. We then read or write fingerprints straight into and out of the array, obviating the need to generate intermediate garbage.

Locking mechanism is a read-write lock. This should be faster than full synchronisation for read-heavy loads.

RELNOTES: None
PiperOrigin-RevId: 184019301

1 files changed, 24 insertions, 33 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index b4d341143c..b48d4a2298 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -22,10 +22,11 @@ import java.util.concurrent.ConcurrentHashMap;
 
 /** Computes fingerprints for nested sets, reusing sub-computations from children. */
 public class NestedSetFingerprintCache {
-  private static final byte[] EMPTY_SET_BYTES = new byte[] {};
+  private static final int DIGEST_SIZE = 16;
+  private static final int EMPTY_SET_DIGEST = 104_395_303;
 
   /** Memoize the subresults. We have to have one cache per type of command item map function. */
-  private Map<CommandLineItem.MapFn<?>, Map<Object, byte[]>> mapFnToFingerprints = createMap();
+  private Map<CommandLineItem.MapFn<?>, DigestMap> mapFnToFingerprints = createMap();
 
   public <T> void addNestedSetToFingerprint(Fingerprint fingerprint, NestedSet<T> nestedSet) {
     addNestedSetToFingerprint(CommandLineItem.MapFn.DEFAULT, fingerprint, nestedSet);
@@ -33,12 +34,16 @@ public class NestedSetFingerprintCache {
 
   public <T> void addNestedSetToFingerprint(
       CommandLineItem.MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet) {
-    Map<Object, byte[]> fingerprints =
-        mapFnToFingerprints.computeIfAbsent(mapFn, k -> new ConcurrentHashMap<>());
+    // Only top-level nested sets can be empty, so we can bail here
+    if (nestedSet.isEmpty()) {
+      fingerprint.addInt(EMPTY_SET_DIGEST);
+      return;
+    }
+    DigestMap digestMap =
+        mapFnToFingerprints.computeIfAbsent(mapFn, k -> new DigestMap(DIGEST_SIZE, 1024));
     fingerprint.addInt(nestedSet.getOrder().ordinal());
     Object children = nestedSet.rawChildren();
-    byte[] bytes = getBytes(mapFn, fingerprints, children);
-    fingerprint.addBytes(bytes);
+    addToFingerprint(mapFn, fingerprint, digestMap, children);
   }
 
   public void clear() {
@@ -46,36 +51,22 @@ public class NestedSetFingerprintCache {
   }
 
   @SuppressWarnings("unchecked")
-  private <T> byte[] getBytes(
-      CommandLineItem.MapFn<? super T> mapFn, Map<Object, byte[]> fingerprints, Object children) {
-    byte[] bytes = fingerprints.get(children);
-    if (bytes == null) {
-      if (children instanceof Object[]) {
-        Fingerprint fingerprint = new Fingerprint();
+  private <T> void addToFingerprint(
+      CommandLineItem.MapFn<? super T> mapFn,
+      Fingerprint fingerprint,
+      DigestMap digestMap,
+      Object children) {
+    if (children instanceof Object[]) {
+      if (!digestMap.readDigest(children, fingerprint)) {
+        Fingerprint childrenFingerprint = new Fingerprint();
         for (Object child : (Object[]) children) {
-          if (child instanceof Object[]) {
-            fingerprint.addBytes(getBytes(mapFn, fingerprints, child));
-          } else {
-            addToFingerprint(mapFn, fingerprint, (T) child);
-          }
+          addToFingerprint(mapFn, childrenFingerprint, digestMap, child);
         }
-        bytes = fingerprint.digestAndReset();
-
-        // There is no point memoizing anything except the multi-item case,
-        // since the single-item case gets inlined into its parents anyway,
-        // and the empty set is a singleton
-        fingerprints.put(children, bytes);
-      } else if (children != NestedSet.EMPTY_CHILDREN) {
-        // Single item
-        Fingerprint fingerprint = new Fingerprint();
-        addToFingerprint(mapFn, fingerprint, (T) children);
-        bytes = fingerprint.digestAndReset();
-      } else {
-        // Empty nested set
-        bytes = EMPTY_SET_BYTES;
+        digestMap.insertAndReadDigest(children, childrenFingerprint, fingerprint);
       }
+    } else {
+      addToFingerprint(mapFn, fingerprint, (T) children);
     }
-    return bytes;
   }
 
   @VisibleForTesting
@@ -84,7 +75,7 @@ public class NestedSetFingerprintCache {
     fingerprint.addString(mapFn.expandToCommandLine(object));
   }
 
-  private static Map<CommandLineItem.MapFn<?>, Map<Object, byte[]>> createMap() {
+  private static Map<CommandLineItem.MapFn<?>, DigestMap> createMap() {
     return new ConcurrentHashMap<>();
   }
 }