[groovy] branch master updated: GROOVY-9060: Make the initial capacity of LinkedHashMap be power of 2 for better performance(closes #903)

[su...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

sunlan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/groovy.git


The following commit(s) were added to refs/heads/master by this push:
     new 5c8f086  GROOVY-9060: Make the initial capacity of LinkedHashMap be power of 2 for better performance(closes #903)
5c8f086 is described below

commit 5c8f08633a320be8836a249d577a549fe5966b76
Author: Daniel Sun <su...@apache.org>
AuthorDate: Mon Apr 1 00:15:38 2019 +0800

    GROOVY-9060: Make the initial capacity of LinkedHashMap be power of 2 for better performance(closes #903)
---
 .../org/codehaus/groovy/runtime/InvokerHelper.java | 23 ++++++++++++++----
 .../codehaus/groovy/runtime/InvokerHelperTest.java | 28 ++++++++++++++++++++--
 2 files changed, 45 insertions(+), 6 deletions(-)

diff --git a/src/main/java/org/codehaus/groovy/runtime/InvokerHelper.java b/src/main/java/org/codehaus/groovy/runtime/InvokerHelper.java
index 64a1ffc..5d5aedf 100644
--- a/src/main/java/org/codehaus/groovy/runtime/InvokerHelper.java
+++ b/src/main/java/org/codehaus/groovy/runtime/InvokerHelper.java
@@ -70,6 +70,8 @@ import java.util.Set;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 
+import static java.lang.Math.max;
+
 /**
  * A static helper class to make bytecode generation easier and act as a facade over the Invoker
  */
@@ -396,10 +398,23 @@ public class InvokerHelper {
         return answer;
     }
 
+    /**
+     * According to the initial entry count, calculate the initial capacity of hash map, which is power of 2
+     * (SEE https://stackoverflow.com/questions/8352378/why-does-hashmap-require-that-the-initial-capacity-be-a-power-of-two)
+     *
+     * @param initialEntryCnt the initial entry count
+     * @return the initial capacity
+     */
+    public static int initialCapacity(int initialEntryCnt) {
+        if (0 == initialEntryCnt) return 16;
+
+        return Integer.highestOneBit(initialEntryCnt) << 1;
+    }
+
     public static Map createMap(Object[] values) {
-        Map answer = new LinkedHashMap(values.length / 2);
-        int i = 0;
-        while (i < values.length - 1) {
+        Map answer = new LinkedHashMap(initialCapacity(values.length / 2));
+
+        for (int i = 0, n = values.length; i < n - 1; ) {
             if ((values[i] instanceof SpreadMap) && (values[i + 1] instanceof Map)) {
                 Map smap = (Map) values[i + 1];
                 for (Object e : smap.entrySet()) {
@@ -726,7 +741,7 @@ public class InvokerHelper {
     }
 
     private static int sizeLeft(int maxSize, StringBuilder buffer) {
-        return maxSize == -1 ? maxSize : Math.max(0, maxSize - buffer.length());
+        return maxSize == -1 ? maxSize : max(0, maxSize - buffer.length());
     }
 
     private static String formatCollection(Collection collection, boolean verbose, int maxSize, boolean safe) {
diff --git a/src/test/org/codehaus/groovy/runtime/InvokerHelperTest.java b/src/test/org/codehaus/groovy/runtime/InvokerHelperTest.java
index c234553..d80ae14 100644
--- a/src/test/org/codehaus/groovy/runtime/InvokerHelperTest.java
+++ b/src/test/org/codehaus/groovy/runtime/InvokerHelperTest.java
@@ -18,14 +18,17 @@
  */
 package org.codehaus.groovy.runtime;
 
-import java.util.HashMap;
-
 import groovy.lang.Binding;
 import groovy.lang.GroovyClassLoader;
 import groovy.lang.GroovyCodeSource;
 import groovy.lang.Script;
 import junit.framework.TestCase;
 
+import java.util.HashMap;
+
+import static org.codehaus.groovy.runtime.InvokerHelper.initialCapacity;
+
+
 public class InvokerHelperTest extends TestCase {
     private HashMap bindingVariables;
 
@@ -51,4 +54,25 @@ public class InvokerHelperTest extends TestCase {
         script.run();
         assertEquals(controlValue, script.getProperty(controlProperty));
     }
+
+    public void testInitialCapacity() {
+        assertEquals(16, initialCapacity(0));
+        assertEquals(2, initialCapacity(1));
+        assertEquals(4, initialCapacity(2));
+        assertEquals(4, initialCapacity(3));
+        assertEquals(8, initialCapacity(4));
+        assertEquals(8, initialCapacity(5));
+        assertEquals(8, initialCapacity(6));
+        assertEquals(8, initialCapacity(7));
+        assertEquals(16, initialCapacity(8));
+        assertEquals(16, initialCapacity(9));
+        assertEquals(16, initialCapacity(10));
+        assertEquals(16, initialCapacity(11));
+        assertEquals(16, initialCapacity(12));
+        assertEquals(16, initialCapacity(13));
+        assertEquals(16, initialCapacity(14));
+        assertEquals(16, initialCapacity(15));
+        assertEquals(32, initialCapacity(16));
+        assertEquals(32, initialCapacity(17));
+    }
 }