[GitHub] [druid] gianm commented on a change in pull request #9278: Speed up joins on indexed tables with string keys

[GitBox <gi...@apache.org>]

gianm commented on a change in pull request #9278: Speed up joins on indexed tables with string keys
URL: https://github.com/apache/druid/pull/9278#discussion_r374411013
 
 

 ##########
 File path: processing/src/main/java/org/apache/druid/segment/join/table/IndexedTableJoinMatcher.java
 ##########
 @@ -308,4 +353,112 @@ public ValueType defaultType()
       return () -> IntIterators.EMPTY_ITERATOR;
     }
   }
+
+  @VisibleForTesting
+  static class LruLoadingHashMap<K, V> extends LinkedHashMap<K, V>
+  {
+    private final int maxSize;
+    private final Function<K, V> loader;
+
+    LruLoadingHashMap(int maxSize, Function<K, V> loader)
+    {
+      super(capacity(maxSize));
+      this.maxSize = maxSize;
+      this.loader = loader;
+    }
+
+    V getAndLoadIfAbsent(K key)
+    {
+      return computeIfAbsent(key, loader);
+    }
+
+    @Override
+    protected boolean removeEldestEntry(Map.Entry eldest)
+    {
+      return size() > maxSize;
+    }
+
+    private static int capacity(int expectedSize)
+    {
+      // This is the calculation used in JDK8 to resize when a putAll happens; it seems to be the most conservative
+      // calculation we can make. 0.75 is the default load factor.
+      return (int) ((float) expectedSize / 0.75F + 1.0F);
+    }
+  }
+
+  private interface Int2IntListMap
+  {
+    IntList getAndLoadIfAbsent(int key);
+  }
+
+  /**
+   * Lookup table for keys in the range from 0 to maxSize - 1
+   */
+  @VisibleForTesting
+  static class Int2IntListLookupTable implements Int2IntListMap
+  {
+    private final IntList[] lookup;
+    private final IntFunction<IntList> loader;
+
+    Int2IntListLookupTable(int maxSize, IntFunction<IntList> loader)
+    {
+      this.loader = loader;
+      this.lookup = new IntList[maxSize];
+      Arrays.fill(lookup, null);
 
 Review comment:
   I thought Java guaranteed that object arrays will start with all `null`s.

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org