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 import org.checkerframework.checker.nullness.qual.Nullable; 29 30 /** 31 * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue. 32 * 33 * @author Sverre Sundsdal 34 */ 35 public class MinMaxPriorityQueueBenchmark { 36 @Param private ComparatorType comparator; 37 38 // TODO(kevinb): add 1000000 back when we have the ability to throw 39 // NotApplicableException in the expensive comparator case. 40 @Param({"100", "10000"}) 41 private int size; 42 43 @Param private HeapType heap; 44 45 private Queue<Integer> queue; 46 47 private final Random random = new Random(); 48 49 @BeforeExperiment setUp()50 void setUp() { 51 queue = heap.create(comparator.get()); 52 for (int i = 0; i < size; i++) { 53 queue.add(random.nextInt()); 54 } 55 } 56 57 @Benchmark pollAndAdd(int reps)58 void pollAndAdd(int reps) { 59 for (int i = 0; i < reps; i++) { 60 // TODO(kevinb): precompute random #s? 61 queue.add(queue.poll() ^ random.nextInt()); 62 } 63 } 64 65 @Benchmark populate(int reps)66 void populate(int reps) { 67 for (int i = 0; i < reps; i++) { 68 queue.clear(); 69 for (int j = 0; j < size; j++) { 70 // TODO(kevinb): precompute random #s? 71 queue.add(random.nextInt()); 72 } 73 } 74 } 75 76 /** 77 * Implementation of the InvertedMinMaxPriorityQueue which forwards all calls to a 78 * MinMaxPriorityQueue, except poll, which is forwarded to pollMax. That way we can benchmark 79 * pollMax using the same code that benchmarks poll. 80 */ 81 static final class InvertedMinMaxPriorityQueue<T> extends ForwardingQueue<T> { 82 MinMaxPriorityQueue<T> mmHeap; 83 InvertedMinMaxPriorityQueue(Comparator<T> comparator)84 public InvertedMinMaxPriorityQueue(Comparator<T> comparator) { 85 mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create(); 86 } 87 88 @Override delegate()89 protected Queue<T> delegate() { 90 return mmHeap; 91 } 92 93 @Override poll()94 public @Nullable T poll() { 95 return mmHeap.pollLast(); 96 } 97 } 98 99 public enum HeapType { 100 MIN_MAX { 101 @Override create(Comparator<Integer> comparator)102 public Queue<Integer> create(Comparator<Integer> comparator) { 103 return MinMaxPriorityQueue.orderedBy(comparator).create(); 104 } 105 }, 106 PRIORITY_QUEUE { 107 @Override create(Comparator<Integer> comparator)108 public Queue<Integer> create(Comparator<Integer> comparator) { 109 return new PriorityQueue<>(11, comparator); 110 } 111 }, 112 INVERTED_MIN_MAX { 113 @Override create(Comparator<Integer> comparator)114 public Queue<Integer> create(Comparator<Integer> comparator) { 115 return new InvertedMinMaxPriorityQueue<>(comparator); 116 } 117 }; 118 create(Comparator<Integer> comparator)119 public abstract Queue<Integer> create(Comparator<Integer> comparator); 120 } 121 122 /** 123 * Does a CPU intensive operation on Integer and returns a BigInteger Used to implement an 124 * ordering that spends a lot of cpu. 125 */ 126 static class ExpensiveComputation implements Function<Integer, BigInteger> { 127 @Override apply(Integer from)128 public BigInteger apply(Integer from) { 129 BigInteger v = BigInteger.valueOf(from); 130 // Math.sin is very slow for values outside 4*pi 131 // Need to take absolute value to avoid inverting the value. 132 for (double i = 0; i < 100; i += 20) { 133 v = 134 v.add( 135 v.multiply( 136 BigInteger.valueOf(((Double) Math.abs(Math.sin(i) * 10.0)).longValue()))); 137 } 138 return v; 139 } 140 } 141 142 public enum ComparatorType { 143 CHEAP { 144 @Override get()145 public Comparator<Integer> get() { 146 return Ordering.natural(); 147 } 148 }, 149 EXPENSIVE { 150 @Override get()151 public Comparator<Integer> get() { 152 return Ordering.natural().onResultOf(new ExpensiveComputation()); 153 } 154 }; 155 get()156 public abstract Comparator<Integer> get(); 157 } 158 } 159