Parsed json data is not in the same order as the original.

[kondrak]

Thanks for this crate!
I'm currently writing a code generator, where you can define the API using JSON. I noticed that if a list of elements is used, the resulting parsed output is not in the same order as defined in the original JSON data, which is a bit of a problem. Example:

What I pass to JSON parser:

{
  "struct": {
  "var": { "type": "int", "name": "x" },
  "func": [ { "type": "int", "name": "return_int" } ]
  }
}

What I get after parsing and printing the parsed data to screen:

{"struct":{"func":[{"name":"return_int","type":"int"}],"var":{"name":"x","type":"int"}}}

Is there a way to get the output exactly in the same order as I defined? So far I'm iterating over members() and entries() and I can't see any other way to do it properly.

Thanks!

[maciejhirsz]

Hey! Thanks for the question.

Currently the internal representation of an object is using a BTreeMap, which sorts keys for lookup performance. This is perfectly fine within the standard:

An object is an unordered set of name/value pairs.

That said ideally I would like to preserve the ordering of keys, there are some crates out there like a linked hash map implementation that can do it, but I haven't gotten to play with it yet.

[maciejhirsz]

Since 0.9 is planned to include other breaking changes, I figure it's a good opportunity to include linked hash map implementation for objects along with the rest of it. Will see how that affects performance.

[kondrak]

Maybe giving the user some kind of an option to choose between faster out-of-order and (potentially?) slower in-order would be a good idea? By default it could work the way it does now since I realize that only specific applications will want the data in-order.

[maciejhirsz]

That's reasonable. I'll see how benchmarks behave, if the hit isn't too big it might be best to just always preserve the order and not introduce extra complexity to the API. I'm still busy-ish today, but from tomorrow on I should have plenty of free time to sink into this project, I hope to have a nice release of 0.9 by the end of the weekend at the latest :).

[kondrak]

Excellent, thanks!

[maciejhirsz]

I've been playing around with a custom implementation of what would be a bastard child of a binary tree and linked list. Given that I can exploit the control over the heap allocation there, I can put short object keys directly on the node without the extra heap allocation that a full blown String would require.

My initial benchmarks show that this cuts the construction time of the tree by about 30%, at the cost of lookups being slightly more expensive than the default BTreeMap. Should be good enough for the initial implementation, I'll look into a proper hash table implementation after 0.9.0.

The added bonus is that since it has characteristics of a linked list, iterating in insertion order will be preserved. Sometimes you can have your cake and eat it too.

[kondrak]

Sounds good! Any indication on when we can expect 0.9? It's not a fix that I need critically but would be nice to have ;)

[maciejhirsz]

Soon™. I want to say tomorrow, but I don't want to be too optimistic so I'll stick to my initial estimate - the end of the weekend.

[kondrak]

takes screenshot ;)

[maciejhirsz]

	BTreeMap	LinkedHashMap	new json-rust Object
create with 11 entries	1,279 ns	1,787 ns	903 ns
create with 3 entries	310 ns	539 ns	216 ns
lookup 11 entries	601 ns	529 ns	434 ns
lookup 3 entries	55 ns	120 ns	75 ns

I said the lookup time is worse, seems it's only worse for small amount of entries. Dunno why BTreeMap is slower with 11. Testing with keys inserted in order:

    map.insert("timestamp".into(), DUMMY);
    map.insert("zone_id".into(), DUMMY);
    map.insert("zone_plan".into(), DUMMY);
    map.insert("http".into(), DUMMY);
    map.insert("origin".into(), DUMMY);
    map.insert("country".into(), DUMMY);
    map.insert("server_ip".into(), DUMMY);
    map.insert("server_name".into(), DUMMY);
    map.insert("remote_ip".into(), DUMMY);
    map.insert("bytes_dlv".into(), DUMMY);
    map.insert("ray_id".into(), DUMMY);

[kondrak]

Looks decent!

[maciejhirsz]

The log benchmark I'm using in readme:

test json_rust_parse                     ... bench:       3,296 ns/iter (+/- 1,614) = 183 MB/s
test json_rust_stringify                 ... bench:       1,819 ns/iter (+/- 895) = 332 MB/s

This is also using the new short strings that also avoid heap allocation. Stringify took a dive since iterating over entries now requires jumping around with pointers instead of indexing a vector, but parsing seems to more than make up for that. I want to try allocating the nodes of the tree on a vector to get old numbers back for stringify, hopefully without hurting the new parsing performance that much.

It's gonna be a long weekend...

edit: back to some more reasonable numbers

test json_rust_parse                     ... bench:       3,549 ns/iter (+/- 1,624) = 170 MB/s
test json_rust_stringify                 ... bench:       1,627 ns/iter (+/- 508) = 371 MB/s