Revision: 22027
Author: [email protected]
Date: Thu Jun 26 00:40:45 2014 UTC
Log: Optimize Map/Set.prototype.forEach
Instead of using an iterator result object and an entries array
(for Map) we introduce a new runtime function that uses an array
as an out param.
On the Map ForEach perf test this leads to a 2.5x performance
improvement. On the overall Map and Set tests this leads to a 18%
and 13% improvement respectively.
BUG=None
LOG=Y
[email protected]
Review URL: https://codereview.chromium.org/355663002
Patch from Erik Arvidsson <[email protected]>.
http://code.google.com/p/v8/source/detail?r=22027
Modified:
/branches/bleeding_edge/src/collection-iterator.js
/branches/bleeding_edge/src/collection.js
/branches/bleeding_edge/src/factory.cc
/branches/bleeding_edge/src/factory.h
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.h
/branches/bleeding_edge/test/mjsunit/runtime-gen/mapiteratornext.js
/branches/bleeding_edge/test/mjsunit/runtime-gen/setiteratornext.js
=======================================
--- /branches/bleeding_edge/src/collection-iterator.js Thu Jun 12 08:53:07
2014 UTC
+++ /branches/bleeding_edge/src/collection-iterator.js Thu Jun 26 00:40:45
2014 UTC
@@ -21,7 +21,23 @@
throw MakeTypeError('incompatible_method_receiver',
['Set Iterator.prototype.next', this]);
}
- return %SetIteratorNext(this);
+
+ var value_array = [UNDEFINED, UNDEFINED];
+ var entry = {value: value_array, done: false};
+ switch (%SetIteratorNext(this, value_array)) {
+ case 0:
+ entry.value = UNDEFINED;
+ entry.done = true;
+ break;
+ case ITERATOR_KIND_VALUES:
+ entry.value = value_array[0];
+ break;
+ case ITERATOR_KIND_ENTRIES:
+ value_array[1] = value_array[0];
+ break;
+ }
+
+ return entry;
}
@@ -97,7 +113,24 @@
throw MakeTypeError('incompatible_method_receiver',
['Map Iterator.prototype.next', this]);
}
- return %MapIteratorNext(this);
+
+ var value_array = [UNDEFINED, UNDEFINED];
+ var entry = {value: value_array, done: false};
+ switch (%MapIteratorNext(this, value_array)) {
+ case 0:
+ entry.value = UNDEFINED;
+ entry.done = true;
+ break;
+ case ITERATOR_KIND_KEYS:
+ entry.value = value_array[0];
+ break;
+ case ITERATOR_KIND_VALUES:
+ entry.value = value_array[1];
+ break;
+ // ITERATOR_KIND_ENTRIES does not need any processing.
+ }
+
+ return entry;
}
=======================================
--- /branches/bleeding_edge/src/collection.js Mon Jun 23 18:05:57 2014 UTC
+++ /branches/bleeding_edge/src/collection.js Thu Jun 26 00:40:45 2014 UTC
@@ -129,11 +129,13 @@
}
var iterator = new SetIterator(this, ITERATOR_KIND_VALUES);
- var entry;
+ var key;
var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
- while (!(entry = %SetIteratorNext(iterator)).done) {
+ var value_array = [UNDEFINED];
+ while (%SetIteratorNext(iterator, value_array)) {
if (stepping) %DebugPrepareStepInIfStepping(f);
- %_CallFunction(receiver, entry.value, entry.value, this, f);
+ key = value_array[0];
+ %_CallFunction(receiver, key, key, this, f);
}
}
@@ -264,11 +266,11 @@
}
var iterator = new MapIterator(this, ITERATOR_KIND_ENTRIES);
- var entry;
var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
- while (!(entry = %MapIteratorNext(iterator)).done) {
+ var value_array = [UNDEFINED, UNDEFINED];
+ while (%MapIteratorNext(iterator, value_array)) {
if (stepping) %DebugPrepareStepInIfStepping(f);
- %_CallFunction(receiver, entry.value[1], entry.value[0], this, f);
+ %_CallFunction(receiver, value_array[1], value_array[0], this, f);
}
}
=======================================
--- /branches/bleeding_edge/src/factory.cc Tue Jun 24 14:53:48 2014 UTC
+++ /branches/bleeding_edge/src/factory.cc Thu Jun 26 00:40:45 2014 UTC
@@ -1392,18 +1392,6 @@
}
return result;
}
-
-
-Handle<JSObject> Factory::NewIteratorResultObject(Handle<Object> value,
- bool done) {
- Handle<Map> map(isolate()->native_context()->iterator_result_map());
- Handle<JSObject> result = NewJSObjectFromMap(map, NOT_TENURED, false);
- result->InObjectPropertyAtPut(
- JSGeneratorObject::kResultValuePropertyIndex, *value);
- result->InObjectPropertyAtPut(
- JSGeneratorObject::kResultDonePropertyIndex, *ToBoolean(done));
- return result;
-}
Handle<ScopeInfo> Factory::NewScopeInfo(int length) {
=======================================
--- /branches/bleeding_edge/src/factory.h Wed Jun 18 13:26:02 2014 UTC
+++ /branches/bleeding_edge/src/factory.h Thu Jun 26 00:40:45 2014 UTC
@@ -551,8 +551,6 @@
Handle<Object> NewEvalError(const char* message,
Vector< Handle<Object> > args);
- Handle<JSObject> NewIteratorResultObject(Handle<Object> value, bool
done);
-
Handle<String> NumberToString(Handle<Object> number,
bool check_number_string_cache = true);
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Wed Jun 25 12:12:21 2014 UTC
+++ /branches/bleeding_edge/src/objects-inl.h Thu Jun 26 00:40:45 2014 UTC
@@ -6962,6 +6962,36 @@
v->VisitPointers(HeapObject::RawField(obj, start_offset),
HeapObject::RawField(obj, object_size));
}
+
+
+template<class Derived, class TableType>
+Object* OrderedHashTableIterator<Derived, TableType>::CurrentKey() {
+ TableType* table(TableType::cast(this->table()));
+ int index = Smi::cast(this->index())->value();
+ Object* key = table->KeyAt(index);
+ ASSERT(!key->IsTheHole());
+ return key;
+}
+
+
+void JSSetIterator::PopulateValueArray(FixedArray* array) {
+ array->set(0, CurrentKey());
+}
+
+
+void JSMapIterator::PopulateValueArray(FixedArray* array) {
+ array->set(0, CurrentKey());
+ array->set(1, CurrentValue());
+}
+
+
+Object* JSMapIterator::CurrentValue() {
+ OrderedHashMap* table(OrderedHashMap::cast(this->table()));
+ int index = Smi::cast(this->index())->value();
+ Object* value = table->ValueAt(index);
+ ASSERT(!value->IsTheHole());
+ return value;
+}
#undef TYPE_CHECKER
=======================================
--- /branches/bleeding_edge/src/objects.cc Tue Jun 24 15:56:36 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Thu Jun 26 00:40:45 2014 UTC
@@ -16245,50 +16245,17 @@
table->set(index + kValueOffset, *value);
return table;
}
-
-
-template<class Derived, class TableType>
-Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
- Handle<Derived> iterator) {
- Isolate* isolate = iterator->GetIsolate();
- Factory* factory = isolate->factory();
-
- Handle<Object> maybe_table(iterator->table(), isolate);
- if (!maybe_table->IsUndefined()) {
- iterator->Transition();
-
- Handle<TableType> table(TableType::cast(iterator->table()), isolate);
- int index = Smi::cast(iterator->index())->value();
- int used_capacity = table->UsedCapacity();
-
- while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
- index++;
- }
-
- if (index < used_capacity) {
- int entry_index = table->EntryToIndex(index);
- Handle<Object> value =
- Derived::ValueForKind(iterator, entry_index);
- iterator->set_index(Smi::FromInt(index + 1));
- return factory->NewIteratorResultObject(value, false);
- }
-
- iterator->set_table(iterator->GetHeap()->undefined_value());
- }
-
- return factory->NewIteratorResultObject(factory->undefined_value(),
true);
-}
template<class Derived, class TableType>
void OrderedHashTableIterator<Derived, TableType>::Transition() {
- Isolate* isolate = GetIsolate();
- Handle<TableType> table(TableType::cast(this->table()), isolate);
+ DisallowHeapAllocation no_allocation;
+ TableType* table = TableType::cast(this->table());
if (!table->IsObsolete()) return;
int index = Smi::cast(this->index())->value();
while (table->IsObsolete()) {
- Handle<TableType> next_table(table->NextTable(), isolate);
+ TableType* next_table = table->NextTable();
if (index > 0) {
int nod = table->NumberOfDeletedElements();
@@ -16309,82 +16276,80 @@
table = next_table;
}
- set_table(*table);
+ set_table(table);
set_index(Smi::FromInt(index));
}
-template Handle<JSObject>
-OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next(
- Handle<JSSetIterator> iterator);
+template<class Derived, class TableType>
+bool OrderedHashTableIterator<Derived, TableType>::HasMore() {
+ DisallowHeapAllocation no_allocation;
+ if (this->table()->IsUndefined()) return false;
-template void
-OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
+ Transition();
+ TableType* table = TableType::cast(this->table());
+ int index = Smi::cast(this->index())->value();
+ int used_capacity = table->UsedCapacity();
-template Handle<JSObject>
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next(
- Handle<JSMapIterator> iterator);
+ while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
+ index++;
+ }
-template void
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
+ set_index(Smi::FromInt(index));
+ if (index < used_capacity) return true;
-Handle<Object> JSSetIterator::ValueForKind(
- Handle<JSSetIterator> iterator, int entry_index) {
- int kind = iterator->kind()->value();
- // Set.prototype only has values and entries.
- ASSERT(kind == kKindValues || kind == kKindEntries);
+ set_table(GetHeap()->undefined_value());
+ return false;
+}
+
+
+template<class Derived, class TableType>
+Smi* OrderedHashTableIterator<Derived, TableType>::Next(JSArray*
value_array) {
+ DisallowHeapAllocation no_allocation;
+ if (HasMore()) {
+ FixedArray* array = FixedArray::cast(value_array->elements());
+ static_cast<Derived*>(this)->PopulateValueArray(array);
+ MoveNext();
+ return kind();
+ }
+ return Smi::FromInt(0);
+}
- Isolate* isolate = iterator->GetIsolate();
- Factory* factory = isolate->factory();
- Handle<OrderedHashSet> table(
- OrderedHashSet::cast(iterator->table()), isolate);
- Handle<Object> value = Handle<Object>(table->get(entry_index), isolate);
+template Smi*
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next(
+ JSArray* value_array);
- if (kind == kKindEntries) {
- Handle<FixedArray> array = factory->NewFixedArray(2);
- array->set(0, *value);
- array->set(1, *value);
- return factory->NewJSArrayWithElements(array);
- }
+template bool
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore();
- return value;
-}
+template void
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
+template Object*
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
-Handle<Object> JSMapIterator::ValueForKind(
- Handle<JSMapIterator> iterator, int entry_index) {
- int kind = iterator->kind()->value();
- ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries);
+template void
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
- Isolate* isolate = iterator->GetIsolate();
- Factory* factory = isolate->factory();
- Handle<OrderedHashMap> table(
- OrderedHashMap::cast(iterator->table()), isolate);
+template Smi*
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next(
+ JSArray* value_array);
- switch (kind) {
- case kKindKeys:
- return Handle<Object>(table->get(entry_index), isolate);
+template bool
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
- case kKindValues:
- return Handle<Object>(table->get(entry_index + 1), isolate);
+template void
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
- case kKindEntries: {
- Handle<Object> key(table->get(entry_index), isolate);
- Handle<Object> value(table->get(entry_index + 1), isolate);
- Handle<FixedArray> array = factory->NewFixedArray(2);
- array->set(0, *key);
- array->set(1, *value);
- return factory->NewJSArrayWithElements(array);
- }
- }
+template Object*
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
- UNREACHABLE();
- return factory->undefined_value();
-}
+template void
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
=======================================
--- /branches/bleeding_edge/src/objects.h Wed Jun 25 12:12:21 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Thu Jun 26 00:40:45 2014 UTC
@@ -4463,11 +4463,11 @@
Handle<Object> key,
Handle<Object> value);
- private:
Object* ValueAt(int entry) {
return get(EntryToIndex(entry) + kValueOffset);
}
+ private:
static const int kValueOffset = 1;
};
@@ -10104,13 +10104,26 @@
kKindEntries = 3
};
- // Returns an iterator result object: {value: any, done: boolean} and
moves
- // the index to the next valid entry. Closes the iterator if moving past
the
- // end.
- static Handle<JSObject> Next(Handle<Derived> iterator);
+ // Whether the iterator has more elements. This needs to be called before
+ // calling |CurrentKey| and/or |CurrentValue|.
+ bool HasMore();
+
+ // Move the index forward one.
+ void MoveNext() {
+ set_index(Smi::FromInt(Smi::cast(index())->value() + 1));
+ }
+
+ // Populates the array with the next key and value and then moves the
iterator
+ // forward.
+ // This returns the |kind| or 0 if the iterator is already at the end.
+ Smi* Next(JSArray* value_array);
+
+ // Returns the current key of the iterator. This should only be called
when
+ // |HasMore| returns true.
+ inline Object* CurrentKey();
private:
- // Transitions the iterator to the non obsolote backing store. This is a
NOP
+ // Transitions the iterator to the non obsolete backing store. This is a
NOP
// if the [table] is not obsolete.
void Transition();
@@ -10127,9 +10140,9 @@
DECLARE_CAST(JSSetIterator)
- static Handle<Object> ValueForKind(
- Handle<JSSetIterator> iterator,
- int entry_index);
+ // Called by |Next| to populate the array. This allows the subclasses to
+ // populate the array differently.
+ inline void PopulateValueArray(FixedArray* array);
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
@@ -10145,11 +10158,15 @@
DECLARE_CAST(JSMapIterator)
- static Handle<Object> ValueForKind(
- Handle<JSMapIterator> iterator,
- int entry_index);
+ // Called by |Next| to populate the array. This allows the subclasses to
+ // populate the array differently.
+ inline void PopulateValueArray(FixedArray* array);
private:
+ // Returns the current value of the iterator. This should only be called
when
+ // |HasMore| returns true.
+ inline Object* CurrentValue();
+
DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
};
=======================================
--- /branches/bleeding_edge/src/runtime.cc Wed Jun 25 15:26:10 2014 UTC
+++ /branches/bleeding_edge/src/runtime.cc Thu Jun 26 00:40:45 2014 UTC
@@ -1604,10 +1604,11 @@
RUNTIME_FUNCTION(Runtime_SetIteratorNext) {
- HandleScope scope(isolate);
- ASSERT(args.length() == 1);
- CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0);
- return *JSSetIterator::Next(holder);
+ SealHandleScope shs(isolate);
+ ASSERT(args.length() == 2);
+ CONVERT_ARG_CHECKED(JSSetIterator, holder, 0);
+ CONVERT_ARG_CHECKED(JSArray, value_array, 1);
+ return holder->Next(value_array);
}
@@ -1708,10 +1709,11 @@
RUNTIME_FUNCTION(Runtime_MapIteratorNext) {
- HandleScope scope(isolate);
- ASSERT(args.length() == 1);
- CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0);
- return *JSMapIterator::Next(holder);
+ SealHandleScope shs(isolate);
+ ASSERT(args.length() == 2);
+ CONVERT_ARG_CHECKED(JSMapIterator, holder, 0);
+ CONVERT_ARG_CHECKED(JSArray, value_array, 1);
+ return holder->Next(value_array);
}
=======================================
--- /branches/bleeding_edge/src/runtime.h Wed Jun 25 15:26:10 2014 UTC
+++ /branches/bleeding_edge/src/runtime.h Thu Jun 26 00:40:45 2014 UTC
@@ -274,7 +274,7 @@
F(SetGetSize, 1, 1) \
\
F(SetIteratorInitialize, 3, 1) \
- F(SetIteratorNext, 1, 1) \
+ F(SetIteratorNext, 2, 1) \
\
/* Harmony maps */ \
F(MapInitialize, 1, 1) \
@@ -286,7 +286,7 @@
F(MapGetSize, 1, 1) \
\
F(MapIteratorInitialize, 3, 1) \
- F(MapIteratorNext, 1, 1) \
+ F(MapIteratorNext, 2, 1) \
\
/* Harmony weak maps and sets */ \
F(WeakCollectionInitialize, 1, 1) \
=======================================
--- /branches/bleeding_edge/test/mjsunit/runtime-gen/mapiteratornext.js Tue
Jun 3 00:34:01 2014 UTC
+++ /branches/bleeding_edge/test/mjsunit/runtime-gen/mapiteratornext.js Thu
Jun 26 00:40:45 2014 UTC
@@ -2,4 +2,5 @@
// AUTO-GENERATED BY tools/generate-runtime-tests.py, DO NOT MODIFY
// Flags: --allow-natives-syntax --harmony
var _holder = new Map().entries();
-%MapIteratorNext(_holder);
+var _value_array = new Array();
+%MapIteratorNext(_holder, _value_array);
=======================================
--- /branches/bleeding_edge/test/mjsunit/runtime-gen/setiteratornext.js Tue
Jun 3 00:34:01 2014 UTC
+++ /branches/bleeding_edge/test/mjsunit/runtime-gen/setiteratornext.js Thu
Jun 26 00:40:45 2014 UTC
@@ -2,4 +2,5 @@
// AUTO-GENERATED BY tools/generate-runtime-tests.py, DO NOT MODIFY
// Flags: --allow-natives-syntax --harmony
var _holder = new Set().values();
-%SetIteratorNext(_holder);
+var _value_array = new Array();
+%SetIteratorNext(_holder, _value_array);
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
