Optimize VM JSON parser for memory use.

runtime/lib/convert_patch.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // 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.
 
 patch _parseJson(String json, reviver(var key, var value)) {
   _BuildJsonListener listener;
   if (reviver == null) {
     listener = new _BuildJsonListener();
   } else {
     listener = new _ReviverJsonListener(reviver);
   }
@@ skipping 35 matching lines @@
    * started. If the container is a [Map], there is also a current [key]
    * which is also stored on the stack.
    */
   List stack = [];
   /** The current [Map] or [List] being built. */
   var currentContainer;
   /** The most recently read property key. */
   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);
   }
 
   /** Pops the top container from the [stack], including a key if applicable. */
   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; }
   void handleNumber(num value) { this.value = value; }
   void handleBool(bool value) { this.value = value; }
   void handleNull() { this.value = null; }
 
   void beginObject() {
     pushContainer();
-    currentContainer = {};
+    currentContainer = new _JsonObjectBuilder(staticCache);
   }
 
   void propertyName() {
     key = value;
     value = null;
   }
 
   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();
   }
 
   void beginArray() {
     pushContainer();
     currentContainer = [];
   }
 
   void arrayElement() {
     List list = currentContainer;
     currentContainer.add(value);
     value = null;
   }
 
   void endArray() {
     popContainer();
   }
 
   /** 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;
   }
 }
 
 class _ReviverJsonListener extends _BuildJsonListener {
   final _Reviver reviver;
   _ReviverJsonListener(reviver(key, value)) : this.reviver = reviver;
 
   void arrayElement() {
     List list = currentContainer;
     value = reviver(list.length, value);
     super.arrayElement();
   }
 
   void propertyValue() {
     value = reviver(key, value);
     super.propertyValue();
   }
 
   get result {
     return reviver(null, value);
   }
 }
 
 class _JsonParser {
   // A simple non-recursive state-based parser for JSON.
   //
   // 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
   // ARRAY_COMMA      X      X                   -> ARRAY_VALUE
   // OBJECT_EMPTY            X          @        -> OBJECT_KEY / pop
   // OBJECT_KEY                   @              -> OBJECT_COLON
   // OBJECT_COLON     X      X                   -> OBJECT_VALUE
   // OBJECT_VALUE                    @  @        -> OBJECT_COMMA / pop
   // OBJECT_COMMA            X                   -> OBJECT_KEY
   // END
@@ skipping 392 matching lines @@
     int sliceEnd = position + 20;
     if (sliceEnd > source.length) {
       slice = "'${source.substring(position)}'";
     } else {
       slice = "'${source.substring(position, sliceEnd)}...'";
     }
     throw new FormatException("Unexpected character at $position: $slice");
   }
 }
 
+/*
+ * 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 {
   /* patch */ static List<int> _createBuffer(int size) => new Uint8List(size);
 }