|
| 1 | +package datadog.trace.util; |
| 2 | + |
| 3 | +import java.util.HashMap; |
| 4 | +import java.util.TreeMap; |
| 5 | +import java.util.concurrent.ThreadLocalRandom; |
| 6 | +import java.util.function.Supplier; |
| 7 | +import org.openjdk.jmh.annotations.Benchmark; |
| 8 | +import org.openjdk.jmh.annotations.Fork; |
| 9 | +import org.openjdk.jmh.annotations.Measurement; |
| 10 | +import org.openjdk.jmh.annotations.Threads; |
| 11 | +import org.openjdk.jmh.annotations.Warmup; |
| 12 | +import org.openjdk.jmh.infra.Blackhole; |
| 13 | + |
| 14 | +/** |
| 15 | + * |
| 16 | + * |
| 17 | + * <ul> |
| 18 | + * Benchmark to illustrate the trade-offs around case-insensitive Map look-ups - using either... |
| 19 | + * <li>(RECOMMENDED) TreeMap with Comparator of String::compareToIgnoreCase |
| 20 | + * <li>HashMap with look-ups using String::to<X>Case |
| 21 | + * </ul> |
| 22 | + * |
| 23 | + * <p>For case-insensitive lookups, TreeMap map creation is consistently faster because it avoids |
| 24 | + * String::to<X>Case calls. |
| 25 | + * |
| 26 | + * <p>Despite calls to String::to<X>Case, HashMap lookups are faster in single threaded |
| 27 | + * microbenchmark by 50% but are worse when frequently called in a multi-threaded system. |
| 28 | + * |
| 29 | + * <p>With many threads, the extra allocation from calling String::to<X>Case leads to frequent GCs |
| 30 | + * which has adverse impacts on the whole system. <code> |
| 31 | + * MacBook M1 with 1 thread (Java 21) |
| 32 | + * |
| 33 | + * Benchmark Mode Cnt Score Error Units |
| 34 | + * CaseInsensitiveMapBenchmark.create_hashMap thrpt 6 994213.041 ± 15718.903 ops/s |
| 35 | + * CaseInsensitiveMapBenchmark.create_treeMap thrpt 6 1522900.015 ± 21646.688 ops/s |
| 36 | + * |
| 37 | + * CaseInsensitiveMapBenchmark.get_hashMap thrpt 6 69149862.293 ± 9168648.566 ops/s |
| 38 | + * CaseInsensitiveMapBenchmark.get_treeMap thrpt 6 42796699.230 ± 9029447.805 ops/s |
| 39 | + * </code> <code> |
| 40 | + * MacBook M1 with 8 threads (Java 21) |
| 41 | + * |
| 42 | + * Benchmark Mode Cnt Score Error Units |
| 43 | + * CaseInsensitiveMapBenchmark.create_hashMap thrpt 6 6641003.483 ± 543210.409 ops/s |
| 44 | + * CaseInsensitiveMapBenchmark.create_treeMap thrpt 6 10030191.764 ± 1308865.113 ops/s |
| 45 | + * |
| 46 | + * CaseInsensitiveMapBenchmark.get_hashMap thrpt 6 38748031.837 ± 9012072.804 ops/s |
| 47 | + * CaseInsensitiveMapBenchmark.get_treeMap thrpt 6 173495470.789 ± 27824904.999 ops/s |
| 48 | + * </code> |
| 49 | + */ |
| 50 | +@Fork(2) |
| 51 | +@Warmup(iterations = 2) |
| 52 | +@Measurement(iterations = 3) |
| 53 | +@Threads(8) |
| 54 | +public class CaseInsensitiveMapBenchmark { |
| 55 | + static final String[] PREFIXES = {"foo", "bar", "baz", "quux"}; |
| 56 | + |
| 57 | + static final int NUM_SUFFIXES = 4; |
| 58 | + |
| 59 | + static <T> T init(Supplier<T> supplier) { |
| 60 | + return supplier.get(); |
| 61 | + } |
| 62 | + |
| 63 | + static final String[] UPPER_PREFIXES = |
| 64 | + init( |
| 65 | + () -> { |
| 66 | + String[] upperPrefixes = new String[PREFIXES.length]; |
| 67 | + for (int i = 0; i < PREFIXES.length; ++i) { |
| 68 | + upperPrefixes[i] = PREFIXES[i].toUpperCase(); |
| 69 | + } |
| 70 | + return upperPrefixes; |
| 71 | + }); |
| 72 | + |
| 73 | + static final String[] LOOKUP_KEYS = |
| 74 | + init( |
| 75 | + () -> { |
| 76 | + ThreadLocalRandom curRandom = ThreadLocalRandom.current(); |
| 77 | + |
| 78 | + String[] keys = new String[32]; |
| 79 | + for (int i = 0; i < keys.length; ++i) { |
| 80 | + int prefixIndex = curRandom.nextInt(PREFIXES.length); |
| 81 | + boolean toUpper = curRandom.nextBoolean(); |
| 82 | + int suffixIndex = curRandom.nextInt(NUM_SUFFIXES + 1); |
| 83 | + |
| 84 | + String key = PREFIXES[prefixIndex] + "-" + suffixIndex; |
| 85 | + keys[i] = toUpper ? key.toUpperCase() : key.toLowerCase(); |
| 86 | + } |
| 87 | + return keys; |
| 88 | + }); |
| 89 | + |
| 90 | + static int sharedLookupIndex = 0; |
| 91 | + |
| 92 | + static String nextLookupKey() { |
| 93 | + int localIndex = ++sharedLookupIndex; |
| 94 | + if (localIndex >= LOOKUP_KEYS.length) { |
| 95 | + sharedLookupIndex = localIndex = 0; |
| 96 | + } |
| 97 | + return LOOKUP_KEYS[localIndex]; |
| 98 | + } |
| 99 | + |
| 100 | + @Benchmark |
| 101 | + public void create_baseline(Blackhole blackhole) { |
| 102 | + for (int suffix = 0; suffix < NUM_SUFFIXES; ++suffix) { |
| 103 | + for (String prefix : PREFIXES) { |
| 104 | + blackhole.consume(prefix + "-" + suffix); |
| 105 | + blackhole.consume(Integer.valueOf(suffix)); |
| 106 | + } |
| 107 | + } |
| 108 | + for (int suffix = 0; suffix < NUM_SUFFIXES; suffix += 2) { |
| 109 | + for (String prefix : UPPER_PREFIXES) { |
| 110 | + blackhole.consume(prefix + "-" + suffix); |
| 111 | + blackhole.consume(Integer.valueOf(suffix + 1)); |
| 112 | + } |
| 113 | + } |
| 114 | + } |
| 115 | + |
| 116 | + @Benchmark |
| 117 | + public void lookup_baseline(Blackhole blackhole) { |
| 118 | + blackhole.consume(nextLookupKey()); |
| 119 | + } |
| 120 | + |
| 121 | + @Benchmark |
| 122 | + public HashMap<String, Integer> create_hashMap() { |
| 123 | + return _create_hashMap(); |
| 124 | + } |
| 125 | + |
| 126 | + static HashMap<String, Integer> _create_hashMap() { |
| 127 | + HashMap<String, Integer> map = new HashMap<>(); |
| 128 | + for (int suffix = 0; suffix < NUM_SUFFIXES; ++suffix) { |
| 129 | + for (String prefix : PREFIXES) { |
| 130 | + map.put( |
| 131 | + (prefix + "-" + suffix).toLowerCase(), |
| 132 | + suffix); // arguable, but real caller probably doesn't know the case ahead-of-time |
| 133 | + } |
| 134 | + } |
| 135 | + for (int suffix = 0; suffix < NUM_SUFFIXES; suffix += 2) { |
| 136 | + for (String prefix : UPPER_PREFIXES) { |
| 137 | + map.put((prefix + "-" + suffix).toLowerCase(), suffix + 1); |
| 138 | + } |
| 139 | + } |
| 140 | + return map; |
| 141 | + } |
| 142 | + |
| 143 | + static final HashMap<String, Integer> HASH_MAP = _create_hashMap(); |
| 144 | + |
| 145 | + @Benchmark |
| 146 | + public Integer lookup_hashMap() { |
| 147 | + // This benchmark is still "correct" in multi-threaded context, |
| 148 | + // Map is populated under the class initialization lock and not changed thereafter |
| 149 | + return HASH_MAP.get(nextLookupKey().toLowerCase()); |
| 150 | + } |
| 151 | + |
| 152 | + @Benchmark |
| 153 | + public TreeMap<String, Integer> create_treeMap() { |
| 154 | + return _create_treeMap(); |
| 155 | + } |
| 156 | + |
| 157 | + static TreeMap<String, Integer> _create_treeMap() { |
| 158 | + TreeMap<String, Integer> map = new TreeMap<>(String::compareToIgnoreCase); |
| 159 | + for (int suffix = 0; suffix < NUM_SUFFIXES; ++suffix) { |
| 160 | + for (String prefix : PREFIXES) { |
| 161 | + map.put(prefix + "-" + suffix, suffix); |
| 162 | + } |
| 163 | + } |
| 164 | + for (int suffix = 0; suffix < NUM_SUFFIXES; suffix += 2) { |
| 165 | + for (String prefix : UPPER_PREFIXES) { |
| 166 | + map.put(prefix + "-" + suffix, suffix + 1); |
| 167 | + } |
| 168 | + } |
| 169 | + return map; |
| 170 | + } |
| 171 | + |
| 172 | + static final TreeMap<String, Integer> TREE_MAP = _create_treeMap(); |
| 173 | + |
| 174 | + @Benchmark |
| 175 | + public Integer lookup_treeMap() { |
| 176 | + // This benchmark is still "correct" in multi-threaded context, |
| 177 | + // Map is populated under the initial class initialization lock and not changed thereafter |
| 178 | + return TREE_MAP.get(nextLookupKey()); |
| 179 | + } |
| 180 | + |
| 181 | + // TODO: Add ConcurrentSkipListMap & synchronized HashMap & TreeMap |
| 182 | +} |
0 commit comments