Repository navigation
Expand file tree
/
Copy pathStringIndexTest.java
More file actions
251 lines (208 loc) · 10 KB
/
Copy pathStringIndexTest.java
File metadata and controls
251 lines (208 loc) · 10 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
package datadog.trace.util;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
import datadog.trace.util.StringIndex.Data;
import datadog.trace.util.StringIndex.EmbeddingSupport;
import org.junit.jupiter.api.Test;
class StringIndexTest {
@Test
void hash_spread_and_zeroSentinel() {
// "".hashCode() == 0 -> remapped to the non-zero sentinel so 0 can mean "empty slot"
assertEquals(0xDD06, EmbeddingSupport.hash(""));
assertEquals(HashingUtils.hashSpread("foo".hashCode()), EmbeddingSupport.hash("foo"));
assertNotEquals(0, EmbeddingSupport.hash("foo"));
}
@Test
void capacityFor_isPow2_andAtLeastDoubled() {
assertEquals(2, EmbeddingSupport.capacityFor(0)); // empty set -> minimal table
assertEquals(2, EmbeddingSupport.capacityFor(1)); // >= 2x, smallest power of two
assertEquals(8, EmbeddingSupport.capacityFor(3)); // ceil(3/0.5)=6 -> 8
assertEquals(8, EmbeddingSupport.capacityFor(4)); // ceil(4/0.5)=8 -> 8 (was 16: tightened)
assertEquals(64, EmbeddingSupport.capacityFor(16, EmbeddingSupport.LOW_LOAD_FACTOR)); // 4x
}
@Test
void capacityFor_rejectsBadArgs() {
assertThrows(IllegalArgumentException.class, () -> EmbeddingSupport.capacityFor(-1));
assertThrows(IllegalArgumentException.class, () -> EmbeddingSupport.capacityFor(4, 0f));
assertThrows(IllegalArgumentException.class, () -> EmbeddingSupport.capacityFor(4, 1f));
}
@Test
void capacityFor_boundsAtMaxCapacity() {
// ceil(n / loadFactor) landing exactly on MAX_CAPACITY still succeeds.
int n = EmbeddingSupport.MAX_CAPACITY / 2; // ceil(n / 0.5) == MAX_CAPACITY
assertEquals(EmbeddingSupport.MAX_CAPACITY, EmbeddingSupport.capacityFor(n));
}
@Test
void capacityFor_rejectsCapacityAboveMax() {
// Required capacity exceeds MAX_CAPACITY: previously the double->int narrowing conversion
// saturated at Integer.MAX_VALUE and the subsequent << 1 wrapped to a negative array size.
assertThrows(IllegalArgumentException.class, () -> EmbeddingSupport.capacityFor(1, 1e-10f));
assertThrows(
IllegalArgumentException.class,
() -> EmbeddingSupport.capacityFor(EmbeddingSupport.MAX_CAPACITY + 1));
}
@Test
void instance_contains_internedAndCopy_andMiss() {
StringIndex set = StringIndex.of("foo", "bar", "baz");
assertEquals(8, set.numSlots()); // 3 names -> capacityFor(3) == 8
assertTrue(set.contains("foo")); // interned literal -> == fast path in eq
assertTrue(set.contains(new String("bar"))); // non-interned -> .equals path
assertFalse(set.contains("nope"));
assertTrue(set.indexOf("baz") >= 0);
assertEquals(-1, set.indexOf("nope"));
}
@Test
void support_create_then_indexOf() {
Data d = EmbeddingSupport.create("x", "y");
int slot = EmbeddingSupport.indexOf(d.hashes, d.names, "x"); // 3-arg overload computes the hash
assertTrue(slot >= 0);
assertEquals("x", d.names[slot]);
assertEquals(-1, EmbeddingSupport.indexOf(d.hashes, d.names, "q"));
}
@Test
void support_contains_internedAndCopy_andMiss() {
Data d = EmbeddingSupport.create("foo", "bar", "baz");
assertTrue(
EmbeddingSupport.contains(d.hashes, d.names, "foo")); // interned literal -> == fast path
assertTrue(EmbeddingSupport.contains(d.hashes, d.names, new String("bar"))); // non-interned
assertFalse(EmbeddingSupport.contains(d.hashes, d.names, "nope"));
}
/** Controlled hashes force collision, linear-probe wraparound, and the already-present path. */
@Test
void put_and_indexOf_collisionAndWraparound() {
int[] hashes = new int[4]; // mask = 3
String[] names = new String[4];
assertEquals(3, EmbeddingSupport.put(hashes, names, "a", 7)); // 7 & 3 == 3
assertEquals(
0, EmbeddingSupport.put(hashes, names, "b", 7)); // collides at 3, probes (3+1)&3 == 0
assertEquals(
3, EmbeddingSupport.put(hashes, names, "a", 7)); // already present -> existing slot
assertEquals(3, EmbeddingSupport.indexOf(hashes, names, "a", 7)); // direct hit
assertEquals(
0, EmbeddingSupport.indexOf(hashes, names, "b", 7)); // hit after collision + wraparound
assertEquals(
-1,
EmbeddingSupport.indexOf(hashes, names, "c", 7)); // miss after probing 3 -> 0 -> 1(empty)
assertEquals(
-1, EmbeddingSupport.indexOf(hashes, names, "z", 6)); // 6 & 3 == 2, empty -> immediate miss
}
@Test
void put_throwsWhenFull() {
int[] hashes = new int[2]; // mask = 1
String[] names = new String[2];
EmbeddingSupport.put(hashes, names, "a", 4); // 4 & 1 == 0
EmbeddingSupport.put(hashes, names, "b", 5); // 5 & 1 == 1
// both slots occupied, no match -> probe exhausts -> throw
assertThrows(IllegalStateException.class, () -> EmbeddingSupport.put(hashes, names, "c", 6));
}
/** The documented usage: build a StringIndex, attach a parallel payload indexed by slot. */
@Test
void parallelPayloadBySlot() {
String[] names = {"a", "b", "c"};
Data d = EmbeddingSupport.create(names);
long[] ids = new long[d.names.length];
for (int j = 0; j < names.length; j++) {
ids[EmbeddingSupport.indexOf(d.hashes, d.names, names[j])] = j + 1L;
}
assertEquals(1L, ids[EmbeddingSupport.indexOf(d.hashes, d.names, "a")]);
assertEquals(2L, ids[EmbeddingSupport.indexOf(d.hashes, d.names, "b")]);
assertEquals(3L, ids[EmbeddingSupport.indexOf(d.hashes, d.names, "c")]);
}
@Test
void mapIntValues_slotAligned_andLookup() {
StringIndex idx = StringIndex.of("a", "b", "c");
// 1-based ids; 0 stays the empty-slot / not-found sentinel.
int[] ids = idx.mapIntValues(s -> s.charAt(0) - 'a' + 1);
assertEquals(idx.numSlots(), ids.length); // sized to the table, not the name count
assertEquals(1, idx.lookup(ids, "a"));
assertEquals(2, idx.lookup(ids, "b"));
assertEquals(3, idx.lookup(ids, "c"));
assertEquals(0, idx.lookup(ids, "z")); // miss -> 0
assertEquals(-1, idx.lookupOrDefault(ids, "z", -1)); // miss -> supplied default
}
@Test
void mapLongValues_slotAligned_andLookup() {
Data d = EmbeddingSupport.create("a", "b", "c");
long[] vals = EmbeddingSupport.mapLongValues(d.names, s -> s.charAt(0) - 'a' + 1L);
assertEquals(1L, EmbeddingSupport.lookup(d.hashes, d.names, vals, "a"));
assertEquals(3L, EmbeddingSupport.lookup(d.hashes, d.names, vals, "c"));
assertEquals(0L, EmbeddingSupport.lookup(d.hashes, d.names, vals, "z")); // miss -> 0
assertEquals(-1L, EmbeddingSupport.lookupOrDefault(d.hashes, d.names, vals, "z", -1L));
}
@Test
void mapValues_objects_typedArray_andLookup() {
StringIndex idx = StringIndex.of("a", "bb", "ccc");
Integer[] lengths = idx.mapValues(Integer.class, String::length);
// Class<T> drives a real Integer[], not an Object[].
assertEquals(Integer[].class, lengths.getClass());
assertEquals(Integer.valueOf(1), idx.lookup(lengths, "a"));
assertEquals(Integer.valueOf(3), idx.lookup(lengths, "ccc"));
assertNull(idx.lookup(lengths, "z")); // miss -> null
assertEquals(Integer.valueOf(-1), idx.lookupOrDefault(lengths, "z", -1));
}
@Test
void support_mapValues_objects_sizedToSlots_emptyStayNull() {
Data d = EmbeddingSupport.create("a", "b", "c");
String[] tagged = EmbeddingSupport.mapValues(d.names, String.class, s -> s + "!");
assertEquals(d.names.length, tagged.length); // sized to the table
int nonNull = 0;
for (String s : tagged) {
if (s != null) {
nonNull++;
}
}
assertEquals(3, nonNull); // only the placed names map; unfilled slots stay null
assertEquals("a!", EmbeddingSupport.lookup(d.hashes, d.names, tagged, "a"));
assertEquals("dflt", EmbeddingSupport.lookupOrDefault(d.hashes, d.names, tagged, "z", "dflt"));
}
@Test
void instance_lookup_delegatesToSupportArrays() {
StringIndex idx = StringIndex.of("x", "y");
int[] ids = idx.mapIntValues(s -> "x".equals(s) ? 7 : 9);
assertEquals(7, idx.lookup(ids, "x"));
assertEquals(9, idx.lookup(ids, "y"));
assertEquals(0, idx.lookup(ids, "missing"));
assertEquals(42, idx.lookupOrDefault(ids, "missing", 42));
}
@Test
void instance_longValues_mapAndLookup() {
StringIndex idx = StringIndex.of("a", "b", "c");
long[] vals = idx.mapLongValues(s -> s.charAt(0) - 'a' + 1L);
assertEquals(idx.numSlots(), vals.length); // sized to the table, not the name count
assertEquals(1L, idx.lookup(vals, "a"));
assertEquals(3L, idx.lookup(vals, "c"));
assertEquals(0L, idx.lookup(vals, "z")); // miss -> 0
assertEquals(2L, idx.lookupOrDefault(vals, "b", -1L)); // hit
assertEquals(-1L, idx.lookupOrDefault(vals, "z", -1L)); // miss -> supplied default
}
@Test
void support_numSlots_matchesTableSize() {
Data d = EmbeddingSupport.create("a", "b", "c");
assertEquals(d.hashes.length, EmbeddingSupport.numSlots(d.hashes));
}
@Test
void sequentialNamesDoNotClusterUnderLinearProbing() {
// Names that differ only in a trailing counter have nearly equal String.hashCodes. Without a
// multiplicative spread they fill runs of adjacent slots: with h ^ (h >>> 16), these 10,030
// names average 6.3 probes, with a worst case of 156.
final int n = 10_030;
final int[] hashes = new int[EmbeddingSupport.capacityFor(n)];
final String[] names = new String[hashes.length];
final int mask = hashes.length - 1;
long probes = 0;
int worst = 0;
for (int i = 0; i < n; i++) {
final String name = String.format("scale-bulk-%05d", i);
final int h = EmbeddingSupport.hash(name);
final int distance = ((EmbeddingSupport.put(hashes, names, name, h) - h) & mask) + 1;
probes += distance;
worst = Math.max(worst, distance);
}
assertTrue(probes < 2L * n, "average probes " + (double) probes / n);
assertTrue(worst < 32, "worst probe " + worst);
}
}