From 0bf93036684b36c143ded51f048181322e3b545c Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Tue, 27 May 2014 13:40:19 +0200 Subject: [PATCH] BUG-648: Create MapAdaptor and friends This introduces the MapAdaptor class, which allows transforming one Map implementation to another, balancing the isolation and access patterns. The core of the idea is that we are using patterns which would benefit from persistent structures where we can take a point-in-time stable snapshot, update it and publish the new version all the while clients accessing the old version suspect nothing. So far we have implemented the isolation by copying maps around -- which is fine as long as there are not too many elements. We do have a persistent strucutre (Ctrie), which allows snapshot and isolation to happen in O(1), but exacts heavy price on access due to volatile variables. Change-Id: I4b745eecc5a915862ab75921703cfce3c2747ab6 Signed-off-by: Robert Varga --- common/pom.xml | 3 +- common/util/pom.xml | 54 ++++++ .../yangtools/util/MapAdaptor.java | 182 ++++++++++++++++++ .../yangtools/util/ReadOnlyTrieMap.java | 61 ++++++ .../yangtools/util/ReadWriteTrieMap.java | 128 ++++++++++++ .../yangtools/util/MapAdaptorTest.java | 148 ++++++++++++++ pom.xml | 11 ++ 7 files changed, 586 insertions(+), 1 deletion(-) create mode 100644 common/util/pom.xml create mode 100644 common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java create mode 100644 common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java create mode 100644 common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java create mode 100644 common/util/src/test/java/org/opendaylight/yangtools/util/MapAdaptorTest.java diff --git a/common/pom.xml b/common/pom.xml index c78f47afa7..cfaf16e46c 100644 --- a/common/pom.xml +++ b/common/pom.xml @@ -20,13 +20,14 @@ pom + checkstyle-logging concepts feature mockito-configuration object-cache-api object-cache-guava object-cache-noop - checkstyle-logging + util diff --git a/common/util/pom.xml b/common/util/pom.xml new file mode 100644 index 0000000000..77f8190205 --- /dev/null +++ b/common/util/pom.xml @@ -0,0 +1,54 @@ + + + + + + + org.opendaylight.yangtools + common-parent + 0.6.2-SNAPSHOT + + bundle + 4.0.0 + util + + + + org.slf4j + slf4j-api + + + com.google.guava + guava + + + com.github.romix + java-concurrent-hash-trie-map + + + + junit + junit + test + + + + + + org.apache.felix + maven-bundle-plugin + true + + org.opendaylight.yangtools.util + java-concurrent-hash-trie-map;inline=true + + + + + diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java b/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java new file mode 100644 index 0000000000..2ef038b99f --- /dev/null +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/MapAdaptor.java @@ -0,0 +1,182 @@ +/* + * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.yangtools.util; + +import java.util.Collections; +import java.util.HashMap; +import java.util.Map; +import java.util.Map.Entry; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import com.google.common.base.Preconditions; +import com.google.common.collect.Iterables; +import com.romix.scala.collection.concurrent.TrieMap; + +/* + * A simple layer on top of maps, which performs snapshot mediation and optimization of + * what the underlying implementation is. + */ +public final class MapAdaptor { + public static final int DEFAULT_COPY_MAX_ITEMS = 100; + public static final String COPY_MAX_ITEMS_MAX_PROP = "org.opendaylight.yangtools.util.mapadaptor.maxcopy"; + + public static final int DEFAULT_PERSIST_MIN_ITEMS = 50; + public static final String PERSIST_MIN_ITEMS_PROP = "org.opendaylight.yangtools.util.mapadaptor.minpersist"; + + private static final Logger LOG = LoggerFactory.getLogger(MapAdaptor.class); + private static final MapAdaptor DEFAULT_INSTANCE; + + private final boolean useSingleton; + private final int persistMinItems; + private final int copyMaxItems; + + static { + DEFAULT_INSTANCE = new MapAdaptor(true, + getProperty(COPY_MAX_ITEMS_MAX_PROP, DEFAULT_COPY_MAX_ITEMS), + getProperty(PERSIST_MIN_ITEMS_PROP, DEFAULT_PERSIST_MIN_ITEMS)); + LOG.debug("Configured HashMap/TrieMap cutoff at {}/{} entries", + DEFAULT_INSTANCE.persistMinItems, DEFAULT_INSTANCE.copyMaxItems); + } + + private static final int getProperty(final String name, final int defaultValue) { + try { + final String p = System.getProperty(name); + if (p != null) { + try { + int pi = Integer.valueOf(p); + if (pi <= 0) { + LOG.warn("Ignoring illegal value of {}: has to be a positive number", name); + } else { + return pi; + } + } catch (NumberFormatException e) { + LOG.warn("Ignoring non-numerical value of {}", name, e); + } + } + } catch (Exception e) { + LOG.debug("Failed to get {}", name, e); + } + return defaultValue; + } + + private MapAdaptor(final boolean useSingleton, final int copyMaxItems, final int persistMinItems) { + this.useSingleton = useSingleton; + this.copyMaxItems = copyMaxItems; + this.persistMinItems = persistMinItems; + } + + /** + * Return the default-configured instance. + * + * @return the singleton global instance + */ + public static MapAdaptor getDefaultInstance() { + return DEFAULT_INSTANCE; + } + + public static MapAdaptor getInstance(final boolean useSingleton, final int copyMaxItems, final int persistMinItems) { + Preconditions.checkArgument(copyMaxItems >= 0, "copyMaxItems has to be a non-negative integer"); + Preconditions.checkArgument(persistMinItems >= 0, "persistMinItems has to be a positive integer"); + Preconditions.checkArgument(persistMinItems <= copyMaxItems, "persistMinItems must be less than or equal to copyMaxItems"); + return new MapAdaptor(useSingleton, copyMaxItems, persistMinItems); + } + + /** + * Input is treated is supposed to be left unmodified, result must be mutable. + * + * @param input + * @return + */ + public Map takeSnapshot(final Map input) { + if (input instanceof ReadOnlyTrieMap) { + return ((ReadOnlyTrieMap)input).toReadWrite(); + } + + LOG.trace("Converting input {} to a HashMap", input); + + // FIXME: be a bit smart about allocation based on observed size + + final Map ret = new HashMap<>(input); + LOG.trace("Read-write HashMap is {}", ret); + return ret; + } + + /** + * Input will be thrown away, result will be retained for read-only access or + * {@link #takeSnapshot(Map)} purposes. + * + * @param input + * @return + */ + public Map optimize(final Map input) { + if (input instanceof ReadOnlyTrieMap) { + LOG.warn("Optimizing read-only map {}", input); + } + + final int size = input.size(); + + /* + * No-brainer :) + */ + if (size == 0) { + LOG.trace("Reducing input {} to an empty map", input); + return Collections.emptyMap(); + } + + /* + * We retain the persistent map as long as it holds at least + * persistMinItems + */ + if (input instanceof ReadWriteTrieMap && size >= persistMinItems) { + return ((ReadWriteTrieMap)input).toReadOnly(); + } + + /* + * If the user opted to use singleton maps, use them. Except for the case + * when persistMinItems dictates we should not move off of the persistent + * map. + */ + if (useSingleton && size == 1) { + final Entry e = Iterables.getOnlyElement(input.entrySet()); + final Map ret = Collections.singletonMap(e.getKey(), e.getValue()); + LOG.trace("Reducing input () to singleton map {}", input, ret); + return ret; + } + + if (size <= copyMaxItems) { + /* + * Favor access speed: use a HashMap and copy it on modification. + */ + if (input instanceof HashMap) { + return input; + } + + LOG.trace("Copying input {} to a HashMap ({} entries)", input, size); + final Map ret = new HashMap<>(input); + LOG.trace("Read-only HashMap is {}", ret); + return ret; + } + + /* + * Favor isolation speed: use a TrieMap and perform snapshots + * + * This one is a bit tricky, as the TrieMap is concurrent and does not + * keep an uptodate size. Updating it requires a full walk -- which is + * O(N) and we want to avoid that. So we wrap it in an interceptor, + * which will maintain the size for us. + */ + LOG.trace("Copying input {} to a TrieMap ({} entries)", input, size); + final TrieMap map = TrieMap.empty(); + map.putAll(input); + final Map ret = new ReadOnlyTrieMap<>(map, size); + LOG.trace("Read-only TrieMap is {}", ret); + return ret; + } +} diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java new file mode 100644 index 0000000000..88da121c86 --- /dev/null +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadOnlyTrieMap.java @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.yangtools.util; + +import java.util.Map; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ForwardingMap; +import com.romix.scala.collection.concurrent.TrieMap; + +/** + * A read-only facade in front of a TrieMap. This is what we give out from + * MapAdaptor.optimize(). The idea is that we want our read-only users to + * share a single snapshot. That snapshot is instantiated lazily either on + * first access. Since we never leak the TrieMap and track its size as it + * changes, we can cache it for future reference. + */ +final class ReadOnlyTrieMap extends ForwardingMap { + private static final Logger LOG = LoggerFactory.getLogger(ReadOnlyTrieMap.class); + private final TrieMap readWrite; + private final int size; + private TrieMap readOnly; + + ReadOnlyTrieMap(final TrieMap map, final int size) { + super(); + this.readWrite = Preconditions.checkNotNull(map); + this.size = size; + } + + Map toReadWrite() { + final Map ret = new ReadWriteTrieMap<>(readWrite.snapshot(), size); + LOG.trace("Converted read-only TrieMap {} to read-write {}", this, ret); + return ret; + } + + @Override + protected Map delegate() { + if (readOnly == null) { + synchronized (this) { + if (readOnly == null) { + readOnly = readWrite.readOnlySnapshot(); + } + } + } + + return readOnly; + } + + @Override + public int size() { + return size; + } +} diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java new file mode 100644 index 0000000000..039e7340a5 --- /dev/null +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/ReadWriteTrieMap.java @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.yangtools.util; + +import java.util.Collection; +import java.util.Collections; +import java.util.Map; +import java.util.Set; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import com.google.common.base.Preconditions; +import com.romix.scala.collection.concurrent.TrieMap; + +/** + * A TrieMap facade tracking modifications. Since we change structures based on + * their size, and determining the size of a TrieMap is expensive, we make sure + * to update it as we go. + * + * FIXME: this map does not support modification view the keySet()/values()/entrySet() + * methods. + * + * @param Key type + * @param Value type + */ +final class ReadWriteTrieMap implements Map { + private static final Logger LOG = LoggerFactory.getLogger(ReadOnlyTrieMap.class); + private final TrieMap delegate; + private int size; + + ReadWriteTrieMap(final TrieMap delegate, final int size) { + this.delegate = Preconditions.checkNotNull(delegate); + this.size = size; + } + + Map toReadOnly() { + final Map ret = new ReadOnlyTrieMap<>(delegate, size); + LOG.trace("Converted read-write TrieMap {} to read-only {}", this, ret); + return ret; + } + + @Override + public int size() { + return size; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public boolean containsKey(final Object key) { + return delegate.containsKey(key); + } + + @Override + public boolean containsValue(final Object value) { + return delegate.containsValue(value); + } + + @Override + public V get(final Object key) { + return delegate.get(key); + } + + @Override + public V put(final K key, final V value) { + final V ret = delegate.put(key, value); + if (ret == null) { + size++; + } + return ret; + } + + @Override + public V remove(final Object key) { + final V ret = delegate.remove(key); + if (ret != null) { + size--; + } + return ret; + } + + @Override + public void putAll(final Map m) { + for (Entry e : m.entrySet()) { + put(e.getKey(), e.getValue()); + } + } + + @Override + public void clear() { + delegate.clear(); + size = 0; + } + + @Override + public Set keySet() { + return Collections.unmodifiableSet(delegate.keySet()); + } + + @Override + public Collection values() { + return Collections.unmodifiableCollection(delegate.values()); + } + + @Override + public Set> entrySet() { + return Collections.unmodifiableSet(delegate.entrySet()); + } + + @Override + public boolean equals(final Object o) { + return delegate.equals(o); + } + + @Override + public int hashCode() { + return delegate.hashCode(); + } +} diff --git a/common/util/src/test/java/org/opendaylight/yangtools/util/MapAdaptorTest.java b/common/util/src/test/java/org/opendaylight/yangtools/util/MapAdaptorTest.java new file mode 100644 index 0000000000..e4ae622121 --- /dev/null +++ b/common/util/src/test/java/org/opendaylight/yangtools/util/MapAdaptorTest.java @@ -0,0 +1,148 @@ +/* + * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.yangtools.util; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertTrue; + +import java.util.Collections; +import java.util.HashMap; +import java.util.Map; +import java.util.TreeMap; + +import org.junit.Before; +import org.junit.Test; + +public class MapAdaptorTest { + private MapAdaptor adaptor; + + @Before + public void setUp() { + adaptor = MapAdaptor.getInstance(true, 10, 5); + } + + @Test + public void testTreeToEmpty() { + final Map input = new TreeMap<>(); + + // Converts the input into a hashmap; + final Map snap = adaptor.takeSnapshot(input); + assertNotSame(input, snap); + assertTrue(snap instanceof HashMap); + + final Map opt1 = adaptor.optimize(input); + assertSame(Collections.EMPTY_MAP, opt1); + + final Map opt2 = adaptor.optimize(snap); + assertSame(Collections.EMPTY_MAP, opt2); + } + + @Test + public void testTreeToSingleton() { + final Map input = new TreeMap<>(); + input.put("a", "b"); + + final Map snap = adaptor.takeSnapshot(input); + assertNotSame(input, snap); + assertTrue(snap instanceof HashMap); + assertEquals(input, snap); + + final Map opt1 = adaptor.optimize(input); + assertNotSame(input, opt1); + assertEquals(input, opt1); + assertEquals(Collections.singletonMap(null, null).getClass(), opt1.getClass()); + final Map snap1 = adaptor.takeSnapshot(opt1); + assertTrue(snap1 instanceof HashMap); + assertEquals(input, snap1); + + final Map opt2 = adaptor.optimize(snap); + assertNotSame(snap, opt2); + assertEquals(input, opt2); + assertEquals(Collections.singletonMap(null, null).getClass(), opt2.getClass()); + + final Map snap2 = adaptor.takeSnapshot(opt2); + assertNotSame(opt2, snap2); + assertTrue(snap2 instanceof HashMap); + assertEquals(input, snap2); + } + + @Test + public void testTreeToTrie() { + final Map input = new TreeMap<>(); + for (char c = 'a'; c <= 'z'; ++c) { + final String s = String.valueOf(c); + input.put(s, s); + } + + final Map snap = adaptor.takeSnapshot(input); + assertTrue(snap instanceof HashMap); + assertEquals(input, snap); + + final Map opt1 = adaptor.optimize(input); + assertEquals(input, opt1); + assertEquals(ReadOnlyTrieMap.class, opt1.getClass()); + + final Map snap2 = adaptor.takeSnapshot(opt1); + assertTrue(snap2 instanceof ReadWriteTrieMap); + assertEquals(opt1, snap2); + assertEquals(26, snap2.size()); + + // snap2 and snap3 are independent + final Map snap3 = adaptor.takeSnapshot(opt1); + + snap2.remove("a"); + assertEquals(25, snap2.size()); + assertEquals(26, snap3.size()); + + snap3.remove("b"); + snap3.remove("c"); + assertEquals(25, snap2.size()); + assertEquals(24, snap3.size()); + + snap2.put("foo", "foo"); + snap2.put("bar", "baz"); + snap3.put("bar", "baz"); + assertEquals(27, snap2.size()); + assertEquals(25, snap3.size()); + } + + @Test + public void testTrieToHash() { + final Map input = new TreeMap<>(); + for (char c = 'a'; c <= 'k'; ++c) { + final String s = String.valueOf(c); + input.put(s, s); + } + + // Translated to read-only + final Map opt1 = adaptor.optimize(input); + assertEquals(input, opt1); + assertEquals(ReadOnlyTrieMap.class, opt1.getClass()); + assertEquals(11, opt1.size()); + + // 11 elements -- should retain TrieMap + final Map snap1 = adaptor.takeSnapshot(opt1); + assertEquals(ReadWriteTrieMap.class, snap1.getClass()); + assertEquals(11, snap1.size()); + + for (char c = 'e'; c <= 'k'; ++c) { + final String s = String.valueOf(c); + snap1.remove(s); + } + + // 4 elements: should revert to HashMap + assertEquals(4, snap1.size()); + + final Map opt2 = adaptor.optimize(snap1); + assertEquals(snap1, opt2); + assertEquals(HashMap.class, opt2.getClass()); + assertEquals(4, opt2.size()); + } +} diff --git a/pom.xml b/pom.xml index 9ccb93b27e..de8b4e1722 100644 --- a/pom.xml +++ b/pom.xml @@ -44,6 +44,7 @@ 2.1.6 1.9.5 3.17.1-GA + 0.2.0 @@ -176,6 +177,11 @@ jsr305 2.0.3 + + com.github.romix + java-concurrent-hash-trie-map + ${ctrie.version} + @@ -216,6 +222,11 @@ object-cache-noop ${project.version} + + ${project.groupId} + util + ${project.version} + -- 2.36.6