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