From 98d1ba0a51e29b3009a0038e078a043a4aed688d Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Mon, 4 May 2020 14:34:27 +0200 Subject: [PATCH] Add lazily-instantiated maps Instantiating an ImmutableMap on each access is quite wasteful, as there are a number of cases where we do not need the entire mapping to be instantiated. Typical uses touch the Map only once -- either to lookup a value based on the key, or to iterate through the values. Others are possible, but those two cover most of the patterns. We add the prerequisite indirection and two implementations to support each of the cases. The iterator part is optimized to perform lazy object instantiation -- similar to LazyBindingList. The lookup part works in a rather similar way, except it keeps a lookup ConcurrentHashMap as the primary storage and values are seen as expendable secondary storage. This makes iteration order unstable, which might be seen as a violation of immutable contract -- but our contract is a Map and mappings remain stable. JIRA: MDSAL-539 Change-Id: I7c095065915f3c0d7b180d4aa1494e15d6374a11 Signed-off-by: Robert Varga --- .../impl/BindingToNormalizedStreamWriter.java | 2 +- .../dom/codec/impl/CodecDataObject.java | 3 +- .../codec/impl/KeyedListNodeCodecContext.java | 22 +- .../dom/codec/impl/LazyBindingList.java | 4 +- .../dom/codec/impl/LazyBindingMap.java | 219 +++++++++++++ .../codec/impl/LazyBindingMapIterState.java | 235 ++++++++++++++ .../codec/impl/LazyBindingMapLookupState.java | 293 ++++++++++++++++++ .../dom/codec/impl/LazyBindingMapTest.java | 231 ++++++++++++++ 8 files changed, 992 insertions(+), 17 deletions(-) create mode 100644 binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMap.java create mode 100644 binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapIterState.java create mode 100644 binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapLookupState.java create mode 100644 binding/mdsal-binding-dom-codec/src/test/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapTest.java diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/BindingToNormalizedStreamWriter.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/BindingToNormalizedStreamWriter.java index b5f586d2d4..5e88eabade 100644 --- a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/BindingToNormalizedStreamWriter.java +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/BindingToNormalizedStreamWriter.java @@ -194,7 +194,7 @@ final class BindingToNormalizedStreamWriter implements AnydataBindingStreamWrite @Override public void startMapEntryNode(final Identifier key, final int childSizeHint) throws IOException { duplicateSchemaEnter(); - NodeIdentifierWithPredicates identifier = ((KeyedListNodeCodecContext) current()).serialize(key); + NodeIdentifierWithPredicates identifier = ((KeyedListNodeCodecContext) current()).serialize(key); delegate.startMapEntryNode(identifier, childSizeHint); } diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/CodecDataObject.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/CodecDataObject.java index 2847153da8..d7663d2204 100644 --- a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/CodecDataObject.java +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/CodecDataObject.java @@ -154,7 +154,8 @@ public abstract class CodecDataObject implements DataObjec private @NonNull Object loadKey(final VarHandle handle) { verify(data instanceof MapEntryNode, "Unsupported value %s", data); verify(context instanceof KeyedListNodeCodecContext, "Unexpected context %s", context); - final Object obj = ((KeyedListNodeCodecContext) context).deserialize(((MapEntryNode) data).getIdentifier()); + final Object obj = ((KeyedListNodeCodecContext) context) + .deserialize(((MapEntryNode) data).getIdentifier()); // key is known to be non-null, no need to mask it final Object witness = handle.compareAndExchangeRelease(this, null, obj); return witness == null ? obj : witness; diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/KeyedListNodeCodecContext.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/KeyedListNodeCodecContext.java index 206baa7c15..7d140c2120 100644 --- a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/KeyedListNodeCodecContext.java +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/KeyedListNodeCodecContext.java @@ -10,8 +10,6 @@ package org.opendaylight.mdsal.binding.dom.codec.impl; import static java.util.Objects.requireNonNull; import static org.opendaylight.mdsal.binding.spec.naming.BindingMapping.IDENTIFIABLE_KEY_NAME; -import com.google.common.collect.ImmutableMap; -import com.google.common.collect.ImmutableMap.Builder; import java.lang.reflect.Method; import java.util.List; import java.util.Map; @@ -23,33 +21,29 @@ import org.opendaylight.yangtools.yang.binding.InstanceIdentifier; import org.opendaylight.yangtools.yang.binding.InstanceIdentifier.IdentifiableItem; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates; -import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; import org.opendaylight.yangtools.yang.data.api.schema.MapNode; import org.opendaylight.yangtools.yang.model.api.ListSchemaNode; -abstract class KeyedListNodeCodecContext> extends ListNodeCodecContext { - private static final class Ordered> extends KeyedListNodeCodecContext { +abstract class KeyedListNodeCodecContext, D extends DataObject & Identifiable> + extends ListNodeCodecContext { + private static final class Ordered, D extends DataObject & Identifiable> + extends KeyedListNodeCodecContext { Ordered(final DataContainerCodecPrototype prototype, final Method keyMethod, final IdentifiableItemCodec codec) { super(prototype, keyMethod, codec); } } - private static final class Unordered> extends KeyedListNodeCodecContext { + static final class Unordered, D extends DataObject & Identifiable> + extends KeyedListNodeCodecContext { Unordered(final DataContainerCodecPrototype prototype, final Method keyMethod, final IdentifiableItemCodec codec) { super(prototype, keyMethod, codec); } @Override - Map fromMap(final MapNode map, final int size) { - // FIXME: MDSAL-539: Make this a lazily-populated map - final Builder builder = ImmutableMap.builderWithExpectedSize(size); - for (MapEntryNode node : map.getValue()) { - final D entry = createBindingProxy(node); - builder.put(entry.key(), entry); - } - return builder.build(); + Map fromMap(final MapNode map, final int size) { + return LazyBindingMap.create(this, map, size); } } diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingList.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingList.java index c0f3fcb7bb..ff82f4257e 100644 --- a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingList.java +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingList.java @@ -40,7 +40,9 @@ import org.slf4j.LoggerFactory; * @param the type of elements in this list */ final class LazyBindingList extends AbstractList implements Immutable, RandomAccess { - private static final VarHandle OBJ_AA = MethodHandles.arrayElementVarHandle(Object[].class); + // Object array access variable handle + static final VarHandle OBJ_AA = MethodHandles.arrayElementVarHandle(Object[].class); + private static final Logger LOG = LoggerFactory.getLogger(LazyBindingList.class); private static final String LAZY_CUTOFF_PROPERTY = "org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.max-eager-elements"; diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMap.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMap.java new file mode 100644 index 0000000000..23a275bd67 --- /dev/null +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMap.java @@ -0,0 +1,219 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. 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.mdsal.binding.dom.codec.impl; + +import static java.util.Objects.requireNonNull; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableMap.Builder; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.VarHandle; +import java.util.AbstractMap; +import java.util.Collection; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.mdsal.binding.dom.codec.impl.KeyedListNodeCodecContext.Unordered; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.yang.binding.DataObject; +import org.opendaylight.yangtools.yang.binding.Identifiable; +import org.opendaylight.yangtools.yang.binding.Identifier; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates; +import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; +import org.opendaylight.yangtools.yang.data.api.schema.MapNode; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * Lazily-populated Map of binding DTOs. This implementation acts as the main entry point, so that we can decide on the + * translation strategy we are going to use. We make that decision based on the first method that touches the mappings + * (or materializes a view). + * + * @param key type + * @param value type + */ +final class LazyBindingMap, V extends DataObject & Identifiable> + extends AbstractMap implements Immutable { + private static final Logger LOG = LoggerFactory.getLogger(LazyBindingMap.class); + private static final String LAZY_CUTOFF_PROPERTY = + "org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingMap.max-eager-elements"; + private static final int DEFAULT_LAZY_CUTOFF = 1; + @VisibleForTesting + static final int LAZY_CUTOFF; + + private static final VarHandle STATE; + + static { + try { + STATE = MethodHandles.lookup().findVarHandle(LazyBindingMap.class, "state", + State.class); + } catch (NoSuchFieldException | IllegalAccessException e) { + throw new ExceptionInInitializerError(e); + } + + final int value = Integer.getInteger(LAZY_CUTOFF_PROPERTY, DEFAULT_LAZY_CUTOFF); + if (value < 0) { + LOG.info("Lazy population of maps disabled"); + LAZY_CUTOFF = Integer.MAX_VALUE; + } else { + LOG.info("Using lazy population for maps larger than {} element(s)", value); + LAZY_CUTOFF = value; + } + } + + private final @NonNull Unordered codec; + private final @NonNull MapNode mapNode; + + // Used via VarHandle above + @SuppressWarnings("unused") + private volatile State state; + + private LazyBindingMap(final Unordered codec, final MapNode mapNode) { + this.codec = requireNonNull(codec); + this.mapNode = requireNonNull(mapNode); + } + + static , V extends DataObject & Identifiable> @NonNull Map create( + final Unordered codec, final MapNode mapNode, final int size) { + if (size == 1) { + // Do not bother with lazy instantiation in case of a singleton + final V entry = codec.createBindingProxy(mapNode.getValue().iterator().next()); + return Map.of(entry.key(), entry); + } + return size > LAZY_CUTOFF ? new LazyBindingMap<>(codec, mapNode) : eagerMap(codec, mapNode, size); + } + + private static , V extends DataObject & Identifiable> @NonNull Map eagerMap( + final Unordered codec, final MapNode mapNode, final int size) { + final Builder builder = ImmutableMap.builderWithExpectedSize(size); + for (MapEntryNode node : mapNode.getValue()) { + final V entry = codec.createBindingProxy(node); + builder.put(entry.key(), entry); + } + return builder.build(); + } + + @Override + public int size() { + return mapNode.size(); + } + + @Override + public V remove(final Object key) { + throw uoe(); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public void putAll(final Map m) { + throw uoe(); + } + + @Override + public void clear() { + throw uoe(); + } + + @Override + public boolean containsKey(final Object key) { + return lookupState().containsKey(requireNonNull(key)); + } + + @Override + public boolean containsValue(final Object value) { + /* + * This implementation relies on the relationship specified by Identifiable/Identifier and its use in binding + * objects. The key is a wrapper object composed of a subset (or all) properties in the value, i.e. we have + * a partial index. + * + * Instead of performing an O(N) search, we extract the key from the value, look the for the corresponding + * mapping. If we find a mapping we check if the mapped value equals the the value being looked up. + * + * Note we prefer throwing ClassCastException/NullPointerException when presented with null or an object which + * cannot possibly be contained in this map. + */ + final V cast = codec.getBindingClass().cast(requireNonNull(value)); + final V found = get(cast.key()); + return found != null && cast.equals(found); + } + + @Override + public V get(final Object key) { + return lookupState().get(requireNonNull(key)); + } + + @Override + public Set keySet() { + return iterState().keySet(); + } + + @Override + public Collection values() { + return iterState().values(); + } + + @Override + public Set> entrySet() { + return iterState().entrySet(); + } + + @NonNull V createValue(final MapEntryNode node) { + return codec.createBindingProxy(node); + } + + Optional lookupValue(final @NonNull Object key) { + final NodeIdentifierWithPredicates childId = codec.serialize((Identifier) key); + return mapNode.getChild(childId).map(codec::createBindingProxy); + } + + @NonNull MapNode mapNode() { + return mapNode; + } + + private @NonNull State lookupState() { + final State local; + return (local = (State) STATE.getAcquire(this)) != null ? local : loadLookup(); + } + + private @NonNull State iterState() { + final State local; + return (local = (State) STATE.getAcquire(this)) != null ? local : loadIter(); + } + + @SuppressWarnings("unchecked") + private @NonNull State loadLookup() { + final State ret = new LazyBindingMapLookupState<>(this); + final Object witness; + return (witness = STATE.compareAndExchangeRelease(this, null, ret)) == null ? ret : (State) witness; + } + + @SuppressWarnings("unchecked") + private @NonNull State loadIter() { + final State ret = new LazyBindingMapIterState<>(this); + final Object witness; + return (witness = STATE.compareAndExchangeRelease(this, null, ret)) == null ? ret : (State) witness; + } + + private static UnsupportedOperationException uoe() { + return new UnsupportedOperationException("Modification is not supported"); + } + + abstract static class State, V extends DataObject & Identifiable> { + abstract boolean containsKey(@NonNull Object key); + + abstract V get(@NonNull Object key); + + abstract @NonNull Set keySet(); + + abstract @NonNull Collection values(); + + abstract @NonNull Set> entrySet(); + } +} diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapIterState.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapIterState.java new file mode 100644 index 0000000000..8c7612f42f --- /dev/null +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapIterState.java @@ -0,0 +1,235 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. 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.mdsal.binding.dom.codec.impl; + +import static java.util.Objects.requireNonNull; +import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA; + +import com.google.common.collect.AbstractIterator; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.Iterators; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.MethodHandles.Lookup; +import java.lang.invoke.VarHandle; +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.Map; +import java.util.Map.Entry; +import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.yang.binding.DataObject; +import org.opendaylight.yangtools.yang.binding.Identifiable; +import org.opendaylight.yangtools.yang.binding.Identifier; +import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * {@link LazyBindingMap.State} optimized for iterator access, mainly via {@link Map#values()}. + * + * @param key type + * @param value type + */ +final class LazyBindingMapIterState, V extends DataObject & Identifiable> + extends LazyBindingMap.State { + private static final Logger LOG = LoggerFactory.getLogger(LazyBindingMapIterState.class); + private static final VarHandle ENTRY_SET; + private static final VarHandle KEY_SET; + private static final VarHandle LOOKUP_MAP; + + static { + final Lookup lookup = MethodHandles.lookup(); + try { + ENTRY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "entrySet", EntrySet.class); + KEY_SET = lookup.findVarHandle(LazyBindingMapIterState.class, "keySet", KeySet.class); + LOOKUP_MAP = lookup.findVarHandle(LazyBindingMapIterState.class, "lookupMap", ImmutableMap.class); + } catch (NoSuchFieldException | IllegalAccessException e) { + throw new ExceptionInInitializerError(e); + } + } + + // Primary storage of transformed nodes. Other views are derived from this. + private final @NonNull Values values; + + // Secondary views derived from values, used via varhandles above + @SuppressWarnings("unused") + private volatile KeySet keySet; + @SuppressWarnings("unused") + private volatile EntrySet entrySet; + + // Lookup map, instantiated on demand, used via varhandle above + @SuppressWarnings("unused") + private volatile ImmutableMap lookupMap; + + LazyBindingMapIterState(final LazyBindingMap map) { + values = new Values<>(map); + } + + @Override + boolean containsKey(final Object key) { + return lookupMap().containsKey(key); + } + + @Override + V get(final Object key) { + return lookupMap().get(key); + } + + @Override + Values values() { + return values; + } + + @Override + EntrySet entrySet() { + final EntrySet ret; + return (ret = (EntrySet) ENTRY_SET.getAcquire(this)) != null ? ret : loadEntrySet(); + } + + @Override + KeySet keySet() { + final KeySet ret; + return (ret = (KeySet) KEY_SET.getAcquire(this)) != null ? ret : loadKeySet(); + } + + private @NonNull ImmutableMap lookupMap() { + final ImmutableMap ret; + return (ret = (ImmutableMap) LOOKUP_MAP.getAcquire(this)) != null ? ret : loadLookupMap(); + } + + // TODO: this is not exactly efficient, as we are forcing full materialization. We also take a lock here, as we + // do not want multiple threads indexing the same thing. Perhaps this should work with the LookupState + // somehow, so that we have a shared object view and two indices? + private synchronized @NonNull ImmutableMap loadLookupMap() { + ImmutableMap ret = (ImmutableMap) LOOKUP_MAP.getAcquire(this); + if (ret == null) { + lookupMap = ret = ImmutableMap.copyOf(entrySet()); + if (LOG.isTraceEnabled()) { + LOG.trace("Inefficient instantiation of lookup secondary", new Throwable()); + } + } + return ret; + } + + @SuppressWarnings("unchecked") + private @NonNull EntrySet loadEntrySet() { + final EntrySet ret = new EntrySet<>(values); + final Object witness; + return (witness = ENTRY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret + : (EntrySet) witness; + } + + @SuppressWarnings("unchecked") + private @NonNull KeySet loadKeySet() { + final KeySet ret = new KeySet<>(values); + final Object witness; + return (witness = KEY_SET.compareAndExchangeRelease(this, null, ret)) == null ? ret : (KeySet) witness; + } + + private static final class EntrySet, V extends DataObject & Identifiable> + extends AbstractSet> implements Immutable { + private final Values values; + + EntrySet(final Values values) { + this.values = requireNonNull(values); + } + + @Override + public int size() { + return values.size(); + } + + @Override + public Iterator> iterator() { + return Iterators.transform(values.iterator(), value -> Map.entry(value.key(), value)); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that + // the entry's value + return values.contains(((Entry)o).getValue()); + } + } + + private static final class KeySet, V extends DataObject & Identifiable> + extends AbstractSet implements Immutable { + private final Values values; + + KeySet(final Values values) { + this.values = requireNonNull(values); + } + + @Override + public int size() { + return values.size(); + } + + @Override + public Iterator iterator() { + return Iterators.transform(values.iterator(), value -> value.key()); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + return values.map.containsKey(o); + } + } + + /* + * Lazily-populated translation of DOM values to binding values. This class is not completely lazy, as we allocate + * the array to hold all values upfront and populate it with MapEntry nodes. That allows us to perform lock-free + * access, as we just end up CASing MapEntryNodes with their Binding replacements. + */ + private static final class Values, V extends DataObject & Identifiable> + extends AbstractSet implements Immutable { + private final LazyBindingMap map; + private final Object[] objects; + + Values(final LazyBindingMap map) { + this.map = requireNonNull(map); + objects = map.mapNode().getValue().toArray(); + } + + @Override + public Iterator iterator() { + return new AbstractIterator<>() { + private int nextOffset; + + @Override + protected V computeNext() { + return nextOffset < objects.length ? objectAt(nextOffset++) : endOfData(); + } + }; + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + return map.containsValue(o); + } + + @Override + public int size() { + return map.size(); + } + + @NonNull V objectAt(final int offset) { + final Object obj = OBJ_AA.getAcquire(objects, offset); + return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj; + } + + private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) { + final V ret = map.createValue(obj); + final Object witness; + return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness; + } + } +} diff --git a/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapLookupState.java b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapLookupState.java new file mode 100644 index 0000000000..7e750a6baa --- /dev/null +++ b/binding/mdsal-binding-dom-codec/src/main/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapLookupState.java @@ -0,0 +1,293 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. 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.mdsal.binding.dom.codec.impl; + +import static java.util.Objects.requireNonNull; +import static org.opendaylight.mdsal.binding.dom.codec.impl.LazyBindingList.OBJ_AA; + +import com.google.common.collect.AbstractIterator; +import com.google.common.collect.Iterators; +import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.VarHandle; +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Optional; +import java.util.concurrent.ConcurrentHashMap; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.yang.binding.DataObject; +import org.opendaylight.yangtools.yang.binding.Identifiable; +import org.opendaylight.yangtools.yang.binding.Identifier; +import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; + +/** + * {@link LazyBindingMap.State} optimized for lookup access, mainly via {@link Map#values()}. Note that this + * implementation, while being effectively immutable, does not guarantee stable iteration order. + * + * @param key type + * @param value type + */ +final class LazyBindingMapLookupState, V extends DataObject & Identifiable> + extends LazyBindingMap.State { + private static final VarHandle VALUES; + + static { + try { + VALUES = MethodHandles.lookup().findVarHandle(LazyBindingMapLookupState.class, "values", Values.class); + } catch (NoSuchFieldException | IllegalAccessException e) { + throw new ExceptionInInitializerError(e); + } + } + + // Primary storage of transformed nodes + private final ConcurrentHashMap objects = new ConcurrentHashMap<>(); + private final LazyBindingMap map; + + // Used via the varhandle above + @SuppressWarnings("unused") + private volatile Values values; + + LazyBindingMapLookupState(final LazyBindingMap map) { + this.map = requireNonNull(map); + } + + @Override + boolean containsKey(final Object key) { + // If we have the value, that is always accurate. Otherwise we have to attempt to load from DOM data and see + // what the result is. + return objects.containsKey(key) || loadKey(key) != null; + } + + @Override + V get(final Object key) { + final V existing; + // Perform a lookup first, otherwise try to load the key from DOM data + return (existing = objects.get(key)) != null ? existing : loadKey(key); + } + + @Override + KeySet keySet() { + return new KeySet<>(values()); + } + + @Override + Values values() { + final Values ret; + return (ret = (Values) VALUES.getAcquire(this)) != null ? ret : loadValues(); + } + + @Override + EntrySet entrySet() { + return new EntrySet<>(values()); + } + + private @Nullable V loadKey(final @NonNull Object key) { + final Optional opt = map.lookupValue(key); + if (opt.isEmpty()) { + return null; + } + + // Here is a conundrum: which key do we use? + // + // We have the lookup key readily available, which means faster insert at the expense of having duplicates once + // the looked-up object is accessed. On the other hand we could use ret.key(), which forces population of key + // properties and the key itself. + // + // Opt for the provided key, as it is likely the user will end up looking at other properties of the returned + // object. + // + // This leaves the option for lookupValue() to use the key to initialize object's cache fields, so that we end + // up reflecting the same key instance as well as reuse key's components as object values. The case for that + // needs to be justified, though, as it ends up doing more work upfront unrelated to what the caller is about + // to do. + return putIfAbsent((K) key, opt.orElseThrow()); + } + + private @NonNull V putIfAbsent(final @NonNull K key, final @NonNull V value) { + final V existing = objects.putIfAbsent(key, value); + return existing == null ? value : existing; + } + + @SuppressWarnings("unchecked") + private @NonNull Values loadValues() { + final Values ret = new Values<>(this); + final Object witness; + return (witness = VALUES.compareAndExchangeRelease(this, null, ret)) == null ? ret : (Values) witness; + } + + private static final class EntrySet, V extends DataObject & Identifiable> + extends AbstractSet> implements Immutable { + private final Values values; + + EntrySet(final Values values) { + this.values = requireNonNull(values); + } + + @Override + public Iterator> iterator() { + return values.entryIterator(); + } + + @Override + public int size() { + return values.size(); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + // Key/Value are related, asking whether we have a particular Entry is asking whether values contain that + // the entry's value + return values.contains(((Entry)o).getValue()); + } + + @Override + @SuppressWarnings("checkstyle:equalsHashCode") + public boolean equals(final Object obj) { + // Fast check due to us not wasting a field for this value + return obj instanceof EntrySet && values == ((EntrySet) obj).values || super.equals(obj); + } + } + + private static final class KeySet, V extends DataObject & Identifiable> + extends AbstractSet implements Immutable { + private final Values values; + + KeySet(final Values values) { + this.values = requireNonNull(values); + } + + @Override + public Iterator iterator() { + return values.keyIterator(); + } + + @Override + public int size() { + return values.size(); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + return values.map().containsKey(o); + } + + @Override + @SuppressWarnings("checkstyle:equalsHashCode") + public boolean equals(final Object obj) { + // Fast check due to us not wasting a field for this value + return obj instanceof KeySet && values == ((KeySet) obj).values || super.equals(obj); + } + } + + private static final class Values, V extends DataObject & Identifiable> + extends AbstractSet implements Immutable { + private final LazyBindingMapLookupState state; + + // Temporary storage for translated objects. We first initialize this to DOM values, so that we know what + // objects we need to visit. As we iterate through them, we pick the source from here, then run them through + // decode, then reconcile with the lookup map and finally store them back here. + // + // Once at least one iterator has gone through the entire entire array, we throw it away, as at that point + // the primary storage is guaranteed to have all the same objects. We then free this array and switch to using + // views on top of primary storage instead. + // + // This has the side-effect of changing iteration order once one of the iterators has made a complete pass. + // While it may be counter-intuitive, we opt for the added memory efficiency and squirm just right to say + // this is okay for Immutable contract :) + @SuppressFBWarnings(value = "VO_VOLATILE_REFERENCE_TO_ARRAY", + justification = "The ref should really be volatile. This class does not access elements directly.") + private volatile Object[] objects; + + Values(final LazyBindingMapLookupState state) { + this.state = requireNonNull(state); + objects = map().mapNode().getValue().toArray(); + } + + @Override + public Iterator iterator() { + final Object[] local = objects; + // When we have null objects it means we have everyone in state.objects + return local == null ? Iterators.unmodifiableIterator(state.objects.values().iterator()) + : new ValuesIter<>(this, local); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") + public boolean contains(final Object o) { + return map().containsValue(o); + } + + @Override + public int size() { + return map().size(); + } + + Iterator> entryIterator() { + final Object[] local = objects; + // When we have null objects it means we have everyone in state.objects + return local == null ? Iterators.unmodifiableIterator(state.objects.entrySet().iterator()) + : Iterators.transform(new ValuesIter<>(this, local), value -> Map.entry(value.key(), value)); + } + + Iterator keyIterator() { + final Object[] local = objects; + // When we have null objects it means we have everyone in state.objects + return local == null ? Iterators.unmodifiableIterator(state.objects.keySet().iterator()) + : Iterators.transform(new ValuesIter<>(this, local), value -> value.key()); + } + + LazyBindingMap map() { + return state.map; + } + + void fullyIterated() { + // We have iterated over all objects. Clear them to indicate further access should go through state.objects + objects = null; + } + } + + private static final class ValuesIter, V extends DataObject & Identifiable> + extends AbstractIterator { + private final Values values; + private final Object[] objects; + private int nextOffset; + + ValuesIter(final Values values, final Object[] objects) { + this.values = requireNonNull(values); + this.objects = requireNonNull(objects); + } + + @Override + protected V computeNext() { + if (nextOffset < objects.length) { + return objectAt(nextOffset++); + } + values.fullyIterated(); + return endOfData(); + } + + private @NonNull V objectAt(final int offset) { + final Object obj = OBJ_AA.getAcquire(objects, offset); + return obj instanceof MapEntryNode ? loadObjectAt(offset, (MapEntryNode) obj) : (V) obj; + } + + private @NonNull V loadObjectAt(final int offset, final MapEntryNode obj) { + final LazyBindingMapLookupState local = values.state; + final V created = local.map.createValue(obj); + final V ret = local.putIfAbsent(created.key(), created); + final Object witness; + return (witness = OBJ_AA.compareAndExchangeRelease(objects, offset, obj, ret)) == obj ? ret : (V) witness; + } + } +} diff --git a/binding/mdsal-binding-dom-codec/src/test/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapTest.java b/binding/mdsal-binding-dom-codec/src/test/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapTest.java new file mode 100644 index 0000000000..548798b851 --- /dev/null +++ b/binding/mdsal-binding-dom-codec/src/test/java/org/opendaylight/mdsal/binding/dom/codec/impl/LazyBindingMapTest.java @@ -0,0 +1,231 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. 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.mdsal.binding.dom.codec.impl; + +import static org.hamcrest.CoreMatchers.instanceOf; +import static org.hamcrest.MatcherAssert.assertThat; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertThrows; +import static org.junit.Assert.assertTrue; +import static org.mockito.Mockito.mock; + +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import org.junit.BeforeClass; +import org.junit.Test; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.Top; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.TopBuilder; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelList; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelListBuilder; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.TopLevelListKey; +import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.mdsal.test.binding.rev140701.two.level.list.top.level.list.NestedListBuilder; +import org.opendaylight.yangtools.yang.binding.DataObject; +import org.opendaylight.yangtools.yang.binding.Identifiable; +import org.opendaylight.yangtools.yang.binding.InstanceIdentifier; + +public class LazyBindingMapTest extends AbstractBindingCodecTest { + private static Top TOP; + + @BeforeClass + public static void prepareTop() { + final Map map = new HashMap<>(); + for (int i = 0; i < 2 * LazyBindingMap.LAZY_CUTOFF; i++) { + final TopLevelList item = new TopLevelListBuilder().setName(String.valueOf(i)).build(); + map.put(item.key(), item); + } + + TOP = new TopBuilder().setTopLevelList(map).build(); + } + + @Test + public void testSimpleEquals() { + final Top actual = prepareData(); + assertThat(actual.getTopLevelList(), instanceOf(LazyBindingMap.class)); + // AbstractMap.equals() goes through its entrySet and performs lookup for each key, hence it is excercising + // primarily LookupState + assertEquals(TOP, actual); + } + + @Test + public void testEqualEntrySet() { + final Top actual = prepareData(); + // Check equality based on entry set. This primarily exercises IterState + assertEquals(TOP.getTopLevelList().entrySet(), actual.getTopLevelList().entrySet()); + } + + @Test + public void testEqualKeySet() { + final Top actual = prepareData(); + // Check equality based on key set. This primarily exercises IterState + assertEquals(TOP.getTopLevelList().keySet(), actual.getTopLevelList().keySet()); + } + + @Test + public void testIterKeySetLookup() { + final Top actual = prepareData(); + // Forces IterState but then switches to key lookups + assertTrue(actual.getTopLevelList().keySet().containsAll(TOP.getTopLevelList().keySet())); + } + + @Test + public void testIterEntrySetLookup() { + final Top actual = prepareData(); + // Forces IterState but then switches to value lookups + assertTrue(actual.getTopLevelList().entrySet().containsAll(TOP.getTopLevelList().entrySet())); + } + + @Test + public void testIterValueIteration() { + assertSameIteratorObjects(prepareData().getTopLevelList().values()); + } + + @Test + public void testLookupValueIteration() { + final Map list = prepareData().getTopLevelList(); + // Force lookup state instantiation + assertFalse(list.containsKey(new TopLevelListKey("blah"))); + + assertSameIteratorObjects(list.values()); + } + + @Test + public void testIterKeysetIteration() { + assertSameIteratorObjects(prepareData().getTopLevelList().keySet()); + } + + @Test + public void testLookupKeysetIteration() { + final Map list = prepareData().getTopLevelList(); + // Force lookup state instantiation + assertFalse(list.containsKey(new TopLevelListKey("blah"))); + + assertSameIteratorObjects(list.keySet()); + } + + private static void assertSameIteratorObjects(final Collection collection) { + final Iterator iter1 = collection.iterator(); + final Iterator iter2 = collection.iterator(); + + while (iter1.hasNext()) { + // Both iterators should return same values + assertSame(iter1.next(), iter2.next()); + } + assertFalse(iter2.hasNext()); + } + + @Test + public void testIterSameViews() { + final Map list = prepareData().getTopLevelList(); + assertSame(list.values(), list.values()); + assertSame(list.keySet(), list.keySet()); + assertSame(list.entrySet(), list.entrySet()); + } + + @Test + public void testLookupSameViews() { + final Map list = prepareData().getTopLevelList(); + // Force lookup state instantiation + assertFalse(list.containsKey(new TopLevelListKey("blah"))); + + // Careful now ... first compare should end up changing the iteration of keyset/entryset + final Set keySet1 = list.keySet(); + final Set keySet2 = list.keySet(); + final Set> entrySet1 = list.entrySet(); + final Set> entrySet2 = list.entrySet(); + + // .. right here ... + assertSame(list.values(), list.values()); + // ... so this should end up iterating slightly differently + assertEquals(new HashSet<>(list.values()), new HashSet<>(list.values())); + + // ... and as we do not reuse keyset/entryset, we need to run full compare + assertEquals(keySet1, keySet2); + assertEquals(keySet1, new HashSet<>(keySet2)); + assertEquals(entrySet1, entrySet2); + assertEquals(entrySet1, new HashSet<>(entrySet2)); + } + + @Test + public void testIterSameSize() { + final Map list = prepareData().getTopLevelList(); + // Force lookup state instantiation + assertFalse(list.containsKey(new TopLevelListKey("blah"))); + + assertEquals(list.size(), list.entrySet().size()); + assertEquals(list.size(), list.keySet().size()); + assertEquals(list.size(), list.values().size()); + } + + @Test + public void testLookupSameSize() { + final Map list = prepareData().getTopLevelList(); + assertEquals(list.size(), list.entrySet().size()); + assertEquals(list.size(), list.keySet().size()); + assertEquals(list.size(), list.values().size()); + } + + @Test + public void testImmutableThrows() { + final Map list = prepareData().getTopLevelList(); + // Various asserts for completeness' sake + assertThrows(UnsupportedOperationException.class, () -> list.clear()); + assertThrows(UnsupportedOperationException.class, () -> list.remove(null)); + assertThrows(UnsupportedOperationException.class, () -> list.putAll(null)); + } + + @Test + public void testLookupContainsValueThrows() { + final Map list = prepareData().getTopLevelList(); + assertThrows(NullPointerException.class, () -> list.containsValue(null)); + assertThrows(ClassCastException.class, () -> list.containsValue(mock(DataObject.class))); + } + + @Test + public void testLookupContainsKeyThrows() { + final Map list = prepareData().getTopLevelList(); + assertThrows(NullPointerException.class, () -> list.containsKey(null)); + assertThrows(ClassCastException.class, () -> list.containsKey(mock(Identifiable.class))); + } + + @Test + public void testLookupKey() { + final Map list = prepareData().getTopLevelList(); + for (TopLevelListKey key : TOP.getTopLevelList().keySet()) { + assertTrue(list.containsKey(key)); + } + + assertFalse(list.containsKey(new TopLevelListKey("blah"))); + } + + @Test + public void testLookupValue() { + final Map list = prepareData().getTopLevelList(); + for (TopLevelList val : TOP.getTopLevelList().values()) { + assertTrue(list.containsValue(val)); + } + + assertFalse(list.containsValue(new TopLevelListBuilder().setName("blah").build())); + + // We checked this key, but this is a different object + assertFalse(list.containsValue(new TopLevelListBuilder(TOP.getTopLevelList().values().iterator().next()) + .setNestedList(List.of(new NestedListBuilder().setName("foo").build())) + .build())); + } + + private Top prepareData() { + return thereAndBackAgain(InstanceIdentifier.create(Top.class), TOP); + } +} -- 2.36.6