You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@baremaps.apache.org by bc...@apache.org on 2023/01/16 22:18:25 UTC
[incubator-baremaps] branch simplify-geometries updated (8ea5b0df -> 493448c8)
This is an automated email from the ASF dual-hosted git repository.
bchapuis pushed a change to branch simplify-geometries
in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
omit 8ea5b0df Clean benchmarks
new 493448c8 Clean benchmarks
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (8ea5b0df)
\
N -- N -- N refs/heads/simplify-geometries (493448c8)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../baremaps/benchmarks/DataMapBenchmark.java | 88 ++++++++--------------
.../baremaps/benchmarks/MemoryBenchmark.java | 4 +-
.../collection/algorithm/BinarySearch.java | 21 +++---
.../baremaps/collection/type/PairDataType.java | 4 +-
.../apache/baremaps/collection/DataMapTest.java | 4 +-
5 files changed, 46 insertions(+), 75 deletions(-)
[incubator-baremaps] 01/01: Clean benchmarks
Posted by bc...@apache.org.
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 <bc...@gmail.com>
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> {