changeset 51396:3c3ff151c75e

8202422: value of 'sizeCtl' in ConcurrentHashMap varies with the constructor called Reviewed-by: martin, psandoz
author dl
date Mon, 25 Jun 2018 09:59:16 -0700
parents cb07f4b539fc
children 3a6d47df8239
files src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java
diffstat 2 files changed, 64 insertions(+), 23 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java	Mon Jun 25 11:33:11 2018 -0400
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java	Mon Jun 25 09:59:16 2018 -0700
@@ -702,12 +702,7 @@
      * See Hackers Delight, sec 3.2
      */
     private static final int tableSizeFor(int c) {
-        int n = c - 1;
-        n |= n >>> 1;
-        n |= n >>> 2;
-        n |= n >>> 4;
-        n |= n >>> 8;
-        n |= n >>> 16;
+        int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
     }
 
@@ -844,12 +839,7 @@
      * elements is negative
      */
     public ConcurrentHashMap(int initialCapacity) {
-        if (initialCapacity < 0)
-            throw new IllegalArgumentException();
-        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
-                   MAXIMUM_CAPACITY :
-                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
-        this.sizeCtl = cap;
+        this(initialCapacity, LOAD_FACTOR, 1);
     }
 
     /**
@@ -883,8 +873,8 @@
 
     /**
      * Creates a new, empty map with an initial table size based on
-     * the given number of elements ({@code initialCapacity}), table
-     * density ({@code loadFactor}), and number of concurrently
+     * the given number of elements ({@code initialCapacity}), initial
+     * table density ({@code loadFactor}), and number of concurrently
      * updating threads ({@code concurrencyLevel}).
      *
      * @param initialCapacity the initial capacity. The implementation
@@ -1473,13 +1463,9 @@
         if (size == 0L)
             sizeCtl = 0;
         else {
-            int n;
-            if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
-                n = MAXIMUM_CAPACITY;
-            else {
-                int sz = (int)size;
-                n = tableSizeFor(sz + (sz >>> 1) + 1);
-            }
+            long ts = (long)(1.0 + size / LOAD_FACTOR);
+            int n = (ts >= (long)MAXIMUM_CAPACITY) ?
+                MAXIMUM_CAPACITY : tableSizeFor((int)ts);
             @SuppressWarnings("unchecked")
             Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
             int mask = n - 1;
--- a/test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java	Mon Jun 25 11:33:11 2018 -0400
+++ b/test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java	Mon Jun 25 09:59:16 2018 -0700
@@ -45,15 +45,20 @@
 import java.io.ByteArrayOutputStream;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
+import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodHandles;
+import java.lang.invoke.MethodType;
 import java.lang.invoke.VarHandle;
+import java.util.List;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Supplier;
 
 @Test
 public class WhiteBox {
     final ThreadLocalRandom rnd = ThreadLocalRandom.current();
     final VarHandle TABLE, NEXTTABLE, SIZECTL;
+    final MethodHandle TABLE_SIZE_FOR;
 
     WhiteBox() throws ReflectiveOperationException {
         Class<?> mClass = ConcurrentHashMap.class;
@@ -65,11 +70,33 @@
         TABLE = lookup.findVarHandle(mClass, "table", nodeArrayClass);
         NEXTTABLE = lookup.findVarHandle(mClass, "nextTable", nodeArrayClass);
         SIZECTL = lookup.findVarHandle(mClass, "sizeCtl", int.class);
+        TABLE_SIZE_FOR = lookup.findStatic(
+                mClass, "tableSizeFor",
+                MethodType.methodType(int.class, int.class));
     }
 
     Object[] table(ConcurrentHashMap m) { return (Object[]) TABLE.getVolatile(m); }
     Object[] nextTable(ConcurrentHashMap m) { return (Object[]) NEXTTABLE.getVolatile(m); }
     int sizeCtl(ConcurrentHashMap m) { return (int) SIZECTL.getVolatile(m); }
+    int tableSizeFor(int n) {
+        try {
+            return (int) TABLE_SIZE_FOR.invoke(n);
+        } catch (Throwable t) { throw new AssertionError(t); }
+    }
+
+    List<Supplier<ConcurrentHashMap>> newConcurrentHashMapSuppliers(
+        int initialCapacity) {
+        return List.of(
+            () -> new ConcurrentHashMap(initialCapacity),
+            () -> new ConcurrentHashMap(initialCapacity, 0.75f),
+            () -> new ConcurrentHashMap(initialCapacity, 0.75f, 1));
+    }
+
+    ConcurrentHashMap newConcurrentHashMap(int initialCapacity) {
+        List<Supplier<ConcurrentHashMap>> suppliers
+            = newConcurrentHashMapSuppliers(initialCapacity);
+        return suppliers.get(rnd.nextInt(suppliers.size())).get();
+    }
 
     @Test
     public void defaultConstructor() {
@@ -83,7 +110,7 @@
     public void shouldNotResizeWhenInitialCapacityProvided() {
         int initialCapacity = rnd.nextInt(1, 100);
         Object[] initialTable = null;
-        ConcurrentHashMap m = new ConcurrentHashMap(initialCapacity);
+        ConcurrentHashMap m = newConcurrentHashMap(initialCapacity);
 
         // table is lazily initialized
         assertNull(table(m));
@@ -101,6 +128,34 @@
         assertEquals(initialTable.length, expectedInitialTableLength);
     }
 
+    @Test
+    public void constructorsShouldGiveSameInitialCapacity() {
+        int initialCapacity = rnd.nextInt(1, 256);
+        long distinctTableLengths
+            = newConcurrentHashMapSuppliers(initialCapacity).stream()
+            .map(Supplier::get)
+            .mapToInt(map -> { map.put(42, 42); return table(map).length; })
+            .distinct()
+            .count();
+        assertEquals(1L, distinctTableLengths);
+    }
+
+    @Test
+    public void testTableSizeFor() {
+        assertEquals(1, tableSizeFor(0));
+        assertEquals(1, tableSizeFor(1));
+        assertEquals(2, tableSizeFor(2));
+        assertEquals(4, tableSizeFor(3));
+        assertEquals(16, tableSizeFor(15));
+        assertEquals(16, tableSizeFor(16));
+        assertEquals(32, tableSizeFor(17));
+        int maxSize = 1 << 30;
+        assertEquals(maxSize, tableSizeFor(maxSize - 1));
+        assertEquals(maxSize, tableSizeFor(maxSize));
+        assertEquals(maxSize, tableSizeFor(maxSize + 1));
+        assertEquals(maxSize, tableSizeFor(Integer.MAX_VALUE));
+    }
+
     byte[] serialBytes(Object o) {
         try {
             ByteArrayOutputStream bos = new ByteArrayOutputStream();
@@ -132,7 +187,7 @@
     public void testSerialization() {
         assertInvariants(serialClone(new ConcurrentHashMap()));
 
-        ConcurrentHashMap m = new ConcurrentHashMap(rnd.nextInt(100));
+        ConcurrentHashMap m = newConcurrentHashMap(rnd.nextInt(100));
         m.put(1, 1);
         ConcurrentHashMap clone = serialClone(m);
         assertInvariants(clone);