nizhikov commented on code in PR #13662: URL: https://github.com/apache/ignite/pull/13662#discussion_r4247201734
########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/CopyOnWriteIntMap.java: ########## @@ -0,0 +1,165 @@ +/* + * 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.ignite.internal.util.collection; + +import java.util.AbstractCollection; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.function.IntFunction; +import org.jetbrains.annotations.Nullable; + +/** + * Thread-safe {@link IntMap} for data that is looked up on hot paths but changes rarely: reads never block or box, + * every write copies the map. With a noticeable share of writes it is slower than a concurrent map. + */ +public class CopyOnWriteIntMap<V> implements IntMap<V> { + /** Current map, never modified after publication: writes replace it with a copy. */ + private volatile IntHashMap<V> map = new IntHashMap<>(); + + /** Live view over the current map. */ + private final Collection<V> vals = new AbstractCollection<V>() { + @Override public Iterator<V> iterator() { + return map.valuesIterator(); + } + + @Override public int size() { + return map.size(); + } + }; + + /** {@inheritDoc} */ + @Override public V get(int key) { + return map.get(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsKey(int key) { + return map.containsKey(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsValue(V val) { + return map.containsValue(val); + } + + /** {@inheritDoc} */ + @Override public <E extends Throwable> void forEach(EntryConsumer<V, E> act) throws E { + map.forEach(act); + } + + /** {@inheritDoc} */ + @Override public int size() { + return map.size(); + } + + /** {@inheritDoc} */ + @Override public boolean isEmpty() { + return map.isEmpty(); + } + + /** {@inheritDoc} */ + @Override public int[] keys() { + return map.keys(); + } + + /** + * {@inheritDoc} + * <p> + * The collection is weakly consistent, like {@link java.util.concurrent.ConcurrentHashMap#values()}: it reflects + * the current state, its iterator traverses the map as it was when the iterator was created and does not support + * removal. + */ + @Override public Collection<V> values() { + return vals; + } + + /** {@inheritDoc} */ + @Override public synchronized V put(int key, V val) { + IntHashMap<V> copy = map.copy(); + + V old = copy.put(key, val); + + map = copy; + + return old; + } + + /** {@inheritDoc} */ + @Override public synchronized V putIfAbsent(int key, V val) { + IntHashMap<V> map = this.map; Review Comment: Nit (style): the local `IntHashMap<V> map = this.map` shadows the field `map` (here, in `remove(int)` and `remove(int, V)`). Ignite convention is `map0` for such locals; it also avoids confusion with the `this.map = copy` write in `removeFromCopy`. ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/CopyOnWriteIntMap.java: ########## @@ -0,0 +1,165 @@ +/* + * 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.ignite.internal.util.collection; + +import java.util.AbstractCollection; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.function.IntFunction; +import org.jetbrains.annotations.Nullable; + +/** + * Thread-safe {@link IntMap} for data that is looked up on hot paths but changes rarely: reads never block or box, + * every write copies the map. With a noticeable share of writes it is slower than a concurrent map. + */ +public class CopyOnWriteIntMap<V> implements IntMap<V> { + /** Current map, never modified after publication: writes replace it with a copy. */ + private volatile IntHashMap<V> map = new IntHashMap<>(); + + /** Live view over the current map. */ + private final Collection<V> vals = new AbstractCollection<V>() { + @Override public Iterator<V> iterator() { + return map.valuesIterator(); + } + + @Override public int size() { + return map.size(); + } + }; + + /** {@inheritDoc} */ + @Override public V get(int key) { + return map.get(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsKey(int key) { + return map.containsKey(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsValue(V val) { + return map.containsValue(val); + } + + /** {@inheritDoc} */ + @Override public <E extends Throwable> void forEach(EntryConsumer<V, E> act) throws E { + map.forEach(act); + } + + /** {@inheritDoc} */ + @Override public int size() { + return map.size(); + } + + /** {@inheritDoc} */ + @Override public boolean isEmpty() { + return map.isEmpty(); + } + + /** {@inheritDoc} */ + @Override public int[] keys() { + return map.keys(); + } + + /** + * {@inheritDoc} + * <p> + * The collection is weakly consistent, like {@link java.util.concurrent.ConcurrentHashMap#values()}: it reflects + * the current state, its iterator traverses the map as it was when the iterator was created and does not support + * removal. + */ + @Override public Collection<V> values() { + return vals; + } + + /** {@inheritDoc} */ + @Override public synchronized V put(int key, V val) { + IntHashMap<V> copy = map.copy(); + + V old = copy.put(key, val); + + map = copy; + + return old; + } + + /** {@inheritDoc} */ + @Override public synchronized V putIfAbsent(int key, V val) { + IntHashMap<V> map = this.map; + + return map.containsKey(key) ? map.get(key) : put(key, val); + } + + /** {@inheritDoc} */ + @Override public synchronized @Nullable V computeIfAbsent(int key, IntFunction<? extends V> mappingFunction) { Review Comment: Minor: `computeIfAbsent` takes the lock even when the key is already present, unlike the `containsKey` + `putIfAbsent` pattern used in `TcpCommunicationMetricsListener`. A lock-free fast path before the synchronized part (`V v = map.get(key); if (v != null) return v;`) would keep future hot-path callers from serializing on reads. No current callers, so optional. ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/CopyOnWriteIntMap.java: ########## @@ -0,0 +1,165 @@ +/* + * 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.ignite.internal.util.collection; + +import java.util.AbstractCollection; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.function.IntFunction; +import org.jetbrains.annotations.Nullable; + +/** + * Thread-safe {@link IntMap} for data that is looked up on hot paths but changes rarely: reads never block or box, + * every write copies the map. With a noticeable share of writes it is slower than a concurrent map. + */ +public class CopyOnWriteIntMap<V> implements IntMap<V> { + /** Current map, never modified after publication: writes replace it with a copy. */ + private volatile IntHashMap<V> map = new IntHashMap<>(); + + /** Live view over the current map. */ + private final Collection<V> vals = new AbstractCollection<V>() { + @Override public Iterator<V> iterator() { + return map.valuesIterator(); + } + + @Override public int size() { + return map.size(); + } + }; + + /** {@inheritDoc} */ + @Override public V get(int key) { + return map.get(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsKey(int key) { + return map.containsKey(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsValue(V val) { + return map.containsValue(val); + } + + /** {@inheritDoc} */ + @Override public <E extends Throwable> void forEach(EntryConsumer<V, E> act) throws E { + map.forEach(act); + } + + /** {@inheritDoc} */ + @Override public int size() { + return map.size(); + } + + /** {@inheritDoc} */ + @Override public boolean isEmpty() { + return map.isEmpty(); + } + + /** {@inheritDoc} */ + @Override public int[] keys() { + return map.keys(); + } + + /** + * {@inheritDoc} + * <p> + * The collection is weakly consistent, like {@link java.util.concurrent.ConcurrentHashMap#values()}: it reflects Review Comment: Nit (docs): the javadoc says the collection is "weakly consistent, like `ConcurrentHashMap#values()`" but then describes snapshot semantics. The iterator is a snapshot, which is stronger than weakly consistent. Suggest: "the iterator traverses a snapshot taken at creation time and does not support removal". ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/IntHashMap.java: ########## @@ -230,11 +285,7 @@ public IntHashMap(IntMap<? extends V> other) { /** {@inheritDoc} */ @Override public void clear() { Review Comment: Note (positive, but outside the ticket scope): `clear()` previously zeroed both thresholds, so the first `put` after `clear` doubled the table to 16 slots. Routing through `init` fixes that and `shouldNotResizeOnFirstPut` covers it. Worth a line in the PR description since it is a behavior change unrelated to boxing. ########## modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheSharedContext.java: ########## @@ -136,7 +136,7 @@ public class GridCacheSharedContext<K, V> { private PartitionsEvictManager evictMgr; /** Cache contexts map. */ - private final ConcurrentHashMap<Integer, GridCacheContext<K, V>> ctxMap; + private final CopyOnWriteIntMap<GridCacheContext<K, V>> ctxMap = new CopyOnWriteIntMap<>(); Review Comment: Nit: in `removeCacheContext` (line 541, outside the diff) `ctxMap.remove(cacheId, cacheCtx)` now passes a raw `GridCacheContext` to a generic `V` parameter, producing an unchecked warning that the old `ConcurrentHashMap.remove(Object, Object)` call did not. Either type the parameter as `GridCacheContext<K, V>` or add `@SuppressWarnings("unchecked")` as `addCacheContext` does. ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/IntHashMap.java: ########## @@ -116,6 +133,44 @@ public IntHashMap(IntMap<? extends V> other) { other.forEach(this::put); } + /** @return Iterator over the values without copying them. The map must not be modified while iterating. */ + Iterator<V> valuesIterator() { + Entry<V>[] entries = this.entries; + + return new Iterator<V>() { + /** Index of the next non-empty slot. */ + private int idx = nextIdx(0); + + @Override public boolean hasNext() { + return idx < entries.length; + } + + @Override public V next() { + if (idx >= entries.length) + throw new NoSuchElementException(); + + V val = entries[idx].val; + + idx = nextIdx(idx + 1); + + return val; + } + + /** @return Index of the first non-empty slot starting from the given one. */ + private int nextIdx(int from) { + while (from < entries.length && entries[from] == null) + from++; + + return from; + } + }; + } + + /** @return Shallow copy of the same table size: the entries are immutable and shared with this map. */ + IntHashMap<V> copy() { + return new IntHashMap<>(Arrays.copyOf(entries, entries.length), size); Review Comment: Nit: `Arrays.copyOf(entries, entries.length)` is `entries.clone()`. ########## modules/core/src/test/java/org/apache/ignite/internal/util/collection/CopyOnWriteIntMapTest.java: ########## @@ -0,0 +1,176 @@ +/* + * 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.ignite.internal.util.collection; + +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.Map; +import java.util.Random; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertTrue; + +/** + * Test for copy-on-write int map. Every write copies the map, so the sizes are kept small on purpose. + */ Review Comment: Optional: this test does not extend `AbstractBaseIntMapTest` like `IntHashMapTest` and `IntRWHashMapTest`. The class comment explains why (the base runs 10M ops against a 1M-key space, far too slow for copy-on-write), so fine as is. If the base ever gets a size parameter, `compareWithReferenceImplementation` and `putIfAbsent` could be shared. ########## modules/core/src/main/java/org/apache/ignite/spi/communication/tcp/TcpCommunicationMetricsListener.java: ########## @@ -430,28 +424,8 @@ public void onNodeLeft(Object consistentId) { private void updateMessageTypeMap(Message msg) { short typeId = msg.directType(); - Map<Short, String> msgTypeMap0 = msgTypeMap; - - if (msgTypeMap0 == null || !msgTypeMap0.containsKey(typeId)) { - synchronized (msgTypeMapMux) { - if (msgTypeMap == null) { - msgTypeMap0 = new HashMap<>(); - - msgTypeMap0.put(typeId, msg.getClass().getName()); - - msgTypeMap = msgTypeMap0; - } - else { - if (!msgTypeMap.containsKey(typeId)) { - msgTypeMap0 = new HashMap<>(msgTypeMap); - - msgTypeMap0.put(typeId, msg.getClass().getName()); - - msgTypeMap = msgTypeMap0; - } - } - } - } + if (!msgTypeMap.containsKey(typeId)) Review Comment: Nit (docs): `if (!containsKey) putIfAbsent(...)` looks redundant at first glance since `putIfAbsent` re-checks under the lock. A one-line comment that the outer check keeps the hot path lock-free would help the next reader. ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/CopyOnWriteIntMap.java: ########## @@ -0,0 +1,165 @@ +/* + * 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.ignite.internal.util.collection; + +import java.util.AbstractCollection; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.function.IntFunction; +import org.jetbrains.annotations.Nullable; + +/** + * Thread-safe {@link IntMap} for data that is looked up on hot paths but changes rarely: reads never block or box, + * every write copies the map. With a noticeable share of writes it is slower than a concurrent map. + */ +public class CopyOnWriteIntMap<V> implements IntMap<V> { + /** Current map, never modified after publication: writes replace it with a copy. */ + private volatile IntHashMap<V> map = new IntHashMap<>(); + + /** Live view over the current map. */ + private final Collection<V> vals = new AbstractCollection<V>() { + @Override public Iterator<V> iterator() { + return map.valuesIterator(); + } + + @Override public int size() { + return map.size(); + } + }; + + /** {@inheritDoc} */ + @Override public V get(int key) { + return map.get(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsKey(int key) { + return map.containsKey(key); + } + + /** {@inheritDoc} */ + @Override public boolean containsValue(V val) { + return map.containsValue(val); + } + + /** {@inheritDoc} */ + @Override public <E extends Throwable> void forEach(EntryConsumer<V, E> act) throws E { + map.forEach(act); + } + + /** {@inheritDoc} */ + @Override public int size() { + return map.size(); + } + + /** {@inheritDoc} */ + @Override public boolean isEmpty() { + return map.isEmpty(); + } + + /** {@inheritDoc} */ + @Override public int[] keys() { + return map.keys(); + } + + /** + * {@inheritDoc} + * <p> + * The collection is weakly consistent, like {@link java.util.concurrent.ConcurrentHashMap#values()}: it reflects + * the current state, its iterator traverses the map as it was when the iterator was created and does not support + * removal. + */ + @Override public Collection<V> values() { + return vals; + } + + /** {@inheritDoc} */ + @Override public synchronized V put(int key, V val) { + IntHashMap<V> copy = map.copy(); + + V old = copy.put(key, val); + + map = copy; + + return old; + } + + /** {@inheritDoc} */ + @Override public synchronized V putIfAbsent(int key, V val) { + IntHashMap<V> map = this.map; + + return map.containsKey(key) ? map.get(key) : put(key, val); + } + + /** {@inheritDoc} */ + @Override public synchronized @Nullable V computeIfAbsent(int key, IntFunction<? extends V> mappingFunction) { + // The default implementation is a lookup followed by a put, the lock makes the pair atomic. + return IntMap.super.computeIfAbsent(key, mappingFunction); + } + + /** {@inheritDoc} */ + @Override public synchronized V remove(int key) { + IntHashMap<V> map = this.map; + + return map.containsKey(key) ? removeFromCopy(map, key) : null; + } + + /** + * Removes the mapping if the key is mapped to the given value. + * + * @param key Key. + * @param val Expected value. + * @return {@code True} if the mapping was removed. + */ + public synchronized boolean remove(int key, V val) { Review Comment: Minor (API): `remove(int, V)` exists only on the concrete class, which forces `GridCacheSharedContext.ctxMap` to be typed as `CopyOnWriteIntMap` instead of `IntMap`. Consider adding `remove(int key, V val)` as a default method on `IntMap` so all three implementations share the API. ########## modules/core/src/main/java/org/apache/ignite/internal/util/collection/IntHashMap.java: ########## @@ -116,6 +133,44 @@ public IntHashMap(IntMap<? extends V> other) { other.forEach(this::put); } + /** @return Iterator over the values without copying them. The map must not be modified while iterating. */ Review Comment: Nit (docs): "The map must not be modified while iterating" is accurate for the copy-on-write use, but the iterator captures the `entries` array, so in-place modification would silently yield stale or duplicate values rather than fail. Say so, or note the method is intended only for `CopyOnWriteIntMap`. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
