This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-lang.git
The following commit(s) were added to refs/heads/master by this push:
new 1aef13126 Memoizer: default caches the first failure forever, has no
size bound or eviction, and runs the user computation inside the
ConcurrentHashMap bin lock (blocking unrelated keys, deadlocking reentrant use)
(f011).
1aef13126 is described below
commit 1aef131265a6b2c8a5ded4301dd92468c7d826c5
Author: Gary Gregory <[email protected]>
AuthorDate: Sat Sep 5 08:46:31 2026 -0400
Memoizer: default caches the first failure forever, has no size bound or
eviction, and runs the user computation inside the ConcurrentHashMap bin
lock (blocking unrelated keys, deadlocking reentrant use) (f011).
---
src/changes/changes.xml | 4 +-
.../apache/commons/lang3/concurrent/Memoizer.java | 39 +++-
.../lang3/concurrent/MemoizerCacheTest.java | 227 +++++++++++++++++++++
3 files changed, 260 insertions(+), 10 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 38bccebe6..77bbd68b2 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -259,7 +259,9 @@ java.lang.NullPointerException: Cannot invoke
<action type="fix" dev="ggregory" due-to="Gary
Gregory">LocaleUtils static caches no longer grows on invalid input to
LocaleUtils.countriesByLanguage(String) (f007).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">ExtendedMessageFormat.applyPattern() is quadratic: full
pattern.toCharArray() per token (f008).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">WordUtils.wrap(wrapLongWords=false, the 2-arg default) copies the
entire remaining string every iteration. (f009).</action>
- <action type="fix" dev="ggregory" due-to="Gary
Gregory">FastDateParser.parse throws undeclared IllegalArgumentException,
NullPointerException, and IllegalStateException on crafted date strings.
(f010).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">FastDateParser.parse throws undeclared IllegalArgumentException,
NullPointerException, and IllegalStateException on crafted date strings
(f010).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">Memoizer: default caches the first failure forever, has no size bound
or eviction, and runs the user computation inside the ConcurrentHashMap bin
lock (blocking unrelated keys, deadlocking reentrant use) (f011).</action>
+
<!-- ADD -->
<action type="add" dev="ggregory" due-to="Gary
Gregory">Add JavaVersion.JAVA_27.</action>
<action type="add" dev="ggregory" due-to="Gary
Gregory">Add SystemUtils.IS_JAVA_27.</action>
diff --git a/src/main/java/org/apache/commons/lang3/concurrent/Memoizer.java
b/src/main/java/org/apache/commons/lang3/concurrent/Memoizer.java
index 1862b62b4..c167311d5 100644
--- a/src/main/java/org/apache/commons/lang3/concurrent/Memoizer.java
+++ b/src/main/java/org/apache/commons/lang3/concurrent/Memoizer.java
@@ -21,6 +21,7 @@
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Future;
+import java.util.concurrent.FutureTask;
import java.util.function.Function;
import org.apache.commons.lang3.exception.ExceptionUtils;
@@ -30,10 +31,12 @@
* results for the calculation will be cached for future requests.
*
* <p>
- * This is not a fully functional cache, there is no way of limiting or
removing results once they have been generated.
- * However, it is possible to get the implementation to regenerate the result
for a given parameter, if an error was
- * thrown during the previous calculation, by setting the option during the
construction of the class. If this is not
- * set the class will return the cached exception.
+ * This is not a fully functional cache: it is unbounded, and there is no way
of limiting or removing results once they
+ * have been generated. In particular, note the exception-caching default:
unless the {@code recalculate} constructor
+ * option is set to {@code true}, the <em>first</em> exception thrown by a
calculation for a given parameter is cached
+ * and rethrown for every future call with that parameter for the lifetime of
this instance - a single transient
+ * failure permanently poisons that key. Set {@code recalculate} to {@code
true} to retry failed calculations on
+ * subsequent calls instead.
* </p>
* <p>
* Thanks go to Brian Goetz, Tim Peierls and the members of JCP JSR-166 Expert
Group for coming up with the
@@ -47,7 +50,7 @@
public class Memoizer<I, O> implements Computable<I, O> {
private final ConcurrentMap<I, Future<O>> cache = new
ConcurrentHashMap<>();
- private final Function<? super I, ? extends Future<O>> mappingFunction;
+ private final Function<? super I, FutureTask<O>> mappingFunction;
private final boolean recalculate;
/**
@@ -74,7 +77,7 @@ public Memoizer(final Computable<I, O> computable) {
*/
public Memoizer(final Computable<I, O> computable, final boolean
recalculate) {
this.recalculate = recalculate;
- this.mappingFunction = k -> FutureTasks.run(() ->
computable.compute(k));
+ this.mappingFunction = k -> new FutureTask<>(() ->
computable.compute(k));
}
/**
@@ -103,7 +106,7 @@ public Memoizer(final Function<I, O> function) {
*/
public Memoizer(final Function<I, O> function, final boolean recalculate)
{
this.recalculate = recalculate;
- this.mappingFunction = k -> FutureTasks.run(() -> function.apply(k));
+ this.mappingFunction = k -> new FutureTask<>(() -> function.apply(k));
}
/**
@@ -111,9 +114,16 @@ public Memoizer(final Function<I, O> function, final
boolean recalculate) {
*
* <p>
* This cache will also cache exceptions that occur during the computation
if the {@code recalculate} parameter in the
- * constructor was set to {@code false}, or not set. Otherwise, if an
exception happened on the previous calculation,
+ * constructor was set to {@code false}, or not set: the first exception
thrown for a given argument is rethrown for
+ * every future call with that argument. Otherwise, if an exception
happened on the previous calculation,
* the method will attempt again to generate a value.
* </p>
+ * <p>
+ * The calculation for a given argument runs at most once per cached entry
and executes <em>outside</em> any internal
+ * lock of the backing map (the pattern published in <em>Java Concurrency
in Practice</em>): a slow calculation for
+ * one key does not block calls for unrelated keys, and a calculation may
itself use this Memoizer without
+ * deadlocking. Concurrent callers for the same argument wait on the same
{@link Future}.
+ * </p>
*
* @param arg The argument for the calculation
* @return The result of the calculation
@@ -122,7 +132,18 @@ public Memoizer(final Function<I, O> function, final
boolean recalculate) {
@Override
public O compute(final I arg) throws InterruptedException {
while (true) {
- final Future<O> future = cache.computeIfAbsent(arg,
mappingFunction);
+ Future<O> future = cache.get(arg);
+ if (future == null) {
+ final FutureTask<O> futureTask = mappingFunction.apply(arg);
+ future = cache.putIfAbsent(arg, futureTask);
+ if (future == null) {
+ // This thread won the race to install the task: run the
user computation here,
+ // outside the ConcurrentHashMap's internal locks. Losing
threads (and later
+ // callers) block on futureTask.get() instead of on a map
bin lock.
+ future = futureTask;
+ futureTask.run();
+ }
+ }
try {
return future.get();
} catch (final CancellationException e) {
diff --git
a/src/test/java/org/apache/commons/lang3/concurrent/MemoizerCacheTest.java
b/src/test/java/org/apache/commons/lang3/concurrent/MemoizerCacheTest.java
new file mode 100644
index 000000000..767541887
--- /dev/null
+++ b/src/test/java/org/apache/commons/lang3/concurrent/MemoizerCacheTest.java
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.lang3.concurrent;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.function.Function;
+
+import org.apache.commons.lang3.AbstractLangTest;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests failure retention, cache retention, and computation lock scope.
+ */
+class MemoizerCacheTest extends AbstractLangTest {
+
+ private static final int TIMEOUT_SECONDS = 10;
+
+ private static void await(final CountDownLatch latch) {
+ try {
+ assertTrue(latch.await(TIMEOUT_SECONDS, TimeUnit.SECONDS), "Timed
out waiting for a test worker");
+ } catch (final InterruptedException e) {
+ Thread.currentThread().interrupt();
+ throw new AssertionError(e);
+ }
+ }
+
+ private static <I, O> Memoizer<I, O> newMemoizer(final boolean
useFunction, final Function<I, O> function) {
+ return useFunction ? new Memoizer<>(function) : new
Memoizer<>((Computable<I, O>) function::apply);
+ }
+
+ private static <I, O> Memoizer<I, O> newMemoizer(final boolean
useFunction, final Function<I, O> function, final boolean recalculate) {
+ return useFunction ? new Memoizer<>(function, recalculate) : new
Memoizer<>((Computable<I, O>) function::apply, recalculate);
+ }
+
+ private static void shutdown(final ExecutorService executor) throws
InterruptedException {
+ executor.shutdownNow();
+ assertTrue(executor.awaitTermination(TIMEOUT_SECONDS,
TimeUnit.SECONDS), "Test workers did not terminate");
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testConcurrentCallsForSameKeyComputeOnce(final boolean useFunction)
throws Exception {
+ final int callerCount = 8;
+ final AtomicInteger calls = new AtomicInteger();
+ final CountDownLatch ready = new CountDownLatch(callerCount);
+ final CountDownLatch start = new CountDownLatch(1);
+ final CountDownLatch entered = new CountDownLatch(1);
+ final CountDownLatch release = new CountDownLatch(1);
+ final Object result = new Object();
+ final Memoizer<String, Object> memoizer = newMemoizer(useFunction, key
-> {
+ calls.incrementAndGet();
+ entered.countDown();
+ await(release);
+ return result;
+ });
+ final ExecutorService executor =
Executors.newFixedThreadPool(callerCount);
+ try {
+ final List<Future<Object>> futures = new ArrayList<>();
+ for (int i = 0; i < callerCount; i++) {
+ futures.add(executor.submit(() -> {
+ ready.countDown();
+ await(start);
+ return memoizer.compute("key");
+ }));
+ }
+ await(ready);
+ start.countDown();
+ await(entered);
+ release.countDown();
+ for (final Future<Object> future : futures) {
+ assertSame(result, future.get(TIMEOUT_SECONDS,
TimeUnit.SECONDS));
+ }
+ assertSame(result, memoizer.compute("key"));
+ assertEquals(1, calls.get());
+ } finally {
+ start.countDown();
+ release.countDown();
+ shutdown(executor);
+ }
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testDefaultCachesFirstFailure(final boolean useFunction) throws
Exception {
+ final AtomicInteger calls = new AtomicInteger();
+ final IllegalStateException failure = new
IllegalStateException("Transient failure");
+ final Memoizer<String, String> memoizer = newMemoizer(useFunction, key
-> {
+ if (calls.incrementAndGet() == 1) {
+ throw failure;
+ }
+ return key;
+ });
+ for (int i = 0; i < 3; i++) {
+ assertSame(failure, assertThrows(IllegalStateException.class, ()
-> memoizer.compute("failed")));
+ }
+ assertEquals(1, calls.get(), "A transient failure remains cached by
default");
+ assertEquals("other", memoizer.compute("other"));
+ assertSame(failure, assertThrows(IllegalStateException.class, () ->
memoizer.compute("failed")));
+ assertEquals(2, calls.get());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testDistinctKeysRetainCachedResults(final boolean useFunction) throws
Exception {
+ final int keyCount = 1024;
+ final AtomicInteger calls = new AtomicInteger();
+ final Memoizer<Integer, Object> memoizer = newMemoizer(useFunction,
key -> {
+ calls.incrementAndGet();
+ return new Object();
+ });
+ final List<Object> results = new ArrayList<>();
+ for (int i = 0; i < keyCount; i++) {
+ results.add(memoizer.compute(i));
+ }
+ // Characterize retention over a bounded sample without exhausting
memory or inspecting the backing map.
+ for (int i = 0; i < keyCount; i++) {
+ assertSame(results.get(i), memoizer.compute(i));
+ }
+ assertEquals(keyCount, calls.get(), "Adding distinct keys must not
evict earlier results");
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testRecalculateRetriesFailureOnNextCall(final boolean useFunction)
throws Exception {
+ final AtomicInteger calls = new AtomicInteger();
+ final IllegalStateException failure = new
IllegalStateException("Transient failure");
+ final Object result = new Object();
+ final Memoizer<String, Object> memoizer = newMemoizer(useFunction, key
-> {
+ if (calls.incrementAndGet() == 1) {
+ throw failure;
+ }
+ return result;
+ }, true);
+ assertSame(failure, assertThrows(IllegalStateException.class, () ->
memoizer.compute("key")));
+ assertEquals(1, calls.get(), "The failing call must propagate its
failure without retrying internally");
+ assertSame(result, memoizer.compute("key"));
+ assertSame(result, memoizer.compute("key"));
+ assertEquals(2, calls.get());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testReentrantComputationForDistinctCollidingKey(final boolean
useFunction) throws Exception {
+ assertEquals("Aa".hashCode(), "BB".hashCode());
+ final AtomicInteger calls = new AtomicInteger();
+ final AtomicReference<Memoizer<String, String>> reference = new
AtomicReference<>();
+ final Memoizer<String, String> memoizer = newMemoizer(useFunction, key
-> {
+ calls.incrementAndGet();
+ if ("Aa".equals(key)) {
+ try {
+ return reference.get().compute("BB");
+ } catch (final InterruptedException e) {
+ Thread.currentThread().interrupt();
+ throw new AssertionError(e);
+ }
+ }
+ return key;
+ });
+ reference.set(memoizer);
+ final ExecutorService executor = Executors.newSingleThreadExecutor();
+ try {
+ assertEquals("BB", executor.submit(() ->
memoizer.compute("Aa")).get(TIMEOUT_SECONDS, TimeUnit.SECONDS));
+ assertEquals("BB", memoizer.compute("Aa"));
+ assertEquals("BB", memoizer.compute("BB"));
+ assertEquals(2, calls.get());
+ } finally {
+ shutdown(executor);
+ }
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSlowComputationDoesNotBlockDistinctCollidingKey(final boolean
useFunction) throws Exception {
+ assertEquals("Aa".hashCode(), "BB".hashCode());
+ final CountDownLatch entered = new CountDownLatch(1);
+ final CountDownLatch release = new CountDownLatch(1);
+ final Memoizer<String, String> memoizer = newMemoizer(useFunction, key
-> {
+ if ("Aa".equals(key)) {
+ entered.countDown();
+ await(release);
+ }
+ return key;
+ });
+ final ExecutorService executor = Executors.newFixedThreadPool(2);
+ try {
+ final Future<String> slow = executor.submit(() ->
memoizer.compute("Aa"));
+ await(entered);
+ final Future<String> other = executor.submit(() ->
memoizer.compute("BB"));
+ assertEquals("BB", other.get(TIMEOUT_SECONDS, TimeUnit.SECONDS));
+ assertEquals(1L, release.getCount(), "The colliding key must
complete while the first computation is blocked");
+ release.countDown();
+ assertEquals("Aa", slow.get(TIMEOUT_SECONDS, TimeUnit.SECONDS));
+ } finally {
+ release.countDown();
+ shutdown(executor);
+ }
+ }
+}
