Use null instead of undefined for deleted elements in code caches....

src/objects.cc

 // Copyright 2006-2008 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 2361 matching lines @@
   FixedArray* cache = code_cache();
 
   // When updating the code cache we disregard the type encoded in the
   // flags. This allows call constant stubs to overwrite call field
   // stubs, etc.
   Code::Flags flags = Code::RemoveTypeFromFlags(code->flags());
 
   // First check whether we can update existing code cache without
   // extending it.
   int length = cache->length();
+  int deleted_index = -1;
   for (int i = 0; i < length; i += 2) {
     Object* key = cache->get(i);
+    if (key->IsNull()) {
+      if (deleted_index < 0) deleted_index = i;
+      continue;
+    }
     if (key->IsUndefined()) {
+      if (deleted_index > 0) i = deleted_index;

[Kasper Lund, 2008/09/18 10:56:22]

What if deleted_index is 0? Shouldn't you use that slot then? 

       cache->set(i + 0, name);
       cache->set(i + 1, code);
       return this;
     }
     if (name->Equals(String::cast(key))) {
       Code::Flags found = Code::cast(cache->get(i + 1))->flags();
       if (Code::RemoveTypeFromFlags(found) == flags) {
         cache->set(i + 1, code);
         return this;
       }
     }
   }
 
+  // Reached the end of the code cache.  If there were deleted
+  // elements, reuse the space for the first of them.
+  if (deleted_index > 0) {

[Kasper Lund, 2008/09/18 10:56:22]

How about reusing if deleted_index is 0? Isn't that the right thing to do?

+    cache->set(deleted_index + 0, name);
+    cache->set(deleted_index + 1, code);
+    return this;
+  }
+
   // Extend the code cache with some new entries (at least one).
   int new_length = length + ((length >> 1) & ~1) + 2;
   ASSERT((new_length & 1) == 0);  // must be a multiple of two
   Object* result = cache->CopySize(new_length);
   if (result->IsFailure()) return result;
 
   // Add the (name, code) pair to the new cache.
   cache = FixedArray::cast(result);
   cache->set(length + 0, name);
   cache->set(length + 1, code);
   set_code_cache(cache);
   return this;
 }
 
 
 Object* Map::FindInCodeCache(String* name, Code::Flags flags) {
   FixedArray* cache = code_cache();
   int length = cache->length();
   for (int i = 0; i < length; i += 2) {
     Object* key = cache->get(i);
+    if (key->IsNull()) {

[Kasper Lund, 2008/09/18 10:56:22]

Maybe add a comment here that explains that we're skipping deleted entries?

+      continue;
+    }
     if (key->IsUndefined()) {
       return key;
     }
     if (name->Equals(String::cast(key))) {
       Code* code = Code::cast(cache->get(i + 1));
       if (code->flags() == flags) return code;
     }
   }
   return Heap::undefined_value();
 }
 
 
 int Map::IndexInCodeCache(Code* code) {
   FixedArray* array = code_cache();
   int len = array->length();
   for (int i = 0; i < len; i += 2) {
     if (array->get(i + 1) == code) return i + 1;
   }
   return -1;
 }
 
 
 void Map::RemoveFromCodeCache(int index) {
   FixedArray* array = code_cache();
   ASSERT(array->length() >= index && array->get(index)->IsCode());
-  array->set_undefined(index - 1);  // key
-  array->set_undefined(index);  // code
+  array->set_null(index - 1);  // key

[Kasper Lund, 2008/09/18 10:56:22]

Add comment that explains that deleted entries are dealt with specially when
looking up in the cache so they can't be undefined (must be null).

+  array->set_null(index);  // code
 }
 
 
 void FixedArray::FixedArrayIterateBody(ObjectVisitor* v) {
   IteratePointers(v, kHeaderSize, kHeaderSize + length() * kPointerSize);
 }
 
 
 static bool HasKey(FixedArray* array, Object* key) {
   int len0 = array->length();
@@ skipping 3833 matching lines @@
   // No break point.
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 
 
 } }  // namespace v8::internal