1 /* 2 * Copyright (C) 2010 Google Inc. 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 benchmarks.regression; 18 19 import com.google.caliper.Param; 20 import com.google.caliper.SimpleBenchmark; 21 import java.util.ArrayList; 22 import java.util.Collections; 23 import java.util.List; 24 import java.util.PriorityQueue; 25 import java.util.Random; 26 27 public class PriorityQueueBenchmark extends SimpleBenchmark { 28 @Param({"100", "1000", "10000"}) private int queueSize; 29 @Param({"0", "25", "50", "75", "100"}) private int hitRate; 30 31 private PriorityQueue<Integer> pq; 32 private PriorityQueue<Integer> usepq; 33 private List<Integer> seekElements; 34 private Random random = new Random(189279387L); 35 36 @Override protected void setUp() throws Exception { 37 pq = new PriorityQueue<Integer>(); 38 usepq = new PriorityQueue<Integer>(); 39 seekElements = new ArrayList<Integer>(); 40 List<Integer> allElements = new ArrayList<Integer>(); 41 int numShared = (int)(queueSize * ((double)hitRate / 100)); 42 // the total number of elements we require to engineer a hit rate of hitRate% 43 int totalElements = 2 * queueSize - numShared; 44 for (int i = 0; i < totalElements; i++) { 45 allElements.add(i); 46 } 47 // shuffle these elements so that we get a reasonable distribution of missed elements 48 Collections.shuffle(allElements, random); 49 // add shared elements 50 for (int i = 0; i < numShared; i++) { 51 pq.add(allElements.get(i)); 52 seekElements.add(allElements.get(i)); 53 } 54 // add priority queue only elements (these won't be touched) 55 for (int i = numShared; i < queueSize; i++) { 56 pq.add(allElements.get(i)); 57 } 58 // add non-priority queue elements (these will be misses) 59 for (int i = queueSize; i < totalElements; i++) { 60 seekElements.add(allElements.get(i)); 61 } 62 usepq = new PriorityQueue<Integer>(pq); 63 // shuffle again so that elements are accessed in a different pattern than they were 64 // inserted 65 Collections.shuffle(seekElements, random); 66 } 67 68 public boolean timeRemove(int reps) { 69 boolean dummy = false; 70 int elementsSize = seekElements.size(); 71 // At most allow the queue to empty 10%. 72 int resizingThreshold = queueSize / 10; 73 for (int i = 0; i < reps; i++) { 74 // Reset queue every so often. This will be called more often for smaller 75 // queueSizes, but since a copy is linear, it will also cost proportionally 76 // less, and hopefully it will approximately balance out. 77 if (i % resizingThreshold == 0) { 78 usepq = new PriorityQueue<Integer>(pq); 79 } 80 dummy = usepq.remove(seekElements.get(i % elementsSize)); 81 } 82 return dummy; 83 } 84 } 85