This is an automated email from the ASF dual-hosted git repository.
henrib pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-jexl.git
The following commit(s) were added to refs/heads/master by this push:
new b3689079 JEXL-414: added performance tests; - added another JexlCache
implementation for testing; - only kept one implementation as default;
b3689079 is described below
commit b36890794bcbef32acc6b11899e5848f10905609
Author: Henri Biestro <hbies...@cloudera.com>
AuthorDate: Thu Nov 23 16:39:02 2023 +0100
JEXL-414: added performance tests;
- added another JexlCache implementation for testing;
- only kept one implementation as default;
---
RELEASE-NOTES.txt | 1 +
pom.xml | 1 +
src/changes/changes.xml | 3 +
.../java/org/apache/commons/jexl3/JexlBuilder.java | 3 +-
.../java/org/apache/commons/jexl3/JexlCache.java | 24 +--
.../apache/commons/jexl3/internal/SoftCache.java | 144 ++++++-----------
.../apache/commons/jexl3/CachePerformanceTest.java | 179 +++++++++++++++++++++
.../java/org/apache/commons/jexl3/CacheTest.java | 3 +-
.../org/apache/commons/jexl3}/ConcurrentCache.java | 15 +-
.../java/org/apache/commons/jexl3/SpreadCache.java | 147 +++++++++++++++++
10 files changed, 397 insertions(+), 123 deletions(-)
diff --git a/RELEASE-NOTES.txt b/RELEASE-NOTES.txt
index 1d173c6f..ef675164 100644
--- a/RELEASE-NOTES.txt
+++ b/RELEASE-NOTES.txt
@@ -38,6 +38,7 @@ New Features in 3.3.1:
Bugs Fixed in 3.3.1:
===================
* JEXL-415: Incorrect template eval result
+* JEXL-414: SoftCache may suffer from race conditions
* JEXL-412: Ambiguous syntax between namespace function call and map
object definition.
* JEXL-410: JexlFeatures: ctor does not enable all features
* JEXL-409: Disable LEXICAL should disable LEXICAL_SHADE
diff --git a/pom.xml b/pom.xml
index 04f3cf3b..482ba00b 100644
--- a/pom.xml
+++ b/pom.xml
@@ -126,6 +126,7 @@
<groupId>com.googlecode.concurrentlinkedhashmap</groupId>
<artifactId>concurrentlinkedhashmap-lru</artifactId>
<version>1.4.2</version>
+ <scope>test</scope>
</dependency>
</dependencies>
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 80fc9107..48c734d0 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -45,6 +45,9 @@
<action dev="henrib" type="fix" issue="JEXL-415" due-to="Xu
Pengcheng" >
Incorrect template eval result.
</action>
+ <action dev="henrib" type="fix" issue="JEXL-414" due-to="Holger
Sunke" >
+ SoftCache may suffer from race conditions
+ </action>
<action dev="henrib" type="fix" issue="JEXL-412" due-to="Xu
Pengcheng" >
Ambiguous syntax between namespace function call and map
object definition.
</action>
diff --git a/src/main/java/org/apache/commons/jexl3/JexlBuilder.java
b/src/main/java/org/apache/commons/jexl3/JexlBuilder.java
index b67640d7..babc6655 100644
--- a/src/main/java/org/apache/commons/jexl3/JexlBuilder.java
+++ b/src/main/java/org/apache/commons/jexl3/JexlBuilder.java
@@ -24,6 +24,7 @@ import java.util.Map;
import java.util.function.IntFunction;
import org.apache.commons.jexl3.internal.Engine;
+import org.apache.commons.jexl3.internal.SoftCache;
import org.apache.commons.jexl3.introspection.JexlPermissions;
import org.apache.commons.jexl3.introspection.JexlSandbox;
import org.apache.commons.jexl3.introspection.JexlUberspect;
@@ -134,7 +135,7 @@ public class JexlBuilder {
private int cache = -1;
/** The cache class factory. */
- private IntFunction<JexlCache<?,?>> cacheFactory =
JexlCache.createConcurrent();
+ private IntFunction<JexlCache<?,?>> cacheFactory = SoftCache::new;
/** The stack overflow limit. */
private int stackOverflow = Integer.MAX_VALUE;
diff --git a/src/main/java/org/apache/commons/jexl3/JexlCache.java
b/src/main/java/org/apache/commons/jexl3/JexlCache.java
index c7776e02..1b13c04f 100644
--- a/src/main/java/org/apache/commons/jexl3/JexlCache.java
+++ b/src/main/java/org/apache/commons/jexl3/JexlCache.java
@@ -21,7 +21,6 @@ import java.util.Collections;
import java.util.Map;
import java.util.function.IntFunction;
-import org.apache.commons.jexl3.internal.ConcurrentCache;
import org.apache.commons.jexl3.internal.SoftCache;
/**
@@ -31,7 +30,14 @@ import org.apache.commons.jexl3.internal.SoftCache;
*/
public interface JexlCache<K, V> {
/**
- * Returns the cache size.
+ * Returns the cache capacity, the maximum number of elements it can contain.
+ *
+ * @return the cache capacity
+ */
+ int capacity();
+
+ /**
+ * Returns the cache size, the actual number of elements it contains.
*
* @return the cache size
*/
@@ -69,18 +75,4 @@ public interface JexlCache<K, V> {
default Collection<Map.Entry<K, V>> entries() {
return Collections.emptyList();
}
-
- /**
- * @return a synchronized cache factory amenable to low concurrency usage
- */
- static IntFunction<JexlCache<?,?>> createSynchronized() {
- return SoftCache::new;
- }
-
- /**
- * @return a concurrent cache factory amenable to high concurrency usage
- */
- static IntFunction<JexlCache<?,?>> createConcurrent() {
- return ConcurrentCache::new;
- }
}
diff --git a/src/main/java/org/apache/commons/jexl3/internal/SoftCache.java
b/src/main/java/org/apache/commons/jexl3/internal/SoftCache.java
index 24db61ac..06d45988 100644
--- a/src/main/java/org/apache/commons/jexl3/internal/SoftCache.java
+++ b/src/main/java/org/apache/commons/jexl3/internal/SoftCache.java
@@ -17,12 +17,9 @@
package org.apache.commons.jexl3.internal;
import java.lang.ref.SoftReference;
-import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.List;
import java.util.Map;
-import java.util.Set;
import org.apache.commons.jexl3.JexlCache;
@@ -34,8 +31,13 @@ import org.apache.commons.jexl3.JexlCache;
* </p>
* <p>
* Note that the underlying map is a synchronized LinkedHashMap.
- * The reason is that a get() will reorder elements (the LRU queue) and thus
- * needs to be guarded to be thread-safe.
+ * The reason is that a get() will reorder elements (the LRU queue) and thus
+ * needs synchronization to ensure thread-safety.
+ * </p>
+ * <p>
+ * When caching JEXL scripts or expressions, one should expect the execution
cost of those
+ * to be several fold the cost of the cache handling; after some (synthetic)
tests, measures indicate
+ * cache handling is a marginal latency factor.
* </p>
*
* @param <K> the cache key entry type
@@ -45,11 +47,11 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
/**
* The default cache load factor.
*/
- private static final float LOAD_FACTOR = 0.75f;
+ protected static final float LOAD_FACTOR = 0.75f;
/**
- * The cache size.
+ * The cache capacity.
*/
- protected final int size;
+ protected final int capacity;
/**
* The soft reference to the cache map.
*/
@@ -61,21 +63,29 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
* @param theSize the cache size
*/
public SoftCache(final int theSize) {
- size = theSize;
+ capacity = theSize;
}
/**
- * Returns the cache size.
- *
- * @return the cache size
+ * {@inheritDoc}
+ */
+ @Override
+ public int capacity() {
+ return capacity;
+ }
+
+ /**
+ * {@inheritDoc}
*/
@Override
public int size() {
- return size;
+ final SoftReference<Map<K, V>> ref = reference;
+ final Map<K, V> map = ref != null ? ref.get() : null;
+ return map != null ? map.size() : 0;
}
/**
- * Clears the cache.
+ * {@inheritDoc}
*/
@Override
public void clear() {
@@ -90,10 +100,7 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
}
/**
- * Gets a value from cache.
- *
- * @param key the cache entry key
- * @return the cache entry value
+ * {@inheritDoc}
*/
@Override
public V get(final K key) {
@@ -103,10 +110,7 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
}
/**
- * Puts a value in cache.
- *
- * @param key the cache entry key
- * @param script the cache entry value
+ * {@inheritDoc}
*/
@Override
public V put(final K key, final V script) {
@@ -117,7 +121,7 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
ref = reference;
map = ref != null ? ref.get() : null;
if (map == null) {
- map = createMap(size);
+ map = createMap(capacity);
reference = new SoftReference<>(map);
}
}
@@ -126,94 +130,50 @@ public class SoftCache<K, V> implements JexlCache<K, V> {
}
/**
- * Produces the cache entry set.
- * <p>
- * For testing only, perform deep copy of cache entries
- *
- * @return the cache entry list
+ * {@inheritDoc}
*/
@Override
public Collection<Map.Entry<K, V>> entries() {
final SoftReference<Map<K, V>> ref = reference;
final Map<K, V> map = ref != null ? ref.get() : null;
- if (map == null) {
- return Collections.emptyList();
- }
- synchronized(map) {
- final Set<Map.Entry<K, V>> set = map.entrySet();
- final List<Map.Entry<K, V>> entries = new ArrayList<>(set.size());
- for (final Map.Entry<K, V> e : set) {
- entries.add(new SoftCacheEntry<>(e));
- }
- return entries;
- }
+ return map == null? Collections.emptyList() : map.entrySet();
}
/**
- * Creates the cache store.
+ * Creates a cache store.
*
- * @param <K> the key type
- * @param <V> the value type
+ * @param <KT> the key type
+ * @param <VT> the value type
* @param cacheSize the cache size, must be > 0
* @return a Map usable as a cache bounded to the given size
*/
- public <K, V> Map<K, V> createMap(final int cacheSize) {
- return Collections.synchronizedMap(
- new java.util.LinkedHashMap<K, V>(cacheSize, LOAD_FACTOR, true) {
- /**
- * Serial version UID.
- */
- private static final long serialVersionUID = 1L;
-
- @Override
- protected boolean removeEldestEntry(final Map.Entry<K, V>
eldest) {
- return super.size() > cacheSize;
- }
- }
- );
+ protected <KT, VT> Map<KT, VT> createMap(final int cacheSize) {
+ return createSynchronizedLinkedHashMap(cacheSize);
}
-}
-
-/**
- * A soft cache entry.
- *
- * @param <K> key type
- * @param <V> value type
- */
-final class SoftCacheEntry<K, V> implements Map.Entry<K, V> {
- /**
- * The entry key.
- */
- private final K key;
- /**
- * The entry value.
- */
- private final V value;
/**
- * Creates an entry clone.
- *
- * @param e the entry to clone
+ * Creates a synchronized LinkedHashMap.
+ * @param capacity the map capacity
+ * @return the map instance
+ * @param <K> key type
+ * @param <V> value type
*/
- SoftCacheEntry(final Map.Entry<K, V> e) {
- key = e.getKey();
- value = e.getValue();
+ public static <K, V> Map<K, V> createSynchronizedLinkedHashMap(final int
capacity) {
+ return Collections.synchronizedMap(new java.util.LinkedHashMap<K,
V>(capacity, LOAD_FACTOR, true) {
+ /**
+ * Serial version UID.
+ */
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
+ return super.size() > capacity;
+ }
+ });
}
+}
- @Override
- public K getKey() {
- return key;
- }
- @Override
- public V getValue() {
- return value;
- }
- @Override
- public V setValue(final V v) {
- throw new UnsupportedOperationException("Not supported.");
- }
-}
diff --git a/src/test/java/org/apache/commons/jexl3/CachePerformanceTest.java
b/src/test/java/org/apache/commons/jexl3/CachePerformanceTest.java
new file mode 100644
index 00000000..4906f988
--- /dev/null
+++ b/src/test/java/org/apache/commons/jexl3/CachePerformanceTest.java
@@ -0,0 +1,179 @@
+/*
+ * 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
+ *
+ * http://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.jexl3;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.text.DecimalFormat;
+import java.text.NumberFormat;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+
+/**
+ * Testing JEXL caching performance.
+ * <p>The core idea is to create and evaluate scripts concurrently by a number
(THREADS) of threads.
+ * The scripts source are number constants to keep the actual cost of
evaluation to a minimum but we still want
+ * these to occur; the cost of creating the evaluation environment, etc is not
negligible and there is no use in
+ * trying to cache/get scripts if its not to evaluate them.
+ * Each script is evaluated a number of times (HIT) in a tight loop to try and
elicit good hit ratios but the number
+ * of potential scripts (SCRIPTS) is greater than the cache capacity (CACHED)
to force eviction.</p>
+ * <p>
+ * The results vary a bit with parameters but the wall-clock times of the
tests shows the worst case as 135% of
+ * best (the former being the default cache, the latter being the Google
based cache).
+ * This indicates that the basic caching mechanism will likely not be a
performance bottleneck in normal usage.
+ * </p>
+ */
+public class CachePerformanceTest {
+ /** Number of test loops. */
+ private static final int LOOPS = 10;//0;
+ /** Number of different scripts. */
+ private static final int SCRIPTS = 800;//0;
+ /** Cache capacity. */
+ private static final int CACHED = 500;//0;
+ /** Number of times each script is evaluated. */
+ private static final int HIT = 5;
+ /** Number of concurrent threads. */
+ private static final int THREADS = 8;
+ /** Teh logger. */
+ Log LOGGER = LogFactory.getLog(getClass());
+
+ public static class Timer {
+ long begin;
+ long end;
+
+ void start() {
+ begin = System.currentTimeMillis();
+ }
+ void stop() {
+ end = System.currentTimeMillis();
+ }
+
+ String elapse() {
+ long delta = end - begin;
+ NumberFormat fmt = new DecimalFormat("#.###");
+ return fmt.format(delta / 1000.d);
+ }
+ }
+
+ @Test
+ public void testSpread() throws Exception {
+ final JexlBuilder builder = new
JexlBuilder().cacheFactory(SpreadCache::new).cache(CACHED);
+ final JexlEngine jexl = builder.create();
+ runTest("testSpread", jexl);
+ }
+
+ @Test
+ public void testConcurrent() throws Exception {
+ final JexlBuilder builder = new
JexlBuilder().cacheFactory(ConcurrentCache::new).cache(CACHED);
+ final JexlEngine jexl = builder.create();
+ runTest("testConcurrent", jexl);
+ }
+
+ @Test
+ public void testSynchronized() throws Exception {
+ final JexlBuilder builder = new JexlBuilder().cache(CACHED);
+ final JexlEngine jexl = builder.create();
+ runTest("testSynchronized", jexl);
+ }
+
+ /**
+ * A task randomly chooses to run scripts (CACHED * HIT times).
+ * Tasks will be run
+ */
+ static class Task implements Callable<Integer> {
+ private final JexlEngine jexl;
+ private final BlockingQueue<?> queue;
+
+ Task(JexlEngine jexl, BlockingQueue<?> queue) {
+ this.jexl = jexl;
+ this.queue = queue;
+ }
+
+ @Override
+ public Integer call() {
+ int count = 0;
+ Object arg;
+ try {
+ while ((arg = queue.take()) != Task.class) {
+ final Random rnd = new Random((int) arg);
+ for(int l = 0; l < LOOPS; ++l) {
+ for (int c = 0; c < CACHED; ++c) {
+ final int ctl = rnd.nextInt(SCRIPTS);
+ for (int r = 0; r < HIT; ++r) {
+ JexlScript script = jexl.createScript(Integer.toString(ctl) +
" + 42 - 42");
+ Object result = script.execute(null);
+ assert ((Number) result).intValue() == ctl;
+ count += 1;
+ }
+ }
+ }
+ }
+ return count;
+ } catch (InterruptedException e) {
+ throw new RuntimeException(e);
+ }
+ }
+ }
+
+ /**
+ * Launches the tasks in parallel.
+ * @param jexl the jexl engine
+ * @throws Exception if something goes wrong
+ */
+ protected void runTest(String name, JexlEngine jexl) throws Exception {
+ ExecutorService exec = Executors.newFixedThreadPool(THREADS);
+ BlockingQueue<Object> queue = new ArrayBlockingQueue<>(THREADS);
+ List<Future<Integer>> results = new ArrayList<>(THREADS);
+ // seed the cache
+ for(int i = 0; i < CACHED; ++i) {
+ JexlScript script = jexl.createScript(Integer.toString(i));
+ Assert.assertNotNull(script);
+ }
+ // create a set of tasks ready to go
+ for(int t = 0; t < THREADS; ++t) {
+ results.add(exec.submit(new Task(jexl, queue)));
+ }
+ Timer tt = new Timer();
+ tt.start();
+ // run each with its own sequence of random seeded by t
+ for(int t = 0; t < THREADS; ++t) {
+ queue.put(t);
+ }
+ // send the poison pill
+ for(int t = 0; t < THREADS; ++t) {
+ queue.put(Task.class);
+ }
+ int total = 0;
+ for(Future<Integer> result : results) {
+ total += result.get();
+ }
+ exec.shutdown();
+ tt.stop();
+ Assert.assertEquals(total, LOOPS * CACHED * THREADS * HIT);
+ LOGGER.info(name+ " : " + tt.elapse());
+ }
+}
diff --git a/src/test/java/org/apache/commons/jexl3/CacheTest.java
b/src/test/java/org/apache/commons/jexl3/CacheTest.java
index 4ae8ddd4..f3618739 100644
--- a/src/test/java/org/apache/commons/jexl3/CacheTest.java
+++ b/src/test/java/org/apache/commons/jexl3/CacheTest.java
@@ -145,7 +145,7 @@ public class CacheTest extends JexlTestCase {
/**
* A set of classes that define different getter/setter methods for the
same properties.
* The goal is to verify that the cached JexlPropertyGet / JexlPropertySet
in the AST Nodes are indeed
- * volatile and do not generate errors even when multiple threads
concurently hammer them.
+ * volatile and do not generate errors even when multiple threads
concurrently hammer them.
*/
public static class Cached {
public static String COMPUTE(final int arg) {
@@ -527,7 +527,6 @@ public class CacheTest extends JexlTestCase {
private static final JexlEngine jexlCache = new JexlBuilder()
.cache(1024)
- .cacheFactory(JexlCache.createSynchronized())
.debug(true)
.strict(true)
.create();
diff --git
a/src/main/java/org/apache/commons/jexl3/internal/ConcurrentCache.java
b/src/test/java/org/apache/commons/jexl3/ConcurrentCache.java
similarity index 77%
rename from src/main/java/org/apache/commons/jexl3/internal/ConcurrentCache.java
rename to src/test/java/org/apache/commons/jexl3/ConcurrentCache.java
index 03c5648e..6806d87c 100644
--- a/src/main/java/org/apache/commons/jexl3/internal/ConcurrentCache.java
+++ b/src/test/java/org/apache/commons/jexl3/ConcurrentCache.java
@@ -14,14 +14,12 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package org.apache.commons.jexl3.internal;
+package org.apache.commons.jexl3;
-import java.lang.ref.SoftReference;
-import java.util.Collection;
-import java.util.Collections;
import java.util.Map;
import com.googlecode.concurrentlinkedhashmap.ConcurrentLinkedHashMap;
+import org.apache.commons.jexl3.internal.SoftCache;
/**
* A cache whose underlying map is a ConcurrentLinkedHashMap.
@@ -40,14 +38,7 @@ public class ConcurrentCache<K, V> extends SoftCache<K, V> {
}
@Override
- public Collection<Map.Entry<K, V>> entries() {
- final SoftReference<Map<K, V>> ref = reference;
- final Map<K, V> map = ref != null ? ref.get() : null;
- return map == null? Collections.emptyList() : map.entrySet();
- }
-
- @Override
- public <K, V> Map<K, V> createMap(final int cacheSize) {
+ protected <K, V> Map<K, V> createMap(final int cacheSize) {
return new ConcurrentLinkedHashMap.Builder<K, V>()
.concurrencyLevel(Runtime.getRuntime().availableProcessors())
.maximumWeightedCapacity(cacheSize)
diff --git a/src/test/java/org/apache/commons/jexl3/SpreadCache.java
b/src/test/java/org/apache/commons/jexl3/SpreadCache.java
new file mode 100644
index 00000000..59400644
--- /dev/null
+++ b/src/test/java/org/apache/commons/jexl3/SpreadCache.java
@@ -0,0 +1,147 @@
+/*
+ * 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
+ *
+ * http://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.jexl3;
+
+import org.apache.commons.jexl3.internal.SoftCache;
+
+import java.util.AbstractMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Creates a cache using an array of synchronized LinkedHashMap as backing
store to spread contention.
+ * <p>Just meant as a contention reducing mechanism for cache tests.</p>
+ *
+ * @param <K> the cached element"e;s key
+ * @param <V> the cached element"e;s value
+ * @return the cache instance
+ */
+public class SpreadCache<K, V> extends SoftCache<K, V> {
+
+ /**
+ * Creates a new instance of a Spread cache.
+ *
+ * @param theSize the cache size
+ */
+ public SpreadCache(int theSize) {
+ super(theSize);
+ }
+
+ @Override
+ public <K, V> Map<K, V> createMap(final int cacheSize) {
+ return new SpreadMap<>(cacheSize);
+ }
+}
+
+/**
+ * A map backed by an array of LinkedHashMap.
+ * <p>This implementation is really tailored to serve the cache methods and
no-other. It foregoes being efficient
+ * for methods that do not serve this purpose.</p>
+ * <p>We spread the map capacity over a number of synchronized sub-maps, the
number being the number of
+ * available processors. This is meant to spread the contention at the cost of
a relaxed LRU.</p>
+ *
+ * @param <K>
+ * @param <V>
+ */
+class SpreadMap<K, V> extends AbstractMap<K, V> {
+ /**
+ * The sub-maps array.
+ */
+ private final Map<K, V>[] maps;
+
+ /**
+ * The unique simple constructor.
+ *
+ * @param capacity the overall map capacity
+ */
+ SpreadMap(int capacity) {
+ int spread = closestPowerOf2(Runtime.getRuntime().availableProcessors());
+ maps = new Map[spread];
+ final int mapCapacity = (capacity + spread + 1) / spread;
+ for (int m = 0; m < spread; ++m) {
+ maps[m] = SoftCache.createSynchronizedLinkedHashMap(mapCapacity);
+ }
+ }
+
+ /**
+ * Returns a power of two for the given target capacity.
+ *
+ * @param cap capacity
+ * @return the smallest power of 2 greater or equal to argument
+ */
+ private static int closestPowerOf2(int cap) {
+ return cap > 1 ? Integer.highestOneBit(cap - 1) << 1 : 1;
+ }
+
+ /**
+ * Gets the map storing a given key.
+ *
+ * @param key the key
+ * @return the map
+ */
+ private final Map<K, V> getMap(Object key) {
+ int h = key.hashCode();
+ h ^= (h >>> 16);
+ // length is a power of 2, length - 1 is the mask of its modulo:
+ // length = 4, length - 1 = 3 = 11b : x % 4 <=> x & 3
+ return maps[h & (maps.length - 1)];
+ }
+
+ @Override
+ public V get(Object key) {
+ return getMap(key).get(key);
+ }
+
+ @Override
+ public V put(final K key, final V value) {
+ return getMap(key).put(key, value);
+ }
+
+ @Override
+ public V remove(final Object key) {
+ return getMap(key).remove(key);
+ }
+
+ @Override
+ public void clear() {
+ for (int m = 0; m < maps.length; ++m) {
+ maps[m].clear();
+ }
+ }
+
+ @Override
+ public int size() {
+ int size = 0;
+ for (int m = 0; m < maps.length; ++m) {
+ size += maps[m].size();
+ }
+ return size;
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ final Set<Map.Entry<K, V>> entries = new LinkedHashSet<>(size());
+ for (Map<K, V> map : maps) {
+ synchronized (map) {
+ entries.addAll(map.entrySet());
+ }
+ }
+ return entries;
+ }
+}
\ No newline at end of file
