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