| 29 |
|
|
| 30 |
|
import java.lang.ref.WeakReference; |
| 31 |
|
import java.util.ArrayDeque; |
| 32 |
– |
import java.util.Arrays; |
| 32 |
|
import java.util.ArrayList; |
| 34 |
– |
import java.util.Collection; |
| 35 |
– |
import java.util.Deque; |
| 33 |
|
import java.util.Enumeration; |
| 34 |
|
import java.util.Iterator; |
| 35 |
|
import java.util.List; |
| 37 |
|
import java.util.Map; |
| 38 |
|
import java.util.Spliterator; |
| 39 |
|
import java.util.Vector; |
| 43 |
– |
import java.util.concurrent.ArrayBlockingQueue; |
| 44 |
– |
import java.util.concurrent.ConcurrentLinkedDeque; |
| 45 |
– |
import java.util.concurrent.ConcurrentLinkedQueue; |
| 46 |
– |
import java.util.concurrent.LinkedBlockingDeque; |
| 47 |
– |
import java.util.concurrent.LinkedBlockingQueue; |
| 48 |
– |
import java.util.concurrent.LinkedTransferQueue; |
| 40 |
|
import java.util.concurrent.ConcurrentSkipListMap; |
| 41 |
|
import java.util.concurrent.CountDownLatch; |
| 42 |
|
import java.util.concurrent.ThreadLocalRandom; |
| 47 |
|
* Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS] |
| 48 |
|
* |
| 49 |
|
* To run this in micro-benchmark mode, simply run as a normal java program. |
| 50 |
< |
* Be patient; this program runs for a very long time. |
| 50 |
> |
* Be patient; this runs for an hour! |
| 51 |
|
* For faster runs, restrict execution using command line args. |
| 52 |
|
* |
| 53 |
|
* @author Martin Buchholz |
| 60 |
|
public abstract void work() throws Throwable; |
| 61 |
|
} |
| 62 |
|
|
| 63 |
< |
int iterations; |
| 73 |
< |
int size; |
| 74 |
< |
double warmupSeconds; |
| 75 |
< |
Pattern filter; |
| 63 |
> |
static double warmupSeconds = 10; |
| 64 |
|
|
| 65 |
|
// --------------- GC finalization infrastructure --------------- |
| 66 |
|
|
| 89 |
|
* compiling everything worth compiling. |
| 90 |
|
* Returns array of average times per job per run. |
| 91 |
|
*/ |
| 92 |
< |
long[] time0(List<Job> jobs) throws Throwable { |
| 92 |
> |
private static long[] time0(Job ... jobs) throws Throwable { |
| 93 |
|
final long warmupNanos = (long) (warmupSeconds * 1000L * 1000L * 1000L); |
| 94 |
< |
final int size = jobs.size(); |
| 95 |
< |
long[] nanoss = new long[size]; |
| 108 |
< |
for (int i = 0; i < size; i++) { |
| 94 |
> |
long[] nanoss = new long[jobs.length]; |
| 95 |
> |
for (int i = 0; i < jobs.length; i++) { |
| 96 |
|
if (warmupNanos > 0) forceFullGc(); |
| 97 |
|
long t0 = System.nanoTime(); |
| 98 |
|
long t; |
| 99 |
|
int j = 0; |
| 100 |
< |
do { jobs.get(i).work(); j++; } |
| 100 |
> |
do { jobs[i].work(); j++; } |
| 101 |
|
while ((t = System.nanoTime() - t0) < warmupNanos); |
| 102 |
|
nanoss[i] = t/j; |
| 103 |
|
} |
| 104 |
|
return nanoss; |
| 105 |
|
} |
| 106 |
|
|
| 107 |
< |
void time(List<Job> jobs) throws Throwable { |
| 107 |
> |
private static void time(Job ... jobs) throws Throwable { |
| 108 |
|
if (warmupSeconds > 0) time0(jobs); // Warm up run |
| 109 |
< |
final int size = jobs.size(); |
| 110 |
< |
final long[] nanoss = time0(jobs); // Real timing run |
| 111 |
< |
final long[] milliss = new long[size]; |
| 125 |
< |
final double[] ratios = new double[size]; |
| 109 |
> |
long[] nanoss = time0(jobs); // Real timing run |
| 110 |
> |
long[] milliss = new long[jobs.length]; |
| 111 |
> |
double[] ratios = new double[jobs.length]; |
| 112 |
|
|
| 113 |
|
final String nameHeader = "Method"; |
| 114 |
|
final String millisHeader = "Millis"; |
| 118 |
|
int millisWidth = millisHeader.length(); |
| 119 |
|
int ratioWidth = ratioHeader.length(); |
| 120 |
|
|
| 121 |
< |
for (int i = 0; i < size; i++) { |
| 122 |
< |
nameWidth = Math.max(nameWidth, jobs.get(i).name().length()); |
| 121 |
> |
for (int i = 0; i < jobs.length; i++) { |
| 122 |
> |
nameWidth = Math.max(nameWidth, jobs[i].name().length()); |
| 123 |
|
|
| 124 |
|
milliss[i] = nanoss[i]/(1000L * 1000L); |
| 125 |
|
millisWidth = Math.max(millisWidth, |
| 137 |
|
System.out.printf(headerFormat, "Method", "Millis", "Ratio"); |
| 138 |
|
|
| 139 |
|
// Print out absolute and relative times, calibrated against first job |
| 140 |
< |
for (int i = 0; i < size; i++) |
| 141 |
< |
System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]); |
| 140 |
> |
for (int i = 0; i < jobs.length; i++) |
| 141 |
> |
System.out.printf(format, jobs[i].name(), milliss[i], ratios[i]); |
| 142 |
|
} |
| 143 |
|
|
| 144 |
|
private static String keywordValue(String[] args, String keyword) { |
| 163 |
|
return (val == null) ? null : Pattern.compile(val); |
| 164 |
|
} |
| 165 |
|
|
| 166 |
< |
private static List<Job> filter(Pattern filter, List<Job> jobs) { |
| 166 |
> |
private static Job[] filter(Pattern filter, Job[] jobs) { |
| 167 |
|
if (filter == null) return jobs; |
| 168 |
< |
ArrayList<Job> newJobs = new ArrayList<>(); |
| 168 |
> |
Job[] newJobs = new Job[jobs.length]; |
| 169 |
> |
int n = 0; |
| 170 |
|
for (Job job : jobs) |
| 171 |
|
if (filter.matcher(job.name()).find()) |
| 172 |
< |
newJobs.add(job); |
| 173 |
< |
return newJobs; |
| 172 |
> |
newJobs[n++] = job; |
| 173 |
> |
// Arrays.copyOf not available in JDK 5 |
| 174 |
> |
Job[] ret = new Job[n]; |
| 175 |
> |
System.arraycopy(newJobs, 0, ret, 0, n); |
| 176 |
> |
return ret; |
| 177 |
|
} |
| 178 |
|
|
| 179 |
|
private static void deoptimize(int sum) { |
| 195 |
|
public void remove() { it.remove(); }};}}; |
| 196 |
|
} |
| 197 |
|
|
| 208 |
– |
// Checks for correctness *and* prevents loop optimizations |
| 209 |
– |
class Check { |
| 210 |
– |
private int sum; |
| 211 |
– |
public void sum(int sum) { |
| 212 |
– |
if (this.sum == 0) |
| 213 |
– |
this.sum = sum; |
| 214 |
– |
if (this.sum != sum) |
| 215 |
– |
throw new AssertionError("Sum mismatch"); |
| 216 |
– |
} |
| 217 |
– |
} |
| 218 |
– |
final Check check = new Check(); |
| 219 |
– |
final Check shortCheck = new Check(); |
| 220 |
– |
|
| 198 |
|
public static void main(String[] args) throws Throwable { |
| 199 |
< |
new IteratorMicroBenchmark().run(args); |
| 200 |
< |
} |
| 201 |
< |
|
| 202 |
< |
void run(String[] args) throws Throwable { |
| 226 |
< |
iterations = intArg(args, "iterations", 100_000); |
| 227 |
< |
size = intArg(args, "size", 1000); |
| 228 |
< |
warmupSeconds = doubleArg(args, "warmup", 10); |
| 229 |
< |
filter = patternArg(args, "filter"); |
| 199 |
> |
final int iterations = intArg(args, "iterations", 100_000); |
| 200 |
> |
final int size = intArg(args, "size", 1000); |
| 201 |
> |
warmupSeconds = doubleArg(args, "warmup", 10); |
| 202 |
> |
final Pattern filter = patternArg(args, "filter"); |
| 203 |
|
// System.out.printf( |
| 204 |
|
// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n", |
| 205 |
|
// iterations, size, warmupSeconds, filter); |
| 214 |
|
m.put(rnd.nextInt(size), rnd.nextInt(size)); |
| 215 |
|
al.add(rnd.nextInt(size)); |
| 216 |
|
} |
| 217 |
< |
final Vector<Integer> v = new Vector<>(al); |
| 218 |
< |
|
| 246 |
< |
final ArrayDeque<Integer> ad = new ArrayDeque<>(al); |
| 217 |
> |
final Vector<Integer> v = new Vector<Integer>(al); |
| 218 |
> |
final ArrayDeque<Integer> ad = new ArrayDeque<Integer>(al); |
| 219 |
|
// shuffle ArrayDeque elements so they wrap |
| 220 |
|
for (int i = 0, n = rnd.nextInt(size); i < n; i++) |
| 221 |
|
ad.addLast(ad.removeFirst()); |
| 222 |
|
|
| 251 |
– |
final ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(al.size()); |
| 252 |
– |
abq.addAll(al); |
| 253 |
– |
|
| 254 |
– |
final ConcurrentLinkedQueue<Integer> clq = new ConcurrentLinkedQueue<>(al); |
| 255 |
– |
final ConcurrentLinkedDeque<Integer> cld = new ConcurrentLinkedDeque<>(al); |
| 256 |
– |
final LinkedBlockingQueue<Integer> lbq = new LinkedBlockingQueue<>(al); |
| 257 |
– |
final LinkedBlockingDeque<Integer> lbd = new LinkedBlockingDeque<>(al); |
| 258 |
– |
final LinkedTransferQueue<Integer> ltq = new LinkedTransferQueue<>(al); |
| 259 |
– |
|
| 223 |
|
// Also test "short" collections |
| 224 |
|
final int shortSize = 5; |
| 225 |
< |
final Vector<Integer> sv = new Vector<>(v.subList(0, shortSize)); |
| 226 |
< |
final ArrayList<Integer> sal = new ArrayList<>(sv); |
| 225 |
> |
final Vector<Integer> sv = new Vector<Integer>(v.subList(0, shortSize)); |
| 226 |
> |
final ArrayList<Integer> sal = new ArrayList<Integer>(sv); |
| 227 |
|
|
| 228 |
< |
Job[] initialJobs = { |
| 228 |
> |
// Checks for correctness *and* prevents loop optimizations |
| 229 |
> |
class Check { |
| 230 |
> |
private int sum; |
| 231 |
> |
public void sum(int sum) { |
| 232 |
> |
if (this.sum == 0) |
| 233 |
> |
this.sum = sum; |
| 234 |
> |
if (this.sum != sum) |
| 235 |
> |
throw new AssertionError("Sum mismatch"); |
| 236 |
> |
} |
| 237 |
> |
} |
| 238 |
> |
final Check check = new Check(); |
| 239 |
> |
final Check shortCheck = new Check(); |
| 240 |
> |
|
| 241 |
> |
Job[] jobs = { |
| 242 |
|
// new Job("Vector iterate desugared") { |
| 243 |
|
// public void work() throws Throwable { |
| 244 |
|
// for (int i = 0; i < iterations; i++) { |
| 617 |
|
deoptimize(sum);}}} |
| 618 |
|
}; |
| 619 |
|
|
| 644 |
– |
ArrayList<Job> jobs = new ArrayList<>(Arrays.asList(initialJobs)); |
| 645 |
– |
|
| 646 |
– |
// Add in pure interface jobs |
| 647 |
– |
List.of(al, ad, v, abq, lbd, lbq, ltq, clq, cld).stream() |
| 648 |
– |
.forEach(x -> { |
| 649 |
– |
jobs.addAll(collectionJobs(x)); |
| 650 |
– |
if (x instanceof Deque) |
| 651 |
– |
jobs.addAll(dequeJobs((Deque<Integer>)x)); |
| 652 |
– |
}); |
| 653 |
– |
|
| 620 |
|
time(filter(filter, jobs)); |
| 621 |
|
} |
| 656 |
– |
|
| 657 |
– |
List<Job> collectionJobs(Collection<Integer> x) { |
| 658 |
– |
String klazz = x.getClass().getSimpleName(); |
| 659 |
– |
String desc = klazz + " Collection interface"; |
| 660 |
– |
return List.of( |
| 661 |
– |
new Job(desc + " iterate for loop") { |
| 662 |
– |
public void work() throws Throwable { |
| 663 |
– |
for (int i = 0; i < iterations; i++) { |
| 664 |
– |
int sum = 0; |
| 665 |
– |
for (Integer n : x) |
| 666 |
– |
sum += n; |
| 667 |
– |
check.sum(sum);}}}, |
| 668 |
– |
new Job(desc + " .iterator().forEachRemaining()") { |
| 669 |
– |
public void work() throws Throwable { |
| 670 |
– |
int[] sum = new int[1]; |
| 671 |
– |
for (int i = 0; i < iterations; i++) { |
| 672 |
– |
sum[0] = 0; |
| 673 |
– |
x.iterator().forEachRemaining(n -> sum[0] += n); |
| 674 |
– |
check.sum(sum[0]);}}}, |
| 675 |
– |
new Job(desc + " .spliterator().tryAdvance()") { |
| 676 |
– |
public void work() throws Throwable { |
| 677 |
– |
int[] sum = new int[1]; |
| 678 |
– |
for (int i = 0; i < iterations; i++) { |
| 679 |
– |
sum[0] = 0; |
| 680 |
– |
Spliterator<Integer> spliterator = x.spliterator(); |
| 681 |
– |
do {} while (spliterator.tryAdvance(n -> sum[0] += n)); |
| 682 |
– |
check.sum(sum[0]);}}}, |
| 683 |
– |
new Job(desc + " .spliterator().forEachRemaining()") { |
| 684 |
– |
public void work() throws Throwable { |
| 685 |
– |
int[] sum = new int[1]; |
| 686 |
– |
for (int i = 0; i < iterations; i++) { |
| 687 |
– |
sum[0] = 0; |
| 688 |
– |
x.spliterator().forEachRemaining(n -> sum[0] += n); |
| 689 |
– |
check.sum(sum[0]);}}}, |
| 690 |
– |
new Job(desc + " .removeIf") { |
| 691 |
– |
public void work() throws Throwable { |
| 692 |
– |
int[] sum = new int[1]; |
| 693 |
– |
for (int i = 0; i < iterations; i++) { |
| 694 |
– |
sum[0] = 0; |
| 695 |
– |
x.removeIf(n -> { sum[0] += n; return false; }); |
| 696 |
– |
check.sum(sum[0]);}}}, |
| 697 |
– |
new Job(desc + " .foreach") { |
| 698 |
– |
public void work() throws Throwable { |
| 699 |
– |
int[] sum = new int[1]; |
| 700 |
– |
for (int i = 0; i < iterations; i++) { |
| 701 |
– |
sum[0] = 0; |
| 702 |
– |
x.forEach(n -> sum[0] += n); |
| 703 |
– |
check.sum(sum[0]);}}}); |
| 704 |
– |
} |
| 705 |
– |
|
| 706 |
– |
List<Job> dequeJobs(Deque<Integer> x) { |
| 707 |
– |
String klazz = x.getClass().getSimpleName(); |
| 708 |
– |
String desc = klazz + " Deque interface"; |
| 709 |
– |
return List.of( |
| 710 |
– |
new Job(desc + " .descendingIterator() loop") { |
| 711 |
– |
public void work() throws Throwable { |
| 712 |
– |
for (int i = 0; i < iterations; i++) { |
| 713 |
– |
int sum = 0; |
| 714 |
– |
Iterator<Integer> it = x.descendingIterator(); |
| 715 |
– |
while (it.hasNext()) |
| 716 |
– |
sum += it.next(); |
| 717 |
– |
check.sum(sum);}}}, |
| 718 |
– |
new Job(desc + " .descendingIterator().forEachRemaining()") { |
| 719 |
– |
public void work() throws Throwable { |
| 720 |
– |
int[] sum = new int[1]; |
| 721 |
– |
for (int i = 0; i < iterations; i++) { |
| 722 |
– |
sum[0] = 0; |
| 723 |
– |
x.descendingIterator().forEachRemaining(n -> sum[0] += n); |
| 724 |
– |
check.sum(sum[0]);}}}); |
| 725 |
– |
} |
| 622 |
|
} |
