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