Optimize VM JSON parser for memory use.

runtime/lib/convert_patch.dart

Index: runtime/lib/convert_patch.dart
diff --git a/runtime/lib/convert_patch.dart b/runtime/lib/convert_patch.dart
index 93da46140cb3fac8b3477af430d4d278bd61a3d0..731fc022b08d20698862173f865320b01287930d 100644
--- a/runtime/lib/convert_patch.dart
+++ b/runtime/lib/convert_patch.dart
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 
 import "dart:typed_data";
+import "dart:collection" show HashMap, LinkedHashMap, Maps, IterableBase;
+import "dart:_internal" show SubListIterable, EfficientLength;
 
 // JSON conversion.
 
@@ -58,10 +60,19 @@ class _BuildJsonListener extends _JsonListener {
   String key;
   /** The most recently read value. */
   var value;
+  /** Cache for reusable hidden classes of objects. Start out in multi-mode. */
+  static _JsonTransitionMap staticCache =
+      new _JsonMultiTransitionMap(const _JsonHiddenClass.empty(),
+                                  new HashMap());
+  // Counts how many transitions have been added to the cache.
+  // Cache is cleared when reaching the max size.
+  static int staticCacheSize = 0;
+  static const int MAX_STATIC_CACHE_SIZE = 512;
 
   /** Pushes the currently active container (and key, if a [Map]). */
   void pushContainer() {
-    if (currentContainer is Map) stack.add(key);
+    if (key != null)

[srdjan, 2014/03/03 15:12:54]

Curly braces missing?

[floitsch, 2014/03/03 15:36:44]

something's not right here.

+    if (currentContainer is _JsonObjectBuilder) stack.add(key);
     stack.add(currentContainer);
   }
 
@@ -69,7 +80,7 @@ class _BuildJsonListener extends _JsonListener {
   void popContainer() {
     value = currentContainer;
     currentContainer = stack.removeLast();
-    if (currentContainer is Map) key = stack.removeLast();
+    if (currentContainer is _JsonObjectBuilder) key = stack.removeLast();
   }
 
   void handleString(String value) { this.value = value; }
@@ -79,7 +90,7 @@ class _BuildJsonListener extends _JsonListener {
 
   void beginObject() {
     pushContainer();
-    currentContainer = {};
+    currentContainer = new _JsonObjectBuilder(staticCache);
   }
 
   void propertyName() {
@@ -88,12 +99,15 @@ class _BuildJsonListener extends _JsonListener {
   }
 
   void propertyValue() {
-    Map map = currentContainer;
-    map[key] = value;
+    _JsonObjectBuilder builder = currentContainer;
+    builder.add(key, value);
     key = value = null;
   }
 
   void endObject() {
+    _JsonObjectBuilder builder = currentContainer;
+    currentContainer = builder.toMap();
+    staticCacheSize += builder.transitionsAdded;
     popContainer();
   }
 
@@ -115,6 +129,11 @@ class _BuildJsonListener extends _JsonListener {
   /** Read out the final result of parsing a JSON string. */
   get result {
     assert(currentContainer == null);
+    if (staticCacheSize > MAX_STATIC_CACHE_SIZE) {
+      _JsonMultiTransitionMap cache = staticCache;
+      cache.mapping.clear();
+      staticCacheSize = 0;
+    }
     return value;
   }
 }
@@ -144,7 +163,7 @@ class _JsonParser {
   //
   // Literal values accepted in states ARRAY_EMPTY, ARRAY_COMMA, OBJECT_COLON
   // and strings also in OBJECT_EMPTY, OBJECT_COMMA.
-  //               VALUE  STRING  :  ,  }  ]        Transitions to
+  //               VALUE  STRING  :  ,  }  ]        f to

[srdjan, 2014/03/03 15:12:54]

?

[floitsch, 2014/03/03 15:36:44]

?

   // EMPTY            X      X                   -> END
   // ARRAY_EMPTY      X      X             @     -> ARRAY_VALUE / pop
   // ARRAY_VALUE                     @     @     -> ARRAY_COMMA / pop
@@ -557,6 +576,480 @@ class _JsonParser {
   }
 }
 
+/*
+ * JSON Map
+ *
+ * A map with hidden class structure.
+ *
+ * When building maps, don't use a linked hashmap directly.
+ * Instead use a "hidden class" map that keeps the hash structure
+ * in a separate sharable structure representation, and only the
+ * data in the actual map.
+ * Basically, use a map of string->index, and a list of values,
+ * and share the map between all objects with the same structure.
+ *
+ * JSON maps are expected to preserve order, so the hidden classes
+ * maintain the order of the keys.
+ *
+ * The maps will be a delegating map that points to the hidden class
+ * (itself a "map") except that all modifying operations makes the
+ * hidden class replace itself with a linked hash map.
+ */
+
+/**
+ * A transition cache that shows transitions from one hidden class
+ * to another.
+ */
+class _JsonTransitionMap {
+  _JsonHiddenClass get hiddenClass;
+  /** See if there is a transition from this class with [key] as key. */
+  _JsonTransitionMap lookup(String key);
+  /** Add a new transition from this class to a new one. */
+  _JsonTransitionMap addAlternative(String key, _JsonTransitionMap targetMap);
+  /** Update the transition map that is linked by a given key. */
+  void update(String key, _JsonTransitionMap map);
+}
+
+class _JsonLeafTransitionMap implements _JsonTransitionMap {
+  final _JsonHiddenClass hiddenClass;
+  _JsonLeafTransitionMap(this.hiddenClass);
+  _JsonTransitionMap lookup(String key) => null;
+  _JsonTransitionMap addAlternative(String key, _JsonTransitionMap targetMap) {
+    return new _JsonSingletonTransitionMap(hiddenClass, key, targetMap);
+  }
+  void update(String key, _JsonTransitionMap map) {
+    assert(false);  // Must not be called.
+  }
+}
+
+class _JsonSingletonTransitionMap implements _JsonTransitionMap {
+  final _JsonHiddenClass hiddenClass;
+  final String key;
+  _JsonTransitionMap next;
+  _JsonSingletonTransitionMap(this.hiddenClass, this.key, this.next);
+
+  _JsonTransitionMap lookup(String key) {
+    if (this.key == key) return next;
+    return null;
+  }
+
+  _JsonTransitionMap addAlternative(String key, _JsonTransitionMap targetMap) {
+    Map mapping = new HashMap();
+    mapping[this.key] = next;
+    mapping[key] = targetMap;
+    return new _JsonMultiTransitionMap(hiddenClass, mapping);
+  }
+
+  void update(String key, _JsonTransitionMap map) {
+    assert(this.key == key);
+    next = map;
+  }
+}
+
+class _JsonMultiTransitionMap implements _JsonTransitionMap {
+  final _JsonHiddenClass hiddenClass;
+  final Map mapping;
+  _JsonMultiTransitionMap(this.hiddenClass, this.mapping);
+  _JsonTransitionMap lookup(String key) => mapping[key];
+  _JsonTransitionMap addAlternative(String key, _JsonTransitionMap targetMap) {
+    assert(!mapping.containsKey(key));
+    mapping[key] = targetMap;
+    return this;
+  }
+  void update(String key, _JsonTransitionMap map) {
+    assert(mapping.containsKey(key));
+    mapping[key] = map;
+  }
+}
+
+/**
+ * A JSON Object builder that keeps a hidden class for keys and a list of
+ * values.
+ *
+ * When the object is complete, it can be extracted as a `Map` using `toMap`.
+ *
+ */
+class _JsonObjectBuilder {
+  int transitionsAdded = 0;
+  _JsonTransitionMap parentMap;
+  String previousKey;
+  _JsonTransitionMap currentMap;
+
+  final List values = [];
+
+  _JsonObjectBuilder(this.currentMap);
+
+  Object toMap() {
+    return currentMap.hiddenClass.asMap(values);
+  }
+
+  /**
+   * Add a property to the object being built.
+   *
+   * If the key is already in the object, its value is just overwritten.
+   * Otherwise the hidden class is transitioned to one with the new key
+   * and the result is added at the end.
+   */
+  void add(String key, var value) {
+    int index = currentMap.hiddenClass.lookup(key);
+    if (index >= 0) {
+      values[index] = value;
+    } else {
+      _JsonTransitionMap nextMap = currentMap.lookup(key);
+      if (nextMap == null) {
+        _JsonHiddenClass nextClass = currentMap.hiddenClass.addKey(key);
+        nextMap = new _JsonLeafTransitionMap(nextClass);
+        currentMap = currentMap.addAlternative(key, nextMap);
+        if (parentMap != null) {
+          parentMap.update(previousKey, currentMap);
+        }
+        transitionsAdded++;
+      }
+      parentMap = currentMap;
+      previousKey = key;
+      currentMap = nextMap;
+
+      values.add(value);
+    }
+  }
+}
+
+/**
+ * A "hidden class" is a mapping from string key to integer index.
+ *
+ * A map using a class will have a list of values for each index in the
+ * hidden class.
+ */
+abstract class _JsonHiddenClass {
+  const _JsonHiddenClass();
+  const factory _JsonHiddenClass.empty() = _JsonEmptyHiddenClass;
+  int lookup(String key);
+  Map toMap(List values) {
+    Map map = new LinkedHashMap<String, dynamic>();
+    addToMap(map, values);
+    return map;
+  }
+  Iterator<String> get keyIterator;
+  void addToMap(Map<String,dynamic> map, List values);
+  int get length;
+
+  _JsonHiddenClass addKey(String key);
+
+  Map<String, dynamic> asMap(List values) {
+    return new _JsonHiddenClassMap(this, values).wrapper;
+  }
+}
+
+class _JsonEmptyHiddenClass extends _JsonHiddenClass {
+  const _JsonEmptyHiddenClass();
+  int lookup(String key) => -1;
+  Map toMap(List values) => new LinkedHashMap<String, dynamic>();
+  Iterator<String> get keyIterator => const[];
+  void addToMap(Map map, List values) {}
+  int get length => 0;
+  _JsonHiddenClass addKey(String key) {
+    return new _JsonSmallHiddenClass(<String>[key], 1);
+  }
+}
+
+/**
+ * A hidden class for a JSON object that maps keys to value indices.
+ *
+ * This is intended for small objects. Looking up a key is done using
+ * linear search.
+ */
+class _JsonSmallHiddenClass extends _JsonHiddenClass {
+  final List keys;
+  final int length;  // `keys` may contain more elements than length.

[floitsch, 2014/03/03 15:36:44]

Point to `addKey` where we add a new key for the next SmallHiddenClass.

+  _JsonSmallHiddenClass(this.keys, this.length);
+  int lookup(String key) {
+    for (int i = 0; i < length; i++) {
+      if (keys[i] == key) return i;
+    }
+    return -1;
+  }
+
+  Iterator<String> get keyIterator => keys.take(length).iterator;
+
+  void addToMap(Map map, List values) {
+    for (int i = 0; i < length; i++) {
+      map[keys[i]] = values[i];
+    }
+  }
+
+  _JsonHiddenClass addKey(String key) {
+    const int MAX_SMALL_CLASS = 4;

[floitsch, 2014/03/03 15:36:44]

I would go higher, but that's just my gut-reaction.

+    if (length == MAX_SMALL_CLASS) {
+      Map map = new LinkedHashMap<String,int>();
+      for (int i = 0; i < length; i++) map[keys[i]] = i;
+      map[key] = length;
+      return new _JsonMediumHiddenClass(map, length + 1);
+    }
+    // TODO(lrn): Add an implementation for larger key lists that doesn't use
+    // linear search. Switch to using that implementation here if length is
+    // above a threshold.
+    var newKeys;
+    if (keys.length > length) {
+      newKeys = keys.sublist(0, length);
+    } else {
+      newKeys = keys;

[floitsch, 2014/03/03 15:36:44]

Add comment that we are sharing the list here.

+    }
+    newKeys.add(key);
+    return new _JsonSmallHiddenClass(newKeys, length + 1);
+  }
+}
+
+/**
+ * A hidden class that uses a [LinkedHashMap] to store the key-to-index mapping.
+ *
+ * This introduces the same overhead as a normal map, so if the hidden class
+ * is only used once, it's just an overhead.
+ */
+class _JsonMediumHiddenClass extends _JsonHiddenClass {
+  final LinkedHashMap<String, int> keys;
+  final int length;  // `keys` may contain more elements than length.

[floitsch, 2014/03/03 15:36:44]

ditto. point to `addKey`.

+  _JsonMediumHiddenClass(this.keys, this.length);
+
+  int lookup(String key) {
+    int index = keys[key];
+    if (index == null || index >= length) return -1;
+    return index;
+  }
+
+  Iterator<String> get keyIterator => keys.keys.take(length).iterator;
+
+  void addToMap(Map map, List values) {
+    int i = 0;
+    assert(length != 0);
+    for (String key in keys.keys) {
+      map[key] = values[i];
+      i++;
+      if (i == length) break;
+    }
+  }
+
+  _JsonHiddenClass addKey(String key) {
+    // TODO(lrn): Add an implementation for larger key lists that doesn't use
+    // linear search. Switch to using that implementation here if length is
+    // above a threshold.
+    var newKeys;
+    if (keys.length > length) {
+      newKeys = new HashMap<String,int>();
+      keys.forEach((String key, int value) {
+        if (value < length) newKeys[key] = value;
+      });
+    } else {
+      newKeys = keys;
+    }
+    newKeys[key] = length;
+    return new _JsonMediumHiddenClass(newKeys, length + 1);
+  }
+}
+
+
+/**
+ * A map based on a hidden class.
+ *
+ * The hidden class translates string keys to integer indices, and the
+ * values are stored at those indices in [values].
+ * The idea is that the hidden class can be shared between multiple similar
+ * objects, reducing the memory overhead of the map created by decoding a
+ * JSON Object. This only works when there are more than one object with
+ * the same structure.
+ *
+ * This object is hidden behind the [_JsonMapWrapper].
+ *
+ * Any attempt to write to the map will make it convert itself to a
+ * [LinkedHashMap] with the same values, and make the wrapper delegate to that
+ * map instead.
+ */
+class _JsonHiddenClassMap implements Map {
+  final _JsonHiddenClass hiddenClass;
+  final List mapValues;
+  bool modified = false;
+  _JsonMapWrapper wrapper;
+
+  _JsonHiddenClassMap(this.hiddenClass, this.mapValues) {
+    wrapper = new _JsonMapWrapper(this);
+  }
+
+  Map convertToMap() {
+    modified = true;
+    Map map = hiddenClass.toMap(mapValues);
+    wrapper._delegate = map;
+    return map;
+  }
+
+  bool containsValue(Object value) {
+    for (int i = 0; i < mapValues.length; i++) {
+      if (mapValues[i] == value) return true;
+    }
+    return false;
+  }
+
+  bool containsKey(Object key) => hiddenClass.lookup(key) >= 0;
+
+  operator [](Object key) {
+    int index = hiddenClass.lookup(key);
+    if (index < 0) return null;
+    return mapValues[index];
+  }
+
+  void operator []=(String key, var value) {
+    int index = hiddenClass.lookup(key);
+    if (index >= 0) {
+      mapValues[index] = value;
+    } else {
+      convertToMap()[key] = value;
+    }
+  }
+
+  putIfAbsent(String key, ifAbsent()) {
+    int index = hiddenClass.lookup(key);
+    if (index >= 0) {
+      return mapValues[index];
+    }
+    return convertToMap().putIfAbsent(key, ifAbsent);
+  }
+
+  void addAll(Map<String, dynamic> other) {
+    Iterator values = other.iterator;

[floitsch, 2014/03/03 15:36:44]

Maps don't have iterators.

+    if (!values.moveNext()) returm

[floitsch, 2014/03/03 15:36:44]

You could also just ask, if other.length == 0, convert, and use addAll.

+    Map map = convertToMap();
+    do {
+      map.add(values.current);

[floitsch, 2014/03/03 15:36:44]

map doesn't have "add".

+    } while (values.moveNext());
+  }
+
+  remove(Object key) {
+    int index = hiddenClass.lookup(key);
+    if (index < 0) return null;
+    return convertToMap().remove(key);
+  }
+
+  void clear() {
+    modified = true;
+    wrapper._delegate = new LinkedHashMap<String, dynamic>();
+  }
+
+  void forEach(void f(String key, var value)) {
+    Iterator keys = hiddenClass.keyIterator;
+    for (int i = 0; i < mapValues.length; i++) {
+      keys.moveNext();
+      String key = keys.current;
+      f(key, mapValues[i]);
+      if (modified) throw new ConcurrentModificationError(wrapper);
+    }
+  }
+
+  Iterable<String> get keys => new _JsonHiddenClassMapKeyIterable(this);
+
+  Iterable get valueIterator => new _JsonHiddenClassMapValueIterable(this);
+
+  int get length => mapValues.length;
+
+  bool get isEmpty => mapValues.length == 0;
+
+  bool get isNotEmpty => mapValues.length != 0;
+
+  String toString() => Maps.mapToString(this);
+}
+
+abstract class _JsonHiddenClassMapIterable<T> extends IterableBase<T>
+    implements EfficientLength {
+  _JsonHiddenClassMap _map;
+  _JsonHiddenClassMapIterable(this._map);
+  int get length => _map.length;
+  bool get isEmpty => _map.isEmpty;
+  bool get isNotEmpty => _map.isNotEmpty;
+}
+
+class _JsonHiddenClassMapKeyIterable
+    extends _JsonHiddenClassMapIterable<String> {
+  _JsonHiddenClassMapKeyIterable(_JsonHiddenClassMap map) : super(map);
+  Iterator get iterator => new _JsonHiddenClassMapKeyIterator(_map);
+}
+
+class _JsonHiddenClassMapValueIterable extends _JsonHiddenClassMapIterable {
+  _JsonHiddenClassMapValueIterable(_JsonHiddenClassMap map) : super(map);
+  Iterator get iterator => new _JsonHiddenClassMapValueIterator(_map);
+}
+
+class _JsonHiddenClassMapKeyIterator implements Iterator<String> {
+  Iterator _keys;
+  _JsonHiddenClassMap _map;
+  _JsonHiddenClassMapKeyIterator(_JsonHiddenClassMap map)
+      : _map = map, _keys = map.hiddenClass.keyIterator;
+  bool moveNext() {
+    if (_map.modified) throw new ConcurrentModificationError(_map.wrapper);
+    return _keys.moveNext();
+  }
+  String get current => _keys.current;
+}
+
+class _JsonHiddenClassMapValueIterator implements Iterator {
+  int _index = 0;
+  var _current;
+  _JsonHiddenClassMap _map;
+  _JsonHiddenClassMapKeyIterator(_JsonHiddenClassMap map)
+      : _map = map;
+  bool moveNext() {
+    if (_map.modified) throw new ConcurrentModificationError(_map.wrapper);
+    if (_index == _map.mapValues.length) {
+      _current = false;
+      return false;
+    }
+    _current = _map.mapValues[_index++];
+    return true;
+  }
+  get current => _current;
+}
+
+/**
+ * Delegating map wrapper.
+ *
+ * Used to have a "copy on write" map implementation optimized for reading,

[floitsch, 2014/03/03 15:36:44]

s/Used to have/Has/

+ * which converts itself to a [LinkedHashMap] on any write operation by
+ * creating the hash map and writing it to [_delegate].
+ *
+ * This is the only object that the JSON decoder's user sees.
+ */
+class _JsonMapWrapper implements Map<String, dynamic> {
+  Map _delegate;
+
+  _JsonMapWrapper(this._delegate);
+
+  bool containsValue(Object value) => _delegate.containsValue(value);
+
+  bool containsKey(Object key) => _delegate.containsKey(key);
+
+  operator [](Object key) => _delegate[key];
+
+  void operator []=(String key, var value) { _delegate[key] = value; }
+
+  putIfAbsent(String key, ifAbsent()) => _delegate.putIfAbsent(key, ifAbsent);
+
+  void addAll(Map<String, dynamic> other) => _delegate.addAll(other);
+
+  remove(Object key) => _delegate.remove(key);
+
+  void clear() { _delegate.clear(); }
+
+  void forEach(void f(String key, var value)) { _delegate.forEach(f); }
+
+  Iterable<String> get keys => _delegate.keys;
+
+  Iterable get values => _delegate.values;
+
+  int get length => _delegate.length;
+
+  bool get isEmpty => _delegate.isEmpty;
+
+  bool get isNotEmpty => _delegate.isNotEmpty;
+
+  String toString() => _delegate.toString();
+}
+
 // UTF-8 conversion.
 
 patch class _Utf8Encoder {