Skip to content

Instantly share code, notes, and snippets.

@amaembo

amaembo/IteratorTest.java

Last active Aug 29, 2015
Embed
What would you like to do?
Unknown size iterator optimization
package org.sample;
import java.util.concurrent.TimeUnit;
import java.util.stream.*;
import java.util.function.*;
import java.util.*;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.annotations.*;
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(3)
@State(Scope.Benchmark)
public class IteratorTest {
@Param({ "2", "3", "5", "10",
"20", "30", "50", "100",
"200", "300", "500", "1000",
"2000", "3000", "5000", "10000",
"20000", "30000", "50000", "100000" })
private int size;
@Param({ "false", "true" })
private boolean parallel;
// Does nothing, just consumes CPU
private final Function<String, String> taskFunction = str -> str.replaceAll("(\\d+\\d+)+x", "$1");
private List<String> input;
@Setup
public void setUp() {
input = IntStream.range(0, size).mapToObj(size -> String.format("%9d", size)).collect(Collectors.toList());
}
@Benchmark
public void base(Blackhole bh) {
bh.consume(StreamSupport.stream(input.spliterator(), parallel).map(taskFunction).collect(Collectors.toList()));
}
@Benchmark
public void jdkSpliterator(Blackhole bh) {
bh.consume(StreamSupport.stream(Spliterators.spliteratorUnknownSize(input.iterator(), Spliterator.ORDERED), parallel).map(taskFunction).collect(Collectors.toList()));
}
@Benchmark
public void optimized(Blackhole bh) {
bh.consume(StreamSupport.stream(new UnknownSizeSpliterator(input.iterator()), parallel).map(taskFunction).collect(Collectors.toList()));
}
}
# JMH 1.9 (released 84 days ago)
# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe
# VM options: <none>
...
# Run complete. Total time: 00:47:47
Benchmark (parallel) (size) Mode Cnt Score Error Units
IteratorTest.base false 2 avgt 30 1.004 ± 0.004 us/op
IteratorTest.base false 3 avgt 30 1.447 ± 0.008 us/op
IteratorTest.base false 5 avgt 30 2.327 ± 0.040 us/op
IteratorTest.base false 10 avgt 30 4.543 ± 0.031 us/op
IteratorTest.base false 20 avgt 30 9.776 ± 0.091 us/op
IteratorTest.base false 30 avgt 30 14.661 ± 0.066 us/op
IteratorTest.base false 50 avgt 30 24.712 ± 0.141 us/op
IteratorTest.base false 100 avgt 30 49.237 ± 0.176 us/op
IteratorTest.base false 200 avgt 30 112.740 ± 0.845 us/op
IteratorTest.base false 300 avgt 30 198.780 ± 0.692 us/op
IteratorTest.base false 500 avgt 30 304.211 ± 1.047 us/op
IteratorTest.base false 1000 avgt 30 646.151 ± 14.511 us/op
IteratorTest.base false 2000 avgt 30 1549.555 ± 26.879 us/op
IteratorTest.base false 3000 avgt 30 2395.780 ± 31.533 us/op
IteratorTest.base false 5000 avgt 30 4118.417 ± 20.251 us/op
IteratorTest.base false 10000 avgt 30 9077.169 ± 204.281 us/op
IteratorTest.base false 20000 avgt 30 27369.616 ± 296.583 us/op
IteratorTest.base false 30000 avgt 30 44389.357 ± 412.948 us/op
IteratorTest.base false 50000 avgt 30 78305.664 ± 1655.693 us/op
IteratorTest.base false 100000 avgt 30 164270.952 ± 4617.414 us/op
IteratorTest.base true 2 avgt 30 3.096 ± 0.056 us/op
IteratorTest.base true 3 avgt 30 3.387 ± 0.030 us/op
IteratorTest.base true 5 avgt 30 5.257 ± 0.137 us/op
IteratorTest.base true 10 avgt 30 5.849 ± 0.058 us/op
IteratorTest.base true 20 avgt 30 8.280 ± 0.088 us/op
IteratorTest.base true 30 avgt 30 9.143 ± 0.187 us/op
IteratorTest.base true 50 avgt 30 11.398 ± 0.049 us/op
IteratorTest.base true 100 avgt 30 17.584 ± 0.048 us/op
IteratorTest.base true 200 avgt 30 38.073 ± 0.305 us/op
IteratorTest.base true 300 avgt 30 61.198 ± 1.181 us/op
IteratorTest.base true 500 avgt 30 96.341 ± 0.772 us/op
IteratorTest.base true 1000 avgt 30 173.775 ± 1.146 us/op
IteratorTest.base true 2000 avgt 30 471.980 ± 9.704 us/op
IteratorTest.base true 3000 avgt 30 720.277 ± 23.665 us/op
IteratorTest.base true 5000 avgt 30 1210.950 ± 10.315 us/op
IteratorTest.base true 10000 avgt 30 2468.787 ± 52.212 us/op
IteratorTest.base true 20000 avgt 30 7703.531 ± 236.184 us/op
IteratorTest.base true 30000 avgt 30 11695.593 ± 182.621 us/op
IteratorTest.base true 50000 avgt 30 20866.573 ± 716.210 us/op
IteratorTest.base true 100000 avgt 30 43061.070 ± 2574.914 us/op
IteratorTest.jdkSpliterator false 2 avgt 30 0.989 ± 0.006 us/op
IteratorTest.jdkSpliterator false 3 avgt 30 1.443 ± 0.017 us/op
IteratorTest.jdkSpliterator false 5 avgt 30 2.301 ± 0.008 us/op
IteratorTest.jdkSpliterator false 10 avgt 30 4.617 ± 0.039 us/op
IteratorTest.jdkSpliterator false 20 avgt 30 9.933 ± 0.075 us/op
IteratorTest.jdkSpliterator false 30 avgt 30 14.759 ± 0.101 us/op
IteratorTest.jdkSpliterator false 50 avgt 30 24.851 ± 0.186 us/op
IteratorTest.jdkSpliterator false 100 avgt 30 49.050 ± 0.188 us/op
IteratorTest.jdkSpliterator false 200 avgt 30 112.670 ± 0.463 us/op
IteratorTest.jdkSpliterator false 300 avgt 30 198.505 ± 1.087 us/op
IteratorTest.jdkSpliterator false 500 avgt 30 305.845 ± 1.408 us/op
IteratorTest.jdkSpliterator false 1000 avgt 30 628.178 ± 6.636 us/op
IteratorTest.jdkSpliterator false 2000 avgt 30 1532.947 ± 6.492 us/op
IteratorTest.jdkSpliterator false 3000 avgt 30 2460.759 ± 51.381 us/op
IteratorTest.jdkSpliterator false 5000 avgt 30 4239.452 ± 87.447 us/op
IteratorTest.jdkSpliterator false 10000 avgt 30 8789.143 ± 133.726 us/op
IteratorTest.jdkSpliterator false 20000 avgt 30 26601.788 ± 609.220 us/op
IteratorTest.jdkSpliterator false 30000 avgt 30 44347.546 ± 711.518 us/op
IteratorTest.jdkSpliterator false 50000 avgt 30 78913.534 ± 1350.676 us/op
IteratorTest.jdkSpliterator false 100000 avgt 30 158781.437 ± 6928.397 us/op
IteratorTest.jdkSpliterator true 2 avgt 30 1.797 ± 0.058 us/op
IteratorTest.jdkSpliterator true 3 avgt 30 2.188 ± 0.057 us/op
IteratorTest.jdkSpliterator true 5 avgt 30 3.466 ± 0.376 us/op
IteratorTest.jdkSpliterator true 10 avgt 30 5.313 ± 0.033 us/op
IteratorTest.jdkSpliterator true 20 avgt 30 10.819 ± 0.059 us/op
IteratorTest.jdkSpliterator true 30 avgt 30 15.686 ± 0.147 us/op
IteratorTest.jdkSpliterator true 50 avgt 30 25.745 ± 0.278 us/op
IteratorTest.jdkSpliterator true 100 avgt 30 51.487 ± 0.384 us/op
IteratorTest.jdkSpliterator true 200 avgt 30 116.317 ± 0.807 us/op
IteratorTest.jdkSpliterator true 300 avgt 30 205.955 ± 3.836 us/op
IteratorTest.jdkSpliterator true 500 avgt 30 307.120 ± 1.172 us/op
IteratorTest.jdkSpliterator true 1000 avgt 30 627.375 ± 2.392 us/op
IteratorTest.jdkSpliterator true 2000 avgt 30 910.208 ± 3.215 us/op
IteratorTest.jdkSpliterator true 3000 avgt 30 1909.974 ± 33.082 us/op
IteratorTest.jdkSpliterator true 5000 avgt 30 1979.849 ± 50.331 us/op
IteratorTest.jdkSpliterator true 10000 avgt 30 3721.535 ± 92.114 us/op
IteratorTest.jdkSpliterator true 20000 avgt 30 10394.891 ± 374.603 us/op
IteratorTest.jdkSpliterator true 30000 avgt 30 17208.746 ± 250.361 us/op
IteratorTest.jdkSpliterator true 50000 avgt 30 26209.758 ± 714.801 us/op
IteratorTest.jdkSpliterator true 100000 avgt 30 50569.225 ± 2213.317 us/op
IteratorTest.optimized false 2 avgt 30 0.976 ± 0.008 us/op
IteratorTest.optimized false 3 avgt 30 1.434 ± 0.006 us/op
IteratorTest.optimized false 5 avgt 30 2.322 ± 0.014 us/op
IteratorTest.optimized false 10 avgt 30 4.564 ± 0.045 us/op
IteratorTest.optimized false 20 avgt 30 9.901 ± 0.098 us/op
IteratorTest.optimized false 30 avgt 30 14.820 ± 0.076 us/op
IteratorTest.optimized false 50 avgt 30 24.656 ± 0.166 us/op
IteratorTest.optimized false 100 avgt 30 49.004 ± 0.172 us/op
IteratorTest.optimized false 200 avgt 30 113.479 ± 0.596 us/op
IteratorTest.optimized false 300 avgt 30 198.808 ± 0.732 us/op
IteratorTest.optimized false 500 avgt 30 304.359 ± 0.470 us/op
IteratorTest.optimized false 1000 avgt 30 636.661 ± 9.201 us/op
IteratorTest.optimized false 2000 avgt 30 1528.881 ± 30.337 us/op
IteratorTest.optimized false 3000 avgt 30 2436.442 ± 50.736 us/op
IteratorTest.optimized false 5000 avgt 30 4174.561 ± 59.391 us/op
IteratorTest.optimized false 10000 avgt 30 8747.307 ± 171.917 us/op
IteratorTest.optimized false 20000 avgt 30 27580.980 ± 128.303 us/op
IteratorTest.optimized false 30000 avgt 30 43338.453 ± 1519.857 us/op
IteratorTest.optimized false 50000 avgt 30 80538.633 ± 1555.353 us/op
IteratorTest.optimized false 100000 avgt 30 159996.821 ± 5371.996 us/op
IteratorTest.optimized true 2 avgt 30 3.366 ± 0.068 us/op
IteratorTest.optimized true 3 avgt 30 1.801 ± 0.011 us/op
IteratorTest.optimized true 5 avgt 30 2.295 ± 0.021 us/op
IteratorTest.optimized true 10 avgt 30 5.324 ± 0.064 us/op
IteratorTest.optimized true 20 avgt 30 6.276 ± 0.074 us/op
IteratorTest.optimized true 30 avgt 30 8.907 ± 0.093 us/op
IteratorTest.optimized true 50 avgt 30 14.184 ± 0.139 us/op
IteratorTest.optimized true 100 avgt 30 27.958 ± 0.232 us/op
IteratorTest.optimized true 200 avgt 30 67.292 ± 0.893 us/op
IteratorTest.optimized true 300 avgt 30 113.114 ± 0.538 us/op
IteratorTest.optimized true 500 avgt 30 167.101 ± 1.025 us/op
IteratorTest.optimized true 1000 avgt 30 331.258 ± 2.321 us/op
IteratorTest.optimized true 2000 avgt 30 669.177 ± 9.021 us/op
IteratorTest.optimized true 3000 avgt 30 933.747 ± 14.316 us/op
IteratorTest.optimized true 5000 avgt 30 1945.820 ± 25.665 us/op
IteratorTest.optimized true 10000 avgt 30 2971.693 ± 19.625 us/op
IteratorTest.optimized true 20000 avgt 30 10118.840 ± 365.402 us/op
IteratorTest.optimized true 30000 avgt 30 16314.766 ± 748.576 us/op
IteratorTest.optimized true 50000 avgt 30 26357.989 ± 938.789 us/op
IteratorTest.optimized true 100000 avgt 30 51449.225 ± 2429.726 us/op
Results in tabular form (in us)
-------------------------------
(parallel) (size) base jdkSpliterator optimized
false 2 1.004 0.989 0.976
false 3 1.447 1.443 1.434
false 5 2.327 2.301 2.322
false 10 4.543 4.617 4.564
false 20 9.776 9.933 9.901
false 30 14.661 14.759 14.820
false 50 24.712 24.851 24.656
false 100 49.237 49.050 49.004
false 200 112.740 112.670 113.479
false 300 198.780 198.505 198.808
false 500 304.211 305.845 304.359
false 1000 646.151 628.178 636.661
false 2000 1549.555 1532.947 1528.881
false 3000 2395.780 2460.759 2436.442
false 5000 4118.417 4239.452 4174.561
false 10000 9077.169 8789.143 8747.307
false 20000 27369.616 26601.788 27580.980
false 30000 44389.357 44347.546 43338.453
false 50000 78305.664 78913.534 80538.633
false 100000 164270.952 158781.437 159996.821
true 2 3.096 1.797 3.366
true 3 3.387 2.188 1.801
true 5 5.257 3.466 2.295
true 10 5.849 5.313 5.324
true 20 8.280 10.819 6.276
true 30 9.143 15.686 8.907
true 50 11.398 25.745 14.184
true 100 17.584 51.487 27.958
true 200 38.073 116.317 67.292
true 300 61.198 205.955 113.114
true 500 96.341 307.120 167.101
true 1000 173.775 627.375 331.258
true 2000 471.980 910.208 669.177
true 3000 720.277 1909.974 933.747
true 5000 1210.950 1979.849 1945.820
true 10000 2468.787 3721.535 2971.693
true 20000 7703.531 10394.891 10118.840
true 30000 11695.593 17208.746 16314.766
true 50000 20866.573 26209.758 26357.989
true 100000 43061.070 50569.225 51449.225
package org.sample;
import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;
class UnknownSizeSpliterator<T> implements Spliterator<T> {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
private Iterator<? extends T> it;
private Object[] array;
private int index, fence;
public UnknownSizeSpliterator(Iterator<? extends T> iterator) {
this.it = iterator;
}
UnknownSizeSpliterator(Object[] array, int index, int fence) {
this.array = array;
this.index = index;
this.fence = fence;
}
@Override
public Spliterator<T> trySplit() {
Iterator<? extends T> i = it;
if (i != null) {
int n = fence + BATCH_UNIT;
if (n > MAX_BATCH)
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do {
a[j] = i.next();
} while (++j < n && i.hasNext());
fence = j;
if (i.hasNext()) {
return new UnknownSizeSpliterator<>(a, 0, j);
}
it = null;
array = a;
}
int lo = index, mid = (lo + fence) >>> 1;
return (lo >= mid) ? null : new UnknownSizeSpliterator<>(array, lo, index = mid);
}
@Override
public void forEachRemaining(Consumer<? super T> action) {
if (it != null)
it.forEachRemaining(action);
else {
Object[] a = array;
int i = index, hi = fence;
if (i < hi && a.length >= hi) {
do {
action.accept((T) a[i]);
} while (++i < hi);
}
}
index = fence;
}
@Override
public boolean tryAdvance(Consumer<? super T> action) {
if (it != null) {
if (it.hasNext()) {
action.accept(it.next());
return true;
} else {
it = null;
index = fence;
}
} else if (index < fence) {
action.accept((T) array[index++]);
return true;
}
return false;
}
@Override
public long estimateSize() {
if (it == null) {
return fence - index;
}
return Long.MAX_VALUE;
}
@Override
public int characteristics() {
if (it == null) {
return SIZED | SUBSIZED | ORDERED;
}
return ORDERED;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment