add bloom filter to Context (#3350)

* This is the bloom filter based context improvement authored by @lukesandberg

1 files changed, 50 insertions, 20 deletions

diff --git a/context/src/main/java/io/grpc/Context.java b/context/src/main/java/io/grpc/Context.java
index 8375fb6c6..5280f407e 100644
--- a/context/src/main/java/io/grpc/Context.java
+++ b/context/src/main/java/io/grpc/Context.java
@@ -23,6 +23,7 @@ import java.util.concurrent.ScheduledExecutorService;
 import java.util.concurrent.ScheduledFuture;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.TimeoutException;
+import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 import java.util.logging.Level;
 import java.util.logging.Logger;
@@ -96,7 +97,7 @@ public class Context {
 
   private static final Logger log = Logger.getLogger(Context.class.getName());
 
-  private static final Object[][] EMPTY_ENTRIES = new Object[0][2];
+  private static final Object[] EMPTY_ENTRIES = new Object[0];
 
   private static final Key<Deadline> DEADLINE_KEY = new Key<Deadline>("deadline");
 
@@ -179,7 +180,12 @@ public class Context {
   }
 
   private final Context parent;
-  private final Object[][] keyValueEntries;
+  // A 64 bit bloom filter of all the Key.bloomFilterMask values in this Context and all the parents
+  // this will help us detect failed lookups faster.  In fact if there are fewer than 64 key objects
+  // this will be perfect (though we don't currently take advantage of that fact).
+  private final long keyBloomFilter;
+  // Alternating Key, Object entries
+  private final Object[] keyValueEntries;
   private final boolean cascadesCancellation;
   private ArrayList<ExecutableListener> listeners;
   private CancellationListener parentListener = new ParentListener();
@@ -191,7 +197,8 @@ public class Context {
   private Context(Context parent) {
     this.parent = parent;
     // Not inheriting cancellation implies not inheriting a deadline too.
-    keyValueEntries = new Object[][]{{DEADLINE_KEY, null}};
+    keyValueEntries = new Object[] {DEADLINE_KEY, null};
+    keyBloomFilter = computeFilter(parent, keyValueEntries);
     cascadesCancellation = false;
     canBeCancelled = false;
   }
@@ -200,9 +207,10 @@ public class Context {
    * Construct a context that cannot be cancelled but will cascade cancellation from its parent if
    * it is cancellable.
    */
-  private Context(Context parent, Object[][] keyValueEntries) {
+  private Context(Context parent, Object[] keyValueEntries) {
     this.parent = parent;
     this.keyValueEntries = keyValueEntries;
+    keyBloomFilter = computeFilter(parent, keyValueEntries);
     cascadesCancellation = true;
     canBeCancelled = this.parent != null && this.parent.canBeCancelled;
   }
@@ -211,13 +219,22 @@ public class Context {
    * Construct a context that can be cancelled and will cascade cancellation from its parent if
    * it is cancellable.
    */
-  private Context(Context parent, Object[][] keyValueEntries, boolean isCancellable) {
+  private Context(Context parent, Object[] keyValueEntries, boolean isCancellable) {
     this.parent = parent;
     this.keyValueEntries = keyValueEntries;
+    keyBloomFilter = computeFilter(parent, keyValueEntries);
     cascadesCancellation = true;
     canBeCancelled = isCancellable;
   }
 
+  private static long computeFilter(Context parent, Object[] keyValueEntries) {
+    long filter = parent != null ? parent.keyBloomFilter : 0;
+    for (int i = 0; i < keyValueEntries.length; i += 2) {
+      filter |= ((Key<?>) keyValueEntries[i]).bloomFilterMask;
+    }
+    return filter;
+  }
+
   /**
    * Create a new context which is independently cancellable and also cascades cancellation from
    * its parent. Callers <em>must</em> ensure that either {@link
@@ -323,7 +340,7 @@ public class Context {
    *
    */
   public <V> Context withValue(Key<V> k1, V v1) {
-    return new Context(this, new Object[][]{{k1, v1}});
+    return new Context(this, new Object[] {k1, v1});
   }
 
   /**
@@ -331,7 +348,7 @@ public class Context {
    * from its parent.
    */
   public <V1, V2> Context withValues(Key<V1> k1, V1 v1, Key<V2> k2, V2 v2) {
-    return new Context(this, new Object[][]{{k1, v1}, {k2, v2}});
+    return new Context(this, new Object[] {k1, v1, k2, v2});
   }
 
   /**
@@ -339,7 +356,7 @@ public class Context {
    * from its parent.
    */
   public <V1, V2, V3> Context withValues(Key<V1> k1, V1 v1, Key<V2> k2, V2 v2, Key<V3> k3, V3 v3) {
-    return new Context(this, new Object[][]{{k1, v1}, {k2, v2}, {k3, v3}});
+    return new Context(this, new Object[] {k1, v1, k2, v2, k3, v3});
   }
 
   /**
@@ -348,7 +365,7 @@ public class Context {
    */
   public <V1, V2, V3, V4> Context withValues(Key<V1> k1, V1 v1, Key<V2> k2, V2 v2,
       Key<V3> k3, V3 v3, Key<V4> k4, V4 v4) {
-    return new Context(this, new Object[][]{{k1, v1}, {k2, v2}, {k3, v3}, {k4, v4}});
+    return new Context(this, new Object[] {k1, v1, k2, v2, k3, v3, k4, v4});
   }
 
   /**
@@ -650,15 +667,26 @@ public class Context {
    * Lookup the value for a key in the context inheritance chain.
    */
   private Object lookup(Key<?> key) {
-    for (int i = 0; i < keyValueEntries.length; i++) {
-      if (key.equals(keyValueEntries[i][0])) {
-        return keyValueEntries[i][1];
-      }
-    }
-    if (parent == null) {
+    if ((key.bloomFilterMask & keyBloomFilter) == 0) {
       return null;
     }
-    return parent.lookup(key);
+    Object[] entries = keyValueEntries;
+    Context current = this;
+    while (true) {
+      // entries in the table are alternating key value pairs where the even numbered slots are the
+      // key objects
+      for (int i = 0; i < entries.length; i += 2) {
+        // Key objects have identity semantics, compare using ==
+        if (key == entries[i]) {
+          return entries[i + 1];
+        }
+      }
+      current = current.parent;
+      if (current == null) {
+        return null;
+      }
+      entries = current.keyValueEntries;
+    }
   }
 
   /**
@@ -678,11 +706,11 @@ public class Context {
      * If the parent deadline is before the given deadline there is no need to install the value
      * or listen for its expiration as the parent context will already be listening for it.
      */
-    private static Object[][] deriveDeadline(Context parent, Deadline deadline) {
+    private static Object[] deriveDeadline(Context parent, Deadline deadline) {
       Deadline parentDeadline = DEADLINE_KEY.get(parent);
       return parentDeadline == null || deadline.isBefore(parentDeadline)
-          ? new Object[][]{{ DEADLINE_KEY, deadline}} :
-          EMPTY_ENTRIES;
+          ? new Object[] {DEADLINE_KEY, deadline}
+          : EMPTY_ENTRIES;
     }
 
     /**
@@ -828,7 +856,8 @@ public class Context {
    * Key for indexing values stored in a context.
    */
   public static final class Key<T> {
-
+    private static final AtomicInteger keyCounter = new AtomicInteger();
+    private final long bloomFilterMask;
     private final String name;
     private final T defaultValue;
 
@@ -839,6 +868,7 @@ public class Context {
     Key(String name, T defaultValue) {
       this.name = checkNotNull(name, "name");
       this.defaultValue = defaultValue;
+      this.bloomFilterMask = 1 << (keyCounter.getAndIncrement() & 63);
     }
 
     /**