< prev index next >
test/jdk/java/util/Collection/IteratorMicroBenchmark.java
Print this page
8200258: Improve CopyOnWriteArrayList subList code
Reviewed-by: martin, psandoz, smarks
@@ -34,10 +34,11 @@
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.PriorityQueue;
@@ -53,10 +54,11 @@
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.LongAdder;
+import java.util.function.UnaryOperator;
import java.util.regex.Pattern;
import java.util.stream.Stream;
/**
* Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
@@ -73,10 +75,17 @@
abstract static class Job {
private final String name;
public Job(String name) { this.name = name; }
public String name() { return name; }
public abstract void work() throws Throwable;
+ public void run() {
+ try { work(); }
+ catch (Throwable ex) {
+ // current job cannot always be deduced from stacktrace.
+ throw new RuntimeException("Job failed: " + name(), ex);
+ }
+ }
}
final int iterations;
final int size; // number of elements in collections
final double warmupSeconds;
@@ -100,10 +109,11 @@
/** No guarantees, but effective in practice. */
static void forceFullGc() {
CountDownLatch finalizeDone = new CountDownLatch(1);
WeakReference<?> ref = new WeakReference<Object>(new Object() {
+ @SuppressWarnings("deprecation")
protected void finalize() { finalizeDone.countDown(); }});
try {
for (int i = 0; i < 10; i++) {
System.gc();
if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
@@ -121,20 +131,20 @@
* Runs each job for long enough that all the runtime compilers
* have had plenty of time to warm up, i.e. get around to
* compiling everything worth compiling.
* Returns array of average times per job per run.
*/
- long[] time0(List<Job> jobs) throws Throwable {
+ long[] time0(List<Job> jobs) {
final int size = jobs.size();
long[] nanoss = new long[size];
for (int i = 0; i < size; i++) {
if (warmupNanos > 0) forceFullGc();
Job job = jobs.get(i);
long totalTime;
int runs = 0;
long startTime = System.nanoTime();
- do { job.work(); runs++; }
+ do { job.run(); runs++; }
while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
nanoss[i] = totalTime/runs;
}
return nanoss;
}
@@ -209,14 +219,10 @@
private static void deoptimize(int sum) {
if (sum == 42)
System.out.println("the answer");
}
- private static <T> List<T> asSubList(List<T> list) {
- return list.subList(0, list.size());
- }
-
private static <T> Iterable<T> backwards(final List<T> list) {
return new Iterable<T>() {
public Iterator<T> iterator() {
return new Iterator<T>() {
final ListIterator<T> it = list.listIterator(list.size());
@@ -239,15 +245,36 @@
public static void main(String[] args) throws Throwable {
new IteratorMicroBenchmark(args).run();
}
- void run() throws Throwable {
-// System.out.printf(
-// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
-// iterations, size, warmupSeconds, nameFilter);
+ HashMap<Class<?>, String> goodClassName = new HashMap<>();
+
+ String goodClassName(Class<?> klazz) {
+ return goodClassName.computeIfAbsent(
+ klazz,
+ k -> {
+ String simple = k.getSimpleName();
+ return (simple.equals("SubList")) // too simple!
+ ? k.getName().replaceFirst(".*\\.", "")
+ : simple;
+ });
+ }
+
+ static List<Integer> makeSubList(List<Integer> list) {
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int size = list.size();
+ if (size <= 2) return list.subList(0, size);
+ List<Integer> subList = list.subList(rnd.nextInt(0, 2),
+ size - rnd.nextInt(0, 2));
+ List<Integer> copy = new ArrayList<>(list);
+ subList.clear();
+ subList.addAll(copy);
+ return subList;
+ }
+ void run() throws Throwable {
final ArrayList<Integer> al = new ArrayList<>(size);
// Populate collections with random data
final ThreadLocalRandom rnd = ThreadLocalRandom.current();
for (int i = 0; i < size; i++)
@@ -263,14 +290,18 @@
abq.add(abq.remove());
}
ArrayList<Job> jobs = Stream.<Collection<Integer>>of(
al, ad, abq,
+ makeSubList(new ArrayList<>(al)),
new LinkedList<>(al),
+ makeSubList(new LinkedList<>(al)),
new PriorityQueue<>(al),
new Vector<>(al),
+ makeSubList(new Vector<>(al)),
new CopyOnWriteArrayList<>(al),
+ makeSubList(new CopyOnWriteArrayList<>(al)),
new ConcurrentLinkedQueue<>(al),
new ConcurrentLinkedDeque<>(al),
new LinkedBlockingQueue<>(al),
new LinkedBlockingDeque<>(al),
new LinkedTransferQueue<>(al),
@@ -292,20 +323,29 @@
}
Stream<Job> jobs(Collection<Integer> x) {
return concatStreams(
collectionJobs(x),
+
(x instanceof Deque)
? dequeJobs((Deque<Integer>)x)
: Stream.empty(),
+
(x instanceof List)
? listJobs((List<Integer>)x)
: Stream.empty());
}
+ Object sneakyAdder(int[] sneakySum) {
+ return new Object() {
+ public int hashCode() { throw new AssertionError(); }
+ public boolean equals(Object z) {
+ sneakySum[0] += (int) z; return false; }};
+ }
+
Stream<Job> collectionJobs(Collection<Integer> x) {
- String klazz = x.getClass().getSimpleName();
+ final String klazz = goodClassName(x.getClass());
return Stream.of(
new Job(klazz + " iterate for loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
int sum = 0;
@@ -343,26 +383,32 @@
throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " contains") {
public void work() throws Throwable {
int[] sum = new int[1];
- Object y = new Object() {
- public boolean equals(Object z) {
- sum[0] += (int) z; return false; }};
+ Object sneakyAdder = sneakyAdder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.contains(sneakyAdder)) throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " containsAll") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Collection<Object> sneakyAdderCollection =
+ Collections.singleton(sneakyAdder(sum));
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- if (x.contains(y)) throw new AssertionError();
+ if (x.containsAll(sneakyAdderCollection))
+ throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " remove(Object)") {
public void work() throws Throwable {
int[] sum = new int[1];
- Object y = new Object() {
- public boolean equals(Object z) {
- sum[0] += (int) z; return false; }};
+ Object sneakyAdder = sneakyAdder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- if (x.remove(y)) throw new AssertionError();
+ if (x.remove(sneakyAdder)) throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " forEach") {
public void work() throws Throwable {
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
@@ -444,11 +490,11 @@
sum[0] += o;
check.sum(sum[0]);}}});
}
Stream<Job> dequeJobs(Deque<Integer> x) {
- String klazz = x.getClass().getSimpleName();
+ String klazz = goodClassName(x.getClass());
return Stream.of(
new Job(klazz + " descendingIterator() loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
int sum = 0;
@@ -464,50 +510,52 @@
x.descendingIterator().forEachRemaining(n -> sum[0] += n);
check.sum(sum[0]);}}});
}
Stream<Job> listJobs(List<Integer> x) {
- String klazz = x.getClass().getSimpleName();
+ final String klazz = goodClassName(x.getClass());
return Stream.of(
- new Job(klazz + " subList toArray()") {
+ new Job(klazz + " listIterator forward loop") {
public void work() throws Throwable {
- int size = x.size();
for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
int sum = 0;
- for (Object o : subList.toArray())
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}},
- new Job(klazz + " subList toArray(a)") {
- public void work() throws Throwable {
- int size = x.size();
- for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
- int sum = 0;
- Integer[] a = new Integer[subList.size()];
- for (Object o : subList.toArray(a))
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}},
- new Job(klazz + " subList toArray(empty)") {
+ ListIterator<Integer> it = x.listIterator();
+ while (it.hasNext())
+ sum += it.next();
+ check.sum(sum);}}},
+ new Job(klazz + " listIterator backward loop") {
public void work() throws Throwable {
- int size = x.size();
- Integer[] empty = new Integer[0];
for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
int sum = 0;
- for (Object o : subList.toArray(empty))
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}});
+ ListIterator<Integer> it = x.listIterator(x.size());
+ while (it.hasPrevious())
+ sum += it.previous();
+ check.sum(sum);}}},
+ new Job(klazz + " indexOf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Object sneakyAdder = sneakyAdder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.indexOf(sneakyAdder) != -1)
+ throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " lastIndexOf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Object sneakyAdder = sneakyAdder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.lastIndexOf(sneakyAdder) != -1)
+ throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " replaceAll") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ UnaryOperator<Integer> sneakyAdder =
+ x -> { sum[0] += x; return x; };
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.replaceAll(sneakyAdder);
+ check.sum(sum[0]);}}});
}
}
< prev index next >