From 66e2f60bf9784b09b963273c488da4722009328a Mon Sep 17 00:00:00 2001 From: adamk Date: Thu, 4 Dec 2014 12:07:41 -0800 Subject: [PATCH] Optimize add/set/delete operations for string keys in Maps and Sets Review URL: https://codereview.chromium.org/773993002 Cr-Commit-Position: refs/heads/master@{#25668} --- src/collection.js | 8 +- src/hydrogen-instructions.h | 7 + src/hydrogen.cc | 371 +++++++++++++++++++++++++++++++++++++++----- src/hydrogen.h | 16 +- src/objects.h | 5 +- src/runtime/runtime.h | 8 +- 6 files changed, 366 insertions(+), 49 deletions(-) diff --git a/src/collection.js b/src/collection.js index d93b8f8..d1b16be 100644 --- a/src/collection.js +++ b/src/collection.js @@ -56,7 +56,7 @@ function SetAddJS(key) { if (key === 0) { key = 0; } - return %SetAdd(this, key); + return %_SetAdd(this, key); } @@ -74,7 +74,7 @@ function SetDeleteJS(key) { throw MakeTypeError('incompatible_method_receiver', ['Set.prototype.delete', this]); } - return %SetDelete(this, key); + return %_SetDelete(this, key); } @@ -209,7 +209,7 @@ function MapSetJS(key, value) { if (key === 0) { key = 0; } - return %MapSet(this, key, value); + return %_MapSet(this, key, value); } @@ -227,7 +227,7 @@ function MapDeleteJS(key) { throw MakeTypeError('incompatible_method_receiver', ['Map.prototype.delete', this]); } - return %MapDelete(this, key); + return %_MapDelete(this, key); } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index b56e921..22c6935 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -6356,6 +6356,13 @@ class HObjectAccess FINAL { Representation::Smi()); } + template + static HObjectAccess ForOrderedHashTableNumberOfDeletedElements() { + return HObjectAccess(kInobject, + CollectionType::kNumberOfDeletedElementsOffset, + Representation::Smi()); + } + inline bool Equals(HObjectAccess that) const { return value_ == that.value_; // portion and offset must match } diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 468de1e..d64200f 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -12114,6 +12114,44 @@ void HOptimizedGraphBuilder::GenerateMathSqrtRT(CallRuntime* call) { } +HValue* HOptimizedGraphBuilder::BuildOrderedHashTableHashToBucket( + HValue* hash, HValue* num_buckets) { + HValue* mask = AddUncasted(num_buckets, graph()->GetConstant1()); + mask->ChangeRepresentation(Representation::Integer32()); + mask->ClearFlag(HValue::kCanOverflow); + return AddUncasted(Token::BIT_AND, hash, mask); +} + + +template +HValue* HOptimizedGraphBuilder::BuildOrderedHashTableHashToEntry( + HValue* table, HValue* hash, HValue* num_buckets) { + HValue* bucket = BuildOrderedHashTableHashToBucket(hash, num_buckets); + HValue* entry_index = AddUncasted( + bucket, Add(CollectionType::kHashTableStartIndex)); + entry_index->ClearFlag(HValue::kCanOverflow); + HValue* entry = Add(table, entry_index, + static_cast(NULL), FAST_ELEMENTS); + entry->set_type(HType::Smi()); + return entry; +} + + +template +HValue* HOptimizedGraphBuilder::BuildOrderedHashTableEntryToIndex( + HValue* entry, HValue* num_buckets) { + HValue* index = + AddUncasted(entry, Add(CollectionType::kEntrySize)); + index->ClearFlag(HValue::kCanOverflow); + index = AddUncasted(index, num_buckets); + index->ClearFlag(HValue::kCanOverflow); + index = AddUncasted( + index, Add(CollectionType::kHashTableStartIndex)); + index->ClearFlag(HValue::kCanOverflow); + return index; +} + + template HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table, HValue* key, @@ -12122,28 +12160,8 @@ HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table, table, static_cast(NULL), HObjectAccess::ForOrderedHashTableNumberOfBuckets()); - // Some things that won't change inside the loop - HValue* not_found = Add(CollectionType::kNotFound); - HValue* start_index = Add(CollectionType::kHashTableStartIndex); - HValue* entry_size = Add(CollectionType::kEntrySize); - HValue* chain_offset = Add(CollectionType::kChainOffset); - HValue* key_start = AddUncasted(start_index, num_buckets); - key_start->ClearFlag(HValue::kCanOverflow); - - // BuildHashToBucket - HValue* mask = AddUncasted(num_buckets, graph()->GetConstant1()); - mask->ChangeRepresentation(Representation::Integer32()); - mask->ClearFlag(HValue::kCanOverflow); - - HValue* bucket = AddUncasted(Token::BIT_AND, hash, mask); - - // BuildHashToEntry - HValue* entry_index = AddUncasted(start_index, bucket); - entry_index->ClearFlag(HValue::kCanOverflow); - HValue* entry = - Add(table, entry_index, static_cast(NULL), - FAST_ELEMENTS, ALLOW_RETURN_HOLE); - entry->set_type(HType::Smi()); + HValue* entry = BuildOrderedHashTableHashToEntry(table, hash, + num_buckets); Push(entry); @@ -12154,21 +12172,17 @@ HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table, { IfBuilder if_not_found(this); - if_not_found.If(entry, not_found, Token::EQ); + if_not_found.If( + entry, Add(CollectionType::kNotFound), Token::EQ); if_not_found.Then(); Push(entry); loop.Break(); } - // BuildEntryToIndex - HValue* key_index = AddUncasted(entry, entry_size); - key_index->ClearFlag(HValue::kCanOverflow); - key_index = AddUncasted(key_index, key_start); - key_index->ClearFlag(HValue::kCanOverflow); - // BuildKeyAt - HValue* candidate_key = - Add(table, key_index, static_cast(NULL), - FAST_ELEMENTS, ALLOW_RETURN_HOLE); + HValue* key_index = + BuildOrderedHashTableEntryToIndex(entry, num_buckets); + HValue* candidate_key = Add( + table, key_index, static_cast(NULL), FAST_ELEMENTS); { IfBuilder if_keys_equal(this); @@ -12181,14 +12195,11 @@ HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table, } // BuildChainAt - HValue* chain_index = AddUncasted(entry, entry_size); - chain_index->ClearFlag(HValue::kCanOverflow); - chain_index = AddUncasted(chain_index, key_start); - chain_index->ClearFlag(HValue::kCanOverflow); - chain_index = AddUncasted(chain_index, chain_offset); + HValue* chain_index = AddUncasted( + key_index, Add(CollectionType::kChainOffset)); chain_index->ClearFlag(HValue::kCanOverflow); entry = Add(table, chain_index, static_cast(NULL), - FAST_ELEMENTS, ALLOW_RETURN_HOLE); + FAST_ELEMENTS); entry->set_type(HType::Smi()); Push(entry); @@ -12322,6 +12333,290 @@ void HOptimizedGraphBuilder::GenerateSetHas(CallRuntime* call) { } +template +HValue* HOptimizedGraphBuilder::BuildOrderedHashTableAddEntry( + HValue* table, HValue* key, HValue* hash, + HIfContinuation* join_continuation) { + HValue* num_buckets = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfBuckets()); + HValue* capacity = AddUncasted( + num_buckets, Add(CollectionType::kLoadFactor)); + capacity->ClearFlag(HValue::kCanOverflow); + HValue* num_elements = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfElements()); + HValue* num_deleted = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfDeletedElements< + CollectionType>()); + HValue* used = AddUncasted(num_elements, num_deleted); + used->ClearFlag(HValue::kCanOverflow); + IfBuilder if_space_available(this); + if_space_available.If(capacity, used, Token::GT); + if_space_available.Then(); + HValue* bucket = BuildOrderedHashTableHashToBucket(hash, num_buckets); + HValue* entry = used; + HValue* key_index = + BuildOrderedHashTableEntryToIndex(entry, num_buckets); + + HValue* bucket_index = AddUncasted( + bucket, Add(CollectionType::kHashTableStartIndex)); + bucket_index->ClearFlag(HValue::kCanOverflow); + HValue* chain_entry = Add( + table, bucket_index, static_cast(NULL), FAST_ELEMENTS); + chain_entry->set_type(HType::Smi()); + + HValue* chain_index = AddUncasted( + key_index, Add(CollectionType::kChainOffset)); + + Add(table, bucket_index, entry, FAST_ELEMENTS); + Add(table, chain_index, chain_entry, FAST_ELEMENTS); + Add(table, key_index, key, FAST_ELEMENTS); + + HValue* new_num_elements = + AddUncasted(num_elements, graph()->GetConstant1()); + new_num_elements->ClearFlag(HValue::kCanOverflow); + Add( + table, + HObjectAccess::ForOrderedHashTableNumberOfElements(), + new_num_elements); + if_space_available.JoinContinuation(join_continuation); + return key_index; +} + + +void HOptimizedGraphBuilder::GenerateMapSet(CallRuntime* call) { + DCHECK(call->arguments()->length() == 3); + CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); + CHECK_ALIVE(VisitForValue(call->arguments()->at(1))); + CHECK_ALIVE(VisitForValue(call->arguments()->at(2))); + HValue* value = Pop(); + HValue* key = Pop(); + HValue* receiver = Pop(); + + NoObservableSideEffectsScope no_effects(this); + + HIfContinuation return_or_call_runtime_continuation( + graph()->CreateBasicBlock(), graph()->CreateBasicBlock()); + HIfContinuation got_string_hash; + HValue* hash = + BuildStringHashLoadIfIsStringAndHashComputed(key, &got_string_hash); + IfBuilder string_checker(this, &got_string_hash); + string_checker.Then(); + { + HValue* table = Add(receiver, static_cast(NULL), + HObjectAccess::ForJSCollectionTable()); + HValue* key_index = + BuildOrderedHashTableFindEntry(table, key, hash); + { + IfBuilder if_found(this); + if_found.If( + key_index, Add(OrderedHashMap::kNotFound), Token::NE); + if_found.Then(); + { + HValue* value_index = AddUncasted( + key_index, Add(OrderedHashMap::kValueOffset)); + value_index->ClearFlag(HValue::kCanOverflow); + Add(table, value_index, value, FAST_ELEMENTS); + } + if_found.Else(); + { + HIfContinuation did_add(graph()->CreateBasicBlock(), + graph()->CreateBasicBlock()); + HValue* key_index = BuildOrderedHashTableAddEntry( + table, key, hash, &did_add); + IfBuilder if_did_add(this, &did_add); + if_did_add.Then(); + { + HValue* value_index = AddUncasted( + key_index, Add(OrderedHashMap::kValueOffset)); + value_index->ClearFlag(HValue::kCanOverflow); + Add(table, value_index, value, FAST_ELEMENTS); + } + if_did_add.JoinContinuation(&return_or_call_runtime_continuation); + } + } + } + string_checker.JoinContinuation(&return_or_call_runtime_continuation); + + { + IfBuilder return_or_call_runtime(this, + &return_or_call_runtime_continuation); + return_or_call_runtime.Then(); + Push(receiver); + return_or_call_runtime.Else(); + Add(receiver, key, value); + Push(Add(call->name(), + Runtime::FunctionForId(Runtime::kMapSet), 3)); + } + + return ast_context()->ReturnValue(Pop()); +} + + +void HOptimizedGraphBuilder::GenerateSetAdd(CallRuntime* call) { + DCHECK(call->arguments()->length() == 2); + CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); + CHECK_ALIVE(VisitForValue(call->arguments()->at(1))); + HValue* key = Pop(); + HValue* receiver = Pop(); + + NoObservableSideEffectsScope no_effects(this); + + HIfContinuation return_or_call_runtime_continuation( + graph()->CreateBasicBlock(), graph()->CreateBasicBlock()); + HIfContinuation got_string_hash; + HValue* hash = + BuildStringHashLoadIfIsStringAndHashComputed(key, &got_string_hash); + IfBuilder string_checker(this, &got_string_hash); + string_checker.Then(); + { + HValue* table = Add(receiver, static_cast(NULL), + HObjectAccess::ForJSCollectionTable()); + HValue* key_index = + BuildOrderedHashTableFindEntry(table, key, hash); + { + IfBuilder if_not_found(this); + if_not_found.If( + key_index, Add(OrderedHashSet::kNotFound), Token::EQ); + if_not_found.Then(); + BuildOrderedHashTableAddEntry( + table, key, hash, &return_or_call_runtime_continuation); + } + } + string_checker.JoinContinuation(&return_or_call_runtime_continuation); + + { + IfBuilder return_or_call_runtime(this, + &return_or_call_runtime_continuation); + return_or_call_runtime.Then(); + Push(receiver); + return_or_call_runtime.Else(); + Add(receiver, key); + Push(Add(call->name(), + Runtime::FunctionForId(Runtime::kSetAdd), 2)); + } + + return ast_context()->ReturnValue(Pop()); +} + + +template +void HOptimizedGraphBuilder::BuildJSCollectionDelete( + CallRuntime* call, const Runtime::Function* c_function) { + DCHECK(call->arguments()->length() == 2); + CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); + CHECK_ALIVE(VisitForValue(call->arguments()->at(1))); + HValue* key = Pop(); + HValue* receiver = Pop(); + + NoObservableSideEffectsScope no_effects(this); + + HIfContinuation return_or_call_runtime_continuation( + graph()->CreateBasicBlock(), graph()->CreateBasicBlock()); + HIfContinuation got_string_hash; + HValue* hash = + BuildStringHashLoadIfIsStringAndHashComputed(key, &got_string_hash); + IfBuilder string_checker(this, &got_string_hash); + string_checker.Then(); + { + HValue* table = Add(receiver, static_cast(NULL), + HObjectAccess::ForJSCollectionTable()); + HValue* key_index = + BuildOrderedHashTableFindEntry(table, key, hash); + { + IfBuilder if_found(this); + if_found.If( + key_index, Add(CollectionType::kNotFound), Token::NE); + if_found.Then(); + { + // If we're removing an element, we might need to shrink. + // If we do need to shrink, we'll be bailing out to the runtime. + HValue* num_elements = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfElements< + CollectionType>()); + HValue* threshold = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfElements< + CollectionType>()); + threshold = AddUncasted( + threshold, Add(CollectionType::kLoadFactor)); + threshold->ClearFlag(HValue::kCanOverflow); + threshold = AddUncasted(threshold, Add(2)); + + IfBuilder if_need_not_shrink(this); + if_need_not_shrink.If(num_elements, threshold, + Token::GTE); + if_need_not_shrink.Then(); + { + Add(table, key_index, graph()->GetConstantHole(), + FAST_ELEMENTS); + + // For maps, also need to clear the value. + if (CollectionType::kChainOffset > 1) { + HValue* value_index = + AddUncasted(key_index, graph()->GetConstant1()); + Add(table, value_index, graph()->GetConstantHole(), + FAST_ELEMENTS); + } + STATIC_ASSERT(CollectionType::kChainOffset <= 2); + + num_elements = + AddUncasted(num_elements, graph()->GetConstant1()); + HValue* num_deleted = Add( + table, static_cast(NULL), + HObjectAccess::ForOrderedHashTableNumberOfDeletedElements< + CollectionType>()); + num_deleted = AddUncasted(num_deleted, graph()->GetConstant1()); + Add( + table, HObjectAccess::ForOrderedHashTableNumberOfElements< + CollectionType>(), + num_elements); + Add( + table, HObjectAccess::ForOrderedHashTableNumberOfDeletedElements< + CollectionType>(), + num_deleted); + Push(graph()->GetConstantTrue()); + } + if_need_not_shrink.JoinContinuation( + &return_or_call_runtime_continuation); + } + if_found.Else(); + { + // Not found, so we're done. + Push(graph()->GetConstantFalse()); + } + } + } + string_checker.JoinContinuation(&return_or_call_runtime_continuation); + + { + IfBuilder return_or_call_runtime(this, + &return_or_call_runtime_continuation); + return_or_call_runtime.Then(); + return_or_call_runtime.Else(); + Add(receiver, key); + Push(Add(call->name(), c_function, 2)); + } + + return ast_context()->ReturnValue(Pop()); +} + + +void HOptimizedGraphBuilder::GenerateMapDelete(CallRuntime* call) { + BuildJSCollectionDelete( + call, Runtime::FunctionForId(Runtime::kMapDelete)); +} + + +void HOptimizedGraphBuilder::GenerateSetDelete(CallRuntime* call) { + BuildJSCollectionDelete( + call, Runtime::FunctionForId(Runtime::kSetDelete)); +} + + void HOptimizedGraphBuilder::GenerateSetGetSize(CallRuntime* call) { DCHECK(call->arguments()->length() == 1); CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); diff --git a/src/hydrogen.h b/src/hydrogen.h index ebd9e8b..f24f172 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -2417,14 +2417,26 @@ class HOptimizedGraphBuilder : public HGraphBuilder, public AstVisitor { ElementsKind fixed_elements_kind, HValue* byte_length, HValue* length); + // TODO(adamk): Move all OrderedHashTable functions to their own class. + HValue* BuildOrderedHashTableHashToBucket(HValue* hash, HValue* num_buckets); + template + HValue* BuildOrderedHashTableHashToEntry(HValue* table, HValue* hash, + HValue* num_buckets); + template + HValue* BuildOrderedHashTableEntryToIndex(HValue* entry, HValue* num_buckets); template HValue* BuildOrderedHashTableFindEntry(HValue* table, HValue* key, HValue* hash); - + template + HValue* BuildOrderedHashTableAddEntry(HValue* table, HValue* key, + HValue* hash, + HIfContinuation* join_continuation); + template + void BuildJSCollectionDelete(CallRuntime* call, + const Runtime::Function* c_function); template void BuildJSCollectionHas(CallRuntime* call, const Runtime::Function* c_function); - HValue* BuildStringHashLoadIfIsStringAndHashComputed( HValue* object, HIfContinuation* continuation); diff --git a/src/objects.h b/src/objects.h index bb9ecee..bb8e9af 100644 --- a/src/objects.h +++ b/src/objects.h @@ -3915,10 +3915,14 @@ class OrderedHashTable: public FixedArray { kHeaderSize + kNumberOfBucketsIndex * kPointerSize; static const int kNumberOfElementsOffset = kHeaderSize + kNumberOfElementsIndex * kPointerSize; + static const int kNumberOfDeletedElementsOffset = + kHeaderSize + kNumberOfDeletedElementsIndex * kPointerSize; static const int kEntrySize = entrysize + 1; static const int kChainOffset = entrysize; + static const int kLoadFactor = 2; + private: static Handle Rehash(Handle table, int new_capacity); @@ -3963,7 +3967,6 @@ class OrderedHashTable: public FixedArray { static const int kNextTableIndex = kNumberOfElementsIndex; static const int kRemovedHolesIndex = kHashTableStartIndex; - static const int kLoadFactor = 2; static const int kMaxCapacity = (FixedArray::kMaxLength - kHashTableStartIndex) / (1 + (kEntrySize * kLoadFactor)); diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index 65fc6fd..ab08ecf 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -303,8 +303,6 @@ namespace internal { \ /* Harmony sets */ \ F(SetInitialize, 1, 1) \ - F(SetAdd, 2, 1) \ - F(SetDelete, 2, 1) \ F(SetClear, 1, 1) \ \ F(SetIteratorInitialize, 3, 1) \ @@ -314,9 +312,7 @@ namespace internal { \ /* Harmony maps */ \ F(MapInitialize, 1, 1) \ - F(MapDelete, 2, 1) \ F(MapClear, 1, 1) \ - F(MapSet, 3, 1) \ \ F(MapIteratorInitialize, 3, 1) \ F(MapIteratorClone, 1, 1) \ @@ -728,9 +724,13 @@ namespace internal { F(MathSqrtRT, 1, 1) \ F(MathLogRT, 1, 1) \ /* ES6 Collections */ \ + F(MapDelete, 2, 1) \ F(MapGet, 2, 1) \ F(MapGetSize, 1, 1) \ F(MapHas, 2, 1) \ + F(MapSet, 3, 1) \ + F(SetAdd, 2, 1) \ + F(SetDelete, 2, 1) \ F(SetGetSize, 1, 1) \ F(SetHas, 2, 1) \ /* Arrays */ \ -- 2.7.4