From: Robert Varga Date: Sat, 6 Nov 2021 13:31:20 +0000 (+0100) Subject: Use ImmutableSortedSet for small ImmutableUnsignedLongSets X-Git-Tag: v4.0.6~3 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=318c0bbc4ecfdf532a4cc3e219508a7c5744d160 Use ImmutableSortedSet for small ImmutableUnsignedLongSets This adds a bit of indirection, but for a few entries this ends up using arrays instead of an RB tree, offering better density. JIRA: CONTROLLER-2012 Change-Id: I09714c6bf3272946f6cee4360f80a106453d0e61 Signed-off-by: Robert Varga --- diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java index e6c900b0f8..47b8a8b015 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java @@ -8,9 +8,12 @@ package org.opendaylight.controller.cluster.datastore.utils; import com.google.common.annotations.Beta; +import com.google.common.collect.ImmutableSortedSet; import java.io.DataInput; import java.io.DataOutput; import java.io.IOException; +import java.util.ArrayList; +import java.util.NavigableSet; import java.util.TreeSet; import org.eclipse.jdt.annotation.NonNull; import org.opendaylight.yangtools.concepts.Immutable; @@ -18,14 +21,24 @@ import org.opendaylight.yangtools.concepts.WritableObject; @Beta public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements Immutable, WritableObject { - private static final @NonNull ImmutableUnsignedLongSet EMPTY = new ImmutableUnsignedLongSet(new TreeSet<>()); + // Do not all + private static final int ARRAY_MAX_ELEMENTS = 4096; - private ImmutableUnsignedLongSet(final TreeSet ranges) { + private static final @NonNull ImmutableUnsignedLongSet EMPTY = + new ImmutableUnsignedLongSet(ImmutableSortedSet.of()); + + private ImmutableUnsignedLongSet(final NavigableSet ranges) { super(ranges); } - static @NonNull ImmutableUnsignedLongSet of(final TreeSet ranges) { - return ranges.isEmpty() ? EMPTY : new ImmutableUnsignedLongSet(ranges); + static @NonNull ImmutableUnsignedLongSet copyOf(final MutableUnsignedLongSet mutable) { + if (mutable.isEmpty()) { + return of(); + } + if (mutable.size() <= ARRAY_MAX_ELEMENTS) { + return new ImmutableUnsignedLongSet(ImmutableSortedSet.copyOfSorted(mutable.trustedRanges())); + } + return new ImmutableUnsignedLongSet(new TreeSet<>(mutable.trustedRanges())); } public static @NonNull ImmutableUnsignedLongSet of() { @@ -46,9 +59,18 @@ public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements I return EMPTY; } - final var ranges = new TreeSet(); - for (int i = 0; i < size; ++i) { - ranges.add(Entry.readUnsigned(in)); + final NavigableSet ranges; + if (size <= ARRAY_MAX_ELEMENTS) { + final var entries = new ArrayList(size); + for (int i = 0; i < size; ++i) { + entries.add(Entry.readUnsigned(in)); + } + ranges = ImmutableSortedSet.copyOf(entries); + } else { + ranges = new TreeSet<>(); + for (int i = 0; i < size; ++i) { + ranges.add(Entry.readUnsigned(in)); + } } return new ImmutableUnsignedLongSet(ranges); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java index e8e479c798..e455f90d89 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java @@ -27,7 +27,7 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut @Override public ImmutableUnsignedLongSet immutableCopy() { - return ImmutableUnsignedLongSet.of(copyRanges()); + return ImmutableUnsignedLongSet.copyOf(this); } public void add(final long longBits) { diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java index 4d4b99bbc9..466c0276cd 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java @@ -7,13 +7,11 @@ */ package org.opendaylight.controller.cluster.datastore.utils; -import static com.google.common.base.Verify.verify; import static java.util.Objects.requireNonNull; import com.google.common.annotations.Beta; import com.google.common.annotations.VisibleForTesting; import com.google.common.base.MoreObjects; -import com.google.common.collect.BoundType; import com.google.common.collect.Collections2; import com.google.common.collect.Range; import com.google.common.collect.RangeSet; @@ -60,12 +58,6 @@ abstract class UnsignedLongSet { return new Entry(lowerBits, upperBits); } - static Entry of(final Range range) { - verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN, - "Unexpected range %s", range); - return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1); - } - @VisibleForTesting public UnsignedLong lower() { return UnsignedLong.fromLongBits(lowerBits); @@ -136,13 +128,13 @@ abstract class UnsignedLongSet { } } - // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that - // for a contains() operation we just need the first headSet() entry. For insert operations we just update either - // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they - // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry. - private final @NonNull TreeSet ranges; + // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means + // that for a contains() operation we just need the first headSet() entry. For insert operations we just update + // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and + // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry. + private final @NonNull NavigableSet ranges; - UnsignedLongSet(final TreeSet ranges) { + UnsignedLongSet(final NavigableSet ranges) { this.ranges = requireNonNull(ranges); } @@ -197,11 +189,7 @@ abstract class UnsignedLongSet { public abstract @NonNull ImmutableUnsignedLongSet immutableCopy(); public final @NonNull MutableUnsignedLongSet mutableCopy() { - return new MutableUnsignedLongSet(copyRanges()); - } - - final @NonNull TreeSet copyRanges() { - return new TreeSet<>(Collections2.transform(ranges, Entry::copy)); + return new MutableUnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy))); } public final @NonNull NavigableSet ranges() { diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java index 1a67547722..af71c42631 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java @@ -10,15 +10,24 @@ package org.opendaylight.controller.cluster.datastore.utils; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotEquals; +import static org.junit.Assert.assertNotSame; +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.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.DataInputStream; +import java.io.DataOutput; import java.io.DataOutputStream; import java.io.IOException; import org.junit.Test; +import org.junit.runner.RunWith; +import org.mockito.junit.MockitoJUnitRunner; +@RunWith(MockitoJUnitRunner.StrictStubs.class) public class UnsignedLongSetTest { @Test public void testOperations() { @@ -86,4 +95,42 @@ public class UnsignedLongSetTest { set.add(3); assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString()); } + + @Test + public void testEmptyCopy() { + final var orig = MutableUnsignedLongSet.of(); + assertSame(ImmutableUnsignedLongSet.of(), orig.immutableCopy()); + final var copy = orig.mutableCopy(); + assertEquals(orig, copy); + assertNotSame(orig, copy); + } + + @Test + public void testMutableCopy() { + final var orig = MutableUnsignedLongSet.of(); + orig.add(-1); + assertEquals("MutableUnsignedLongSet{span=[18446744073709551615..18446744073709551615], size=1}", + orig.toString()); + + final var copy = orig.mutableCopy(); + assertEquals(orig, copy); + assertNotSame(orig, copy); + + orig.add(-2); + assertNotEquals(orig, copy); + assertEquals("MutableUnsignedLongSet{span=[18446744073709551614..18446744073709551615], size=1}", + orig.toString()); + } + + @Test + public void testWriteRangesTo() throws IOException { + ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 0); + } + + @Test + public void testWriteRangesToViolation() { + final var ex = assertThrows(IOException.class, + () -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1)); + assertEquals("Mismatched size: expected 0, got 1", ex.getMessage()); + } }