This is an automated email from the ASF dual-hosted git repository.
dcapwell pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
The following commit(s) were added to refs/heads/trunk by this push:
new 3c9b3077 Accord: Topology serializer has a lot of repeated data, can
dedup to shrink the cost
3c9b3077 is described below
commit 3c9b3077df1c74a14d8fe8dc58fb3f61b8257236
Author: David Capwell <dcapw...@apple.com>
AuthorDate: Thu Jul 10 20:04:55 2025 -0700
Accord: Topology serializer has a lot of repeated data, can dedup to shrink
the cost
patch by David Capwell; reviewed by Benedict Elliott Smith for
CASSANDRA-20715
---
.../src/main/java/accord/topology/Topology.java | 9 ++++-
.../main/java/accord/topology/TopologyManager.java | 15 ++++++++
.../src/main/java/accord/utils/SortedArrays.java | 32 ++++++++++++++++
.../test/java/accord/utils/SortedArraysTest.java | 43 ++++++++++++++++++++++
4 files changed, 97 insertions(+), 2 deletions(-)
diff --git a/accord-core/src/main/java/accord/topology/Topology.java
b/accord-core/src/main/java/accord/topology/Topology.java
index 3df0d750..00658466 100644
--- a/accord-core/src/main/java/accord/topology/Topology.java
+++ b/accord-core/src/main/java/accord/topology/Topology.java
@@ -26,7 +26,6 @@ import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Objects;
-import java.util.Set;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Predicate;
@@ -183,6 +182,12 @@ public class Topology
this.supersetIndexes = supersetIndexes;
}
+ @VisibleForTesting
+ public Topology withEpoch(long epoch)
+ {
+ return new Topology(global, epoch, shards, ranges, staleNodes,
nodeIds, nodeLookup, subsetOfRanges, supersetIndexes);
+ }
+
public Topology global()
{
return global == null ? this : global;
@@ -659,7 +664,7 @@ public class Topology
return subsetOfRanges;
}
- public Set<Id> staleIds()
+ public SortedArrayList<Id> staleIds()
{
return staleNodes;
}
diff --git a/accord-core/src/main/java/accord/topology/TopologyManager.java
b/accord-core/src/main/java/accord/topology/TopologyManager.java
index fc30ef31..521c8a4b 100644
--- a/accord-core/src/main/java/accord/topology/TopologyManager.java
+++ b/accord-core/src/main/java/accord/topology/TopologyManager.java
@@ -25,6 +25,7 @@ import java.util.BitSet;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
+import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.Executor;
@@ -937,6 +938,20 @@ public class TopologyManager
}
}
+ @Override
+ public boolean equals(Object o)
+ {
+ if (o == null || getClass() != o.getClass()) return false;
+ TopologyRange that = (TopologyRange) o;
+ return min == that.min && current == that.current && firstNonEmpty
== that.firstNonEmpty && Objects.equals(topologies, that.topologies);
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return Objects.hash(min, current, firstNonEmpty, topologies);
+ }
+
@Override
public String toString()
{
diff --git a/accord-core/src/main/java/accord/utils/SortedArrays.java
b/accord-core/src/main/java/accord/utils/SortedArrays.java
index cef9b183..3199207c 100644
--- a/accord-core/src/main/java/accord/utils/SortedArrays.java
+++ b/accord-core/src/main/java/accord/utils/SortedArrays.java
@@ -1793,4 +1793,36 @@ public class SortedArrays
values[i] = values[j];
values[j] = t;
}
+
+ public static <T extends Comparable<? super T>> SimpleBitSet
toSimpleBitSet(SortedArrays.SortedArrayList<T> superset,
+
SortedArrays.SortedArrayList<T> subset)
+ {
+ SimpleBitSet bitSet = new SimpleBitSet(superset.size());
+ int subsetIndex = 0;
+ for (int i = 0; i < superset.size(); i++)
+ {
+ long ri = SortedArrays.findNextIntersection(superset.array, i,
subset.array, subsetIndex);
+ if (ri < 0)
+ break;
+ i = (int) (ri);
+ subsetIndex = (int) (ri >>> 32);
+
+ bitSet.set(i);
+ }
+ Invariants.require(bitSet.getSetBitCount() <= subset.size(),
"Generated bit set is larger than the subset!");
+ return bitSet;
+ }
+
+ public static <T extends Comparable<? super T>>
SortedArrays.SortedArrayList<T>
fromSimpleBitSet(SortedArrays.SortedArrayList<T> superset,
+
SimpleBitSet bitSet,
+
IntFunction<T[]> alloc)
+ {
+ SortedArrays.SortedArrayList.Builder<T> builder = new
SortedArrays.SortedArrayList.Builder<>(alloc.apply(bitSet.getSetBitCount()));
+ for (int i = bitSet.firstSetBit(); i >= 0 ; i = bitSet.nextSetBit(i +
1))
+ {
+ if (bitSet.get(i))
+ builder.add(superset.get(i));
+ }
+ return builder.build();
+ }
}
diff --git a/accord-core/src/test/java/accord/utils/SortedArraysTest.java
b/accord-core/src/test/java/accord/utils/SortedArraysTest.java
index 23977f55..d4c7c1de 100644
--- a/accord-core/src/test/java/accord/utils/SortedArraysTest.java
+++ b/accord-core/src/test/java/accord/utils/SortedArraysTest.java
@@ -26,6 +26,7 @@ import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
+import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
@@ -33,6 +34,8 @@ import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.Stream;
+import accord.utils.SortedArrays.SortedArrayList;
+
import static accord.utils.ArrayBuffers.uncached;
import static accord.utils.Property.qt;
import static accord.utils.Utils.toArray;
@@ -315,6 +318,46 @@ class SortedArraysTest
});
}
+ @Test
+ public void bitsetSerde()
+ {
+ qt().forAll(simpleIntList(), Gens.random()).check((expected, rs) -> {
+ testSerde(expected, expected);
+
+ if (expected.isEmpty()) return;
+ Gen<SortedArrayList<Integer>> subsetGen =
Gens.select(expected).map(l -> {
+ l = new ArrayList<>(l); // its immutable; make it mutable
+ l.sort(Comparator.naturalOrder());
+ return new SortedArrayList<>(l.toArray(Integer[]::new));
+ });
+ for (int i = 0; i < 10; i++)
+ {
+ var subset = subsetGen.next(rs);
+ testSerde(expected, subset);
+ }
+ });
+ }
+
+ private static void testSerde(SortedArrayList<Integer> expected,
SortedArrayList<Integer> subset)
+ {
+ var serialize = SortedArrays.toSimpleBitSet(expected, subset);
+ Assertions.assertEquals(subset.size(), serialize.getSetBitCount());
+ SortedArrayList<Integer> read =
SortedArrays.fromSimpleBitSet(expected, serialize, Integer[]::new);
+ Assertions.assertEquals(subset, read);
+ }
+
+ private static Gen<SortedArrayList<Integer>> simpleIntList()
+ {
+ return Gens.arrays(Integer.class, Gens.ints().all())
+ .unique()
+ .ofSizeBetween(0, 1 << 9)
+ .map(a -> {
+ Arrays.sort(a);
+ return a;
+ })
+ .map(SortedArrayList::new);
+ }
+
private static int indexOfNth(String original, String search, int n)
{
String str = original;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
