guava-tests/benchmark/com/google/common/collect/MinMaxPriorityQueueBenchmark.java

/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.Param;
import com.google.common.base.Function;
import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

/**
 * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue.
 *
 * @author Sverre Sundsdal
 */
public class MinMaxPriorityQueueBenchmark {
  @Param private ComparatorType comparator;

  // TODO(kevinb): add 1000000 back when we have the ability to throw
  // NotApplicableException in the expensive comparator case.
  @Param({"100", "10000"})
  private int size;

  @Param private HeapType heap;

  private Queue<Integer> queue;

  private final Random random = new Random();

  @BeforeExperiment
  void setUp() {
    queue = heap.create(comparator.get());
    for (int i = 0; i < size; i++) {
      queue.add(random.nextInt());
    }
  }

  @Benchmark
  void pollAndAdd(int reps) {
    for (int i = 0; i < reps; i++) {
      // TODO(kevinb): precompute random #s?
      queue.add(queue.poll() ^ random.nextInt());
    }
  }

  @Benchmark
  void populate(int reps) {
    for (int i = 0; i < reps; i++) {
      queue.clear();
      for (int j = 0; j < size; j++) {
        // TODO(kevinb): precompute random #s?
        queue.add(random.nextInt());
      }
    }
  }

  /**
   * Implementation of the InvertedMinMaxPriorityQueue which forwards all calls to a
   * MinMaxPriorityQueue, except poll, which is forwarded to pollMax. That way we can benchmark
   * pollMax using the same code that benchmarks poll.
   */
  static final class InvertedMinMaxPriorityQueue<T> extends ForwardingQueue<T> {
    MinMaxPriorityQueue<T> mmHeap;

    public InvertedMinMaxPriorityQueue(Comparator<T> comparator) {
      mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create();
    }

    @Override
    protected Queue<T> delegate() {
      return mmHeap;
    }

    @Override
    public T poll() {
      return mmHeap.pollLast();
    }
  }

  public enum HeapType {
    MIN_MAX {
      @Override
      public Queue<Integer> create(Comparator<Integer> comparator) {
        return MinMaxPriorityQueue.orderedBy(comparator).create();
      }
    },
    PRIORITY_QUEUE {
      @Override
      public Queue<Integer> create(Comparator<Integer> comparator) {
        return new PriorityQueue<>(11, comparator);
      }
    },
    INVERTED_MIN_MAX {
      @Override
      public Queue<Integer> create(Comparator<Integer> comparator) {
        return new InvertedMinMaxPriorityQueue<>(comparator);
      }
    };

    public abstract Queue<Integer> create(Comparator<Integer> comparator);
  }

  /**
   * Does a CPU intensive operation on Integer and returns a BigInteger Used to implement an
   * ordering that spends a lot of cpu.
   */
  static class ExpensiveComputation implements Function<Integer, BigInteger> {
    @Override
    public BigInteger apply(Integer from) {
      BigInteger v = BigInteger.valueOf(from);
      // Math.sin is very slow for values outside 4*pi
      // Need to take absolute value to avoid inverting the value.
      for (double i = 0; i < 100; i += 20) {
        v =
            v.add(
                v.multiply(
                    BigInteger.valueOf(((Double) Math.abs(Math.sin(i) * 10.0)).longValue())));
      }
      return v;
    }
  }

  public enum ComparatorType {
    CHEAP {
      @Override
      public Comparator<Integer> get() {
        return Ordering.natural();
      }
    },
    EXPENSIVE {
      @Override
      public Comparator<Integer> get() {
        return Ordering.natural().onResultOf(new ExpensiveComputation());
      }
    };

    public abstract Comparator<Integer> get();
  }
}