Limit initial size of hidden properties and store identity hashes inline.

src/objects.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 2742 matching lines @@
     // Code will be set on the JavaScript side.
   } else {
     isolate->factory()->BecomeJSObject(self);
   }
   ASSERT(self->IsJSObject());
 
   // Inherit identity, if it was present.
   Object* hash;
   if (maybe_hash->To<Object>(&hash) && hash->IsSmi()) {
     Handle<JSObject> new_self(JSObject::cast(*self));
-    isolate->factory()->SetIdentityHash(new_self, hash);
+    isolate->factory()->SetIdentityHash(new_self, Smi::cast(hash));
   }
 }
 
 
 MUST_USE_RESULT Handle<Object> JSProxy::CallTrap(const char* name,
                                                  Handle<Object> derived,
                                                  int argc,
                                                  Handle<Object> argv[]) {
   Isolate* isolate = GetIsolate();
   Handle<Object> handler(this->handler());
@@ skipping 723 matching lines @@
     // within a smi.
     hash_value = V8::RandomPrivate(isolate) & Smi::kMaxValue;
     attempts++;
   } while (hash_value == 0 && attempts < 30);
   hash_value = hash_value != 0 ? hash_value : 1;  // never return 0
 
   return Smi::FromInt(hash_value);
 }
 
 
-MaybeObject* JSObject::SetIdentityHash(Object* hash, CreationFlag flag) {
+MaybeObject* JSObject::SetIdentityHash(Smi* hash, CreationFlag flag) {
   MaybeObject* maybe = SetHiddenProperty(GetHeap()->identity_hash_symbol(),
                                          hash);
   if (maybe->IsFailure()) return maybe;
   return this;
 }
 
 
 int JSObject::GetIdentityHash(Handle<JSObject> obj) {
   CALL_AND_RETRY(obj->GetIsolate(),
                  obj->GetIdentityHash(ALLOW_CREATION),
@@ skipping 34 matching lines @@
 Object* JSObject::GetHiddenProperty(String* key) {
   if (IsJSGlobalProxy()) {
     // For a proxy, use the prototype as target object.
     Object* proxy_parent = GetPrototype();
     // If the proxy is detached, return undefined.
     if (proxy_parent->IsNull()) return GetHeap()->undefined_value();
     ASSERT(proxy_parent->IsJSGlobalObject());
     return JSObject::cast(proxy_parent)->GetHiddenProperty(key);
   }
   ASSERT(!IsJSGlobalProxy());
-  MaybeObject* hidden_lookup = GetHiddenPropertiesDictionary(false);
+  MaybeObject* hidden_lookup = GetHiddenPropertiesHashTable(false);

[Toon Verwaest, 2012/07/30 09:13:23]

Can we make an enum out of the bool argument?

   ASSERT(!hidden_lookup->IsFailure());  // No failure when passing false as arg.
+  Object* inline_value = hidden_lookup->ToObjectUnchecked();
+
+  if (inline_value->IsSmi()) {
+    // Handle inline-stored identity hash.
+    if (key == GetHeap()->identity_hash_symbol()) {
+      return inline_value;
+    } else {
+      return GetHeap()->undefined_value();
+    }
+  }
+
   if (hidden_lookup->ToObjectUnchecked()->IsUndefined()) {

[Toon Verwaest, 2012/07/30 09:13:23]

Replace hidden_lookup->ToObjectUnchecked() by inline_value.

     return GetHeap()->undefined_value();
   }
-  StringDictionary* dictionary =
-      StringDictionary::cast(hidden_lookup->ToObjectUnchecked());
-  int entry = dictionary->FindEntry(key);
-  if (entry == StringDictionary::kNotFound) return GetHeap()->undefined_value();
-  return dictionary->ValueAt(entry);
+
+  ObjectHashTable* hashtable =
+      ObjectHashTable::cast(hidden_lookup->ToObjectUnchecked());

[Toon Verwaest, 2012/07/30 09:13:23]

Replace hidden_lookup->ToObjectUnchecked() by inline_value.

+  Object* entry = hashtable->Lookup(key);

[Toon Verwaest, 2012/07/30 09:13:23]

The API for hidden values does not convert strings as keys for hidden values to
symbols. The StringDictionary handles normal strings in addition to symbols,
while ObjectHashTable does not. We should probably convert all keys from the API
to symbols to ensure we don't break the API.

+  if (entry->IsTheHole()) return GetHeap()->undefined_value();
+  return entry;
 }
 
 
 Handle<Object> JSObject::SetHiddenProperty(Handle<JSObject> obj,
                                  Handle<String> key,
                                  Handle<Object> value) {
   CALL_HEAP_FUNCTION(obj->GetIsolate(),
                      obj->SetHiddenProperty(*key, *value),
                      Object);
 }
 
 
 MaybeObject* JSObject::SetHiddenProperty(String* key, Object* value) {
   if (IsJSGlobalProxy()) {
     // For a proxy, use the prototype as target object.
     Object* proxy_parent = GetPrototype();
     // If the proxy is detached, return undefined.
     if (proxy_parent->IsNull()) return GetHeap()->undefined_value();
     ASSERT(proxy_parent->IsJSGlobalObject());
     return JSObject::cast(proxy_parent)->SetHiddenProperty(key, value);
   }
   ASSERT(!IsJSGlobalProxy());
-  MaybeObject* hidden_lookup = GetHiddenPropertiesDictionary(true);
-  StringDictionary* dictionary;
-  if (!hidden_lookup->To<StringDictionary>(&dictionary)) return hidden_lookup;
+
+  // If there is no backing store yet, store the identity hash inline.
+  MaybeObject* hidden_lookup = GetHiddenPropertiesHashTable(false);
+  ASSERT(!hidden_lookup->IsFailure());
+  Object* inline_value = hidden_lookup->ToObjectUnchecked();
+
+  if (value->IsSmi() &&
+      key == GetHeap()->identity_hash_symbol() &&
+      (inline_value->IsUndefined() || inline_value->IsSmi())) {
+    return SetHiddenPropertiesHashTable(value);
+  }
+
+  hidden_lookup = GetHiddenPropertiesHashTable(true);
+  ObjectHashTable* hashtable;
+  if (!hidden_lookup->To<ObjectHashTable>(&hashtable)) return hidden_lookup;

[Toon Verwaest, 2012/07/30 09:13:23]

You don't need the <ObjectHashTable> afaik.

 
   // If it was found, check if the key is already in the dictionary.
-  int entry = dictionary->FindEntry(key);
-  if (entry != StringDictionary::kNotFound) {
-    // If key was found, just update the value.
-    dictionary->ValueAtPut(entry, value);
-    return this;
-  }
-  // Key was not already in the dictionary, so add the entry.
-  MaybeObject* insert_result = dictionary->Add(key,
-                                               value,
-                                               PropertyDetails(NONE, NORMAL));
-  StringDictionary* new_dict;
-  if (!insert_result->To<StringDictionary>(&new_dict)) return insert_result;
-  if (new_dict != dictionary) {
+  MaybeObject* insert_result = hashtable->Put(key, value);
+  ObjectHashTable* new_table;
+  if (!insert_result->To<ObjectHashTable>(&new_table)) return insert_result;

[Toon Verwaest, 2012/07/30 09:13:24]

Don't need the <ObjectHashTable>.

+  if (new_table != hashtable) {
     // If adding the key expanded the dictionary (i.e., Add returned a new
     // dictionary), store it back to the object.
-    MaybeObject* store_result = SetHiddenPropertiesDictionary(new_dict);
+    MaybeObject* store_result = SetHiddenPropertiesHashTable(new_table);
     if (store_result->IsFailure()) return store_result;
   }
   // Return this to mark success.
   return this;
 }
 
 
 void JSObject::DeleteHiddenProperty(String* key) {
   if (IsJSGlobalProxy()) {
     // For a proxy, use the prototype as target object.
     Object* proxy_parent = GetPrototype();
     // If the proxy is detached, return immediately.
     if (proxy_parent->IsNull()) return;
     ASSERT(proxy_parent->IsJSGlobalObject());
     JSObject::cast(proxy_parent)->DeleteHiddenProperty(key);
     return;
   }
-  MaybeObject* hidden_lookup = GetHiddenPropertiesDictionary(false);
+  MaybeObject* hidden_lookup = GetHiddenPropertiesHashTable(false);
   ASSERT(!hidden_lookup->IsFailure());  // No failure when passing false as arg.
   if (hidden_lookup->ToObjectUnchecked()->IsUndefined()) return;
-  StringDictionary* dictionary =
-      StringDictionary::cast(hidden_lookup->ToObjectUnchecked());
-  int entry = dictionary->FindEntry(key);
-  if (entry == StringDictionary::kNotFound) {
-    // Key wasn't in dictionary. Deletion is a success.
-    return;
-  }
-  // Key was in the dictionary. Remove it.
-  dictionary->DeleteProperty(entry, JSReceiver::FORCE_DELETION);
+  // We never delete (inline-stored) identity hashes.
+  ASSERT(!hidden_lookup->ToObjectUnchecked()->IsSmi());
+
+  ObjectHashTable* hashtable =
+      ObjectHashTable::cast(hidden_lookup->ToObjectUnchecked());
+  MaybeObject* delete_result = hashtable->Put(key, GetHeap()->the_hole_value());
+  ASSERT(!delete_result->IsFailure());  // Delete does not cause GC.
 }
 
 
 bool JSObject::HasHiddenProperties() {
   return GetPropertyAttributePostInterceptor(this,
                                              GetHeap()->hidden_symbol(),
                                              false) != ABSENT;
 }
 
 
-MaybeObject* JSObject::GetHiddenPropertiesDictionary(bool create_if_absent) {
+MaybeObject* JSObject::GetHiddenPropertiesHashTable(bool create_if_absent) {
   ASSERT(!IsJSGlobalProxy());
+  Object* inline_value;
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
       ASSERT(descriptors->GetType(0) == FIELD);
-      Object* hidden_store =
-          this->FastPropertyAt(descriptors->GetFieldIndex(0));
-      return StringDictionary::cast(hidden_store);
+      inline_value = this->FastPropertyAt(descriptors->GetFieldIndex(0));
+    } else {
+      inline_value = GetHeap()->undefined_value();
     }
   } else {
     PropertyAttributes attributes;
     // You can't install a getter on a property indexed by the hidden symbol,
     // so we can be sure that GetLocalPropertyPostInterceptor returns a real
     // object.
-    Object* lookup =
+    inline_value =
         GetLocalPropertyPostInterceptor(this,
                                         GetHeap()->hidden_symbol(),
                                         &attributes)->ToObjectUnchecked();
-    if (!lookup->IsUndefined()) {
-      return StringDictionary::cast(lookup);
-    }
   }
-  if (!create_if_absent) return GetHeap()->undefined_value();
-  const int kInitialSize = 5;
-  MaybeObject* dict_alloc = StringDictionary::Allocate(kInitialSize);
-  StringDictionary* dictionary;
-  if (!dict_alloc->To<StringDictionary>(&dictionary)) return dict_alloc;
+
+  if (!create_if_absent || inline_value->IsHashTable()) return inline_value;
+
+  ObjectHashTable* hashtable;
+  static const int kInitialCapacity = 4;
+  { MaybeObject* maybe_obj = ObjectHashTable::Allocate(kInitialCapacity, true);
+    if (!maybe_obj->To<ObjectHashTable>(&hashtable)) return maybe_obj;
+  }

[Toon Verwaest, 2012/07/30 09:13:24]

Please remove the { ... } around the MaybeObject. That's unnecessary; and we're
slowly removing it everywhere.

+
+  if (inline_value->IsSmi()) {
+    // We were storing the identity hash inline and now allocated an actual
+    // dictionary.  Put the identity hash into the new dictionary.
+    MaybeObject* insert_result =
+        hashtable->Put(GetHeap()->identity_hash_symbol(), inline_value);
+    ObjectHashTable* new_table;
+    if (!insert_result->To<ObjectHashTable>(&new_table)) return insert_result;

[Toon Verwaest, 2012/07/30 09:13:24]

Remove the <ObjectHashTable>

+    // We expect no resizing for the first insert.
+    ASSERT_EQ(hashtable, new_table);
+  }
+
   MaybeObject* store_result =
       SetPropertyPostInterceptor(GetHeap()->hidden_symbol(),
-                                 dictionary,
+                                 hashtable,
                                  DONT_ENUM,
                                  kNonStrictMode,
                                  OMIT_EXTENSIBILITY_CHECK);
   if (store_result->IsFailure()) return store_result;
-  return dictionary;
+  return hashtable;
 }
 
 
-MaybeObject* JSObject::SetHiddenPropertiesDictionary(
-    StringDictionary* dictionary) {
+MaybeObject* JSObject::SetHiddenPropertiesHashTable(
+    Object* hidden) {

[Toon Verwaest, 2012/07/30 09:13:24]

Can we rename hidden to hidden_properties or so? Put it on one line if it fits.

   ASSERT(!IsJSGlobalProxy());
-  ASSERT(HasHiddenProperties());
+  ASSERT(HasHiddenProperties() || hidden->IsSmi());
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
       ASSERT(descriptors->GetType(0) == FIELD);
-      this->FastPropertyAtPut(descriptors->GetFieldIndex(0), dictionary);
+      this->FastPropertyAtPut(descriptors->GetFieldIndex(0), hidden);
       return this;
     }
   }
   MaybeObject* store_result =
       SetPropertyPostInterceptor(GetHeap()->hidden_symbol(),
-                                 dictionary,
+                                 hidden,
                                  DONT_ENUM,
                                  kNonStrictMode,
                                  OMIT_EXTENSIBILITY_CHECK);
   if (store_result->IsFailure()) return store_result;
   return this;
 }
 
 
 MaybeObject* JSObject::DeletePropertyPostInterceptor(String* name,
                                                      DeleteMode mode) {
@@ skipping 7305 matching lines @@
 template<typename Shape, typename Key>
 void HashTable<Shape, Key>::IterateElements(ObjectVisitor* v) {
   IteratePointers(v,
                   kElementsStartOffset,
                   kHeaderSize + length() * kPointerSize);
 }
 
 
 template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::Allocate(int at_least_space_for,
+                                             bool force_capacity,

[Toon Verwaest, 2012/07/30 09:13:24]

Please use an enum.

                                              PretenureFlag pretenure) {
-  int capacity = ComputeCapacity(at_least_space_for);
+  ASSERT(!force_capacity || IS_POWER_OF_TWO(at_least_space_for));
+  int capacity = force_capacity ? at_least_space_for
+                                : ComputeCapacity(at_least_space_for);
   if (capacity > HashTable::kMaxCapacity) {
     return Failure::OutOfMemoryException();
   }
 
   Object* obj;
   { MaybeObject* maybe_obj = Isolate::Current()->heap()->
         AllocateHashTable(EntryToIndex(capacity), pretenure);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   HashTable::cast(obj)->SetNumberOfElements(0);
@@ skipping 88 matching lines @@
   if (nod <= (capacity - nof) >> 1) {
     int needed_free = nof >> 1;
     if (nof + needed_free <= capacity) return this;
   }
 
   const int kMinCapacityForPretenure = 256;
   bool pretenure =
       (capacity > kMinCapacityForPretenure) && !GetHeap()->InNewSpace(this);
   Object* obj;
   { MaybeObject* maybe_obj =
-        Allocate(nof * 2, pretenure ? TENURED : NOT_TENURED);
+        Allocate(nof * 2, false, pretenure ? TENURED : NOT_TENURED);

[Toon Verwaest, 2012/07/30 09:13:24]

enum.

     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
 
   return Rehash(HashTable::cast(obj), key);
 }
 
 
 template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::Shrink(Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements();
 
   // Shrink to fit the number of elements if only a quarter of the
   // capacity is filled with elements.
   if (nof > (capacity >> 2)) return this;
   // Allocate a new dictionary with room for at least the current
   // number of elements. The allocation method will make sure that
   // there is extra room in the dictionary for additions. Don't go
   // lower than room for 16 elements.
   int at_least_room_for = nof;
   if (at_least_room_for < 16) return this;
 
   const int kMinCapacityForPretenure = 256;
   bool pretenure =
       (at_least_room_for > kMinCapacityForPretenure) &&
       !GetHeap()->InNewSpace(this);
   Object* obj;
   { MaybeObject* maybe_obj =
-        Allocate(at_least_room_for, pretenure ? TENURED : NOT_TENURED);
+        Allocate(at_least_room_for, false, pretenure ? TENURED : NOT_TENURED);

[Toon Verwaest, 2012/07/30 09:13:24]

enum.

     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
 
   return Rehash(HashTable::cast(obj), key);
 }
 
 
 template<typename Shape, typename Key>
 uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
   uint32_t capacity = Capacity();
@@ skipping 1929 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal