17dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Copyright (C) 2010 The Guava Authors 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 57dd252788645e940eada959bdde927426e2531c9Paul Duffin * you may not use this file except in compliance with the License. 67dd252788645e940eada959bdde927426e2531c9Paul Duffin * You may obtain a copy of the License at 77dd252788645e940eada959bdde927426e2531c9Paul Duffin * 87dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * 107dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unless required by applicable law or agreed to in writing, software 117dd252788645e940eada959bdde927426e2531c9Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 127dd252788645e940eada959bdde927426e2531c9Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137dd252788645e940eada959bdde927426e2531c9Paul Duffin * See the License for the specific language governing permissions and 147dd252788645e940eada959bdde927426e2531c9Paul Duffin * limitations under the License. 157dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 167dd252788645e940eada959bdde927426e2531c9Paul Duffin 177dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.collect; 187dd252788645e940eada959bdde927426e2531c9Paul Duffin 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.caliper.AfterExperiment; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.caliper.BeforeExperiment; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.caliper.Benchmark; 227dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.caliper.Param; 237dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Function; 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.MapMaker; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.primitives.Ints; 267dd252788645e940eada959bdde927426e2531c9Paul Duffin 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Map; 287dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Random; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.atomic.AtomicLong; 307dd252788645e940eada959bdde927426e2531c9Paul Duffin 317dd252788645e940eada959bdde927426e2531c9Paul Duffin/** 327dd252788645e940eada959bdde927426e2531c9Paul Duffin * Simple single-threaded benchmark for a computing map with maximum size. 337dd252788645e940eada959bdde927426e2531c9Paul Duffin * 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Charles Fry 357dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 360888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic class MapMakerSingleThreadBenchmark { 377dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param({"1000", "2000"}) int maximumSize; 387dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param("5000") int distinctKeys; 397dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param("4") int segments; 407dd252788645e940eada959bdde927426e2531c9Paul Duffin 417dd252788645e940eada959bdde927426e2531c9Paul Duffin // 1 means uniform likelihood of keys; higher means some keys are more popular 427dd252788645e940eada959bdde927426e2531c9Paul Duffin // tweak this to control hit rate 437dd252788645e940eada959bdde927426e2531c9Paul Duffin @Param("2.5") double concentration; 447dd252788645e940eada959bdde927426e2531c9Paul Duffin 457dd252788645e940eada959bdde927426e2531c9Paul Duffin Random random = new Random(); 467dd252788645e940eada959bdde927426e2531c9Paul Duffin 477dd252788645e940eada959bdde927426e2531c9Paul Duffin Map<Integer, Integer> cache; 487dd252788645e940eada959bdde927426e2531c9Paul Duffin 497dd252788645e940eada959bdde927426e2531c9Paul Duffin int max; 507dd252788645e940eada959bdde927426e2531c9Paul Duffin 517dd252788645e940eada959bdde927426e2531c9Paul Duffin static AtomicLong requests = new AtomicLong(0); 527dd252788645e940eada959bdde927426e2531c9Paul Duffin static AtomicLong misses = new AtomicLong(0); 537dd252788645e940eada959bdde927426e2531c9Paul Duffin 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin @BeforeExperiment void setUp() { 557dd252788645e940eada959bdde927426e2531c9Paul Duffin // random integers will be generated in this range, then raised to the 567dd252788645e940eada959bdde927426e2531c9Paul Duffin // power of (1/concentration) and floor()ed 577dd252788645e940eada959bdde927426e2531c9Paul Duffin max = Ints.checkedCast((long) Math.pow(distinctKeys, concentration)); 587dd252788645e940eada959bdde927426e2531c9Paul Duffin 597dd252788645e940eada959bdde927426e2531c9Paul Duffin cache = new MapMaker() 607dd252788645e940eada959bdde927426e2531c9Paul Duffin .concurrencyLevel(segments) 617dd252788645e940eada959bdde927426e2531c9Paul Duffin .maximumSize(maximumSize) 627dd252788645e940eada959bdde927426e2531c9Paul Duffin .makeComputingMap( 637dd252788645e940eada959bdde927426e2531c9Paul Duffin new Function<Integer, Integer>() { 647dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public Integer apply(Integer from) { 657dd252788645e940eada959bdde927426e2531c9Paul Duffin return (int) misses.incrementAndGet(); 667dd252788645e940eada959bdde927426e2531c9Paul Duffin } 677dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 687dd252788645e940eada959bdde927426e2531c9Paul Duffin 697dd252788645e940eada959bdde927426e2531c9Paul Duffin // To start, fill up the cache. 707dd252788645e940eada959bdde927426e2531c9Paul Duffin // Each miss both increments the counter and causes the map to grow by one, 717dd252788645e940eada959bdde927426e2531c9Paul Duffin // so until evictions begin, the size of the map is the greatest return 727dd252788645e940eada959bdde927426e2531c9Paul Duffin // value seen so far 737dd252788645e940eada959bdde927426e2531c9Paul Duffin while (cache.get(nextRandomKey()) < maximumSize) {} 747dd252788645e940eada959bdde927426e2531c9Paul Duffin 757dd252788645e940eada959bdde927426e2531c9Paul Duffin requests.set(0); 767dd252788645e940eada959bdde927426e2531c9Paul Duffin misses.set(0); 777dd252788645e940eada959bdde927426e2531c9Paul Duffin } 787dd252788645e940eada959bdde927426e2531c9Paul Duffin 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Benchmark int time(int reps) { 807dd252788645e940eada959bdde927426e2531c9Paul Duffin int dummy = 0; 817dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < reps; i++) { 827dd252788645e940eada959bdde927426e2531c9Paul Duffin dummy += cache.get(nextRandomKey()); 837dd252788645e940eada959bdde927426e2531c9Paul Duffin } 847dd252788645e940eada959bdde927426e2531c9Paul Duffin requests.addAndGet(reps); 857dd252788645e940eada959bdde927426e2531c9Paul Duffin return dummy; 867dd252788645e940eada959bdde927426e2531c9Paul Duffin } 877dd252788645e940eada959bdde927426e2531c9Paul Duffin 887dd252788645e940eada959bdde927426e2531c9Paul Duffin private int nextRandomKey() { 897dd252788645e940eada959bdde927426e2531c9Paul Duffin int a = random.nextInt(max); 907dd252788645e940eada959bdde927426e2531c9Paul Duffin 917dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 927dd252788645e940eada959bdde927426e2531c9Paul Duffin * For example, if concentration=2.0, the following takes the square root of 937dd252788645e940eada959bdde927426e2531c9Paul Duffin * the uniformly-distributed random integer, then truncates any fractional 947dd252788645e940eada959bdde927426e2531c9Paul Duffin * part, so higher integers would appear (in this case linearly) more often 957dd252788645e940eada959bdde927426e2531c9Paul Duffin * than lower ones. 967dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 977dd252788645e940eada959bdde927426e2531c9Paul Duffin return (int) Math.pow(a, 1.0 / concentration); 987dd252788645e940eada959bdde927426e2531c9Paul Duffin } 997dd252788645e940eada959bdde927426e2531c9Paul Duffin 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin @AfterExperiment void tearDown() { 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin double req = requests.get(); 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin double hit = req - misses.get(); 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin // Currently, this is going into /dev/null, but I'll fix that 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin System.out.println("hit rate: " + hit / req); 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin // for proper distributions later: 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin // import JSci.maths.statistics.ProbabilityDistribution; 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin // int key = (int) dist.inverse(random.nextDouble()); 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin} 112