Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <stdlib.h>
6 : #include <sstream>
7 : #include <utility>
8 :
9 : #include "src/objects-inl.h"
10 : #include "src/objects.h"
11 : #include "src/third_party/siphash/halfsiphash.h"
12 : #include "src/utils.h"
13 : #include "src/v8.h"
14 :
15 : #include "test/cctest/cctest.h"
16 :
17 : namespace v8 {
18 : namespace internal {
19 :
20 50 : int AddToSetAndGetHash(Isolate* isolate, Handle<JSObject> obj,
21 : bool has_fast_properties) {
22 50 : CHECK_EQ(has_fast_properties, obj->HasFastProperties());
23 150 : CHECK_EQ(ReadOnlyRoots(isolate).undefined_value(), obj->GetHash());
24 50 : Handle<OrderedHashSet> set = isolate->factory()->NewOrderedHashSet();
25 50 : OrderedHashSet::Add(isolate, set, obj);
26 50 : CHECK_EQ(has_fast_properties, obj->HasFastProperties());
27 50 : return Smi::ToInt(obj->GetHash());
28 : }
29 :
30 20 : void CheckFastObject(Handle<JSObject> obj, int hash) {
31 20 : CHECK(obj->HasFastProperties());
32 40 : CHECK(obj->raw_properties_or_hash()->IsPropertyArray());
33 60 : CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
34 20 : CHECK_EQ(hash, obj->property_array()->Hash());
35 20 : }
36 :
37 15 : void CheckDictionaryObject(Handle<JSObject> obj, int hash) {
38 15 : CHECK(!obj->HasFastProperties());
39 30 : CHECK(obj->raw_properties_or_hash()->IsDictionary());
40 45 : CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
41 15 : CHECK_EQ(hash, obj->property_dictionary()->Hash());
42 15 : }
43 :
44 25880 : TEST(AddHashCodeToFastObjectWithoutProperties) {
45 5 : CcTest::InitializeVM();
46 5 : v8::HandleScope scope(CcTest::isolate());
47 : Isolate* isolate = CcTest::i_isolate();
48 :
49 : Handle<JSObject> obj =
50 5 : isolate->factory()->NewJSObject(isolate->object_function());
51 5 : CHECK(obj->HasFastProperties());
52 :
53 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
54 15 : CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
55 5 : }
56 :
57 25880 : TEST(AddHashCodeToFastObjectWithInObjectProperties) {
58 5 : CcTest::InitializeVM();
59 5 : v8::HandleScope scope(CcTest::isolate());
60 : Isolate* isolate = CcTest::i_isolate();
61 :
62 : const char* source = " var x = { a: 1};";
63 : CompileRun(source);
64 :
65 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
66 15 : CHECK_EQ(ReadOnlyRoots(isolate).empty_fixed_array(),
67 : obj->raw_properties_or_hash());
68 :
69 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
70 15 : CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
71 5 : }
72 :
73 25880 : TEST(AddHashCodeToFastObjectWithPropertiesArray) {
74 5 : CcTest::InitializeVM();
75 5 : v8::HandleScope scope(CcTest::isolate());
76 : Isolate* isolate = CcTest::i_isolate();
77 :
78 : const char* source =
79 : " var x = {}; "
80 : " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
81 : CompileRun(source);
82 :
83 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
84 5 : CHECK(obj->HasFastProperties());
85 :
86 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
87 5 : CheckFastObject(obj, hash);
88 5 : }
89 :
90 25880 : TEST(AddHashCodeToSlowObject) {
91 5 : CcTest::InitializeVM();
92 5 : v8::HandleScope scope(CcTest::isolate());
93 : Isolate* isolate = CcTest::i_isolate();
94 :
95 : Handle<JSObject> obj =
96 5 : isolate->factory()->NewJSObject(isolate->object_function());
97 5 : CHECK(obj->HasFastProperties());
98 : JSObject::NormalizeProperties(obj, CLEAR_INOBJECT_PROPERTIES, 0,
99 5 : "cctest/test-hashcode");
100 10 : CHECK(obj->raw_properties_or_hash()->IsDictionary());
101 :
102 5 : int hash = AddToSetAndGetHash(isolate, obj, false);
103 5 : CheckDictionaryObject(obj, hash);
104 5 : }
105 :
106 25880 : TEST(TransitionFastWithInObjectToFastWithPropertyArray) {
107 5 : CcTest::InitializeVM();
108 5 : v8::HandleScope scope(CcTest::isolate());
109 : Isolate* isolate = CcTest::i_isolate();
110 :
111 : const char* source =
112 : " var x = { };"
113 : " x.a = 1; x.b = 2; x.c = 3; x.d = 4;";
114 : CompileRun(source);
115 :
116 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
117 5 : CHECK(obj->HasFastProperties());
118 :
119 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
120 15 : CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
121 :
122 10 : int length = obj->property_array()->length();
123 : CompileRun("x.e = 5;");
124 10 : CHECK(obj->property_array()->length() > length);
125 5 : CheckFastObject(obj, hash);
126 5 : }
127 :
128 25880 : TEST(TransitionFastWithPropertyArray) {
129 5 : CcTest::InitializeVM();
130 5 : v8::HandleScope scope(CcTest::isolate());
131 : Isolate* isolate = CcTest::i_isolate();
132 :
133 : const char* source =
134 : " var x = { };"
135 : " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
136 : CompileRun(source);
137 :
138 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
139 10 : CHECK(obj->raw_properties_or_hash()->IsPropertyArray());
140 :
141 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
142 5 : CHECK_EQ(hash, obj->property_array()->Hash());
143 :
144 10 : int length = obj->property_array()->length();
145 : CompileRun("x.f = 2; x.g = 5; x.h = 2");
146 10 : CHECK(obj->property_array()->length() > length);
147 5 : CheckFastObject(obj, hash);
148 5 : }
149 :
150 25880 : TEST(TransitionFastWithPropertyArrayToSlow) {
151 5 : CcTest::InitializeVM();
152 5 : v8::HandleScope scope(CcTest::isolate());
153 : Isolate* isolate = CcTest::i_isolate();
154 :
155 : const char* source =
156 : " var x = { };"
157 : " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
158 : CompileRun(source);
159 :
160 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
161 10 : CHECK(obj->raw_properties_or_hash()->IsPropertyArray());
162 :
163 5 : int hash = AddToSetAndGetHash(isolate, obj, true);
164 10 : CHECK(obj->raw_properties_or_hash()->IsPropertyArray());
165 5 : CHECK_EQ(hash, obj->property_array()->Hash());
166 :
167 : JSObject::NormalizeProperties(obj, KEEP_INOBJECT_PROPERTIES, 0,
168 5 : "cctest/test-hashcode");
169 5 : CheckDictionaryObject(obj, hash);
170 5 : }
171 :
172 25880 : TEST(TransitionSlowToSlow) {
173 5 : CcTest::InitializeVM();
174 5 : v8::HandleScope scope(CcTest::isolate());
175 : Isolate* isolate = CcTest::i_isolate();
176 :
177 : const char* source = " var x = {}; ";
178 : CompileRun(source);
179 :
180 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
181 : JSObject::NormalizeProperties(obj, CLEAR_INOBJECT_PROPERTIES, 0,
182 5 : "cctest/test-hashcode");
183 10 : CHECK(obj->raw_properties_or_hash()->IsDictionary());
184 :
185 5 : int hash = AddToSetAndGetHash(isolate, obj, false);
186 5 : CHECK_EQ(hash, obj->property_dictionary()->Hash());
187 :
188 10 : int length = obj->property_dictionary()->length();
189 : CompileRun("for(var i = 0; i < 10; i++) { x['f'+i] = i };");
190 10 : CHECK(obj->property_dictionary()->length() > length);
191 5 : CheckDictionaryObject(obj, hash);
192 5 : }
193 :
194 25880 : TEST(TransitionSlowToFastWithoutProperties) {
195 5 : CcTest::InitializeVM();
196 5 : v8::HandleScope scope(CcTest::isolate());
197 : Isolate* isolate = CcTest::i_isolate();
198 :
199 : Handle<JSObject> obj =
200 5 : isolate->factory()->NewJSObject(isolate->object_function());
201 : JSObject::NormalizeProperties(obj, CLEAR_INOBJECT_PROPERTIES, 0,
202 5 : "cctest/test-hashcode");
203 10 : CHECK(obj->raw_properties_or_hash()->IsDictionary());
204 :
205 5 : int hash = AddToSetAndGetHash(isolate, obj, false);
206 5 : CHECK_EQ(hash, obj->property_dictionary()->Hash());
207 :
208 5 : JSObject::MigrateSlowToFast(obj, 0, "cctest/test-hashcode");
209 15 : CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
210 5 : }
211 :
212 25880 : TEST(TransitionSlowToFastWithPropertyArray) {
213 5 : CcTest::InitializeVM();
214 5 : v8::HandleScope scope(CcTest::isolate());
215 : Isolate* isolate = CcTest::i_isolate();
216 :
217 : const char* source =
218 : " var x = Object.create(null); "
219 : " for(var i = 0; i < 10; i++) { x['f'+i] = i }; ";
220 : CompileRun(source);
221 :
222 5 : Handle<JSObject> obj = GetGlobal<JSObject>("x");
223 10 : CHECK(obj->raw_properties_or_hash()->IsDictionary());
224 :
225 5 : int hash = AddToSetAndGetHash(isolate, obj, false);
226 5 : CHECK_EQ(hash, obj->property_dictionary()->Hash());
227 :
228 5 : JSObject::MigrateSlowToFast(obj, 0, "cctest/test-hashcode");
229 5 : CheckFastObject(obj, hash);
230 5 : }
231 :
232 : namespace {
233 :
234 : typedef uint32_t (*HashFunction)(uint32_t key, uint64_t seed);
235 :
236 180 : void TestIntegerHashQuality(const int samples_log2, int num_buckets_log2,
237 : uint64_t seed, double max_var,
238 : HashFunction hash_function) {
239 180 : int samples = 1 << samples_log2;
240 180 : int num_buckets = 1 << num_buckets_log2;
241 180 : int mean = samples / num_buckets;
242 180 : int* buckets = new int[num_buckets];
243 :
244 180 : for (int i = 0; i < num_buckets; i++) buckets[i] = 0;
245 :
246 7741440 : for (int i = 0; i < samples; i++) {
247 7741440 : uint32_t hash = hash_function(i, seed);
248 7741440 : buckets[hash % num_buckets]++;
249 : }
250 :
251 : int sum_deviation = 0;
252 272160 : for (int i = 0; i < num_buckets; i++) {
253 272160 : int deviation = abs(buckets[i] - mean);
254 272160 : sum_deviation += deviation * deviation;
255 : }
256 180 : delete[] buckets;
257 :
258 180 : double variation_coefficient = sqrt(sum_deviation * 1.0 / num_buckets) / mean;
259 :
260 : printf("samples: 1 << %2d, buckets: 1 << %2d, var_coeff: %0.3f\n",
261 : samples_log2, num_buckets_log2, variation_coefficient);
262 180 : CHECK_LT(variation_coefficient, max_var);
263 180 : }
264 2580480 : uint32_t HalfSipHash(uint32_t key, uint64_t seed) {
265 2580480 : return halfsiphash(key, seed);
266 : }
267 :
268 2580480 : uint32_t JenkinsHash(uint32_t key, uint64_t seed) {
269 5160960 : return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
270 : }
271 :
272 2580480 : uint32_t DefaultHash(uint32_t key, uint64_t seed) {
273 2580480 : return ComputeSeededHash(key, seed);
274 : }
275 : } // anonymous namespace
276 :
277 15 : void TestIntegerHashQuality(HashFunction hash_function) {
278 15 : TestIntegerHashQuality(17, 13, 0x123456789ABCDEFU, 0.4, hash_function);
279 15 : TestIntegerHashQuality(16, 12, 0x123456789ABCDEFU, 0.4, hash_function);
280 15 : TestIntegerHashQuality(15, 11, 0xFEDCBA987654321U, 0.4, hash_function);
281 15 : TestIntegerHashQuality(14, 10, 0xFEDCBA987654321U, 0.4, hash_function);
282 15 : TestIntegerHashQuality(13, 9, 1, 0.4, hash_function);
283 15 : TestIntegerHashQuality(12, 8, 1, 0.4, hash_function);
284 :
285 15 : TestIntegerHashQuality(17, 10, 0x123456789ABCDEFU, 0.2, hash_function);
286 15 : TestIntegerHashQuality(16, 9, 0x123456789ABCDEFU, 0.2, hash_function);
287 15 : TestIntegerHashQuality(15, 8, 0xFEDCBA987654321U, 0.2, hash_function);
288 15 : TestIntegerHashQuality(14, 7, 0xFEDCBA987654321U, 0.2, hash_function);
289 15 : TestIntegerHashQuality(13, 6, 1, 0.2, hash_function);
290 15 : TestIntegerHashQuality(12, 5, 1, 0.2, hash_function);
291 15 : }
292 :
293 25880 : TEST(HalfSipHashQuality) { TestIntegerHashQuality(HalfSipHash); }
294 :
295 25880 : TEST(JenkinsHashQuality) { TestIntegerHashQuality(JenkinsHash); }
296 :
297 25880 : TEST(DefaultHashQuality) { TestIntegerHashQuality(DefaultHash); }
298 :
299 : } // namespace internal
300 77625 : } // namespace v8
|
