Serializer: cache recent back references for shorter encoding.

src/serialize.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_SERIALIZE_H_
 #define V8_SERIALIZE_H_
 
 #include "src/compiler.h"
 #include "src/hashmap.h"
 #include "src/heap-profiler.h"
@@ skipping 267 matching lines @@
     Add(string, BackReference::SourceReference());
   }
 
  private:
   DisallowHeapAllocation no_allocation_;
   HashMap* map_;
   DISALLOW_COPY_AND_ASSIGN(BackReferenceMap);
 };
 
 
+class HotObjectsList {
+ public:
+  HotObjectsList() : index_(0) {
+    for (int i = 0; i < kSize; i++) circular_queue_[i] = NULL;
+  }
+
+  void Add(HeapObject* object) {
+    circular_queue_[index_] = object;
+    index_ = (index_ + 1) & kSizeMask;
+  }
+
+  HeapObject* Get(int index) {
+    DCHECK_NE(NULL, circular_queue_[index]);
+    return circular_queue_[index];
+  }
+
+  static const int kNotFound = -1;
+
+  int Find(HeapObject* object) {
+    for (int i = 0; i < kSize; i++) {
+      if (circular_queue_[i] == object) return i;
+    }
+    return kNotFound;
+  }
+
+  static const int kSize = 8;
+
+ private:
+  STATIC_ASSERT(IS_POWER_OF_TWO(kSize));
+  static const int kSizeMask = kSize - 1;
+  HeapObject* circular_queue_[kSize];
+  int index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HotObjectsList);
+};
+
+
 // The Serializer/Deserializer class is a common superclass for Serializer and
 // Deserializer which is used to store common constants and methods used by
 // both.
 class SerializerDeserializer: public ObjectVisitor {
  public:
   static void Iterate(Isolate* isolate, ObjectVisitor* visitor);
 
   static int nop() { return kNop; }
 
   // No reservation for large object space necessary.
   static const int kNumberOfPreallocatedSpaces = LO_SPACE;
   static const int kNumberOfSpaces = LAST_SPACE + 1;
 
  protected:
   // Where the pointed-to object can be found:
   enum Where {
     kNewObject = 0,  //              Object is next in snapshot.
     // 1-7                           One per space.
+    // 0x8                           Unused.
     kRootArray = 0x9,             // Object is found in root array.
     kPartialSnapshotCache = 0xa,  // Object is in the cache.
     kExternalReference = 0xb,     // Pointer to an external reference.
     kSkip = 0xc,                  // Skip n bytes.
     kBuiltin = 0xd,               // Builtin code object.
     kAttachedReference = 0xe,     // Object is described in an attached list.
     // 0xf                           Used by misc. See below.
     kBackref = 0x10,  //             Object is described relative to end.
     // 0x11-0x17                     One per space.
     kBackrefWithSkip = 0x18,  //     Object is described relative to end.
@@ skipping 23 matching lines @@
     kInnerPointer = 0x80,  // First insn in code object or payload of cell.
     kWhereToPointMask = 0x80
   };
 
   // Misc.
   // Raw data to be copied from the snapshot.  This byte code does not advance
   // the current pointer, which is used for code objects, where we write the
   // entire code in one memcpy, then fix up stuff with kSkip and other byte
   // codes that overwrite data.
   static const int kRawData = 0x20;
-  // Some common raw lengths: 0x21-0x3f.  These autoadvance the current pointer.
+  // Some common raw lengths: 0x21-0x3f.
+  // These autoadvance the current pointer.
+  static const int kOnePointerRawData = 0x21;
+
+  static const int kVariableRepeat = 0x60;
+  // 0x61-0x6f   Repeat last word
+  static const int kFixedRepeat = 0x61;
+  static const int kFixedRepeatBase = kFixedRepeat - 1;
+  static const int kLastFixedRepeat = 0x6f;
+  static const int kMaxFixedRepeats = kLastFixedRepeat - kFixedRepeatBase;
+  static int CodeForRepeats(int repeats) {
+    DCHECK(repeats >= 1 && repeats <= kMaxFixedRepeats);
+    return kFixedRepeatBase + repeats;
+  }
+  static int RepeatsForCode(int byte_code) {
+    DCHECK(byte_code > kFixedRepeatBase && byte_code <= kLastFixedRepeat);
+    return byte_code - kFixedRepeatBase;
+  }
+
+  // Hot objects are a small set of recently seen or back-referenced objects.
+  // They are represented by a single opcode to save space.
+  // We use 0x70..0x77 for 8 hot objects, and 0x78..0x7f to add skip.
+  static const int kHotObject = 0x70;
+  static const int kMaxHotObjectIndex = 0x77 - kHotObject;
+  static const int kHotObjectWithSkip = 0x78;
+  STATIC_ASSERT(HotObjectsList::kSize == kMaxHotObjectIndex + 1);
+  STATIC_ASSERT(0x7f - kHotObjectWithSkip == kMaxHotObjectIndex);
+  static const int kHotObjectIndexMask = 0x7;
+
+  static const int kRootArrayConstants = 0xa0;
+  // 0xa0-0xbf  Things from the first 32 elements of the root array.
+  static const int kRootArrayNumberOfConstantEncodings = 0x20;
+  static int RootArrayConstantFromByteCode(int byte_code) {
+    return byte_code & 0x1f;
+  }
+
+  // Do nothing, used for padding.
+  static const int kNop = 0xf;
+
+  // Move to next reserved chunk.
+  static const int kNextChunk = 0x4f;
+
   // A tag emitted at strategic points in the snapshot to delineate sections.
   // If the deserializer does not find these at the expected moments then it
   // is an indication that the snapshot and the VM do not fit together.
   // Examine the build process for architecture, version or configuration
   // mismatches.
-  static const int kSynchronize = 0x70;
+  static const int kSynchronize = 0x8f;
+
   // Used for the source code of the natives, which is in the executable, but
   // is referred to from external strings in the snapshot.
-  static const int kNativesStringResource = 0x71;
-  static const int kRepeat = 0x72;
-  static const int kConstantRepeat = 0x73;
-  // 0x73-0x7f            Repeat last word (subtract 0x72 to get the count).
-  static const int kMaxRepeats = 0x7f - 0x72;
-  static int CodeForRepeats(int repeats) {
-    DCHECK(repeats >= 1 && repeats <= kMaxRepeats);
-    return 0x72 + repeats;
-  }
-  static int RepeatsForCode(int byte_code) {
-    DCHECK(byte_code >= kConstantRepeat && byte_code <= 0x7f);
-    return byte_code - 0x72;
-  }
-  static const int kRootArrayConstants = 0xa0;
-  // 0xa0-0xbf            Things from the first 32 elements of the root array.
-  static const int kRootArrayNumberOfConstantEncodings = 0x20;
-  static int RootArrayConstantFromByteCode(int byte_code) {
-    return byte_code & 0x1f;
-  }
-
-  static const int kNop = 0xf;  // Do nothing, used for padding.
-
-  static const int kNextChunk = 0x4f;  // Move to next reserved chunk.
+  static const int kNativesStringResource = 0xcf;
 
   static const int kAnyOldSpace = -1;
 
   // A bitmask for getting the space out of an instruction.
   static const int kSpaceMask = 7;
   STATIC_ASSERT(kNumberOfSpaces <= kSpaceMask + 1);
 
   // Sentinel after a new object to indicate that double alignment is needed.
   static const int kDoubleAlignmentSentinel = 0;
+
+  // Used as index for the attached reference representing the source object.
+  static const int kSourceObjectReference = 0;
+
+  HotObjectsList hot_objects_;
 };
 
 
 // A Deserializer reads a snapshot and reconstructs the Object graph it defines.
 class Deserializer: public SerializerDeserializer {
  public:
   // Create a deserializer from a snapshot byte source.
   explicit Deserializer(SnapshotByteSource* source);
 
   virtual ~Deserializer();
@@ skipping 42 matching lines @@
   // of the object we are writing into, or NULL if we are not writing into an
   // object, i.e. if we are writing a series of tagged values that are not on
   // the heap.
   void ReadData(Object** start, Object** end, int space,
                 Address object_address);
   void ReadObject(int space_number, Object** write_back);
   Address Allocate(int space_index, int size);
 
   // Special handling for serialized code like hooking up internalized strings.
   HeapObject* ProcessNewObjectFromSerializedCode(HeapObject* obj);
-  Object* ProcessBackRefInSerializedCode(Object* obj);
 
   // This returns the address of an object that has been described in the
   // snapshot by chunk index and offset.
-  HeapObject* GetBackReferencedObject(int space) {
-    if (space == LO_SPACE) {
-      uint32_t index = source_->GetInt();
-      return deserialized_large_objects_[index];
-    } else {
-      BackReference back_reference(source_->GetInt());
-      DCHECK(space < kNumberOfPreallocatedSpaces);
-      uint32_t chunk_index = back_reference.chunk_index();
-      DCHECK_LE(chunk_index, current_chunk_[space]);
-      uint32_t chunk_offset = back_reference.chunk_offset();
-      return HeapObject::FromAddress(reservations_[space][chunk_index].start +
-                                     chunk_offset);
-    }
-  }
+  HeapObject* GetBackReferencedObject(int space);
 
   // Cached current isolate.
   Isolate* isolate_;
 
   // Objects from the attached object descriptions in the serialized user code.
   Vector<Handle<Object> >* attached_objects_;
 
   SnapshotByteSource* source_;
   // The address of the next object that will be allocated in each space.
   // Each space has a number of chunks reserved by the GC, with each chunk
@@ skipping 89 matching lines @@
     bool code_object_;
     bool code_has_been_output_;
   };
 
   virtual void SerializeObject(HeapObject* o, HowToCode how_to_code,
                                WhereToPoint where_to_point, int skip) = 0;
 
   void PutRoot(int index, HeapObject* object, HowToCode how, WhereToPoint where,
                int skip);
 
-  void SerializeBackReference(BackReference back_reference,
-                              HowToCode how_to_code,
-                              WhereToPoint where_to_point, int skip);
+  // Returns true if the object was successfully serialized.
+  bool SerializeKnownObject(HeapObject* obj, HowToCode how_to_code,
+                            WhereToPoint where_to_point, int skip);
+
+  inline void FlushSkip(int skip) {
+    if (skip != 0) {
+      sink_->Put(kSkip, "SkipFromSerializeObject");
+      sink_->PutInt(skip, "SkipDistanceFromSerializeObject");
+    }
+  }
+
   void InitializeAllocators();
   // This will return the space for an object.
   static AllocationSpace SpaceOfObject(HeapObject* object);
   BackReference AllocateLargeObject(int size);
   BackReference Allocate(AllocationSpace space, int size);
   int EncodeExternalReference(Address addr) {
     return external_reference_encoder_->Encode(addr);
   }
 
   // GetInt reads 4 bytes at once, requiring padding at the end.
@@ skipping 117 matching lines @@
 class CodeSerializer : public Serializer {
  public:
   static ScriptData* Serialize(Isolate* isolate,
                                Handle<SharedFunctionInfo> info,
                                Handle<String> source);
 
   MUST_USE_RESULT static MaybeHandle<SharedFunctionInfo> Deserialize(
       Isolate* isolate, ScriptData* cached_data, Handle<String> source);
 
   static const int kSourceObjectIndex = 0;
+  STATIC_ASSERT(kSourceObjectReference == kSourceObjectIndex);
+
   static const int kCodeStubsBaseIndex = 1;
 
   String* source() const {
     DCHECK(!AllowHeapAllocation::IsAllowed());
     return source_;
   }
 
   List<uint32_t>* stub_keys() { return &stub_keys_; }
   int num_internalized_strings() const { return num_internalized_strings_; }
 
@@ skipping 139 matching lines @@
   // Following the header, we store, in sequential order
   // - code stub keys
   // - serialization payload
 
   ScriptData* script_data_;
   bool owns_script_data_;
 };
 } }  // namespace v8::internal
 
 #endif  // V8_SERIALIZE_H_