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
17package com.google.common.collect;
18
19import static com.google.common.collect.Lists.newArrayList;
20
21import com.google.caliper.BeforeExperiment;
22import com.google.caliper.Benchmark;
23import com.google.caliper.Param;
24import com.google.common.collect.CollectionBenchmarkSampleData.Element;
25
26import java.util.Collection;
27import java.util.Collections;
28import java.util.List;
29import java.util.Map;
30import java.util.concurrent.ConcurrentHashMap;
31import java.util.concurrent.ConcurrentSkipListMap;
32
33/**
34 * A microbenchmark that tests the performance of get() and iteration on various map
35 * implementations.  Forked from {@link SetContainsBenchmark}.
36 *
37 * @author Nicholaus Shupe
38 */
39public class MapBenchmark {
40  @Param({"Hash", "LinkedHM", "MapMaker1", "Immutable"})
41  private Impl impl;
42
43  public enum Impl {
44    Hash {
45      @Override Map<Element, Element> create(Collection<Element> keys) {
46        Map<Element, Element> map = Maps.newHashMap();
47        for (Element element: keys) {
48          map.put(element, element);
49        }
50        return map;
51      }
52    },
53    LinkedHM {
54      @Override Map<Element, Element> create(Collection<Element> keys) {
55        Map<Element, Element> map = Maps.newLinkedHashMap();
56        for (Element element: keys) {
57          map.put(element, element);
58        }
59        return map;
60      }
61    },
62    UnmodHM {
63      @Override Map<Element, Element> create(Collection<Element> keys) {
64        return Collections.unmodifiableMap(Hash.create(keys));
65      }
66    },
67    SyncHM {
68      @Override Map<Element, Element> create(Collection<Element> keys) {
69        return Collections.synchronizedMap(Hash.create(keys));
70      }
71    },
72    Tree {
73      @Override Map<Element, Element> create(Collection<Element> keys) {
74        Map<Element, Element> map = Maps.newTreeMap();
75        for (Element element: keys) {
76          map.put(element, element);
77        }
78        return map;
79      }
80    },
81    SkipList {
82      @Override Map<Element, Element> create(Collection<Element> keys) {
83        Map<Element, Element> map = new ConcurrentSkipListMap<Element, Element>();
84        for (Element element: keys) {
85          map.put(element, element);
86        }
87        return map;
88      }
89    },
90    ConcurrentHM1 {
91      @Override Map<Element, Element> create(Collection<Element> keys) {
92        Map<Element, Element> map =
93            new ConcurrentHashMap<Element, Element>(keys.size(), 0.75f, 1);
94        for (Element element: keys) {
95          map.put(element, element);
96        }
97        return map;
98      }
99    },
100    ConcurrentHM16 {
101      @Override Map<Element, Element> create(Collection<Element> keys) {
102        Map<Element, Element> map =
103            new ConcurrentHashMap<Element, Element>(keys.size(), 0.75f, 16);
104        for (Element element: keys) {
105          map.put(element, element);
106        }
107        return map;
108      }
109    },
110    MapMaker1 {
111      @Override Map<Element, Element> create(Collection<Element> keys) {
112        Map<Element, Element> map = new MapMaker()
113            .concurrencyLevel(1)
114            .makeMap();
115        for (Element element: keys) {
116          map.put(element, element);
117        }
118        return map;
119      }
120    },
121    MapMaker16 {
122      @Override Map<Element, Element> create(Collection<Element> keys) {
123        Map<Element, Element> map = new MapMaker()
124            .concurrencyLevel(16)
125            .makeMap();
126        for (Element element: keys) {
127          map.put(element, element);
128        }
129        return map;
130      }
131    },
132    Immutable {
133      @Override Map<Element, Element> create(Collection<Element> keys) {
134        ImmutableMap.Builder<Element, Element> builder = ImmutableMap.builder();
135        for (Element element : keys) {
136          builder.put(element, element);
137        }
138        return builder.build();
139      }
140    },
141    ImmutableSorted {
142      @Override Map<Element, Element> create(Collection<Element> keys) {
143        ImmutableSortedMap.Builder<Element, Element> builder =
144            ImmutableSortedMap.naturalOrder();
145        for (Element element : keys) {
146          builder.put(element, element);
147        }
148        return builder.build();
149      }
150    };
151
152    abstract Map<Element, Element> create(Collection<Element> contents);
153  }
154
155  @Param({"5", "50", "500", "5000", "50000"})
156  private int size;
157
158  // TODO: look at exact (==) hits vs. equals() hits?
159  @Param("0.9")
160  private double hitRate;
161
162  @Param("true")
163  private boolean isUserTypeFast;
164
165  // "" means no fixed seed
166  @Param("")
167  private SpecialRandom random;
168
169  @Param("false")
170  private boolean sortedData;
171
172  // the following must be set during setUp
173  private Element[] queries;
174  private Map<Element, Element> mapToTest;
175
176  private Collection<Element> values;
177
178  @BeforeExperiment void setUp() {
179    CollectionBenchmarkSampleData sampleData =
180        new CollectionBenchmarkSampleData(
181            isUserTypeFast, random, hitRate, size);
182
183    if (sortedData) {
184      List<Element> valueList = newArrayList(sampleData.getValuesInSet());
185      Collections.sort(valueList);
186      values = valueList;
187    } else {
188      values = sampleData.getValuesInSet();
189    }
190    this.mapToTest = impl.create(values);
191    this.queries = sampleData.getQueries();
192  }
193
194  @Benchmark boolean get(int reps) {
195    // Paranoia: acting on hearsay that accessing fields might be slow
196    // Should write a benchmark to test that!
197    Map<Element, Element> map = mapToTest;
198    Element[] queries = this.queries;
199
200    // Allows us to use & instead of %, acting on hearsay that division
201    // operators (/%) are disproportionately expensive; should test this too!
202    int mask = queries.length - 1;
203
204    boolean dummy = false;
205    for (int i = 0; i < reps; i++) {
206      dummy ^= map.get(queries[i & mask]) != null;
207    }
208    return dummy;
209  }
210
211  @Benchmark int createAndPopulate(int reps) {
212    int dummy = 0;
213    for (int i = 0; i < reps; i++) {
214      dummy += impl.create(values).size();
215    }
216    return dummy;
217  }
218
219  @Benchmark boolean iterateWithEntrySet(int reps) {
220    Map<Element, Element> map = mapToTest;
221
222    boolean dummy = false;
223    for (int i = 0; i < reps; i++) {
224      for (Map.Entry<Element, Element> entry : map.entrySet()) {
225        dummy ^= entry.getKey() != entry.getValue();
226      }
227    }
228    return dummy;
229  }
230
231  @Benchmark boolean iterateWithKeySetAndGet(int reps) {
232    Map<Element, Element> map = mapToTest;
233
234    boolean dummy = false;
235    for (int i = 0; i < reps; i++) {
236      for (Element key : map.keySet()) {
237        Element value = map.get(key);
238        dummy ^= key != value;
239      }
240    }
241    return dummy;
242
243  }
244}
245