fmt: maps should format in sorted order

[purpleidea]

Please answer these questions before submitting your issue. Thanks!

What version of Go are you using (go version)?

go version go1.8.1 linux/amd64

What operating system and processor architecture are you using (go env)?

GOARCH="amd64"
GOHOSTOS="linux"
GCCGO="gccgo"
CC="gcc"

What did you do?

I ran the attached playground link.

https://play.golang.org/p/EjvBekU87U

What did you expect to see?

I expect the displayed map output to be deterministic.

What did you see instead?

It changes randomly.

I understand that map randomizes the key order, and I actually think this is a cool implementation feature, however I think the displayed text output should be deterministic. It could display by sorted key order for example.

This will make diff-ing logs, and viewing output more consistent, with less flip-flop.

Thanks,
James

[martisch]

Observation: Even with sorting we will not always get stable output. e.g. NaNs will always be in some random order and sorting them will not help.

If stable output is needed one could dump and sort the map outside of fmt and then output the result. Making fmt always sort the map will always incur time and allocation overhead that can not be avoided even if unstable output is fine.

Maybe we can add a special modifier that will try to make output as stable as possible for printing maps instead of modifying the default unordered behaviour.

[purpleidea]

@martisch Can you elaborate on your NaN comment with an example please?

[purpleidea]

@martisch

If stable output is needed one could dump and sort the map outside of fmt and then output the result.

Actually, this is not possible because golang string representation values are unfortunately not unique. For example look at this map value:

map[answer:42 hello:13]

Is this a map with keys answer & hello which are both ints?
OR
Is it a map with one key named answer which has string: 42 hello:13 ?

They display the same.

[purpleidea]

@martisch

Making fmt always sort the map will always incur time and allocation overhead

You're making the assumption, you didn't test or profile this. Since it would only come out when folks did a fmt: %+v then I don't think it will affect anyone negatively.

[randall77]

Sorting the keys presupposes there is a sort order on the keys. For complicated keys like

struct {
   x int16
   y float64
   z interface{}
   p *int
}

It's not clear how to sort them. Floats don't always sort correctly, and how do you look inside interfaces to sort them?
The obvious sort order for pointers may not be stable across executions of your program.
So, it's complicated. Simple cases like string or int keys may sound tempting, but doing this in general is hard. Maybe not impossible, but I'm not convinced it would be worth the trouble.

[purpleidea]

On Thu, Jul 20, 2017 at 1:18 AM, Keith Randall ***@***.***> wrote: Sorting the keys presupposes there is a sort order on the keys. For complicated keys like struct { x int16 y float64 z interface{} p *int } It's not clear how to sort them. Floats don't always sort correctly

I've had a long day so maybe I'm missing something, but we're talking about map's, not structs. We sort by the key name.

[cznic]

Map keys are guaranteed to be comparable, but they're not guaranteed to be ordered - sorting them is not even possible in the general case.

[bradfitz]

I've had a long day so maybe I'm missing something

https://play.golang.org/p/RYac90kI-H

[purpleidea]

On Thu, Jul 20, 2017 at 1:45 AM, Brad Fitzpatrick ***@***.***> wrote: I've had a long day so maybe I'm missing something https://play.golang.org/p/RYac90kI-H

Gotcha, thanks! So I think we could plausibly have in the worst case something that *usually* provides good results. If in certain corner cases a display isn't stable, I don't think it's the end of the world. It would certainly be pleasing for the general cases. Thanks

[martisch]

Can you elaborate on your NaN comment with an example please?

NaNs can not be ordered and we only get them back random from ranging over a map. So sorting them afterwards we will not get a stable output across calls unless the map itself provides a mechanism to return key, values in stable order.

Actually, this is not possible because golang string representation values are unfortunately not unique.

I did not mean to suggest to sort the string representation but to sort the a slice constructed by collecting all key,value pairs in a slice using the range statement over a map.

You're making the assumption, you didn't test or profile this. Since it would only come out when folks did a fmt: %+v then I don't think it will affect anyone negatively.

I did not know your proposal was to only have ordered output for %+v as the proposal or example did not mention it. Println uses the %v internally. Note that using + also affect how keys and values will be printed for the map and always adds field names.

[martisch]

Added a correction in previous comment where i confused +v with regular + modifier.