Skip to content

Commit a803fad

Browse files
jaro-sevcikCommit Bot
jaro-sevcik
authored and
Commit Bot
committed
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}
1 parent e34deba commit a803fad

8 files changed

Lines changed: 53 additions & 51 deletions

File tree

‎src/code-stub-assembler.cc‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1253,8 +1253,8 @@ TNode<Int32T> CodeStubAssembler::LoadHashForJSObject(
12531253
{
12541254
Node* length_and_hash_int32 = LoadAndUntagToWord32ObjectField(
12551255
properties_or_hash, PropertyArray::kLengthAndHashOffset);
1256-
var_hash.Bind(Word32And(length_and_hash_int32,
1257-
Int32Constant(PropertyArray::kHashMask)));
1256+
var_hash.Bind(
1257+
DecodeWord32<PropertyArray::HashField>(length_and_hash_int32));
12581258
Goto(&done);
12591259
}
12601260

@@ -2644,7 +2644,8 @@ void CodeStubAssembler::InitializePropertyArrayLength(Node* property_array,
26442644
CSA_ASSERT(
26452645
this,
26462646
IntPtrOrSmiLessThanOrEqual(
2647-
length, IntPtrOrSmiConstant(PropertyArray::kMaxLength, mode), mode));
2647+
length, IntPtrOrSmiConstant(PropertyArray::LengthField::kMax, mode),
2648+
mode));
26482649
StoreObjectFieldNoWriteBarrier(
26492650
property_array, PropertyArray::kLengthAndHashOffset,
26502651
ParameterToTagged(length, mode), MachineRepresentation::kTaggedSigned);

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

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2438,14 +2438,18 @@ Node* JSNativeContextSpecialization::BuildExtendPropertiesBackingStore(
24382438
jsgraph()->SmiConstant(PropertyArray::kNoHashSentinel));
24392439
hash = graph()->NewNode(common()->TypeGuard(Type::SignedSmall()), hash,
24402440
control);
2441+
hash =
2442+
graph()->NewNode(simplified()->NumberShiftLeft(), hash,
2443+
jsgraph()->Constant(PropertyArray::HashField::kShift));
24412444
} else {
24422445
hash = effect = graph()->NewNode(
24432446
simplified()->LoadField(AccessBuilder::ForPropertyArrayLengthAndHash()),
24442447
properties, effect, control);
24452448
effect = graph()->NewNode(
24462449
common()->BeginRegion(RegionObservability::kNotObservable), effect);
2447-
hash = graph()->NewNode(simplified()->NumberBitwiseAnd(), hash,
2448-
jsgraph()->Constant(JSReceiver::kHashMask));
2450+
hash =
2451+
graph()->NewNode(simplified()->NumberBitwiseAnd(), hash,
2452+
jsgraph()->Constant(PropertyArray::HashField::kMask));
24492453
}
24502454

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

‎src/ic/accessor-assembler.cc‎

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1174,7 +1174,7 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11741174
// TODO(gsathya): Clean up the type conversions by creating smarter
11751175
// helpers that do the correct op based on the mode.
11761176
VARIABLE(var_properties, MachineRepresentation::kTaggedPointer);
1177-
VARIABLE(var_hash, MachineRepresentation::kWord32);
1177+
VARIABLE(var_encoded_hash, MachineRepresentation::kWord32);
11781178
VARIABLE(var_length, ParameterRepresentation(mode));
11791179

11801180
Node* properties = LoadObjectField(object, JSObject::kPropertiesOrHashOffset);
@@ -1185,7 +1185,10 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11851185

11861186
BIND(&if_smi_hash);
11871187
{
1188-
var_hash.Bind(SmiToWord32(properties));
1188+
Node* hash = SmiToWord32(properties);
1189+
Node* encoded_hash =
1190+
Word32Shl(hash, Int32Constant(PropertyArray::HashField::kShift));
1191+
var_encoded_hash.Bind(encoded_hash);
11891192
var_length.Bind(IntPtrOrSmiConstant(0, mode));
11901193
var_properties.Bind(EmptyFixedArrayConstant());
11911194
Goto(&extend_store);
@@ -1195,10 +1198,11 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
11951198
{
11961199
Node* length_and_hash_int32 = LoadAndUntagToWord32ObjectField(
11971200
var_properties.value(), PropertyArray::kLengthAndHashOffset);
1198-
var_hash.Bind(Word32And(length_and_hash_int32,
1199-
Int32Constant(PropertyArray::kHashMask)));
1200-
Node* length_intptr = ChangeInt32ToIntPtr(Word32And(
1201-
length_and_hash_int32, Int32Constant(PropertyArray::kLengthMask)));
1201+
var_encoded_hash.Bind(Word32And(
1202+
length_and_hash_int32, Int32Constant(PropertyArray::HashField::kMask)));
1203+
Node* length_intptr = ChangeInt32ToIntPtr(
1204+
Word32And(length_and_hash_int32,
1205+
Int32Constant(PropertyArray::LengthField::kMask)));
12021206
Node* length = WordToParameter(length_intptr, mode);
12031207
var_length.Bind(length);
12041208
Goto(&extend_store);
@@ -1244,7 +1248,7 @@ void AccessorAssembler::ExtendPropertiesBackingStore(Node* object,
12441248
Node* new_capacity_int32 =
12451249
TruncateWordToWord32(ParameterToWord(new_capacity, mode));
12461250
Node* new_length_and_hash_int32 =
1247-
Word32Or(var_hash.value(), new_capacity_int32);
1251+
Word32Or(var_encoded_hash.value(), new_capacity_int32);
12481252
StoreObjectField(new_properties, PropertyArray::kLengthAndHashOffset,
12491253
SmiFromWord32(new_length_and_hash_int32));
12501254
StoreObjectField(object, JSObject::kPropertiesOrHashOffset, new_properties);

‎src/objects-inl.h‎

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2662,33 +2662,31 @@ SYNCHRONIZED_SMI_ACCESSORS(FixedArrayBase, length, kLengthOffset)
26622662
int PropertyArray::length() const {
26632663
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
26642664
int value = Smi::ToInt(value_obj);
2665-
return value & kLengthMask;
2665+
return LengthField::decode(value);
26662666
}
26672667

26682668
void PropertyArray::initialize_length(int len) {
26692669
SLOW_DCHECK(len >= 0);
2670-
SLOW_DCHECK(len < kMaxLength);
2670+
SLOW_DCHECK(len < LengthField::kMax);
26712671
WRITE_FIELD(this, kLengthAndHashOffset, Smi::FromInt(len));
26722672
}
26732673

26742674
int PropertyArray::synchronized_length() const {
26752675
Object* value_obj = ACQUIRE_READ_FIELD(this, kLengthAndHashOffset);
26762676
int value = Smi::ToInt(value_obj);
2677-
return value & kLengthMask;
2677+
return LengthField::decode(value);
26782678
}
26792679

26802680
int PropertyArray::Hash() const {
26812681
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
26822682
int value = Smi::ToInt(value_obj);
2683-
int hash = value & kHashMask;
2684-
return hash;
2683+
return HashField::decode(value);
26852684
}
26862685

2687-
void PropertyArray::SetHash(int masked_hash) {
2688-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
2686+
void PropertyArray::SetHash(int hash) {
26892687
Object* value_obj = READ_FIELD(this, kLengthAndHashOffset);
26902688
int value = Smi::ToInt(value_obj);
2691-
value = (value & kLengthMask) | masked_hash;
2689+
value = HashField::update(value, hash);
26922690
WRITE_FIELD(this, kLengthAndHashOffset, Smi::FromInt(value));
26932691
}
26942692

‎src/objects.cc‎

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

63886388
namespace {
63896389

6390-
Object* SetHashAndUpdateProperties(HeapObject* properties, int masked_hash) {
6391-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6392-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
6390+
Object* SetHashAndUpdateProperties(HeapObject* properties, int hash) {
6391+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
6392+
DCHECK(PropertyArray::HashField::is_valid(hash));
63936393

63946394
if (properties == properties->GetHeap()->empty_fixed_array() ||
63956395
properties == properties->GetHeap()->empty_property_dictionary()) {
6396-
return Smi::FromInt(masked_hash);
6396+
return Smi::FromInt(hash);
63976397
}
63986398

63996399
if (properties->IsPropertyArray()) {
6400-
PropertyArray::cast(properties)->SetHash(masked_hash);
6400+
PropertyArray::cast(properties)->SetHash(hash);
64016401
return properties;
64026402
}
64036403

64046404
DCHECK(properties->IsDictionary());
6405-
NameDictionary::cast(properties)->SetHash(masked_hash);
6405+
NameDictionary::cast(properties)->SetHash(hash);
64066406
return properties;
64076407
}
64086408

@@ -6433,14 +6433,14 @@ int GetIdentityHashHelper(Isolate* isolate, JSReceiver* object) {
64336433
}
64346434
} // namespace
64356435

6436-
void JSReceiver::SetIdentityHash(int masked_hash) {
6436+
void JSReceiver::SetIdentityHash(int hash) {
64376437
DisallowHeapAllocation no_gc;
6438-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6439-
DCHECK_EQ(masked_hash & JSReceiver::kHashMask, masked_hash);
6438+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
6439+
DCHECK(PropertyArray::HashField::is_valid(hash));
64406440

64416441
HeapObject* existing_properties = HeapObject::cast(raw_properties_or_hash());
64426442
Object* new_properties =
6443-
SetHashAndUpdateProperties(existing_properties, masked_hash);
6443+
SetHashAndUpdateProperties(existing_properties, hash);
64446444
set_raw_properties_or_hash(new_properties);
64456445
}
64466446

@@ -6495,11 +6495,11 @@ Smi* JSObject::GetOrCreateIdentityHash(Isolate* isolate) {
64956495
return Smi::cast(hash_obj);
64966496
}
64976497

6498-
int masked_hash = isolate->GenerateIdentityHash(JSReceiver::kHashMask);
6499-
DCHECK_NE(PropertyArray::kNoHashSentinel, masked_hash);
6498+
int hash = isolate->GenerateIdentityHash(PropertyArray::HashField::kMax);
6499+
DCHECK_NE(PropertyArray::kNoHashSentinel, hash);
65006500

6501-
SetIdentityHash(masked_hash);
6502-
return Smi::FromInt(masked_hash);
6501+
SetIdentityHash(hash);
6502+
return Smi::FromInt(hash);
65036503
}
65046504

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

‎src/objects.h‎

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

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

19691962
static const int kNoHashSentinel = 0;
19701963

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

2194-
static const int kHashMask = PropertyArray::kHashMask;
2187+
static const int kHashMask = PropertyArray::HashField::kMask;
21952188

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

‎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.

‎test/cctest/test-weakmaps.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -184,7 +184,7 @@ TEST(Regress2060a) {
184184
Handle<JSObject> object = factory->NewJSObject(function, TENURED);
185185
CHECK(!heap->InNewSpace(*object));
186186
CHECK(!first_page->Contains(object->address()));
187-
int32_t hash = object->GetOrCreateHash(isolate)->value();
187+
int32_t hash = key->GetOrCreateHash(isolate)->value();
188188
JSWeakCollection::Set(weakmap, key, object, hash);
189189
}
190190
}

0 commit comments

Comments
 (0)