Optimize VM JSON parser for memory use.

Optimize VM JSON parser for speed and memory use.

Large JSON structures are likely to have many objects with similar structure.
This change keeps the structure separate from the values, and a JSON object
is a map backed by the structure (the "hidden class") and a list of values.
Any modification of the object/map will make it fall back to a linked hash map.

Caching might need tweaking (if we want caching at all).
The hidden class approach does cause an overhead for unstructured data, but
a memory saving for structured data.

BUG= http://dartbug.com/16692

[Lasse Reichstein Nielsen, 2014-02-26 16:39:17]

There are several tweaking options: when to switch to maps in the hidden
classes, whether to keep the "map transitions" alive between parses, and whether
to even use hidden classes (which could be determined by the size of the JSON,
and hiving a plain builder like the current one as well).

[sra1, 2014-02-26 20:48:42]

I think we need a test for the order of keys in the parsed JSON.

Ideas:

1. Construct a string for a JSON list with all permutations of key orders, with
some of them repeated later in the list to exercise the internal classes.

[{"a":1, "b":2, "c":3, "d":4, "e":5},
 {"b":1, "a":2, ...

At the same time construct the expected value of

JSON.decode(data).map((m) => m.keys).toList()

2. A JSON map's existing keys don't change order when you insert a new key (test
the map upgrade path).

[sra1, 2014-02-26 21:56:06]

I would split this into two CLs, one for the number and string parsing time
performance improvements, and a second for the space saving map implementation.

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
File runtime/lib/convert_patch.dart (right):

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:956: * This is the only object that the JSON
decoder's user sees.
Interesting trick.

Can you think of a way to make an upgradable delegating map public and part of
dart:collection without adding a public 'delegate' member?

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:958: class _JsonMapWrapper implements Map<String,
dynamic> {
The original map was created with

currentContainer = {};

which would be Map<dynamic, dynamic>

Is the intention to change the type and restrict how it might be consumed?
You could defend either choice, just lets be explicit.

We should ensure the type of the parsed object is consistent between VM and
dart2js, and tested.

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:977: void clear() { _delegate.clear(); }
FYI you can use => for these too.
I guess in poorly optimized checked mode, your form has no result==null check.

[sra1, 2014-02-27 04:45:22]

More DBC

https://chromiumcodereview.appspot.com/181543004/diff/40001/runtime/lib/conve...
File runtime/lib/convert_patch.dart (right):

https://chromiumcodereview.appspot.com/181543004/diff/40001/runtime/lib/conve...
runtime/lib/convert_patch.dart:754: //return new _JsonHiddenClassMap(this,
makeListFixedLength(values)).wrapper;
Delete comment.

https://chromiumcodereview.appspot.com/181543004/diff/40001/runtime/lib/conve...
runtime/lib/convert_patch.dart:938: new SubListIterable(mapValues, 0,
values.length);
If we modify the map while iterating the keys or values, we not longer get a
ConcurrentModificationError for the first modification.

Add tests for this for all potentially mutating operations.

Also, we have existing behaviour that we should not change:
Removing an existing key modifies the Map.
Removing a non-existing key does not modify the Map.

[Lasse Reichstein Nielsen, 2014-02-27 09:10:38]

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
File runtime/lib/convert_patch.dart (right):

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:754: //return new _JsonHiddenClassMap(this,
makeListFixedLength(values)).wrapper;
Acl, yes. It was an attempt to save a little extra memory, but it is a
significant overhead, probably because it calls into C to do the work.

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:938: new SubListIterable(mapValues, 0,
values.length);
Ack.
Concurrent modification. Why don't we just disallow it?
(Seriously, I would prefer a collection library where objects were either
modifiable or iterable, but never both).

But true. And adding/updating an existing key also does not cause 
a concurrent modification error, which means that that operation must be handled
internally in the hidden-class map.

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:956: * This is the only object that the JSON
decoder's user sees.
I am considering adding a public static setter function to the wrapper classes
in package:collection.
The object's interface won't expose the hidden base object being delegated to,
but if you know that it's a wrapper, you can update the base object from the
side.
Anyone can do that, but then, anyone can use dart:mirrors to change the field
too. It's just more obvious that it's not a freely available operation.
I won't make a getter function, so you don't leak the contained object (but the
same mirror argument suggests that it's probably not a rational choice on my
part :).

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:958: class _JsonMapWrapper implements Map<String,
dynamic> {
On 2014/02/26 21:56:06, sra1 wrote:
> The original map was created with
> 
> currentContainer = {};
> 
> which would be Map<dynamic, dynamic>
> 
> Is the intention to change the type and restrict how it might be consumed?

It wasn't the intent, because I hadn't noticed that the map wasn't
<String,dynamic>. I do like the change (really, it's a JSON map!), but we should
probably see if it causes problems.

> You could defend either choice, just lets be explicit.
> 
> We should ensure the type of the parsed object is consistent between VM and
> dart2js, and tested.

https://codereview.chromium.org/181543004/diff/40001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:977: void clear() { _delegate.clear(); }
I prefre (strongly) to not use "=>" for void functions. It may cost me one extra
character, but it's much easier to see what happens.

[Lasse Reichstein Nielsen, 2014-03-03 11:44:35]

Moved optimizations to other CL. PTAL

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

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
File runtime/lib/convert_patch.dart (right):

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:74: if (key != null)
Curly braces missing?

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:166: //               VALUE  STRING  :  ,  }  ]  
     f to
?

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

LGTM with minor comments.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
File runtime/lib/convert_patch.dart (right):

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:74: if (key != null)
something's not right here.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:166: //               VALUE  STRING  :  ,  }  ]  
     f to
?

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:763: final int length;  // `keys` may contain
more elements than length.
Point to `addKey` where we add a new key for the next SmallHiddenClass.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:781: const int MAX_SMALL_CLASS = 4;
I would go higher, but that's just my gut-reaction.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:795: newKeys = keys;
Add comment that we are sharing the list here.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:810: final int length;  // `keys` may contain
more elements than length.
ditto. point to `addKey`.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:916: Iterator values = other.iterator;
Maps don't have iterators.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:917: if (!values.moveNext()) returm
You could also just ask, if other.length == 0, convert, and use addAll.

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:920: map.add(values.current);
map doesn't have "add".

https://codereview.chromium.org/181543004/diff/80001/runtime/lib/convert_patc...
runtime/lib/convert_patch.dart:1011: * Used to have a "copy on write" map
implementation optimized for reading,
s/Used to have/Has/

[srdjan, 2014-03-03 21:03:55]

LGTM after addressing comments. Do you see performance numbers?

[Lasse Reichstein Nielsen, 2014-03-06 14:25:02]

The performance change for this CL alone is actually negative (by 5-10%). It
does use less memory (well, I think it does), but for our benchmarks, it never
really shows up. 
I have an idea to avoid some string comparisons by building the keys using a
Trie so the keys will be canonicalized (and an initial implementation of that
that is almost performance neutral on the benchmarks). I'll see if it can help
this CL reduce its overhead.

[sra1, 2014-03-06 18:47:08]

On 2014/03/06 14:25:02, Lasse Reichstein Nielsen wrote:
> The performance change for this CL alone is actually negative (by 5-10%). It
> does use less memory (well, I think it does), but for our benchmarks, it never
> really shows up. 
> I have an idea to avoid some string comparisons by building the keys using a
> Trie so the keys will be canonicalized (and an initial implementation of that
> that is almost performance neutral on the benchmarks). I'll see if it can help
> this CL reduce its overhead.

We also need a benchmark that uses JSON data, so we know the new Map classes are
not slower than the old ones.

[Lasse Reichstein Nielsen, 2014-03-07 09:26:05]

On 2014/03/06 18:47:08, sra1 wrote:

> We also need a benchmark that uses JSON data, so we know the new Map classes
are
> not slower than the old ones.

They are slower. They pretty much have to be: It's doing the same map lookup,
but instead of directly getting the value, there is a further array lookup with
the index from the map.

This is optimizing for memory, and trying not to regress speed by too much, but
it will certainly be a little slower.
(That said, a benchmark would be great so we can see HOW much slower).