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 b66ee3c7fb51fea0e6ff49c3974cb396fbc10c8b Author: Bertil Chapuis <[email protected]> AuthorDate: Mon Jul 3 15:39:47 2023 +0200 Add jagged data structure --- .../baremaps/benchmarks/DataMapBenchmark.java | 25 ++- .../database/collection/JaggedDataMap.java | 190 +++++++++++++++++++++ .../java/org/apache/baremaps/utils/ArrayUtils.java | 76 +++++++++ .../org/apache/baremaps/database/DataMapTest.java | 4 +- 4 files changed, 288 insertions(+), 7 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 1d5e0af0..91d8318c 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 @@ -15,11 +15,8 @@ package org.apache.baremaps.benchmarks; import java.util.concurrent.TimeUnit; - -import org.apache.baremaps.database.collection.AppendOnlyBuffer; -import org.apache.baremaps.database.collection.DataMap; -import org.apache.baremaps.database.collection.MemoryAlignedDataMap; -import org.apache.baremaps.database.collection.MonotonicDataMap; +import org.apache.baremaps.database.collection.*; +import org.apache.baremaps.database.collection.JaggedDataMap; import org.apache.baremaps.database.memory.OffHeapMemory; import org.apache.baremaps.database.type.LongDataType; import org.openjdk.jmh.annotations.*; @@ -32,7 +29,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> map, long n) { for (long i = 0; i < n; i++) { @@ -46,6 +43,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/database/collection/JaggedDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/JaggedDataMap.java new file mode 100644 index 00000000..6b5fdd23 --- /dev/null +++ b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/JaggedDataMap.java @@ -0,0 +1,190 @@ +/* + * Licensed 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.baremaps.database.collection; + +import java.util.Arrays; +import java.util.Iterator; +import java.util.Map; +import java.util.stream.IntStream; +import org.apache.baremaps.stream.StreamUtils; + +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..bbcf9699 --- /dev/null +++ b/baremaps-core/src/main/java/org/apache/baremaps/utils/ArrayUtils.java @@ -0,0 +1,76 @@ +/* + * Licensed 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.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/database/DataMapTest.java b/baremaps-core/src/test/java/org/apache/baremaps/database/DataMapTest.java index a91e8bb7..2109e745 100644 --- a/baremaps-core/src/test/java/org/apache/baremaps/database/DataMapTest.java +++ b/baremaps-core/src/test/java/org/apache/baremaps/database/DataMapTest.java @@ -146,7 +146,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)); @@ -158,6 +157,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()))),
