279 lines
7.6 KiB
Java
279 lines
7.6 KiB
Java
/*
|
|
* Copyright (C) 2010 The Guava Authors
|
|
*
|
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
* you may not use this file except in compliance with the License.
|
|
* You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
|
|
package com.google.common.collect;
|
|
|
|
import static com.google.common.collect.Lists.newArrayList;
|
|
|
|
import com.google.caliper.BeforeExperiment;
|
|
import com.google.caliper.Benchmark;
|
|
import com.google.caliper.Param;
|
|
import com.google.common.collect.CollectionBenchmarkSampleData.Element;
|
|
import java.util.Collection;
|
|
import java.util.Collections;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.concurrent.ConcurrentHashMap;
|
|
import java.util.concurrent.ConcurrentSkipListMap;
|
|
|
|
/**
|
|
* A microbenchmark that tests the performance of get() and iteration on various map
|
|
* implementations. Forked from {@link SetContainsBenchmark}.
|
|
*
|
|
* @author Nicholaus Shupe
|
|
*/
|
|
public class MapBenchmark {
|
|
@Param({"Hash", "LinkedHM", "MapMaker1", "Immutable"})
|
|
private Impl impl;
|
|
|
|
public enum Impl {
|
|
Hash {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = Maps.newHashMap();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
LinkedHM {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = Maps.newLinkedHashMap();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
UnmodHM {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
return Collections.unmodifiableMap(Hash.create(keys));
|
|
}
|
|
},
|
|
SyncHM {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
return Collections.synchronizedMap(Hash.create(keys));
|
|
}
|
|
},
|
|
Tree {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = Maps.newTreeMap();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
SkipList {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = new ConcurrentSkipListMap<>();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
ConcurrentHM1 {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = new ConcurrentHashMap<>(keys.size(), 0.75f, 1);
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
ConcurrentHM16 {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = new ConcurrentHashMap<>(keys.size(), 0.75f, 16);
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
MapMaker1 {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = new MapMaker().concurrencyLevel(1).makeMap();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
MapMaker16 {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
Map<Element, Element> map = new MapMaker().concurrencyLevel(16).makeMap();
|
|
for (Element element : keys) {
|
|
map.put(element, element);
|
|
}
|
|
return map;
|
|
}
|
|
},
|
|
Immutable {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
ImmutableMap.Builder<Element, Element> builder = ImmutableMap.builder();
|
|
for (Element element : keys) {
|
|
builder.put(element, element);
|
|
}
|
|
return builder.build();
|
|
}
|
|
},
|
|
ImmutableSorted {
|
|
@Override
|
|
Map<Element, Element> create(Collection<Element> keys) {
|
|
ImmutableSortedMap.Builder<Element, Element> builder = ImmutableSortedMap.naturalOrder();
|
|
for (Element element : keys) {
|
|
builder.put(element, element);
|
|
}
|
|
return builder.build();
|
|
}
|
|
};
|
|
|
|
abstract Map<Element, Element> create(Collection<Element> contents);
|
|
}
|
|
|
|
@Param({"5", "50", "500", "5000", "50000"})
|
|
private int size;
|
|
|
|
// TODO: look at exact (==) hits vs. equals() hits?
|
|
@Param("0.9")
|
|
private double hitRate;
|
|
|
|
@Param("true")
|
|
private boolean isUserTypeFast;
|
|
|
|
// "" means no fixed seed
|
|
@Param("")
|
|
private SpecialRandom random;
|
|
|
|
@Param("false")
|
|
private boolean sortedData;
|
|
|
|
// the following must be set during setUp
|
|
private Element[] queries;
|
|
private Map<Element, Element> mapToTest;
|
|
|
|
private Collection<Element> values;
|
|
|
|
@BeforeExperiment
|
|
void setUp() {
|
|
CollectionBenchmarkSampleData sampleData =
|
|
new CollectionBenchmarkSampleData(isUserTypeFast, random, hitRate, size);
|
|
|
|
if (sortedData) {
|
|
List<Element> valueList = newArrayList(sampleData.getValuesInSet());
|
|
Collections.sort(valueList);
|
|
values = valueList;
|
|
} else {
|
|
values = sampleData.getValuesInSet();
|
|
}
|
|
this.mapToTest = impl.create(values);
|
|
this.queries = sampleData.getQueries();
|
|
}
|
|
|
|
@Benchmark
|
|
boolean get(int reps) {
|
|
// Paranoia: acting on hearsay that accessing fields might be slow
|
|
// Should write a benchmark to test that!
|
|
Map<Element, Element> map = mapToTest;
|
|
Element[] queries = this.queries;
|
|
|
|
// Allows us to use & instead of %, acting on hearsay that division
|
|
// operators (/%) are disproportionately expensive; should test this too!
|
|
int mask = queries.length - 1;
|
|
|
|
boolean dummy = false;
|
|
for (int i = 0; i < reps; i++) {
|
|
dummy ^= map.get(queries[i & mask]) != null;
|
|
}
|
|
return dummy;
|
|
}
|
|
|
|
@Benchmark
|
|
int createAndPopulate(int reps) {
|
|
int dummy = 0;
|
|
for (int i = 0; i < reps; i++) {
|
|
dummy += impl.create(values).size();
|
|
}
|
|
return dummy;
|
|
}
|
|
|
|
@Benchmark
|
|
boolean createPopulateAndRemove(int reps) {
|
|
boolean dummy = false;
|
|
for (int i = 1; i < reps; i++) {
|
|
Map<Element, Element> map = impl.create(values);
|
|
for (Element value : values) {
|
|
dummy |= map.remove(value) == null;
|
|
}
|
|
}
|
|
return dummy;
|
|
}
|
|
|
|
@Benchmark
|
|
boolean iterateWithEntrySet(int reps) {
|
|
Map<Element, Element> map = mapToTest;
|
|
|
|
boolean dummy = false;
|
|
for (int i = 0; i < reps; i++) {
|
|
for (Map.Entry<Element, Element> entry : map.entrySet()) {
|
|
dummy ^= entry.getKey() != entry.getValue();
|
|
}
|
|
}
|
|
return dummy;
|
|
}
|
|
|
|
@Benchmark
|
|
boolean iterateWithKeySetAndGet(int reps) {
|
|
Map<Element, Element> map = mapToTest;
|
|
|
|
boolean dummy = false;
|
|
for (int i = 0; i < reps; i++) {
|
|
for (Element key : map.keySet()) {
|
|
Element value = map.get(key);
|
|
dummy ^= key != value;
|
|
}
|
|
}
|
|
return dummy;
|
|
}
|
|
|
|
@Benchmark
|
|
boolean iterateValuesAndGet(int reps) {
|
|
Map<Element, Element> map = mapToTest;
|
|
|
|
boolean dummy = false;
|
|
for (int i = 0; i < reps; i++) {
|
|
for (Element key : map.values()) {
|
|
// This normally wouldn't make sense, but because our keys are our values it kind of does
|
|
Element value = map.get(key);
|
|
dummy ^= key != value;
|
|
}
|
|
}
|
|
return dummy;
|
|
}
|
|
}
|