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