Define a natural sort order for Structs

[ghost]

Right now, primitives (bool, number, string) sort "naturally" but all other objects sort by ascending hash value.

Sorting by hash can be useful if your goal is to normally distribute values, which can be useful.

However, sorting naturally would, in particular:

1. Allow Structs as keys in maps, approximating sql compound keys and allow for more control over locality.
2. Remove the burden of compute the hash for every value inserting into a set/map (which is considerable)
3. Remove weirdness in the implementation of map/set, that internal nodes of p-trees hold Value if the value sorts naturally, and Ref otherwise (and a bunch of related code cruft).

One big reason to be afraid of doing this is effectively reducing the number of down-pointers an internally tree node may hold, if the key value of the down pointer becomes too large. The solution to this is likely: #2763 for which there is a currently decent plan.

It'll always be possible to screw yourself (i.e. by using a key value whose encoding is > ~4k), but that will be true for strings as keys in maps regardless.

[ghost]

@aboodman points out that doing this for all values isn't possible. Not totally sure why I thought it was. The most obvious case is Set<Ref>. Ref can't sort by value. trees of level > 1 are also not possible.

Therefore I'm changing the title of this bug to have a more narrow scope.

[ghost]

Ok, I still think that just making structs sort naturally is valuable because it's common to key maps with structs, and that a lot of benefit accrues from 1 & 2 above.

In addition, once we land #3363, it'll mean that the importers for collection can have a fast path which examines the type of the collection and if it's keys sort naturally, it can use NewStreaming, rather than an Editor, which will be the common case, faster, and doesn't require implementing Editors spilling to disks to be correct.

[ghost]

Hmm.. Thinking about this more, it's really sort structs which contain only structs or other naturally sorting types to sort naturally.

Damn my dad brain. This argument is getting more sketchy. It could still work, but it's a less clean division between naturally sorting types and hash sorting types.

@aboodman?

[ghost]

Ok. I've arrived. This is a bad idea. Especially considering that if the primary value is the expectation that structs will sort as a kind of compound key, the fact that there isn't control of the field precedence kinda kills it.

I think the answer for now is that if you want a compound key that sorts naturally, you need to encode it as a string. =-(