1 /* 2 * Copyright (C) 2010 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.caliper.BeforeExperiment; 20 import com.google.caliper.Benchmark; 21 import com.google.caliper.Param; 22 import com.google.common.base.Function; 23 import java.math.BigInteger; 24 import java.util.Comparator; 25 import java.util.PriorityQueue; 26 import java.util.Queue; 27 import java.util.Random; 28 29 /** 30 * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue. 31 * 32 * @author Sverre Sundsdal 33 */ 34 public class MinMaxPriorityQueueBenchmark { 35 @Param private ComparatorType comparator; 36 37 // TODO(kevinb): add 1000000 back when we have the ability to throw 38 // NotApplicableException in the expensive comparator case. 39 @Param({"100", "10000"}) 40 private int size; 41 42 @Param private HeapType heap; 43 44 private Queue<Integer> queue; 45 46 private final Random random = new Random(); 47 48 @BeforeExperiment setUp()49 void setUp() { 50 queue = heap.create(comparator.get()); 51 for (int i = 0; i < size; i++) { 52 queue.add(random.nextInt()); 53 } 54 } 55 56 @Benchmark pollAndAdd(int reps)57 void pollAndAdd(int reps) { 58 for (int i = 0; i < reps; i++) { 59 // TODO(kevinb): precompute random #s? 60 queue.add(queue.poll() ^ random.nextInt()); 61 } 62 } 63 64 @Benchmark populate(int reps)65 void populate(int reps) { 66 for (int i = 0; i < reps; i++) { 67 queue.clear(); 68 for (int j = 0; j < size; j++) { 69 // TODO(kevinb): precompute random #s? 70 queue.add(random.nextInt()); 71 } 72 } 73 } 74 75 /** 76 * Implementation of the InvertedMinMaxPriorityQueue which forwards all calls to a 77 * MinMaxPriorityQueue, except poll, which is forwarded to pollMax. That way we can benchmark 78 * pollMax using the same code that benchmarks poll. 79 */ 80 static final class InvertedMinMaxPriorityQueue<T> extends ForwardingQueue<T> { 81 MinMaxPriorityQueue<T> mmHeap; 82 InvertedMinMaxPriorityQueue(Comparator<T> comparator)83 public InvertedMinMaxPriorityQueue(Comparator<T> comparator) { 84 mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create(); 85 } 86 87 @Override delegate()88 protected Queue<T> delegate() { 89 return mmHeap; 90 } 91 92 @Override poll()93 public T poll() { 94 return mmHeap.pollLast(); 95 } 96 } 97 98 public enum HeapType { 99 MIN_MAX { 100 @Override create(Comparator<Integer> comparator)101 public Queue<Integer> create(Comparator<Integer> comparator) { 102 return MinMaxPriorityQueue.orderedBy(comparator).create(); 103 } 104 }, 105 PRIORITY_QUEUE { 106 @Override create(Comparator<Integer> comparator)107 public Queue<Integer> create(Comparator<Integer> comparator) { 108 return new PriorityQueue<>(11, comparator); 109 } 110 }, 111 INVERTED_MIN_MAX { 112 @Override create(Comparator<Integer> comparator)113 public Queue<Integer> create(Comparator<Integer> comparator) { 114 return new InvertedMinMaxPriorityQueue<>(comparator); 115 } 116 }; 117 create(Comparator<Integer> comparator)118 public abstract Queue<Integer> create(Comparator<Integer> comparator); 119 } 120 121 /** 122 * Does a CPU intensive operation on Integer and returns a BigInteger Used to implement an 123 * ordering that spends a lot of cpu. 124 */ 125 static class ExpensiveComputation implements Function<Integer, BigInteger> { 126 @Override apply(Integer from)127 public BigInteger apply(Integer from) { 128 BigInteger v = BigInteger.valueOf(from); 129 // Math.sin is very slow for values outside 4*pi 130 // Need to take absolute value to avoid inverting the value. 131 for (double i = 0; i < 100; i += 20) { 132 v = 133 v.add( 134 v.multiply( 135 BigInteger.valueOf(((Double) Math.abs(Math.sin(i) * 10.0)).longValue()))); 136 } 137 return v; 138 } 139 } 140 141 public enum ComparatorType { 142 CHEAP { 143 @Override get()144 public Comparator<Integer> get() { 145 return Ordering.natural(); 146 } 147 }, 148 EXPENSIVE { 149 @Override get()150 public Comparator<Integer> get() { 151 return Ordering.natural().onResultOf(new ExpensiveComputation()); 152 } 153 }; 154 get()155 public abstract Comparator<Integer> get(); 156 } 157 } 158