FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

deps: cherry-pick a803fad from upstream V8 · nodejs/node@f12db24 · GitHub

/ node Public

Commit f12db24

Browse files
targos
authored and
gibfahn
committed
deps: cherry-pick a803fad from upstream V8
Original commit message: Make sure the identity hash is uniform (at least in the lower bits). In the current implementation of hash code for objects (identity hash), we do not bother to shift the hash when we retrieve it from the hash-length bitfield in a property array. (Even worse, we store shifted value even if we do not have property array or inside dictionaries.) That means that the hash-code for objects is always divisible by 1024. Since our hash table uses a simple masking with (2^logsize - 1) to obtain the bucket, we get terrible hash collisions - essentially, our hash table degenerates to a linked list for fewer than 1024 elements. This CL always shifts the hash code so that the value in the lowest 21 bits is uniformly distributed. This results in big improvements on medium to large hash tables. A program storing 1M elements into a WeakMap gets roughly 17x faster. A program retrieving 1M elements from a Map improves even more dramatically (>100x). const a = []; for (let i = 0; i < 1e6; i++) a[i] = {}; const m = new Map(); console.time("Map.set"); for (let i = 0; i < 1e6; i++) { m.set(a[i], i); } console.timeEnd("Map.set"); console.time("Map.get"); let s = 0; for (let i = 0; i < 1e6; i++) { s += m.get(a[i]); } console.timeEnd("Map.get"); const w = new WeakMap(); console.time("WeakMap.set"); for (let i = 0; i < 1e6; i++) { w.set(a[i], i); } console.timeEnd("WeakMap.set"); Before the fix: Map.set: 157.575000 Map.get: 28333.182000 WeakMap.set: 6923.826000 After the fix: Map.set: 178.382000 Map.get: 185.930000 WeakMap.set: 409.529000 Note that Map does not suffer from the hash collision on insertion because it uses chaining (insertion into linked list is fast regardless of size!), and we cleverly avoid lookup in the hash table on update if the key does not have identity hash yet. This is in contrast to the WeakMap, which uses open-addressing, and deals with collisions on insertion. Bug: v8:6916 Change-Id: Ic5497bd4501e3b767b3f4acb7efb4784cbb3a2e4 Reviewed-on: https://chromium-review.googlesource.com/713616 Reviewed-by: Benedikt Meurer <bmeurer@chromium.org> Commit-Queue: Benedikt Meurer <bmeurer@chromium.org> Cr-Commit-Position: refs/heads/master@{#48480} PR-URL: #19824 Refs: v8/v8@a803fad Fixes: #19769 Reviewed-By: Yang Guo <yangguo@chromium.org> Reviewed-By: Gibson Fahnestock <gibfahn@gmail.com>
1 parent 09f5e25 commit f12db24

9 files changed

Lines changed: 54 additions & 52 deletions

File tree

‎deps/v8/include/v8-version.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
#define V8_MAJOR_VERSION 6
1212
#define V8_MINOR_VERSION 2
1313
#define V8_BUILD_NUMBER 414
14-
#define V8_PATCH_LEVEL 52
14+
#define V8_PATCH_LEVEL 53
1515

1616
// Use 1 for candidates and 0 otherwise.
1717
// (Boolean macro values are not supported by all preprocessors.)

‎deps/v8/src/code-stub-assembler.cc‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1187,8 +1187,8 @@ TNode<Int32T> CodeStubAssembler::LoadHashForJSObject(
11871187
{
11881188
Node* length_and_hash_int32 = LoadAndUntagToWord32ObjectField(
11891189
properties_or_hash, PropertyArray::kLengthAndHashOffset);
1190-
var_hash.Bind(Word32And(length_and_hash_int32,
1191-
Int32Constant(PropertyArray::kHashMask)));
1190+
var_hash.Bind(
1191+
DecodeWord32<PropertyArray::HashField>(length_and_hash_int32));
11921192
Goto(&done);
11931193
}
11941194

@@ -2508,7 +2508,8 @@ void CodeStubAssembler::InitializePropertyArrayLength(Node* property_array,
25082508
CSA_ASSERT(
25092509
this,
25102510
IntPtrOrSmiLessThanOrEqual(
2511-
length, IntPtrOrSmiConstant(PropertyArray::kMaxLength, mode), mode));
2511+
length, IntPtrOrSmiConstant(PropertyArray::LengthField::kMax, mode),
2512+
mode));
25122513
StoreObjectFieldNoWriteBarrier(
25132514
property_array, PropertyArray::kLengthAndHashOffset,
25142515
ParameterToTagged(length, mode), MachineRepresentation::kTaggedSigned);

‎deps/v8/src/compiler/js-native-context-specialization.cc‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2255,14 +2255,18 @@ Node* JSNativeContextSpecialization::BuildExtendPropertiesBackingStore(
22552255
jsgraph()->SmiConstant(PropertyArray::kNoHashSentinel));
22562256
hash = graph()->NewNode(common()->TypeGuard(Type::SignedSmall()), hash,
22572257
control);
2258+
hash =
2259+
graph()->NewNode(simplified()->NumberShiftLeft(), hash,
2260+
jsgraph()->Constant(PropertyArray::HashField::kShift));
22582261
} else {
22592262
hash = effect = graph()->NewNode(
22602263
simplified()->LoadField(AccessBuilder::ForPropertyArrayLengthAndHash()),
22612264
properties, effect, control);
22622265
effect = graph()->NewNode(
22632266
common()->BeginRegion(RegionObservability::kNotObservable), effect);
2264-
hash = graph()->NewNode(simplified()->NumberBitwiseAnd(), hash,
2265-
jsgraph()->Constant(JSReceiver::kHashMask));
2267+
hash =
2268+
graph()->NewNode(simplified()->NumberBitwiseAnd(), hash,
2269+
jsgraph()->Constant(PropertyArray::HashField::kMask));
22662270
}
22672271

22682272
Node* new_length_and_hash = graph()->NewNode(

‎deps/v8/src/ic/accessor-assembler.cc‎

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1091,7 +1091,7 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
10911091
// TODO(gsathya): Clean up the type conversions by creating smarter
10921092
// helpers that do the correct op based on the mode.
10931093
VARIABLE(var_properties, MachineRepresentation::kTaggedPointer);
1094-
VARIABLE(var_hash, MachineRepresentation::kWord32);
1094+
VARIABLE(var_encoded_hash, MachineRepresentation::kWord32);
10951095
VARIABLE(var_length, ParameterRepresentation(mode));
10961096

10971097
Node* properties = LoadObjectField(object, JSObject::kPropertiesOrHashOffset);
@@ -1102,7 +1102,10 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11021102

11031103
BIND(&if_smi_hash);
11041104
{
1105-
var_hash.Bind(SmiToWord32(properties));
1105+
Node* hash = SmiToWord32(properties);
1106+
Node* encoded_hash =
1107+
Word32Shl(hash, Int32Constant(PropertyArray::HashField::kShift));
1108+
var_encoded_hash.Bind(encoded_hash);
11061109
var_length.Bind(IntPtrOrSmiConstant(0, mode));
11071110
var_properties.Bind(EmptyFixedArrayConstant());
11081111
Goto(&extend_store);
@@ -1112,10 +1115,11 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11121115
{
11131116
Node* length_and_hash_int32 = LoadAndUntagToWord32ObjectField(
11141117
var_properties.value(), PropertyArray::kLengthAndHashOffset);
1115-
var_hash.Bind(Word32And(length_and_hash_int32,
1116-
Int32Constant(PropertyArray::kHashMask)));
1117-
Node* length_intptr = ChangeInt32ToIntPtr(Word32And(
1118-
length_and_hash_int32, Int32Constant(PropertyArray::kLengthMask)));
1118+
var_encoded_hash.Bind(Word32And(
1119+
length_and_hash_int32, Int32Constant(PropertyArray::HashField::kMask)));
1120+
Node* length_intptr = ChangeInt32ToIntPtr(
1121+
Word32And(length_and_hash_int32,
1122+
Int32Constant(PropertyArray::LengthField::kMask)));
11191123
Node* length = WordToParameter(length_intptr, mode);
11201124
var_length.Bind(length);
11211125
Goto(&extend_store);
@@ -1161,7 +1165,7 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11611165
Node* new_capacity_int32 =
11621166
TruncateWordToWord32(ParameterToWord(new_capacity, mode));
11631167
Node* new_length_and_hash_int32 =
1164-
Word32Or(var_hash.value(), new_capacity_int32);
1168+
Word32Or(var_encoded_hash.value(), new_capacity_int32);
11651169
StoreObjectField(new_properties, PropertyArray::kLengthAndHashOffset,
11661170
SmiFromWord32(new_length_and_hash_int32));
11671171
StoreObjectField(object, JSObject::kPropertiesOrHashOffset, new_properties);

‎deps/v8/src/objects-inl.h‎

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2679,33 +2679,31 @@ SYNCHRONIZED_SMI_ACCESSORS(FixedArrayBase, length, kLengthOffset)
26792679
int PropertyArray::length() const {
26802680
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
26812681
int value = Smi::ToInt(value_obj);
2682-
return value & kLengthMask;
2682+
return LengthField::decode(value);
26832683
}
26842684

26852685
void PropertyArray::initialize_length(int len) {
26862686
SLOW_DCHECK(len >= 0);
2687-
SLOW_DCHECK(len < kMaxLength);
2687+
SLOW_DCHECK(len < LengthField::kMax);
26882688
WRITE_FIELD(this, kLengthAndHashOffset, Smi::FromInt(len));
26892689
}
26902690

26912691
int PropertyArray::synchronized_length() const {
26922692
Object* value_obj = ACQUIRE_READ_FIELD(this, kLengthAndHashOffset);
26932693
int value = Smi::ToInt(value_obj);
2694-
return value & kLengthMask;
2694+
return LengthField::decode(value);
26952695
}
26962696

26972697
int PropertyArray::Hash() const {
26982698
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
26992699
int value = Smi::ToInt(value_obj);
2700-
int hash = value & kHashMask;
2701-
return hash;
2700+
return HashField::decode(value);
27022701
}
27032702

2704-
void PropertyArray::SetHash(int masked_hash) {
2705-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
2703+
void PropertyArray::SetHash(int hash) {
27062704
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
27072705
int value = Smi::ToInt(value_obj);
2708-
value = (value & kLengthMask) | masked_hash;
2706+
value = HashField::update(value, hash);
27092707
WRITE_FIELD(this, kLengthAndHashOffset, Smi::FromInt(value));
27102708
}
27112709

‎deps/v8/src/objects.cc‎

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -6269,22 +6269,22 @@ Handle<SeededNumberDictionary> JSObject::NormalizeElements(
62696269

62706270
namespace {
62716271

6272-
Object* SetHashAndUpdateProperties(HeapObject* properties, int masked_hash) {
6273-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6274-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
6272+
Object* SetHashAndUpdateProperties(HeapObject* properties, int hash) {
6273+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
6274+
DCHECK(PropertyArray::HashField::is_valid(hash));
62756275

62766276
if (properties == properties->GetHeap()->empty_fixed_array() ||
62776277
properties == properties->GetHeap()->empty_property_dictionary()) {
6278-
return Smi::FromInt(masked_hash);
6278+
return Smi::FromInt(hash);
62796279
}
62806280

62816281
if (properties->IsPropertyArray()) {
6282-
PropertyArray::cast(properties)->SetHash(masked_hash);
6282+
PropertyArray::cast(properties)->SetHash(hash);
62836283
return properties;
62846284
}
62856285

62866286
DCHECK(properties->IsDictionary());
6287-
NameDictionary::cast(properties)->SetHash(masked_hash);
6287+
NameDictionary::cast(properties)->SetHash(hash);
62886288
return properties;
62896289
}
62906290

@@ -6315,14 +6315,14 @@ int GetIdentityHashHelper(Isolate* isolate, JSReceiver* object) {
63156315
}
63166316
} // namespace
63176317

6318-
void JSReceiver::SetIdentityHash(int masked_hash) {
6318+
void JSReceiver::SetIdentityHash(int hash) {
63196319
DisallowHeapAllocation no_gc;
6320-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6321-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
6320+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
6321+
DCHECK(PropertyArray::HashField::is_valid(hash));
63226322

63236323
HeapObject* existing_properties = HeapObject::cast(raw_properties_or_hash());
63246324
Object* new_properties =
6325-
SetHashAndUpdateProperties(existing_properties, masked_hash);
6325+
SetHashAndUpdateProperties(existing_properties, hash);
63266326
set_raw_properties_or_hash(new_properties);
63276327
}
63286328

@@ -6377,11 +6377,11 @@ Smi* JSObject::GetOrCreateIdentityHash(Isolate* isolate) {
63776377
return Smi::cast(hash_obj);
63786378
}
63796379

6380-
int masked_hash = isolate->GenerateIdentityHash(JSReceiver::kHashMask);
6381-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6380+
int hash = isolate->GenerateIdentityHash(PropertyArray::HashField::kMax);
6381+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
63826382

6383-
SetIdentityHash(masked_hash);
6384-
return Smi::FromInt(masked_hash);
6383+
SetIdentityHash(hash);
6384+
return Smi::FromInt(hash);
63856385
}
63866386

63876387
Object* JSProxy::GetIdentityHash() { return hash(); }

‎deps/v8/src/objects.h‎

Lines changed: 5 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1953,17 +1953,10 @@ class PropertyArray : public HeapObject {
19531953
// No weak fields.
19541954
typedef BodyDescriptor BodyDescriptorWeak;
19551955

1956-
static const int kLengthMask = 0x3ff;
1957-
#if V8_TARGET_ARCH_64_BIT
1958-
static const int kHashMask = 0x7ffffc00;
1959-
STATIC_ASSERT(kLengthMask + kHashMask == 0x7fffffff);
1960-
#else
1961-
static const int kHashMask = 0x3ffffc00;
1962-
STATIC_ASSERT(kLengthMask + kHashMask == 0x3fffffff);
1963-
#endif
1964-
1965-
static const int kMaxLength = kLengthMask;
1966-
STATIC_ASSERT(kMaxLength > kMaxNumberOfDescriptors);
1956+
static const int kLengthFieldSize = 10;
1957+
class LengthField : public BitField<int, 0, kLengthFieldSize> {};
1958+
class HashField : public BitField<int, kLengthFieldSize,
1959+
kSmiValueSize - kLengthFieldSize - 1> {};
19671960

19681961
static const int kNoHashSentinel = 0;
19691962

@@ -2190,7 +2183,7 @@ class JSReceiver: public HeapObject {
21902183
MUST_USE_RESULT static MaybeHandle<FixedArray> GetOwnEntries(
21912184
Handle<JSReceiver> object, PropertyFilter filter);
21922185

2193-
static const int kHashMask = PropertyArray::kHashMask;
2186+
static const int kHashMask = PropertyArray::HashField::kMask;
21942187

21952188
// Layout description.
21962189
static const int kPropertiesOrHashOffset = HeapObject::kHeaderSize;

‎deps/v8/src/objects/dictionary.h‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -138,14 +138,16 @@ class BaseNameDictionary : public Dictionary<Derived, Shape> {
138138
return Smi::ToInt(this->get(kNextEnumerationIndexIndex));
139139
}
140140

141-
void SetHash(int masked_hash) {
142-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
143-
this->set(kObjectHashIndex, Smi::FromInt(masked_hash));
141+
void SetHash(int hash) {
142+
DCHECK(PropertyArray::HashField::is_valid(hash));
143+
this->set(kObjectHashIndex, Smi::FromInt(hash));
144144
}
145145

146146
int Hash() const {
147147
Object* hash_obj = this->get(kObjectHashIndex);
148-
return Smi::ToInt(hash_obj);
148+
int hash = Smi::ToInt(hash_obj);
149+
DCHECK(PropertyArray::HashField::is_valid(hash));
150+
return hash;
149151
}
150152

151153
// Creates a new dictionary.

‎deps/v8/test/cctest/test-weakmaps.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -191,7 +191,7 @@ TEST(Regress2060a) {
191191
Handle<JSObject> object = factory->NewJSObject(function, TENURED);
192192
CHECK(!heap->InNewSpace(*object));
193193
CHECK(!first_page->Contains(object->address()));
194-
int32_t hash = object->GetOrCreateHash(isolate)->value();
194+
int32_t hash = key->GetOrCreateHash(isolate)->value();
195195
JSWeakCollection::Set(weakmap, key, object, hash);
196196
}
197197
}

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL