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
17package com.google.common.collect;
18
19import com.google.caliper.BeforeExperiment;
20import com.google.caliper.Benchmark;
21import com.google.caliper.Param;
22import com.google.common.base.Function;
23import com.google.common.collect.ForwardingQueue;
24import com.google.common.collect.MinMaxPriorityQueue;
25import com.google.common.collect.Ordering;
26
27import java.math.BigInteger;
28import java.util.Comparator;
29import java.util.PriorityQueue;
30import java.util.Queue;
31import java.util.Random;
32
33/**
34 * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue.
35 *
36 * @author Sverre Sundsdal
37 */
38public 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
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
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
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;
82    public InvertedMinMaxPriorityQueue(Comparator<T> comparator) {
83      mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create();
84    }
85
86    @Override
87    protected Queue<T> delegate() {
88      return mmHeap;
89    }
90
91    @Override
92    public T poll() {
93      return mmHeap.pollLast();
94    }
95
96  }
97
98  public enum HeapType {
99    MIN_MAX {
100      @Override public Queue<Integer> create(Comparator<Integer> comparator) {
101        return MinMaxPriorityQueue.orderedBy(comparator).create();
102      }
103    },
104    PRIORITY_QUEUE {
105      @Override public Queue<Integer> create(Comparator<Integer> comparator) {
106        return new PriorityQueue<Integer>(11, comparator);
107      }
108    },
109    INVERTED_MIN_MAX {
110      @Override public Queue<Integer> create(Comparator<Integer> comparator) {
111        return new InvertedMinMaxPriorityQueue<Integer>(comparator);
112      }
113    };
114
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
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 {
139      @Override public Comparator<Integer> get() {
140        return Ordering.natural();
141      }
142    },
143    EXPENSIVE {
144      @Override public Comparator<Integer> get() {
145        return Ordering.natural().onResultOf(new ExpensiveComputation());
146      }
147    };
148    public abstract Comparator<Integer> get();
149  }
150}
151