LCOV - code coverage report
Current view: top level - test/cctest - test-hashcode.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 159 159 100.0 %
Date: 2019-01-20 Functions: 23 23 100.0 %

          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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : 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       28342 : TEST(HalfSipHashQuality) { TestIntegerHashQuality(HalfSipHash); }
     294             : 
     295       28342 : TEST(JenkinsHashQuality) { TestIntegerHashQuality(JenkinsHash); }
     296             : 
     297       28342 : TEST(DefaultHashQuality) { TestIntegerHashQuality(DefaultHash); }
     298             : 
     299             : }  // namespace internal
     300       85011 : }  // namespace v8

Generated by: LCOV version 1.10