Revision: 7679
Author: [email protected]
Date: Tue Apr 26 02:44:55 2011
Log: Add prototype transitions cache to Map.
Review URL: http://codereview.chromium.org/6902029
http://code.google.com/p/v8/source/detail?r=7679
Modified:
/branches/bleeding_edge/src/flag-definitions.h
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/mark-compact.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/flag-definitions.h Fri Apr 15 05:31:03 2011
+++ /branches/bleeding_edge/src/flag-definitions.h Tue Apr 26 02:44:55 2011
@@ -223,6 +223,8 @@
// compilation-cache.cc
DEFINE_bool(compilation_cache, true, "enable compilation cache")
+DEFINE_bool(cache_prototype_transitions, true, "cache prototype
transitions")
+
// data-flow.cc
DEFINE_bool(loop_peeling, false, "Peel off the first iteration of loops.")
=======================================
--- /branches/bleeding_edge/src/heap.cc Thu Apr 21 23:40:22 2011
+++ /branches/bleeding_edge/src/heap.cc Tue Apr 26 02:44:55 2011
@@ -1594,6 +1594,7 @@
map->set_pre_allocated_property_fields(0);
map->set_instance_descriptors(empty_descriptor_array());
map->set_code_cache(empty_fixed_array());
+ map->set_prototype_transitions(empty_fixed_array());
map->set_unused_property_fields(0);
map->set_bit_field(0);
map->set_bit_field2((1 << Map::kIsExtensible) | (1 <<
Map::kHasFastElements));
@@ -1686,12 +1687,15 @@
// Fix the instance_descriptors for the existing maps.
meta_map()->set_instance_descriptors(empty_descriptor_array());
meta_map()->set_code_cache(empty_fixed_array());
+ meta_map()->set_prototype_transitions(empty_fixed_array());
fixed_array_map()->set_instance_descriptors(empty_descriptor_array());
fixed_array_map()->set_code_cache(empty_fixed_array());
+ fixed_array_map()->set_prototype_transitions(empty_fixed_array());
oddball_map()->set_instance_descriptors(empty_descriptor_array());
oddball_map()->set_code_cache(empty_fixed_array());
+ oddball_map()->set_prototype_transitions(empty_fixed_array());
// Fix prototype object for existing maps.
meta_map()->set_prototype(null_value());
=======================================
--- /branches/bleeding_edge/src/mark-compact.cc Wed Apr 6 12:17:54 2011
+++ /branches/bleeding_edge/src/mark-compact.cc Tue Apr 26 02:44:55 2011
@@ -1077,6 +1077,12 @@
void MarkCompactCollector::MarkMapContents(Map* map) {
+ // Mark prototype transitions array but don't push it into marking stack.
+ // This will make references from it weak. We will clean dead prototype
+ // transitions in ClearNonLiveTransitions.
+ FixedArray* prototype_transitions =
map->unchecked_prototype_transitions();
+ if (!prototype_transitions->IsMarked()) SetMark(prototype_transitions);
+
MarkDescriptorArray(reinterpret_cast<DescriptorArray*>(
*HeapObject::RawField(map, Map::kInstanceDescriptorsOffset)));
@@ -1494,7 +1500,7 @@
void MarkCompactCollector::ClearNonLiveTransitions() {
- HeapObjectIterator map_iterator(heap() ->map_space(),
&SizeOfMarkedObject);
+ HeapObjectIterator map_iterator(heap()->map_space(),
&SizeOfMarkedObject);
// Iterate over the map space, setting map transitions that go from
// a marked map to an unmarked map to null transitions. At the same
time,
// set all the prototype fields of maps back to their original value,
@@ -1521,6 +1527,41 @@
// Since it survived the GC, reattach it now.
map->unchecked_constructor()->unchecked_shared()->AttachInitialMap(map);
}
+
+ // Clear dead prototype transitions.
+ FixedArray* prototype_transitions =
map->unchecked_prototype_transitions();
+ if (prototype_transitions->length() > 0) {
+ int finger = Smi::cast(prototype_transitions->get(0))->value();
+ int new_finger = 1;
+ for (int i = 1; i < finger; i += 2) {
+ Object* prototype = prototype_transitions->get(i);
+ Object* cached_map = prototype_transitions->get(i + 1);
+ if (HeapObject::cast(prototype)->IsMarked() &&
+ HeapObject::cast(cached_map)->IsMarked()) {
+ if (new_finger != i) {
+ prototype_transitions->set_unchecked(heap_,
+ new_finger,
+ prototype,
+ UPDATE_WRITE_BARRIER);
+ prototype_transitions->set_unchecked(heap_,
+ new_finger + 1,
+ cached_map,
+ SKIP_WRITE_BARRIER);
+ }
+ new_finger += 2;
+ }
+ }
+
+ // Fill slots that became free with undefined value.
+ Object* undefined = heap()->raw_unchecked_undefined_value();
+ for (int i = new_finger; i < finger; i++) {
+ prototype_transitions->set_unchecked(heap_,
+ i,
+ undefined,
+ SKIP_WRITE_BARRIER);
+ }
+ prototype_transitions->set_unchecked(0, Smi::FromInt(new_finger));
+ }
// Follow the chain of back pointers to find the prototype.
Map* current = map;
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Thu Apr 21 00:15:43 2011
+++ /branches/bleeding_edge/src/objects-inl.h Tue Apr 26 02:44:55 2011
@@ -2535,6 +2535,12 @@
JSFunction* Map::unchecked_constructor() {
return reinterpret_cast<JSFunction*>(READ_FIELD(this,
kConstructorOffset));
}
+
+
+FixedArray* Map::unchecked_prototype_transitions() {
+ return reinterpret_cast<FixedArray*>(
+ READ_FIELD(this, kPrototypeTransitionsOffset));
+}
Code::Flags Code::flags() {
@@ -2945,6 +2951,7 @@
ACCESSORS(Map, instance_descriptors, DescriptorArray,
kInstanceDescriptorsOffset)
ACCESSORS(Map, code_cache, Object, kCodeCacheOffset)
+ACCESSORS(Map, prototype_transitions, FixedArray,
kPrototypeTransitionsOffset)
ACCESSORS(Map, constructor, Object, kConstructorOffset)
ACCESSORS(JSFunction, shared, SharedFunctionInfo,
kSharedFunctionInfoOffset)
=======================================
--- /branches/bleeding_edge/src/objects.cc Thu Apr 21 00:15:43 2011
+++ /branches/bleeding_edge/src/objects.cc Tue Apr 26 02:44:55 2011
@@ -6881,6 +6881,49 @@
set_elements(FixedArray::cast(obj));
return this;
}
+
+
+Object* Map::GetPrototypeTransition(Object* prototype) {
+ FixedArray* cache = prototype_transitions();
+ int capacity = cache->length();
+ if (capacity == 0) return NULL;
+ int finger = Smi::cast(cache->get(0))->value();
+ for (int i = 1; i < finger; i += 2) {
+ if (cache->get(i) == prototype) return cache->get(i + 1);
+ }
+ return NULL;
+}
+
+
+MaybeObject* Map::PutPrototypeTransition(Object* prototype, Map* map) {
+ // Don't cache prototype transition if this map is shared.
+ if (is_shared() || !FLAG_cache_prototype_transitions) return this;
+
+ FixedArray* cache = prototype_transitions();
+
+ int capacity = cache->length();
+
+ int finger = (capacity == 0) ? 1 : Smi::cast(cache->get(0))->value();
+
+ if (finger >= capacity) {
+ if (capacity > kMaxCachedPrototypeTransitions) return this;
+
+ FixedArray* new_cache;
+ { MaybeObject* maybe_cache = heap()->AllocateFixedArray(finger * 2 +
1);
+ if (!maybe_cache->To<FixedArray>(&new_cache)) return maybe_cache;
+ }
+
+ for (int i = 1; i < capacity; i++) new_cache->set(i, cache->get(i));
+ cache = new_cache;
+ set_prototype_transitions(cache);
+ }
+
+ cache->set(finger, prototype);
+ cache->set(finger + 1, map);
+ cache->set(0, Smi::FromInt(finger + 2));
+
+ return cache;
+}
MaybeObject* JSObject::SetPrototype(Object* value,
@@ -6933,11 +6976,25 @@
}
// Set the new prototype of the object.
- Object* new_map;
- { MaybeObject* maybe_new_map =
real_receiver->map()->CopyDropTransitions();
- if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
- }
- Map::cast(new_map)->set_prototype(value);
+ Map* map = real_receiver->map();
+
+ // Nothing to do if prototype is already set.
+ if (map->prototype() == value) return value;
+
+ Object* new_map = map->GetPrototypeTransition(value);
+ if (new_map == NULL) {
+ { MaybeObject* maybe_new_map = map->CopyDropTransitions();
+ if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
+ }
+
+ { MaybeObject* maybe_new_cache =
+ map->PutPrototypeTransition(value, Map::cast(new_map));
+ if (maybe_new_cache->IsFailure()) return maybe_new_cache;
+ }
+
+ Map::cast(new_map)->set_prototype(value);
+ }
+ ASSERT(Map::cast(new_map)->prototype() == value);
real_receiver->set_map(Map::cast(new_map));
heap->ClearInstanceofCache();
=======================================
--- /branches/bleeding_edge/src/objects.h Thu Apr 21 00:15:43 2011
+++ /branches/bleeding_edge/src/objects.h Tue Apr 26 02:44:55 2011
@@ -648,6 +648,13 @@
CHECK(!IsFailure());
return reinterpret_cast<Object*>(this);
}
+
+ template<typename T>
+ inline bool To(T** obj) {
+ if (IsFailure()) return false;
+ *obj = T::cast(reinterpret_cast<Object*>(this));
+ return true;
+ }
#ifdef OBJECT_PRINT
// Prints this object with details.
@@ -3744,6 +3751,16 @@
// [stub cache]: contains stubs compiled for this map.
DECL_ACCESSORS(code_cache, Object)
+ // [prototype transitions]: cache of prototype transitions.
+ // Prototype transition is a transition that happens
+ // when we change object's prototype to a new one.
+ // Cache format:
+ // 0: finger - index of the first free cell in the cache
+ // 1 + 2 * i: prototype
+ // 2 + 2 * i: target map
+ DECL_ACCESSORS(prototype_transitions, FixedArray)
+ inline FixedArray* unchecked_prototype_transitions();
+
// Lookup in the map's instance descriptors and fill out the result
// with the given holder if the name is found. The holder may be
// NULL when this function is used from the compiler.
@@ -3843,6 +3860,12 @@
void TraverseTransitionTree(TraverseCallback callback, void* data);
+ static const int kMaxCachedPrototypeTransitions = 256;
+
+ Object* GetPrototypeTransition(Object* prototype);
+
+ MaybeObject* PutPrototypeTransition(Object* prototype, Map* map);
+
static const int kMaxPreAllocatedPropertyFields = 255;
// Layout description.
@@ -3853,14 +3876,16 @@
static const int kInstanceDescriptorsOffset =
kConstructorOffset + kPointerSize;
static const int kCodeCacheOffset = kInstanceDescriptorsOffset +
kPointerSize;
- static const int kPadStart = kCodeCacheOffset + kPointerSize;
+ static const int kPrototypeTransitionsOffset =
+ kCodeCacheOffset + kPointerSize;
+ static const int kPadStart = kPrototypeTransitionsOffset + kPointerSize;
static const int kSize = MAP_POINTER_ALIGN(kPadStart);
// Layout of pointer fields. Heap iteration code relies on them
// being continiously allocated.
static const int kPointerFieldsBeginOffset = Map::kPrototypeOffset;
static const int kPointerFieldsEndOffset =
- Map::kCodeCacheOffset + kPointerSize;
+ Map::kPrototypeTransitionsOffset + kPointerSize;
// Byte offsets within kInstanceSizesOffset.
static const int kInstanceSizeOffset = kInstanceSizesOffset + 0;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
