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.AfterExperiment; 20 import com.google.caliper.BeforeExperiment; 21 import com.google.caliper.Benchmark; 22 import com.google.caliper.Param; 23 import com.google.common.base.Function; 24 import com.google.common.collect.MapMaker; 25 import com.google.common.primitives.Ints; 26 27 import java.util.Map; 28 import java.util.Random; 29 import java.util.concurrent.atomic.AtomicLong; 30 31 /** 32 * Simple single-threaded benchmark for a computing map with maximum size. 33 * 34 * @author Charles Fry 35 */ 36 public class MapMakerSingleThreadBenchmark { 37 @Param({"1000", "2000"}) int maximumSize; 38 @Param("5000") int distinctKeys; 39 @Param("4") int segments; 40 41 // 1 means uniform likelihood of keys; higher means some keys are more popular 42 // tweak this to control hit rate 43 @Param("2.5") double concentration; 44 45 Random random = new Random(); 46 47 Map<Integer, Integer> cache; 48 49 int max; 50 51 static AtomicLong requests = new AtomicLong(0); 52 static AtomicLong misses = new AtomicLong(0); 53 setUp()54 @BeforeExperiment void setUp() { 55 // random integers will be generated in this range, then raised to the 56 // power of (1/concentration) and floor()ed 57 max = Ints.checkedCast((long) Math.pow(distinctKeys, concentration)); 58 59 cache = new MapMaker() 60 .concurrencyLevel(segments) 61 .maximumSize(maximumSize) 62 .makeComputingMap( 63 new Function<Integer, Integer>() { 64 @Override public Integer apply(Integer from) { 65 return (int) misses.incrementAndGet(); 66 } 67 }); 68 69 // To start, fill up the cache. 70 // Each miss both increments the counter and causes the map to grow by one, 71 // so until evictions begin, the size of the map is the greatest return 72 // value seen so far 73 while (cache.get(nextRandomKey()) < maximumSize) {} 74 75 requests.set(0); 76 misses.set(0); 77 } 78 time(int reps)79 @Benchmark int time(int reps) { 80 int dummy = 0; 81 for (int i = 0; i < reps; i++) { 82 dummy += cache.get(nextRandomKey()); 83 } 84 requests.addAndGet(reps); 85 return dummy; 86 } 87 nextRandomKey()88 private int nextRandomKey() { 89 int a = random.nextInt(max); 90 91 /* 92 * For example, if concentration=2.0, the following takes the square root of 93 * the uniformly-distributed random integer, then truncates any fractional 94 * part, so higher integers would appear (in this case linearly) more often 95 * than lower ones. 96 */ 97 return (int) Math.pow(a, 1.0 / concentration); 98 } 99 tearDown()100 @AfterExperiment void tearDown() { 101 double req = requests.get(); 102 double hit = req - misses.get(); 103 104 // Currently, this is going into /dev/null, but I'll fix that 105 System.out.println("hit rate: " + hit / req); 106 } 107 108 // for proper distributions later: 109 // import JSci.maths.statistics.ProbabilityDistribution; 110 // int key = (int) dist.inverse(random.nextDouble()); 111 } 112