17dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Copyright (C) 2010 The Guava Authors 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 57dd252788645e940eada959bdde927426e2531c9Paul Duffin * you may not use this file except in compliance with the License. 67dd252788645e940eada959bdde927426e2531c9Paul Duffin * You may obtain a copy of the License at 77dd252788645e940eada959bdde927426e2531c9Paul Duffin * 87dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * 107dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unless required by applicable law or agreed to in writing, software 117dd252788645e940eada959bdde927426e2531c9Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 127dd252788645e940eada959bdde927426e2531c9Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137dd252788645e940eada959bdde927426e2531c9Paul Duffin * See the License for the specific language governing permissions and 147dd252788645e940eada959bdde927426e2531c9Paul Duffin * limitations under the License. 157dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 167dd252788645e940eada959bdde927426e2531c9Paul Duffin 177dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.collect; 187dd252788645e940eada959bdde927426e2531c9Paul Duffin 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.caliper.BeforeExperiment; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.caliper.Benchmark; 217dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.caliper.Param; 227dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Function; 237dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.ForwardingQueue; 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.MinMaxPriorityQueue; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.Ordering; 267dd252788645e940eada959bdde927426e2531c9Paul Duffin 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.math.BigInteger; 287dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Comparator; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.PriorityQueue; 307dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Queue; 317dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Random; 327dd252788645e940eada959bdde927426e2531c9Paul Duffin 337dd252788645e940eada959bdde927426e2531c9Paul Duffin/** 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue. 357dd252788645e940eada959bdde927426e2531c9Paul Duffin * 367dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Sverre Sundsdal 377dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 380888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic class MinMaxPriorityQueueBenchmark { 397dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param private ComparatorType comparator; 407dd252788645e940eada959bdde927426e2531c9Paul Duffin 417dd252788645e940eada959bdde927426e2531c9Paul Duffin // TODO(kevinb): add 1000000 back when we have the ability to throw 427dd252788645e940eada959bdde927426e2531c9Paul Duffin // NotApplicableException in the expensive comparator case. 437dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param({"100", "10000"}) private int size; 447dd252788645e940eada959bdde927426e2531c9Paul Duffin 457dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param private HeapType heap; 467dd252788645e940eada959bdde927426e2531c9Paul Duffin 477dd252788645e940eada959bdde927426e2531c9Paul Duffin private Queue<Integer> queue; 487dd252788645e940eada959bdde927426e2531c9Paul Duffin 497dd252788645e940eada959bdde927426e2531c9Paul Duffin private final Random random = new Random(); 507dd252788645e940eada959bdde927426e2531c9Paul Duffin 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @BeforeExperiment void setUp() { 527dd252788645e940eada959bdde927426e2531c9Paul Duffin queue = heap.create(comparator.get()); 537dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < size; i++) { 547dd252788645e940eada959bdde927426e2531c9Paul Duffin queue.add(random.nextInt()); 557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 567dd252788645e940eada959bdde927426e2531c9Paul Duffin } 577dd252788645e940eada959bdde927426e2531c9Paul Duffin 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Benchmark void pollAndAdd(int reps) { 597dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < reps; i++) { 607dd252788645e940eada959bdde927426e2531c9Paul Duffin // TODO(kevinb): precompute random #s? 617dd252788645e940eada959bdde927426e2531c9Paul Duffin queue.add(queue.poll() ^ random.nextInt()); 627dd252788645e940eada959bdde927426e2531c9Paul Duffin } 637dd252788645e940eada959bdde927426e2531c9Paul Duffin } 647dd252788645e940eada959bdde927426e2531c9Paul Duffin 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Benchmark void populate(int reps) { 667dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < reps; i++) { 677dd252788645e940eada959bdde927426e2531c9Paul Duffin queue.clear(); 687dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int j = 0; j < size; j++) { 697dd252788645e940eada959bdde927426e2531c9Paul Duffin // TODO(kevinb): precompute random #s? 707dd252788645e940eada959bdde927426e2531c9Paul Duffin queue.add(random.nextInt()); 717dd252788645e940eada959bdde927426e2531c9Paul Duffin } 727dd252788645e940eada959bdde927426e2531c9Paul Duffin } 737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 747dd252788645e940eada959bdde927426e2531c9Paul Duffin 757dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 767dd252788645e940eada959bdde927426e2531c9Paul Duffin * Implementation of the InvertedMinMaxPriorityQueue which forwards all calls to 777dd252788645e940eada959bdde927426e2531c9Paul Duffin * a MinMaxPriorityQueue, except poll, which is forwarded to pollMax. That way 787dd252788645e940eada959bdde927426e2531c9Paul Duffin * we can benchmark pollMax using the same code that benchmarks poll. 797dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 807dd252788645e940eada959bdde927426e2531c9Paul Duffin static final class InvertedMinMaxPriorityQueue <T> extends ForwardingQueue<T> { 817dd252788645e940eada959bdde927426e2531c9Paul Duffin MinMaxPriorityQueue<T> mmHeap; 827dd252788645e940eada959bdde927426e2531c9Paul Duffin public InvertedMinMaxPriorityQueue(Comparator<T> comparator) { 837dd252788645e940eada959bdde927426e2531c9Paul Duffin mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create(); 847dd252788645e940eada959bdde927426e2531c9Paul Duffin } 857dd252788645e940eada959bdde927426e2531c9Paul Duffin 867dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 877dd252788645e940eada959bdde927426e2531c9Paul Duffin protected Queue<T> delegate() { 887dd252788645e940eada959bdde927426e2531c9Paul Duffin return mmHeap; 897dd252788645e940eada959bdde927426e2531c9Paul Duffin } 907dd252788645e940eada959bdde927426e2531c9Paul Duffin 917dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 927dd252788645e940eada959bdde927426e2531c9Paul Duffin public T poll() { 937dd252788645e940eada959bdde927426e2531c9Paul Duffin return mmHeap.pollLast(); 947dd252788645e940eada959bdde927426e2531c9Paul Duffin } 957dd252788645e940eada959bdde927426e2531c9Paul Duffin 967dd252788645e940eada959bdde927426e2531c9Paul Duffin } 977dd252788645e940eada959bdde927426e2531c9Paul Duffin 987dd252788645e940eada959bdde927426e2531c9Paul Duffin public enum HeapType { 997dd252788645e940eada959bdde927426e2531c9Paul Duffin MIN_MAX { 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Queue<Integer> create(Comparator<Integer> comparator) { 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin return MinMaxPriorityQueue.orderedBy(comparator).create(); 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin }, 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin PRIORITY_QUEUE { 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Queue<Integer> create(Comparator<Integer> comparator) { 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin return new PriorityQueue<Integer>(11, comparator); 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin }, 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin INVERTED_MIN_MAX { 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Queue<Integer> create(Comparator<Integer> comparator) { 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin return new InvertedMinMaxPriorityQueue<Integer>(comparator); 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 1147dd252788645e940eada959bdde927426e2531c9Paul Duffin 1157dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract Queue<Integer> create(Comparator<Integer> comparator); 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin * Does a CPU intensive operation on Integer and returns a BigInteger 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin * Used to implement an ordering that spends a lot of cpu. 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin static class ExpensiveComputation implements Function<Integer, BigInteger> { 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin public BigInteger apply(Integer from) { 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin BigInteger v = BigInteger.valueOf(from); 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin // Math.sin is very slow for values outside 4*pi 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin // Need to take absolute value to avoid inverting the value. 1287dd252788645e940eada959bdde927426e2531c9Paul Duffin for (double i = 0; i < 100; i += 20) { 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin v = v.add(v.multiply( 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin BigInteger.valueOf( 1317dd252788645e940eada959bdde927426e2531c9Paul Duffin ((Double) Math.abs(Math.sin(i) * 10.0)).longValue()))); 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1337dd252788645e940eada959bdde927426e2531c9Paul Duffin return v; 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1357dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1367dd252788645e940eada959bdde927426e2531c9Paul Duffin 1377dd252788645e940eada959bdde927426e2531c9Paul Duffin public enum ComparatorType { 1387dd252788645e940eada959bdde927426e2531c9Paul Duffin CHEAP { 1397dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Comparator<Integer> get() { 1407dd252788645e940eada959bdde927426e2531c9Paul Duffin return Ordering.natural(); 1417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1427dd252788645e940eada959bdde927426e2531c9Paul Duffin }, 1437dd252788645e940eada959bdde927426e2531c9Paul Duffin EXPENSIVE { 1447dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Comparator<Integer> get() { 1457dd252788645e940eada959bdde927426e2531c9Paul Duffin return Ordering.natural().onResultOf(new ExpensiveComputation()); 1467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1477dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 1487dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract Comparator<Integer> get(); 1497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin} 151