Repository: groovy Updated Branches: refs/heads/master 4d3d0ed0f -> 10c6ef9cc
Implement a high performance cache and use it at some places Project: http://git-wip-us.apache.org/repos/asf/groovy/repo Commit: http://git-wip-us.apache.org/repos/asf/groovy/commit/10c6ef9c Tree: http://git-wip-us.apache.org/repos/asf/groovy/tree/10c6ef9c Diff: http://git-wip-us.apache.org/repos/asf/groovy/diff/10c6ef9c Branch: refs/heads/master Commit: 10c6ef9cc1ef59cbc358c01ff32e9afe50fcd02a Parents: 4d3d0ed Author: sunlan <[email protected]> Authored: Mon Mar 5 08:55:44 2018 +0800 Committer: sunlan <[email protected]> Committed: Mon Mar 5 08:55:44 2018 +0800 ---------------------------------------------------------------------- .../groovy/groovy/lang/GroovyClassLoader.java | 4 +- .../runtime/memoize/ConcurrentCommonCache.java | 5 - .../groovy/runtime/memoize/EvictableCache.java | 18 ++ .../runtime/memoize/StampedCommonCache.java | 269 +++++++++++++++++++ .../stc/StaticTypeCheckingSupport.java | 4 +- .../runtime/memoize/StampedCommonCacheTest.java | 235 ++++++++++++++++ .../macro/transform/MacroMethodsCache.java | 4 +- 7 files changed, 528 insertions(+), 11 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/main/groovy/groovy/lang/GroovyClassLoader.java ---------------------------------------------------------------------- diff --git a/src/main/groovy/groovy/lang/GroovyClassLoader.java b/src/main/groovy/groovy/lang/GroovyClassLoader.java index 07d946f..1beecfe 100644 --- a/src/main/groovy/groovy/lang/GroovyClassLoader.java +++ b/src/main/groovy/groovy/lang/GroovyClassLoader.java @@ -43,8 +43,8 @@ import org.codehaus.groovy.control.Phases; import org.codehaus.groovy.control.SourceUnit; import org.codehaus.groovy.runtime.IOGroovyMethods; import org.codehaus.groovy.runtime.InvokerHelper; -import org.codehaus.groovy.runtime.memoize.ConcurrentCommonCache; import org.codehaus.groovy.runtime.memoize.EvictableCache; +import org.codehaus.groovy.runtime.memoize.StampedCommonCache; import org.codehaus.groovy.runtime.memoize.UnlimitedConcurrentCache; import org.objectweb.asm.ClassVisitor; import org.objectweb.asm.ClassWriter; @@ -103,7 +103,7 @@ public class GroovyClassLoader extends URLClassLoader { * This cache contains mappings of file name to class. It is used * to bypass compilation. */ - protected final ConcurrentCommonCache<String, Class> sourceCache = new ConcurrentCommonCache<String, Class>(); + protected final StampedCommonCache<String, Class> sourceCache = new StampedCommonCache<String, Class>(); private final CompilerConfiguration config; private String sourceEncoding; http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/main/java/org/codehaus/groovy/runtime/memoize/ConcurrentCommonCache.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/codehaus/groovy/runtime/memoize/ConcurrentCommonCache.java b/src/main/java/org/codehaus/groovy/runtime/memoize/ConcurrentCommonCache.java index 27ee102..a6aa112 100644 --- a/src/main/java/org/codehaus/groovy/runtime/memoize/ConcurrentCommonCache.java +++ b/src/main/java/org/codehaus/groovy/runtime/memoize/ConcurrentCommonCache.java @@ -237,9 +237,4 @@ public class ConcurrentCommonCache<K, V> implements EvictableCache<K, V>, ValueC readLock.unlock(); } } - - @FunctionalInterface - public interface Action<K, V, R> { - R doWith(CommonCache<K, V> commonCache); - } } http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/main/java/org/codehaus/groovy/runtime/memoize/EvictableCache.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/codehaus/groovy/runtime/memoize/EvictableCache.java b/src/main/java/org/codehaus/groovy/runtime/memoize/EvictableCache.java index 1cd45a8..6621f99 100644 --- a/src/main/java/org/codehaus/groovy/runtime/memoize/EvictableCache.java +++ b/src/main/java/org/codehaus/groovy/runtime/memoize/EvictableCache.java @@ -82,4 +82,22 @@ public interface EvictableCache<K, V> extends MemoizeCache<K, V> { */ FIFO } + + /** + * Represents the action to deal with the cache + * + * @param <K> key type + * @param <V> value type + * @param <R> result type + * + * @since 3.0.0 + */ + @FunctionalInterface + interface Action<K, V, R> { + /** + * Deal with the cache + * @param evictableCache + */ + R doWith(EvictableCache<K, V> evictableCache); + } } http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/main/java/org/codehaus/groovy/runtime/memoize/StampedCommonCache.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/codehaus/groovy/runtime/memoize/StampedCommonCache.java b/src/main/java/org/codehaus/groovy/runtime/memoize/StampedCommonCache.java new file mode 100644 index 0000000..50c7706 --- /dev/null +++ b/src/main/java/org/codehaus/groovy/runtime/memoize/StampedCommonCache.java @@ -0,0 +1,269 @@ +/* + * 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.codehaus.groovy.runtime.memoize; + +import javax.annotation.concurrent.ThreadSafe; +import java.io.Serializable; +import java.util.Collection; +import java.util.Map; +import java.util.Set; +import java.util.concurrent.locks.StampedLock; + +/** + * Represents a simple key-value cache, which is thread safe and backed by a {@link Map} instance. + * StampedCommonCache has better performance than {@link ConcurrentCommonCache}, + * but it is not reentrant, in other words, <b>it may cause deadlock</b> if {@link #getAndPut(K, ValueProvider)} OR {@link #getAndPut(K, ValueProvider, boolean)} is called recursively: + * readlock -> upgrade to writelock -> readlock(fails to get and wait forever) + * + * + * @param <K> type of the keys + * @param <V> type of the values + * @since 3.0.0 + */ +@ThreadSafe +public class StampedCommonCache<K, V> implements EvictableCache<K, V>, ValueConvertable<V, Object>, Serializable { + private static final long serialVersionUID = -7352338549333024936L; + + private final StampedLock sl = new StampedLock(); + private final CommonCache<K, V> commonCache; + + /** + * Constructs a cache with unlimited size + */ + public StampedCommonCache() { + commonCache = new CommonCache<K, V>(); + } + + /** + * Constructs a cache with limited size + * + * @param initialCapacity initial capacity of the cache + * @param maxSize max size of the cache + * @param evictionStrategy LRU or FIFO, see {@link EvictionStrategy} + */ + public StampedCommonCache(int initialCapacity, int maxSize, EvictionStrategy evictionStrategy) { + commonCache = new CommonCache<K, V>(initialCapacity, maxSize, evictionStrategy); + } + + /** + * Constructs a LRU cache with the specified initial capacity and max size. + * The LRU cache is slower than {@link LRUCache} + * + * @param initialCapacity initial capacity of the LRU cache + * @param maxSize max size of the LRU cache + */ + public StampedCommonCache(int initialCapacity, int maxSize) { + commonCache = new CommonCache<K, V>(initialCapacity, maxSize); + } + + /** + * Constructs a LRU cache with the default initial capacity(16) + * + * @param maxSize max size of the LRU cache + * @see #StampedCommonCache(int, int) + */ + public StampedCommonCache(int maxSize) { + commonCache = new CommonCache<K, V>(maxSize); + } + + /** + * Constructs a cache backed by the specified {@link Map} instance + * + * @param map the {@link Map} instance + */ + public StampedCommonCache(Map<K, V> map) { + commonCache = new CommonCache<K, V>(map); + } + + /** + * {@inheritDoc} + */ + @Override + public V get(final K key) { + return doWithReadLock(c -> c.get(key)); + } + + /** + * {@inheritDoc} + */ + @Override + public V put(final K key, final V value) { + return doWithWriteLock(c -> c.put(key, value)); + } + + /** + * {@inheritDoc} + */ + @Override + public V getAndPut(K key, ValueProvider<? super K, ? extends V> valueProvider) { + return getAndPut(key, valueProvider, true); + } + + public V getAndPut(K key, ValueProvider<? super K, ? extends V> valueProvider, boolean shouldCache) { + V value; + + // try optimistic read first, which is non-blocking + long optimisticReadStamp = sl.tryOptimisticRead(); + value = commonCache.get(key); + if (sl.validate(optimisticReadStamp)) { + if (null != convertValue(value)) { + return value; + } + } + + long stamp = sl.readLock(); + try { + // if stale, read again + if (!sl.validate(optimisticReadStamp)) { + value = commonCache.get(key); + if (null != convertValue(value)) { + return value; + } + } + + long ws = sl.tryConvertToWriteLock(stamp); // the new local variable `ws` is necessary here! + if (0L == ws) { // Failed to convert read lock to write lock + sl.unlockRead(stamp); + stamp = sl.writeLock(); + + // try to read again + value = commonCache.get(key); + if (null != convertValue(value)) { + return value; + } + } else { + stamp = ws; + } + + value = compute(key, valueProvider, shouldCache); + } finally { + sl.unlock(stamp); + } + + return value; + } + + private V compute(K key, ValueProvider<? super K, ? extends V> valueProvider, boolean shouldCache) { + V value = null == valueProvider ? null : valueProvider.provide(key); + if (shouldCache && null != convertValue(value)) { + commonCache.put(key, value); + } + return value; + } + + /** + * {@inheritDoc} + */ + @Override + public Collection<V> values() { + return doWithReadLock(c -> c.values()); + } + + /** + * {@inheritDoc} + */ + @Override + public Set<K> keys() { + return doWithReadLock(c -> c.keys()); + } + + /** + * {@inheritDoc} + */ + @Override + public boolean containsKey(final K key) { + return doWithReadLock(c -> c.containsKey(key)); + } + + /** + * {@inheritDoc} + */ + @Override + public int size() { + return doWithReadLock(c -> c.size()); + } + + /** + * {@inheritDoc} + */ + @Override + public V remove(final K key) { + return doWithWriteLock(c -> c.remove(key)); + } + + /** + * {@inheritDoc} + */ + @Override + public Map<K, V> clear() { + return doWithWriteLock(c -> c.clear()); + } + + /** + * {@inheritDoc} + */ + @Override + public void cleanUpNullReferences() { + doWithWriteLock(c -> { + c.cleanUpNullReferences(); + return null; + }); + } + + /** + * {@inheritDoc} + */ + @Override + public Object convertValue(V value) { + return value; + } + + /** + * deal with the backed cache guarded by write lock + * @param action the content to complete + */ + private <R> R doWithWriteLock(Action<K, V, R> action) { + long stamp = sl.writeLock(); + try { + return action.doWith(commonCache); + } finally { + sl.unlockWrite(stamp); + } + } + + /** + * deal with the backed cache guarded by read lock + * @param action the content to complete + */ + private <R> R doWithReadLock(Action<K, V, R> action) { + long stamp = sl.tryOptimisticRead(); + R result = action.doWith(commonCache); + + if (!sl.validate(stamp)) { + stamp = sl.readLock(); + try { + result = action.doWith(commonCache); + } finally { + sl.unlockRead(stamp); + } + } + + return result; + } +} http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/main/java/org/codehaus/groovy/transform/stc/StaticTypeCheckingSupport.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/codehaus/groovy/transform/stc/StaticTypeCheckingSupport.java b/src/main/java/org/codehaus/groovy/transform/stc/StaticTypeCheckingSupport.java index 5f0e983..cd5d977 100644 --- a/src/main/java/org/codehaus/groovy/transform/stc/StaticTypeCheckingSupport.java +++ b/src/main/java/org/codehaus/groovy/transform/stc/StaticTypeCheckingSupport.java @@ -46,8 +46,8 @@ import org.codehaus.groovy.runtime.DefaultGroovyStaticMethods; import org.codehaus.groovy.runtime.m12n.ExtensionModule; import org.codehaus.groovy.runtime.m12n.ExtensionModuleScanner; import org.codehaus.groovy.runtime.m12n.MetaInfExtensionModule; -import org.codehaus.groovy.runtime.memoize.ConcurrentCommonCache; import org.codehaus.groovy.runtime.memoize.EvictableCache; +import org.codehaus.groovy.runtime.memoize.StampedCommonCache; import org.codehaus.groovy.runtime.metaclass.MetaClassRegistryImpl; import org.codehaus.groovy.tools.GroovyClass; import org.codehaus.groovy.transform.trait.Traits; @@ -2167,7 +2167,7 @@ public abstract class StaticTypeCheckingSupport { * a method lookup. */ private static class ExtensionMethodCache { - private final EvictableCache<ClassLoader, Map<String, List<MethodNode>>> cache = new ConcurrentCommonCache<ClassLoader, Map<String, List<MethodNode>>>(new WeakHashMap<ClassLoader, Map<String, List<MethodNode>>>()); + private final EvictableCache<ClassLoader, Map<String, List<MethodNode>>> cache = new StampedCommonCache<ClassLoader, Map<String, List<MethodNode>>>(new WeakHashMap<ClassLoader, Map<String, List<MethodNode>>>()); public Map<String, List<MethodNode>> getExtensionMethods(ClassLoader loader) { return cache.getAndPut( http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/src/test/org/codehaus/groovy/runtime/memoize/StampedCommonCacheTest.java ---------------------------------------------------------------------- diff --git a/src/test/org/codehaus/groovy/runtime/memoize/StampedCommonCacheTest.java b/src/test/org/codehaus/groovy/runtime/memoize/StampedCommonCacheTest.java new file mode 100644 index 0000000..953425d --- /dev/null +++ b/src/test/org/codehaus/groovy/runtime/memoize/StampedCommonCacheTest.java @@ -0,0 +1,235 @@ +/* + * 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.codehaus.groovy.runtime.memoize; + +import org.apache.groovy.util.Maps; +import org.junit.Assert; +import org.junit.Test; + +import java.util.HashMap; +import java.util.LinkedHashMap; +import java.util.concurrent.CountDownLatch; +import java.util.concurrent.atomic.AtomicInteger; + +public class StampedCommonCacheTest { + @Test + public void get() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertEquals("Daniel", sc.get("name")); + Assert.assertEquals("Male", sc.get("gender")); + Assert.assertEquals("Shanghai", sc.get("city")); + Assert.assertNull(sc.get("foo")); + } + + @Test + public void put() { + StampedCommonCache<String, String> sc = new StampedCommonCache<>(); + + Assert.assertNull(sc.put("name", "Daniel")); + Assert.assertEquals("Daniel", sc.get("name")); + + Assert.assertEquals("Daniel", sc.put("name", "sunlan")); + Assert.assertEquals("sunlan", sc.get("name")); + } + + @Test + public void getAndPut() { + StampedCommonCache<String, String> sc = new StampedCommonCache<>(); + + EvictableCache.ValueProvider vp = + new EvictableCache.ValueProvider<String, String>() { + @Override + public String provide(String key) { + return "Chinese"; + } + }; + + Assert.assertEquals("Chinese", sc.getAndPut("language", vp,false)); + Assert.assertNull(sc.get("language")); + + Assert.assertEquals("Chinese", sc.getAndPut("language", vp)); + Assert.assertEquals("Chinese", sc.get("language")); + } + + @Test + public void values() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertArrayEquals(new String[] {"Daniel", "Male", "Shanghai"}, sc.values().toArray(new String[0])); + } + + @Test + public void keys() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertArrayEquals(new String[] {"name", "gender", "city"}, sc.keys().toArray(new String[0])); + } + + @Test + public void containsKey() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertTrue(sc.containsKey("name")); + } + + @Test + public void size() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertEquals(3, sc.size()); + } + + @Test + public void remove() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new HashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertEquals("Shanghai", sc.remove("city")); + Assert.assertNull(sc.get("city")); + } + + @Test + public void clear() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", "Shanghai") + ) + ); + + Assert.assertArrayEquals(new String[] {"Daniel", "Male", "Shanghai"}, sc.clear().values().toArray(new String[0])); + } + + @Test + public void cleanUpNullReferences() { + StampedCommonCache<String, String> sc = + new StampedCommonCache<>( + new LinkedHashMap<>( + Maps.of("name", "Daniel", + "gender", "Male", + "city", null) + ) + ); + + sc.cleanUpNullReferences(); + Assert.assertArrayEquals(new String[] {"Daniel", "Male"}, sc.values().toArray(new String[0])); + } + + @Test + public void testLruCache() { + StampedCommonCache<String, String> sc = new StampedCommonCache<String, String>(3); + sc.put("a", "1"); + sc.put("b", "2"); + sc.put("c", "3"); + sc.put("a", "4"); + sc.put("d", "5"); + Assert.assertArrayEquals(new String[] {"c", "a", "d"}, sc.keys().toArray(new String[0])); + Assert.assertEquals("3", sc.get("c")); + Assert.assertEquals("4", sc.get("a")); + Assert.assertEquals("5", sc.get("d")); + } + + @Test + public void testFifoCache() { + StampedCommonCache<String, String> sc = new StampedCommonCache<String, String>(3, 3, EvictableCache.EvictionStrategy.FIFO); + sc.put("a", "1"); + sc.put("b", "2"); + sc.put("c", "3"); + sc.put("a", "4"); + sc.put("d", "5"); + Assert.assertArrayEquals(new String[] {"b", "c", "d"}, sc.keys().toArray(new String[0])); + Assert.assertEquals("2", sc.get("b")); + Assert.assertEquals("3", sc.get("c")); + Assert.assertEquals("5", sc.get("d")); + } + + @Test + public void testAccessCacheConcurrently() throws InterruptedException { + final StampedCommonCache<Integer, Integer> m = new StampedCommonCache<>(); + + final int threadNum = 30; + final CountDownLatch countDownLatch = new CountDownLatch(1); + final CountDownLatch countDownLatch2 = new CountDownLatch(threadNum); + + final AtomicInteger cnt = new AtomicInteger(0); + + for (int i = 0; i < threadNum; i++) { + new Thread(() -> { + try { + countDownLatch.await(); + + m.getAndPut(123, k -> cnt.getAndIncrement()); + } catch (InterruptedException e) { + e.printStackTrace(); + } finally { + countDownLatch2.countDown(); + } + }).start(); + } + + countDownLatch.countDown(); + countDownLatch2.await(); + + Assert.assertEquals(1, cnt.get()); + } +} http://git-wip-us.apache.org/repos/asf/groovy/blob/10c6ef9c/subprojects/groovy-macro/src/main/groovy/org/codehaus/groovy/macro/transform/MacroMethodsCache.java ---------------------------------------------------------------------- diff --git a/subprojects/groovy-macro/src/main/groovy/org/codehaus/groovy/macro/transform/MacroMethodsCache.java b/subprojects/groovy-macro/src/main/groovy/org/codehaus/groovy/macro/transform/MacroMethodsCache.java index 0072c1e..ebb4423 100644 --- a/subprojects/groovy-macro/src/main/groovy/org/codehaus/groovy/macro/transform/MacroMethodsCache.java +++ b/subprojects/groovy-macro/src/main/groovy/org/codehaus/groovy/macro/transform/MacroMethodsCache.java @@ -26,8 +26,8 @@ import org.codehaus.groovy.macro.runtime.Macro; import org.codehaus.groovy.runtime.m12n.ExtensionModule; import org.codehaus.groovy.runtime.m12n.ExtensionModuleScanner; import org.codehaus.groovy.runtime.m12n.MetaInfExtensionModule; -import org.codehaus.groovy.runtime.memoize.ConcurrentCommonCache; import org.codehaus.groovy.runtime.memoize.EvictableCache; +import org.codehaus.groovy.runtime.memoize.StampedCommonCache; import org.codehaus.groovy.transform.stc.ExtensionMethodNode; import java.util.ArrayList; @@ -44,7 +44,7 @@ import java.util.WeakHashMap; */ class MacroMethodsCache { private static final ClassNode MACRO_ANNOTATION_CLASS_NODE = ClassHelper.make(Macro.class); - private static final EvictableCache<ClassLoader, Map<String, List<MethodNode>>> CACHE = new ConcurrentCommonCache<ClassLoader, Map<String, List<MethodNode>>>(new WeakHashMap<ClassLoader, Map<String, List<MethodNode>>>()); + private static final EvictableCache<ClassLoader, Map<String, List<MethodNode>>> CACHE = new StampedCommonCache<ClassLoader, Map<String, List<MethodNode>>>(new WeakHashMap<ClassLoader, Map<String, List<MethodNode>>>()); public static Map<String, List<MethodNode>> get(final ClassLoader classLoader) { return CACHE.getAndPut(classLoader, new EvictableCache.ValueProvider<ClassLoader, Map<String, List<MethodNode>>>() {
