Blink-compatible serialization of arrays, both dense and sparse.

src/value-serializer.cc

 // Copyright 2016 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.
 
 #include "src/value-serializer.h"
 
 #include <type_traits>
 
 #include "src/base/logging.h"
 #include "src/factory.h"
@@ skipping 42 matching lines @@
   kDouble = 'N',
   // byteLength:uint32_t, then raw data
   kUtf8String = 'S',
   kTwoByteString = 'c',
   // Reference to a serialized object. objectID:uint32_t
   kObjectReference = '^',
   // Beginning of a JS object.
   kBeginJSObject = 'o',
   // End of a JS object. numProperties:uint32_t
   kEndJSObject = '{',
+  // Beginning of a sparse JS array. length:uint32_t
+  // Elements and properties are written as key/value pairs, like objects.
+  kBeginSparseJSArray = 'a',
+  // End of a sparse JS array. numProperties:uint32_t length:uint32_t
+  kEndSparseJSArray = '@',
+  // Beginning of a dense JS array. length:uint32_t
+  // |length| elements, followed by properties as key/value pairs
+  kBeginDenseJSArray = 'A',
+  // End of a dense JS array. numProperties:uint32_t length:uint32_t
+  kEndDenseJSArray = '$',
 };
 
 ValueSerializer::ValueSerializer(Isolate* isolate)
     : isolate_(isolate),
       zone_(isolate->allocator()),
       id_map_(isolate->heap(), &zone_) {}
 
 ValueSerializer::~ValueSerializer() {}
 
 void ValueSerializer::WriteHeader() {
@@ skipping 173 matching lines @@
   InstanceType instance_type = receiver->map()->instance_type();
   if (receiver->IsCallable() || instance_type <= LAST_SPECIAL_RECEIVER_TYPE) {
     return Nothing<bool>();
   }
 
   // If we are at the end of the stack, abort. This function may recurse.
   if (StackLimitCheck(isolate_).HasOverflowed()) return Nothing<bool>();
 
   HandleScope scope(isolate_);
   switch (instance_type) {
+    case JS_ARRAY_TYPE:
+      return WriteJSArray(Handle<JSArray>::cast(receiver));
     case JS_OBJECT_TYPE:
     case JS_API_OBJECT_TYPE:
       return WriteJSObject(Handle<JSObject>::cast(receiver));
     default:
       UNIMPLEMENTED();
       break;
   }
   return Nothing<bool>();
 }
 
 Maybe<bool> ValueSerializer::WriteJSObject(Handle<JSObject> object) {
   WriteTag(SerializationTag::kBeginJSObject);
   Handle<FixedArray> keys;
   uint32_t properties_written;
   if (!KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,
                                ENUMERABLE_STRINGS)
            .ToHandle(&keys) ||
       !WriteJSObjectProperties(object, keys).To(&properties_written)) {
     return Nothing<bool>();
   }
   WriteTag(SerializationTag::kEndJSObject);
   WriteVarint<uint32_t>(properties_written);
   return Just(true);
 }
 
+Maybe<bool> ValueSerializer::WriteJSArray(Handle<JSArray> array) {
+  uint32_t length;
+  array->length()->ToArrayLength(&length);
+
+  // This currently does not use dense serialization for holey elements, since
+  // the format currently does not provide for properly distinguishing between

[Jakob Kummerow, 2016/08/18 13:49:56]

The deserializer implementation below treats every |undefined| as if it was the
hole, so that's not a reason to skip holey elements here.

However, a holey array can have an arbitrary number of holes in it, so sparse
serialization might be vastly more efficient. Your test cases are examples of
this: "new Array(100000)" gives you a FAST_HOLEY_SMI_ELEMENTS array containing
100K holes, where the sparse serialization would be an empty list of pairs,
whereas the dense serialization would be a very long sequence of "_" tags.

[jbroman, 2016/08/18 15:03:03]

That's fair enough. I'd originally had the deserializer read it as undefined,
before I realized Chrome currently does the opposite.
Sparse serialization is currently used for such cases. (The tests naturally get
noticeably slower if I do not.)

[Jakob Kummerow, 2016/08/18 17:42:28]

Yes, I know.

I meant my review comment as considerations for putting a more accurate comment
into the source (sorry, I should have been clearer about that). I'd write
something like:

// To keep things simple, we decide between dense and sparse serialization
// format based on elements kind: fast packed elements use the dense
// format. A more advanced heuristic could determine the actual array
// density by counting its elements.

[jbroman, 2016/08/18 18:10:11]

Reworded the comment to that effect, and expanded to add detail about what I was
getting at with a bit vector below.

+  // undefined and the hole. Additionally, if holey elements were used, it's
+  // possible that an element which began non-enumerable (by being a hole)
+  // became enumerable (by being assigned to).
+  const bool should_serialize_densely =
+      array->HasFastElements() && !array->HasFastHoleyElements();

[Jakob Kummerow, 2016/08/18 13:49:56]

Given that the array could transition to slow or holey elements at any time,
this is but a crude heuristic...

[jbroman, 2016/08/18 15:03:04]

A more principled heuristic would be used_elements >= length / 4 (because a
missing element takes one byte to encode but an explicit integer key takes 2-5
bytes, say 3 typically, to encode).

Doing this, however, requires explicitly enumerating first the elements first
(in case some are non-enumerable). If there are no holes, it's pretty
convenient, because every element must be enumerable (IIUC, a non-enumerable
element would cause dictionary elements, and a hole would cause holey or
dictionary elements).

A proliferation of fast paths are possible. e.g., for fast holey elements, we
could use a bit vector to record where the holes are, and then if skip indices
that originally had holes; or if there are too many holes we can do a sparse
serialization, but still more efficiently than the slow path, except of course
it still has to have the escape hatch if a getter changes the backing store.

I don't have a good sense for what the typical elements kinds are in practice
(I'd expect that in practice most arrays likely to be serialized are fast
non-holey arrays, but I don't know). This seemed like the quickest way of opting
most stuff into a reasonably fast path without yet going down the road of adding
various fast paths.

[Jakob Kummerow, 2016/08/18 17:42:28]

Yes, something like that. Doing that later (if at all) is fine.
Correct. (For the record: holey arrays can have holes, but no non-enumerable
elements. Only dictionary elements can have the DONT_ENUM flag set.)
You can't precompute/cache much, as everything can change. The bit vector idea,
for that reason, doesn't make much sense to me. Also, comparing elements against
the hole isn't any harder/slower than checking a bit vector's bits.
Hard to say, because that obviously depends a lot on the application. Arrays
with HOLEY elements kinds but no actual holes are probably pretty common too.
Sadly, using the LookupIterator/GetProperty() for every element lookup is not
particularly fast; but at least it's safe so it's a reasonable choice for this
implementation.

[jbroman, 2016/08/18 18:10:11]

I've reworded the comment to (hopefully) be clearer on this point. What I meant
was, indices occupied by holes would not be among the enumerable own property
keys (and so those indices should not be serialized).
Except this thing _should_ be precomputed, per spec. Technically, the own
property names (except for symbols) are enumerated before we begin serializing
any elements. As a result, if a hole is filled in during serialization, that
index should be skipped (at least, per spec and per Firefox's implementation; I
doubt any web content actually relies on this).

Definitely agreed that we have to be careful about precomputation.
It's still faster than what Blink is doing today. :)

+
+  if (should_serialize_densely) {
+    // TODO(jbroman): Take fuller advantage of fast elements.
+    // TODO(jbroman): Distinguish between undefined and a hole (this can happen
+    // if serializing one of the elements deletes another). This requires wire
+    // format changes.
+    WriteTag(SerializationTag::kBeginDenseJSArray);
+    WriteVarint<uint32_t>(length);
+    for (uint32_t i = 0; i < length; i++) {
+      Handle<Object> element;
+      LookupIterator it(isolate_, array, i, array, LookupIterator::OWN);

[Jakob Kummerow, 2016/08/18 13:49:56]

Please add a comment:
// Recursively serializing the array's elements can have arbitrary
// side effects, so we can't rely on still having fast packed elements.

(Otherwise it's surprising that you're not just using "Handle<Object>
element(array->elements()->get(i), isolate_);" here; but doing so would be a
bug. You'd have to be very careful about checking in every iteration that the
backing store hasn't changed.)

[jbroman, 2016/08/18 15:03:04]

Done. That's why I left taking advantage of the elements being fast to a
subsequent CL. (Also, doesn't that require an additional check that it isn't
fast double elements; the elements aren't necessarily a FixedArray, right?)

[Jakob Kummerow, 2016/08/18 17:42:28]

Yes.

+      if (!Object::GetProperty(&it).ToHandle(&element) ||
+          !WriteObject(element).FromMaybe(false)) {
+        return Nothing<bool>();
+      }
+    }
+    KeyAccumulator accumulator(isolate_, KeyCollectionMode::kOwnOnly,
+                               ENUMERABLE_STRINGS);
+    if (!accumulator.CollectOwnPropertyNames(array, array).FromMaybe(false)) {
+      return Nothing<bool>();
+    }
+    Handle<FixedArray> keys =
+        accumulator.GetKeys(GetKeysConversion::kConvertToString);
+    uint32_t properties_written;
+    if (!WriteJSObjectProperties(array, keys).To(&properties_written)) {
+      return Nothing<bool>();
+    }
+    WriteTag(SerializationTag::kEndDenseJSArray);
+    WriteVarint<uint32_t>(properties_written);
+    WriteVarint<uint32_t>(length);

[Jakob Kummerow, 2016/08/18 13:49:56]

Any particular reason why |length| is written twice?

[jbroman, 2016/08/18 15:03:03]

Compatibility with the existing format. Some of this redundancy could certainly
be removed with a revision of the wire format, but if the deserializer wants to
handle existing serialized objects (which may be stored in IndexedDB) it has to
handle this, so for now I've been making the serializer fully compatible.

+  } else {
+    WriteTag(SerializationTag::kBeginSparseJSArray);
+    WriteVarint<uint32_t>(length);
+    Handle<FixedArray> keys;
+    uint32_t properties_written;
+    if (!KeyAccumulator::GetKeys(array, KeyCollectionMode::kOwnOnly,
+                                 ENUMERABLE_STRINGS)
+             .ToHandle(&keys) ||
+        !WriteJSObjectProperties(array, keys).To(&properties_written)) {
+      return Nothing<bool>();
+    }
+    WriteTag(SerializationTag::kEndSparseJSArray);
+    WriteVarint<uint32_t>(properties_written);
+    WriteVarint<uint32_t>(length);
+  }
+  return Just(true);
+}
+
 Maybe<uint32_t> ValueSerializer::WriteJSObjectProperties(
     Handle<JSObject> object, Handle<FixedArray> keys) {
   uint32_t properties_written = 0;
   int length = keys->length();
   for (int i = 0; i < length; i++) {
     Handle<Object> key(keys->get(i), isolate_);
 
     bool success;
     LookupIterator it = LookupIterator::PropertyOrElement(
         isolate_, object, key, &success, LookupIterator::OWN);
@@ skipping 156 matching lines @@
       return ReadUtf8String();
     case SerializationTag::kTwoByteString:
       return ReadTwoByteString();
     case SerializationTag::kObjectReference: {
       uint32_t id;
       if (!ReadVarint<uint32_t>().To(&id)) return MaybeHandle<Object>();
       return GetObjectWithID(id);
     }
     case SerializationTag::kBeginJSObject:
       return ReadJSObject();
+    case SerializationTag::kBeginSparseJSArray:
+      return ReadSparseJSArray();
+    case SerializationTag::kBeginDenseJSArray:
+      return ReadDenseJSArray();
     default:
       return MaybeHandle<Object>();
   }
 }
 
 MaybeHandle<String> ValueDeserializer::ReadUtf8String() {
   uint32_t utf8_length;
   Vector<const uint8_t> utf8_bytes;
   if (!ReadVarint<uint32_t>().To(&utf8_length) ||
       utf8_length >
@@ skipping 43 matching lines @@
            .To(&num_properties) ||
       !ReadVarint<uint32_t>().To(&expected_num_properties) ||
       num_properties != expected_num_properties) {
     return MaybeHandle<JSObject>();
   }
 
   DCHECK(HasObjectWithID(id));
   return scope.CloseAndEscape(object);
 }
 
+MaybeHandle<JSArray> ValueDeserializer::ReadSparseJSArray() {
+  // If we are at the end of the stack, abort. This function may recurse.
+  if (StackLimitCheck(isolate_).HasOverflowed()) return MaybeHandle<JSArray>();
+
+  uint32_t length;
+  if (!ReadVarint<uint32_t>().To(&length)) return MaybeHandle<JSArray>();
+
+  uint32_t id = next_id_++;
+  HandleScope scope(isolate_);
+  Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
+  JSArray::SetLength(array, length);
+  AddObjectWithID(id, array);
+
+  uint32_t num_properties;
+  uint32_t expected_num_properties;
+  uint32_t expected_length;
+  if (!ReadJSObjectProperties(array, SerializationTag::kEndSparseJSArray)
+           .To(&num_properties) ||
+      !ReadVarint<uint32_t>().To(&expected_num_properties) ||
+      !ReadVarint<uint32_t>().To(&expected_length) ||
+      num_properties != expected_num_properties || length != expected_length) {
+    return MaybeHandle<JSArray>();
+  }
+
+  DCHECK(HasObjectWithID(id));
+  return scope.CloseAndEscape(array);
+}
+
+MaybeHandle<JSArray> ValueDeserializer::ReadDenseJSArray() {
+  // If we are at the end of the stack, abort. This function may recurse.
+  if (StackLimitCheck(isolate_).HasOverflowed()) return MaybeHandle<JSArray>();
+
+  uint32_t length;
+  if (!ReadVarint<uint32_t>().To(&length)) return MaybeHandle<JSArray>();
+
+  uint32_t id = next_id_++;
+  HandleScope scope(isolate_);
+  Handle<JSArray> array = isolate_->factory()->NewJSArray(
+      FAST_HOLEY_ELEMENTS, length, length, INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);

[Jakob Kummerow, 2016/08/18 13:49:56]

It's a bit sad that deserialized arrays will always have FAST_HOLEY_ELEMENTS,
but I suppose it's OK for a generic slow path implementation.

[jbroman, 2016/08/18 15:03:03]

Probably logic to use FAST_ELEMENTS if there are no holes could be added later
(though I'd have to figure out the map transitions for that case, as the JSArray
has to be created before we deserialize the elements). Efficiently knowing more
in advance would require wire format changes.

+  AddObjectWithID(id, array);
+
+  Handle<FixedArray> elements(FixedArray::cast(array->elements()), isolate_);
+  for (uint32_t i = 0; i < length; i++) {
+    Handle<Object> element;
+    if (!ReadObject().ToHandle(&element)) return MaybeHandle<JSArray>();
+    // TODO(jbroman): Distinguish between undefined and a hole.
+    if (element->IsUndefined(isolate_)) continue;

[Jakob Kummerow, 2016/08/18 13:49:56]

This is inconsistent with the serializer. Are you sure you want to serialize but
then forget explicitly present but undefined values? Specifically, a
RoundTripTest on "[undefined,undefined]" would return "[<hole>, <hole>]"
currently.

[jbroman, 2016/08/18 15:03:03]

In fact I don't want to, but the existing wire format doesn't provide for
representing holes in the wire format. I intend to add a tag for a hole (as
distinct from undefined) in a future version of the wire format, but indeed
today if you postMessage([undefined,undefined], '*') in Chrome, you will get
[<hole>,<hole>] on the other side. I have to interpret undefined as either
undefined or a hole, so for consistency I've chosen the hole because Chrome does
so today.

[Jakob Kummerow, 2016/08/18 17:42:28]

I'm aware of the wire format's limitation. I was just pointing out the
inconsistency. If that's intentional, fine.

[jbroman, 2016/08/18 18:10:11]

It's unfortunate but intentional, yes.

+    elements->set(i, *element);
+  }
+
+  uint32_t num_properties;
+  uint32_t expected_num_properties;
+  uint32_t expected_length;
+  if (!ReadJSObjectProperties(array, SerializationTag::kEndDenseJSArray)
+           .To(&num_properties) ||
+      !ReadVarint<uint32_t>().To(&expected_num_properties) ||
+      !ReadVarint<uint32_t>().To(&expected_length) ||
+      num_properties != expected_num_properties || length != expected_length) {
+    return MaybeHandle<JSArray>();
+  }
+
+  DCHECK(HasObjectWithID(id));
+  return scope.CloseAndEscape(array);
+}
+
 Maybe<uint32_t> ValueDeserializer::ReadJSObjectProperties(
     Handle<JSObject> object, SerializationTag end_tag) {
   for (uint32_t num_properties = 0;; num_properties++) {
     SerializationTag tag;
     if (!PeekTag().To(&tag)) return Nothing<uint32_t>();
     if (tag == end_tag) {
       ConsumeTag(end_tag);
       return Just(num_properties);
     }
 
@@ skipping 110 matching lines @@
   }
 #endif
   position_ = end_;
 
   if (stack.size() != 1) return MaybeHandle<Object>();
   return scope.CloseAndEscape(stack[0]);
 }
 
 }  // namespace internal
 }  // namespace v8