< 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 >