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
|
// Similar test as "cacheir/set-has-string.js", except that we now perform
// duplicate lookups to ensure GVN works properly.
// Return a new set, possibly filling some dummy entries to enforce creating
// multiple hash buckets.
function createSet(values, n) {
var xs = [...values];
for (var i = 0; i < n; ++i) {
xs.push({});
}
return new Set(xs);
}
function runTest(fn) {
fn(0);
fn(100);
}
function testConstant_same_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set = createSet(xs, n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3];
if (set.has(z)) c++;
if (set.has(z)) c++;
}
assertEq(c, N);
}
runTest(testConstant_same_set);
function testComputed_same_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set = createSet(xs, n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3];
z = String.fromCharCode(z.charCodeAt(0));
if (set.has(z)) c++;
if (set.has(z)) c++;
}
assertEq(c, N);
}
runTest(testComputed_same_set);
function testRope_same_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set = createSet(xs.map(x => x.repeat(100)), n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3].repeat(100);
if (set.has(z)) c++;
if (set.has(z)) c++;
}
assertEq(c, N);
}
runTest(testRope_same_set);
// Duplicate the above tests, but this time use a different set.
function testConstant_different_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set1 = createSet(xs, n);
var set2 = createSet(xs, n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3];
if (set1.has(z)) c++;
if (set2.has(z)) c++;
}
assertEq(c, N);
}
runTest(testConstant_different_set);
function testComputed_different_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set1 = createSet(xs, n);
var set2 = createSet(xs, n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3];
z = String.fromCharCode(z.charCodeAt(0));
if (set1.has(z)) c++;
if (set2.has(z)) c++;
}
assertEq(c, N);
}
runTest(testComputed_different_set);
function testRope_different_set(n) {
var xs = ["a", "b"];
var ys = ["c", "d"];
var zs = [...xs, ...ys];
var set1 = createSet(xs.map(x => x.repeat(100)), n);
var set2 = createSet(xs.map(x => x.repeat(100)), n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var z = zs[i & 3].repeat(100);
if (set1.has(z)) c++;
if (set2.has(z)) c++;
}
assertEq(c, N);
}
runTest(testRope_different_set);
// Test the alias information is correct.
function test_alias(n) {
var xs = ["a", "b"];
var set = createSet([], n);
var N = 100;
var c = 0;
for (var i = 0; i < N; ++i) {
var x = xs[i & 1];
set.add(x);
if (set.has(x)) c++;
set.delete(x);
if (set.has(x)) c++;
}
assertEq(c, N);
}
runTest(test_alias);
|
