1 /*
   2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.openjdk.bench.java.util.concurrent;
  24 
  25 import org.openjdk.jmh.annotations.Benchmark;
  26 import org.openjdk.jmh.annotations.BenchmarkMode;
  27 import org.openjdk.jmh.annotations.Mode;
  28 import org.openjdk.jmh.annotations.OutputTimeUnit;
  29 import org.openjdk.jmh.annotations.Scope;
  30 import org.openjdk.jmh.annotations.Setup;
  31 import org.openjdk.jmh.annotations.State;
  32 import org.openjdk.jmh.annotations.Threads;
  33 
  34 import java.util.Map;
  35 import java.util.concurrent.ConcurrentHashMap;
  36 import java.util.concurrent.TimeUnit;
  37 import java.util.concurrent.atomic.AtomicLong;
  38 
  39 @BenchmarkMode(Mode.AverageTime)
  40 @OutputTimeUnit(TimeUnit.NANOSECONDS)
  41 @State(Scope.Benchmark)
  42 public class Maps {
  43     private SimpleRandom rng;
  44     private Map<Integer, Integer> map;
  45     private Integer[] key;
  46 
  47     private int removesPerMaxRandom;
  48     private int insertsPerMaxRandom;
  49     private int total;
  50     private int position;
  51 
  52     @Setup
  53     public void initTest() {
  54         int nkeys = 10000;
  55         int pRemove = 10;
  56         int pInsert = 90;
  57         removesPerMaxRandom = (int) ((pRemove / 100.0 * 0x7FFFFFFFL));
  58         insertsPerMaxRandom = (int) ((pInsert / 100.0 * 0x7FFFFFFFL));
  59 
  60         rng = new SimpleRandom();
  61         map = new ConcurrentHashMap<>();
  62         total = 0;
  63         key = new Integer[nkeys];
  64         for (int i = 0; i < key.length; ++i) {
  65             key[i] = new Integer(rng.next());
  66         }
  67         position = key.length / 2;
  68     }
  69 
  70     @Benchmark
  71     @Threads(4)
  72     public void testConcurrentHashMap() {
  73         int pos = position;
  74         // random-walk around key positions, bunching accesses
  75         int r = rng.next();
  76         pos += (r & 7) - 3;
  77         while (pos >= key.length) {
  78             pos -= key.length;
  79         }
  80         while (pos < 0) {
  81             pos += key.length;
  82         }
  83         Integer k = key[pos];
  84         Integer x = map.get(k);
  85         if (x != null) {
  86             if (x.intValue() != k.intValue()) {
  87                 throw new Error("bad mapping: " + x + " to " + k);
  88             }
  89 
  90             if (r < removesPerMaxRandom) {
  91                 if (map.remove(k) != null) {
  92                     pos = total % key.length; // move from position
  93                 }
  94             }
  95         } else if (r < insertsPerMaxRandom) {
  96             ++pos;
  97             map.put(k, k);
  98         }
  99         total += r;
 100         position = pos;
 101     }
 102 
 103     private static class SimpleRandom {
 104         private final static long multiplier = 0x5DEECE66DL;
 105         private final static long addend = 0xBL;
 106         private final static long mask = (1L << 48) - 1;
 107         private final static AtomicLong seq = new AtomicLong(1);
 108         private long seed = System.nanoTime() + seq.getAndIncrement();
 109 
 110         public int next() {
 111             long nextSeed = (seed * multiplier + addend) & mask;
 112             seed = nextSeed;
 113             return ((int) (nextSeed >>> 17)) & 0x7FFFFFFF;
 114         }
 115     }
 116 }