This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch simplify-geometries in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit 493448c86e0b32b06702459a9bcfbe91e34331fb Author: Bertil Chapuis <[email protected]> AuthorDate: Mon Jan 16 12:30:12 2023 +0100 Clean benchmarks --- ...DataMapBenchmark.java => DataMapBenchmark.java} | 55 ++++++++-------- ...gDataMapBenchmark.java => MemoryBenchmark.java} | 4 +- .../collection/algorithm/BinarySearch.java | 75 +++++++++++++++++++++- .../baremaps/collection/type/PairDataType.java | 12 +--- 4 files changed, 104 insertions(+), 42 deletions(-) diff --git a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java similarity index 57% copy from baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java copy to baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java index 75934f62..070bb9e9 100644 --- a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java +++ b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/DataMapBenchmark.java @@ -14,26 +14,12 @@ package org.apache.baremaps.benchmarks; -import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; -import java.nio.file.Paths; import java.util.concurrent.TimeUnit; -import org.apache.baremaps.collection.DataMap; -import org.apache.baremaps.collection.MemoryAlignedDataMap; -import org.apache.baremaps.collection.memory.MemoryMappedFile; +import org.apache.baremaps.collection.*; import org.apache.baremaps.collection.memory.OffHeapMemory; -import org.apache.baremaps.collection.memory.OnHeapMemory; import org.apache.baremaps.collection.type.LongDataType; -import org.openjdk.jmh.annotations.Benchmark; -import org.openjdk.jmh.annotations.BenchmarkMode; -import org.openjdk.jmh.annotations.Fork; -import org.openjdk.jmh.annotations.Measurement; -import org.openjdk.jmh.annotations.Mode; -import org.openjdk.jmh.annotations.OutputTimeUnit; -import org.openjdk.jmh.annotations.Scope; -import org.openjdk.jmh.annotations.State; -import org.openjdk.jmh.annotations.Warmup; +import org.apache.baremaps.collection.type.PairDataType; +import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.OptionsBuilder; @@ -41,11 +27,11 @@ import org.openjdk.jmh.runner.options.OptionsBuilder; @State(Scope.Benchmark) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Fork(1) -public class LongDataMapBenchmark { +public class DataMapBenchmark { private static final long N = 1 << 25; - private void benchmark(DataMap<Long> store, long n) { + private static void benchmark(DataMap<Long> store, long n) { for (long i = 0; i < n; i++) { store.put(i, i); } @@ -61,32 +47,43 @@ public class LongDataMapBenchmark { @BenchmarkMode(Mode.SingleShotTime) @Warmup(iterations = 2) @Measurement(iterations = 5) - public void onHeap() { - benchmark(new MemoryAlignedDataMap<>(new LongDataType(), new OnHeapMemory()), N); + public void memoryAlignedDataMap() { + benchmark(new MemoryAlignedDataMap<>(new LongDataType(), new OffHeapMemory()), N); } @Benchmark @BenchmarkMode(Mode.SingleShotTime) @Warmup(iterations = 2) @Measurement(iterations = 5) - public void offHeap() { - benchmark(new MemoryAlignedDataMap<>(new LongDataType(), new OffHeapMemory()), N); + public void monotonicDataMap() { + benchmark(new MonotonicDataMap<>(new AppendOnlyBuffer<>(new LongDataType())), N); + } + + @Benchmark + @BenchmarkMode(Mode.SingleShotTime) + @Warmup(iterations = 2) + @Measurement(iterations = 5) + public void monotonicPairedDataMap() { + benchmark(new MonotonicPairedDataMap<>( + new MemoryAlignedDataList<>( + new PairDataType<>(new LongDataType(), new LongDataType()), + new OffHeapMemory())), N); } @Benchmark @BenchmarkMode(Mode.SingleShotTime) @Warmup(iterations = 2) @Measurement(iterations = 5) - public void onDisk() throws IOException { - Path file = Files.createTempFile(Paths.get("."), "baremaps_", ".tmp"); - benchmark(new MemoryAlignedDataMap<>(new LongDataType(), new MemoryMappedFile(file)), - N); - Files.delete(file); + public void monotonicFixedSizeDataMap() { + benchmark(new MonotonicFixedSizeDataMap<>( + new MemoryAlignedDataList<>(new LongDataType()), + new MemoryAlignedDataList<>(new LongDataType()), + new MemoryAlignedDataList<>(new LongDataType())), N); } public static void main(String[] args) throws RunnerException { org.openjdk.jmh.runner.options.Options opt = - new OptionsBuilder().include(LongDataMapBenchmark.class.getSimpleName()).forks(1).build(); + new OptionsBuilder().include(DataMapBenchmark.class.getSimpleName()).forks(1).build(); new Runner(opt).run(); } } diff --git a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/MemoryBenchmark.java similarity index 95% rename from baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java rename to baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/MemoryBenchmark.java index 75934f62..85bb831c 100644 --- a/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/LongDataMapBenchmark.java +++ b/baremaps-benchmark/src/main/java/org/apache/baremaps/benchmarks/MemoryBenchmark.java @@ -41,7 +41,7 @@ import org.openjdk.jmh.runner.options.OptionsBuilder; @State(Scope.Benchmark) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Fork(1) -public class LongDataMapBenchmark { +public class MemoryBenchmark { private static final long N = 1 << 25; @@ -86,7 +86,7 @@ public class LongDataMapBenchmark { public static void main(String[] args) throws RunnerException { org.openjdk.jmh.runner.options.Options opt = - new OptionsBuilder().include(LongDataMapBenchmark.class.getSimpleName()).forks(1).build(); + new OptionsBuilder().include(MemoryBenchmark.class.getSimpleName()).forks(1).build(); new Runner(opt).run(); } } diff --git a/baremaps-core/src/main/java/org/apache/baremaps/collection/algorithm/BinarySearch.java b/baremaps-core/src/main/java/org/apache/baremaps/collection/algorithm/BinarySearch.java index 277088e3..4d973a97 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/collection/algorithm/BinarySearch.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/collection/algorithm/BinarySearch.java @@ -15,6 +15,7 @@ package org.apache.baremaps.collection.algorithm; import java.util.Comparator; +import java.util.function.Function; import org.apache.baremaps.collection.DataList; /** @@ -52,8 +53,8 @@ public class BinarySearch { long hi = toIndex; while (lo <= hi) { long mi = (lo + hi) >>> 1; - E v = list.get(mi); - int cmp = comparator.compare(v, value); + E e = list.get(mi); + int cmp = comparator.compare(e, value); if (cmp < 0) { lo = mi + 1; } else if (cmp > 0) { @@ -65,4 +66,74 @@ public class BinarySearch { return null; // key not found. } + /** + * Returns the value corresponding the search key, if it is contained in the list; null otherwise. + * + * @param list the list to search + * @param extractor the attribute extractor + * @param value the value to search for + * @param comparator the comparator + * @return the index of the search key + * @param <E> the type of the elements in the list + */ + public static <E, A> E binarySearchAttribute( + DataList<E> list, + Function<E, A> extractor, + A value, + Comparator<A> comparator) { + long lo = 0; + long hi = list.sizeAsLong() - 1l; + while (lo <= hi) { + long mi = (lo + hi) >>> 1; + E e = list.get(mi); + A a = extractor.apply(e); + int cmp = comparator.compare(a, value); + if (cmp < 0) { + lo = mi + 1; + } else if (cmp > 0) { + hi = mi - 1; + } else { + return e; // key found + } + } + return null; // key not found. + } + + /** + * Returns the value corresponding the search key, if it is contained in the list; null otherwise. + * + * @param list the list to search + * @param extractor the attribute extractor + * @param value the value to search for + * @param comparator the comparator + * @param fromIndex the low index + * @param toIndex the high index + * @return the index of the search key + * @param <E> the type of the elements in the list + */ + public static <E, A> E binarySearchAttribute( + DataList<E> list, + Function<E, A> extractor, + A value, + Comparator<A> comparator, + long fromIndex, + long toIndex) { + long lo = fromIndex; + long hi = toIndex; + while (lo <= hi) { + long mi = (lo + hi) >>> 1; + E e = list.get(mi); + A a = extractor.apply(e); + int cmp = comparator.compare(a, value); + if (cmp < 0) { + lo = mi + 1; + } else if (cmp > 0) { + hi = mi - 1; + } else { + return e; // key found + } + } + return null; // key not found. + } + } diff --git a/baremaps-core/src/main/java/org/apache/baremaps/collection/type/PairDataType.java b/baremaps-core/src/main/java/org/apache/baremaps/collection/type/PairDataType.java index 349cb092..f775d763 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/collection/type/PairDataType.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/collection/type/PairDataType.java @@ -30,12 +30,6 @@ public class PairDataType<L, R> extends FixedSizeDataType<Pair<L, R>> { this.right = right; } - /** {@inheritDoc} */ - @Override - public int size(Pair<L, R> value) { - return left.size() + right.size(); - } - /** {@inheritDoc} */ @Override public void write(ByteBuffer buffer, int position, Pair<L, R> value) { @@ -46,9 +40,9 @@ public class PairDataType<L, R> extends FixedSizeDataType<Pair<L, R>> { /** {@inheritDoc} */ @Override public Pair<L, R> read(ByteBuffer buffer, int position) { - L l = left.read(buffer, position); - R r = right.read(buffer, position + left.size()); - return new Pair<>(l, r); + return new Pair<>( + left.read(buffer, position), + right.read(buffer, position + left.size())); } public static class Pair<L, R> {
