This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch 681-handle-the-out-of-memory-errors in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit 36ba04ae49dda2a804f154023032d5123ca7c4c0 Author: Bertil Chapuis <[email protected]> AuthorDate: Mon Jul 3 15:39:47 2023 +0200 Add jagged data structure --- .../baremaps/benchmarks/DataMapBenchmark.java | 18 ++- .../apache/baremaps/collection/JaggedDataMap.java | 179 +++++++++++++++++++++ .../java/org/apache/baremaps/utils/ArrayUtils.java | 64 ++++++++ .../apache/baremaps/collection/DataMapTest.java | 4 +- 4 files changed, 263 insertions(+), 2 deletions(-) diff --git a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java index 8e868e19..440d4587 100644 --- a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java +++ b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java @@ -28,7 +28,7 @@ import org.openjdk.jmh.runner.options.OptionsBuilder; @Fork(1) public class DataMapBenchmark { - private static final long N = 1 << 25; + private static final long N = 1 << 24; private static void benchmark(DataMap<Long> store, long n) { for (long i = 0; i < n; i++) { @@ -42,6 +42,22 @@ public class DataMapBenchmark { } } + @Benchmark + @BenchmarkMode(Mode.SingleShotTime) + @Warmup(iterations = 2) + @Measurement(iterations = 5) + public void simpleDataMap() { + benchmark(new JaggedDataMap<>(new AppendOnlyBuffer<>(new LongDataType())), N); + } + + @Benchmark + @BenchmarkMode(Mode.SingleShotTime) + @Warmup(iterations = 2) + @Measurement(iterations = 5) + public void indexedDataMap() { + benchmark(new IndexedDataMap<>(new AppendOnlyBuffer<>(new LongDataType())), N); + } + @Benchmark @BenchmarkMode(Mode.SingleShotTime) @Warmup(iterations = 2) diff --git a/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java new file mode 100644 index 00000000..427b7209 --- /dev/null +++ b/baremaps-core/src/main/java/org/apache/baremaps/collection/JaggedDataMap.java @@ -0,0 +1,179 @@ +package org.apache.baremaps.collection; + +import org.apache.baremaps.stream.StreamUtils; + +import java.util.Arrays; +import java.util.Iterator; +import java.util.Map; +import java.util.stream.IntStream; + +public class JaggedDataMap<E> extends DataMap<E> { + + private long[][][][] index; + + private final AppendOnlyBuffer<E> values; + + /** + * Constructs a map. + * + * @param values the values + */ + public JaggedDataMap(AppendOnlyBuffer<E> values) { + this.index = new long[1<<12][][][]; + this.values = values; + } + + /** + * {@inheritDoc} + */ + @Override + public E put(Long key, E value) { + long v = key; + int i = (int) (v >>> 28) & 0xFFF; + int j = (int) (v >>> 16) & 0xFFF; + int k = (int) (v >>> 8) & 0xFF; + int l = (int) (v & 0xFF); + if (index[i] == null) { + index[i] = new long[1<<12][][]; + } + if (index[i][j] == null) { + index[i][j] = new long[1<<12][]; + } + if (index[i][j][k] == null) { + index[i][j][k] = new long[1<<8]; + Arrays.fill(index[i][j][k], -1); + } + long position = values.addPositioned(value); + index[i][j][k][l] = position; + return value; + } + + /** + * {@inheritDoc} + */ + @Override + public E get(Object key) { + long v = (Long) key; + int i = (int) (v >>> 28) & 0xFFF; + int j = (int) (v >>> 16) & 0xFFF; + int k = (int) (v >>> 8) & 0xFF; + int l = (int) (v & 0xFF); + if (index[i] == null) { + return null; + } + if (index[i][j] == null) { + return null; + } + if (index[i][j][k] == null) { + return null; + } + long position = index[i][j][k][l]; + if (position == -1) { + return null; + } + return values.read(position); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<Long> keyIterator() { + return IntStream.range(0, index.length) + .filter(i -> index[i] != null) + .mapToObj(i -> IntStream.range(0, index[i].length) + .filter(j -> index[i][j] != null) + .mapToObj(j -> IntStream.range(0, index[i][j].length) + .filter(k -> index[i][j][k] != null) + .mapToObj(k -> IntStream.range(0, index[i][j][k].length) + .filter(l -> index[i][j][k][l] != -1) + .mapToObj(l -> (long) ((i << 28) | (j << 16) | (k << 8) | l))) + .flatMap(x -> x)) + .flatMap(x -> x)) + .flatMap(x -> x) + .iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<E> valueIterator() { + return StreamUtils.stream(keyIterator()).map(this::get).iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + protected Iterator<Entry<Long, E>> entryIterator() { + return StreamUtils.stream(keyIterator()).map(key -> Map.entry(key, get(key))).iterator(); + } + + /** + * {@inheritDoc} + */ + @Override + public boolean isEmpty() { + return StreamUtils.stream(keyIterator()).findAny().isEmpty(); + } + + /** + * {@inheritDoc} + */ + @Override + public long sizeAsLong() { + return StreamUtils.stream(keyIterator()).count(); + } + + /** + * {@inheritDoc} + */ + @Override + public boolean containsKey(Object key) { + return get(key) != null; + } + + /** + * {@inheritDoc} + */ + @Override + public boolean containsValue(Object value) { + return StreamUtils.stream(valueIterator()).anyMatch(v -> v.equals(value)); + } + + /** + * {@inheritDoc} + */ + @Override + public E remove(Object key) { + long v = (Long) key; + int i = (int) (v >>> 28) & 0xFFF; + int j = (int) (v >>> 16) & 0xFFF; + int k = (int) (v >>> 8) & 0xFF; + int l = (int) (v & 0xFF); + if (index[i] == null) { + return null; + } + if (index[i][j] == null) { + return null; + } + if (index[i][j][k] == null) { + return null; + } + long position = index[i][j][k][l]; + if (position == -1) { + return null; + } + index[i][j][k][l] = -1; + return values.read(position); + } + + /** + * {@inheritDoc} + */ + @Override + public void clear() { + index = new long[1<<12][][][]; + } +} diff --git a/baremaps-core/src/main/java/org/apache/baremaps/utils/ArrayUtils.java b/baremaps-core/src/main/java/org/apache/baremaps/utils/ArrayUtils.java new file mode 100644 index 00000000..0b70db72 --- /dev/null +++ b/baremaps-core/src/main/java/org/apache/baremaps/utils/ArrayUtils.java @@ -0,0 +1,64 @@ +package org.apache.baremaps.utils; + +public class ArrayUtils { + + private ArrayUtils() { + + } + + public static Object of(int dimensions, int size) { + return switch (dimensions) { + case 1 -> d1(size); + case 2 -> d2(size); + case 3 -> d3(size); + case 4 -> d4(size); + case 5 -> d5(size); + case 6 -> d6(size); + case 7 -> d7(size); + case 8 -> d8(size); + case 9 -> d9(size); + case 10 -> d10(size); + default -> throw new IllegalArgumentException("Unsupported dimension"); + }; + } + + private static Object d1(int size) { + return new long[size]; + } + + private static Object d2(int size) { + return new long[size][]; + } + + private static Object d3(int size) { + return new long[size][][]; + } + + private static Object d4(int size) { + return new long[size][][][]; + } + + private static Object d5(int size) { + return new long[size][][][][]; + } + + private static Object d6(int size) { + return new long[size][][][][][]; + } + + private static Object d7(int size) { + return new long[size][][][][][][]; + } + + private static Object d8(int size) { + return new long[size][][][][][][][]; + } + + private static Object d9(int size) { + return new long[size][][][][][][][][]; + } + + public static Object d10(int size) { + return new long[size][][][][][][][][][]; + } +} diff --git a/baremaps-core/src/test/java/org/apache/baremaps/collection/DataMapTest.java b/baremaps-core/src/test/java/org/apache/baremaps/collection/DataMapTest.java index 7da6e68f..ed662384 100644 --- a/baremaps-core/src/test/java/org/apache/baremaps/collection/DataMapTest.java +++ b/baremaps-core/src/test/java/org/apache/baremaps/collection/DataMapTest.java @@ -145,7 +145,6 @@ class DataMapTest { assertFalse(map.isEmpty()); assertEquals(3l, map.size()); - assertEquals(10l, map.get(10l)); assertEquals(15l, map.get(15l)); assertEquals(20l, map.get(20l)); @@ -157,6 +156,9 @@ class DataMapTest { static Stream<Arguments> mapProvider() { return Stream .of( + Arguments.of( + new JaggedDataMap<>( + new AppendOnlyBuffer<>(new LongDataType(), new OffHeapMemory()))), Arguments.of( new IndexedDataMap<>( new AppendOnlyBuffer<>(new LongDataType(), new OffHeapMemory()))),
