< prev index next >
test/jdk/java/util/Collection/IteratorMicroBenchmark.java
Print this page
8200258: Improve CopyOnWriteArrayList subList code
Reviewed-by: martin, psandoz, smarks
*** 34,43 ****
--- 34,44 ----
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,62 ****
--- 54,64 ----
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,82 ****
--- 75,91 ----
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,109 ****
--- 109,119 ----
/** 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,140 ****
* 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 {
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++; }
while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
nanoss[i] = totalTime/runs;
}
return nanoss;
}
--- 131,150 ----
* 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) {
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.run(); runs++; }
while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
nanoss[i] = totalTime/runs;
}
return nanoss;
}
*** 209,222 ****
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());
--- 219,228 ----
*** 239,253 ****
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);
final ArrayList<Integer> al = new ArrayList<>(size);
// Populate collections with random data
final ThreadLocalRandom rnd = ThreadLocalRandom.current();
for (int i = 0; i < size; i++)
--- 245,280 ----
public static void main(String[] args) throws Throwable {
new IteratorMicroBenchmark(args).run();
}
! 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,276 ****
--- 290,307 ----
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,311 ****
}
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());
}
Stream<Job> collectionJobs(Collection<Integer> x) {
! String klazz = x.getClass().getSimpleName();
return Stream.of(
new Job(klazz + " iterate for loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
int sum = 0;
--- 323,351 ----
}
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) {
! 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,368 ****
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; }};
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
! if (x.contains(y)) 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; }};
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
! if (x.remove(y)) 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++) {
--- 383,414 ----
throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " contains") {
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.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.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 sneakyAdder = sneakyAdder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
! 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,454 ****
sum[0] += o;
check.sum(sum[0]);}}});
}
Stream<Job> dequeJobs(Deque<Integer> x) {
! String klazz = x.getClass().getSimpleName();
return Stream.of(
new Job(klazz + " descendingIterator() loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
int sum = 0;
--- 490,500 ----
sum[0] += o;
check.sum(sum[0]);}}});
}
Stream<Job> dequeJobs(Deque<Integer> x) {
! 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,513 ****
x.descendingIterator().forEachRemaining(n -> sum[0] += n);
check.sum(sum[0]);}}});
}
Stream<Job> listJobs(List<Integer> x) {
! String klazz = x.getClass().getSimpleName();
return Stream.of(
! new Job(klazz + " subList toArray()") {
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)") {
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);}}});
}
}
--- 510,561 ----
x.descendingIterator().forEachRemaining(n -> sum[0] += n);
check.sum(sum[0]);}}});
}
Stream<Job> listJobs(List<Integer> x) {
! final String klazz = goodClassName(x.getClass());
return Stream.of(
! new Job(klazz + " listIterator forward loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
int sum = 0;
! 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 {
for (int i = 0; i < iterations; i++) {
int sum = 0;
! 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 >