Home | History | Annotate | Download | only in collect 
      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 
     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