changeset 56791:35bac2745d04

8231592: Clarify that ConcurrentHashMap compute methods mapping functions execute at most once Reviewed-by: martin
author dl
date Fri, 01 Nov 2019 09:04:04 -0700
parents ab4db38ed085
children ec954ef6caf1
files src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java test/jdk/java/util/concurrent/tck/ConcurrentHashMapTest.java test/jdk/java/util/concurrent/tck/ConcurrentSkipListMapTest.java test/jdk/java/util/concurrent/tck/HashMapTest.java test/jdk/java/util/concurrent/tck/HashtableTest.java test/jdk/java/util/concurrent/tck/JSR166TestCase.java test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java test/jdk/java/util/concurrent/tck/MapImplementation.java test/jdk/java/util/concurrent/tck/MapTest.java test/jdk/java/util/concurrent/tck/TreeMapTest.java
diffstat 10 files changed, 109 insertions(+), 30 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java	Fri Nov 01 09:04:04 2019 -0700
@@ -1667,11 +1667,14 @@
      * If the specified key is not already associated with a value,
      * attempts to compute its value using the given mapping function
      * and enters it into this map unless {@code null}.  The entire
-     * method invocation is performed atomically, so the function is
-     * applied at most once per key.  Some attempted update operations
-     * on this map by other threads may be blocked while computation
-     * is in progress, so the computation should be short and simple,
-     * and must not attempt to update any other mappings of this map.
+     * method invocation is performed atomically.  The supplied
+     * function is invoked exactly once per invocation of this method
+     * if the key is absent, else not at all.  Some attempted update
+     * operations on this map by other threads may be blocked while
+     * computation is in progress, so the computation should be short
+     * and simple.
+     *
+     * <p>The mapping function must not modify this map during computation.
      *
      * @param key key with which the specified value is to be associated
      * @param mappingFunction the function to compute a value
@@ -1778,10 +1781,13 @@
      * If the value for the specified key is present, attempts to
      * compute a new mapping given the key and its current mapped
      * value.  The entire method invocation is performed atomically.
-     * Some attempted update operations on this map by other threads
-     * may be blocked while computation is in progress, so the
-     * computation should be short and simple, and must not attempt to
-     * update any other mappings of this map.
+     * The supplied function is invoked exactly once per invocation of
+     * this method if the key is present, else not at all.  Some
+     * attempted update operations on this map by other threads may be
+     * blocked while computation is in progress, so the computation
+     * should be short and simple.
+     *
+     * <p>The remapping function must not modify this map during computation.
      *
      * @param key key with which a value may be associated
      * @param remappingFunction the function to compute a value
@@ -1870,10 +1876,12 @@
      * Attempts to compute a mapping for the specified key and its
      * current mapped value (or {@code null} if there is no current
      * mapping). The entire method invocation is performed atomically.
-     * Some attempted update operations on this map by other threads
-     * may be blocked while computation is in progress, so the
-     * computation should be short and simple, and must not attempt to
-     * update any other mappings of this Map.
+     * The supplied function is invoked exactly once per invocation of
+     * this method.  Some attempted update operations on this map by
+     * other threads may be blocked while computation is in progress,
+     * so the computation should be short and simple.
+     *
+     * <p>The remapping function must not modify this map during computation.
      *
      * @param key key with which the specified value is to be associated
      * @param remappingFunction the function to compute a value
--- a/test/jdk/java/util/concurrent/tck/ConcurrentHashMapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/ConcurrentHashMapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -55,8 +55,6 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return ConcurrentHashMap.class; }
             public Map emptyMap() { return new ConcurrentHashMap(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return true; }
             public boolean permitsNullKeys() { return false; }
             public boolean permitsNullValues() { return false; }
--- a/test/jdk/java/util/concurrent/tck/ConcurrentSkipListMapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/ConcurrentSkipListMapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -54,9 +54,8 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return ConcurrentSkipListMap.class; }
             public Map emptyMap() { return new ConcurrentSkipListMap(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return true; }
+            public boolean remappingFunctionCalledAtMostOnce() { return false; };
             public boolean permitsNullKeys() { return false; }
             public boolean permitsNullValues() { return false; }
             public boolean supportsSetValue() { return false; }
--- a/test/jdk/java/util/concurrent/tck/HashMapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/HashMapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -46,8 +46,6 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return HashMap.class; }
             public Map emptyMap() { return new HashMap(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return false; }
             public boolean permitsNullKeys() { return true; }
             public boolean permitsNullValues() { return true; }
--- a/test/jdk/java/util/concurrent/tck/HashtableTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/HashtableTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -44,8 +44,6 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return Hashtable.class; }
             public Map emptyMap() { return new Hashtable(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return true; }
             public boolean permitsNullKeys() { return false; }
             public boolean permitsNullValues() { return false; }
--- a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java	Fri Nov 01 09:04:04 2019 -0700
@@ -731,6 +731,13 @@
     /**
      * Returns a random element from given choices.
      */
+    <T> T chooseRandomly(List<T> choices) {
+        return choices.get(ThreadLocalRandom.current().nextInt(choices.size()));
+    }
+
+    /**
+     * Returns a random element from given choices.
+     */
     <T> T chooseRandomly(T... choices) {
         return choices[ThreadLocalRandom.current().nextInt(choices.length)];
     }
@@ -1799,7 +1806,7 @@
 
         public int await() {
             try {
-                return super.await(2 * LONG_DELAY_MS, MILLISECONDS);
+                return super.await(LONGER_DELAY_MS, MILLISECONDS);
             } catch (TimeoutException timedOut) {
                 throw new AssertionError("timed out");
             } catch (Exception fail) {
--- a/test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/LinkedHashMapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -46,8 +46,6 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return LinkedHashMap.class; }
             public Map emptyMap() { return new LinkedHashMap(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return false; }
             public boolean permitsNullKeys() { return true; }
             public boolean permitsNullValues() { return true; }
--- a/test/jdk/java/util/concurrent/tck/MapImplementation.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/MapImplementation.java	Fri Nov 01 09:04:04 2019 -0700
@@ -40,9 +40,15 @@
     public Class<?> klazz();
     /** Returns an empty map. */
     public Map emptyMap();
-    public Object makeKey(int i);
-    public Object makeValue(int i);
+
+    // General purpose implementations can use Integers for key and value
+    default Object makeKey(int i) { return i; }
+    default Object makeValue(int i) { return i; }
+    default int keyToInt(Object key) { return (Integer) key; }
+    default int valueToInt(Object value) { return (Integer) value; }
+
     public boolean isConcurrent();
+    default boolean remappingFunctionCalledAtMostOnce() { return true; };
     public boolean permitsNullKeys();
     public boolean permitsNullValues();
     public boolean supportsSetValue();
--- a/test/jdk/java/util/concurrent/tck/MapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/MapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -32,13 +32,17 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
-import junit.framework.Test;
-
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.concurrent.CompletableFuture;
 import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.function.BiFunction;
+
+import junit.framework.Test;
 
 /**
  * Contains tests applicable to all Map implementations.
@@ -227,6 +231,71 @@
         assertTrue(clone.isEmpty());
     }
 
+    /**
+     * Concurrent access by compute methods behaves as expected
+     */
+    public void testConcurrentAccess() throws Throwable {
+        final Map map = impl.emptyMap();
+        final long testDurationMillis = expensiveTests ? 1000 : 2;
+        final int nTasks = impl.isConcurrent()
+            ? ThreadLocalRandom.current().nextInt(1, 10)
+            : 1;
+        final AtomicBoolean done = new AtomicBoolean(false);
+        final boolean remappingFunctionCalledAtMostOnce
+            = impl.remappingFunctionCalledAtMostOnce();
+        final List<CompletableFuture> futures = new ArrayList<>();
+        final AtomicLong expectedSum = new AtomicLong(0);
+        final Action[] tasks = {
+            // repeatedly increment values using compute()
+            () -> {
+                long[] invocations = new long[2];
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                BiFunction<Object, Object, Object> incValue = (k, v) -> {
+                    invocations[1]++;
+                    int vi = (v == null) ? 1 : impl.valueToInt(v) + 1;
+                    return impl.makeValue(vi);
+                };
+                while (!done.getAcquire()) {
+                    invocations[0]++;
+                    Object key = impl.makeKey(3 * rnd.nextInt(10));
+                    map.compute(key, incValue);
+                }
+                if (remappingFunctionCalledAtMostOnce)
+                    assertEquals(invocations[0], invocations[1]);
+                expectedSum.getAndAdd(invocations[0]);
+            },
+            // repeatedly increment values using computeIfPresent()
+            () -> {
+                long[] invocations = new long[2];
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                BiFunction<Object, Object, Object> incValue = (k, v) -> {
+                    invocations[1]++;
+                    int vi = impl.valueToInt(v) + 1;
+                    return impl.makeValue(vi);
+                };
+                while (!done.getAcquire()) {
+                    Object key = impl.makeKey(3 * rnd.nextInt(10));
+                    if (map.computeIfPresent(key, incValue) != null)
+                        invocations[0]++;
+                }
+                if (remappingFunctionCalledAtMostOnce)
+                    assertEquals(invocations[0], invocations[1]);
+                expectedSum.getAndAdd(invocations[0]);
+            },
+        };
+        for (int i = nTasks; i--> 0; ) {
+            Action task = chooseRandomly(tasks);
+            futures.add(CompletableFuture.runAsync(checkedRunnable(task)));
+        }
+        Thread.sleep(testDurationMillis);
+        done.setRelease(true);
+        for (var future : futures)
+            checkTimedGet(future, null);
+
+        long sum = map.values().stream().mapToLong(x -> (int) x).sum();
+        assertEquals(expectedSum.get(), sum);
+    }
+
 //     public void testFailsIntentionallyForDebugging() {
 //         fail(impl.klazz().getSimpleName());
 //     }
--- a/test/jdk/java/util/concurrent/tck/TreeMapTest.java	Fri Nov 01 16:16:05 2019 +0100
+++ b/test/jdk/java/util/concurrent/tck/TreeMapTest.java	Fri Nov 01 09:04:04 2019 -0700
@@ -53,8 +53,6 @@
         class Implementation implements MapImplementation {
             public Class<?> klazz() { return TreeMap.class; }
             public Map emptyMap() { return new TreeMap(); }
-            public Object makeKey(int i) { return i; }
-            public Object makeValue(int i) { return i; }
             public boolean isConcurrent() { return false; }
             public boolean permitsNullKeys() { return false; }
             public boolean permitsNullValues() { return true; }