In Ord instance in json, compare Objects more efficiently

[catamorphism]

as per a FIXME (formerly an XXX)

[pnkfelix]

To save future reviewers time: the FIXME is referring to a loop for comparing two encoded JSON Objects (as opposed to Number, String, Boolean, Null, and List (aka "JSON Arrays")). Such Objects are represented as hashmaps. The comparison of two Objects is implemented by copying each hashmap to a ~[(~str, Json)] vector, quick-sorting the vectors, and finally returning the result of comparing the two vectors.

There are potentially some interesting backwards-compatibility questions here; i.e. would we be willing to change the ordering defined by the above algorithm in order to have better overall performance. I assume the answer there is yes.

Examples of some hacks that would change the ordering and improve performance (at least in special cases):

• Use the number of hashmap entries as a partial ordering on Object.
• Use the keys alone as a (second) partial ordering on Object (to avoid recursive copy and traversal of the values until we've confirmed it is necessary).
• Extract the keys alone, sort them, then traverse the sorted list of keys and compare the associated values. This cuts the size of the temporary ~[(~str, Json)] list structure in half (and I think usually much more than that, since its it looks like the Json objects are copied into the temporary list structure).
  • I had thought it might also help avoid unnecessary comparisons between Json objects, but since there will not be duplicate keys in the ~[(~str, Json)], and since presumably d0_flat < d1_flat will short-circuit as soon as it sees the first smaller Json Object, I am no longer sure there's a further win to be had here.

But since json.rs lives in libextra (and not the core), I am guessing that this does not mean that we need to worry about its backwards-compatibility. It would be good to clarify that, though.

[alexcrichton]

Another interesting idea that could happen here is to use a TreeMap instead of a HashMap by default. I like the idea of not performing an allocation during a comparison because that's always a sad thing to do. Obviously a bad part here is that lookups are then not O(1). This probably isn't enough reason to use TreeMap, but it would have the other bonus of 0 allocations during comparisons.

[emberian]

The fixme is still there and does all sorts of horrible things, but TreeMap is now used rather than HashMap.