Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

No safe efficient ways to do three-way string comparisons in Go

go101.org

Post reply on HN
Print view View original

21–30 of 154 posts

Re: No safe efficient ways to do three-way string comparisons in Go

#21

Post by Dylan16807 »

irogers wrote: post #14

People try to get cute with 3-way compares. A real Java bug that inspired: https://errorprone.info/bugpattern/BadComparable public MyFile implements Comparable { ... long timestamp; ... @Override public int compare(Object other) { return (int)(((MyFile)other).timestamp - timestamp; } ... } The int conversion loses the sign of the subtract. The particular use of the code was sorting files to delete the X number of old…

I don't blame the cute three way comparison at all for that problem. Converting number types incorrectly is an endemic problem, and using the right conversion would have made this work quite nicely.

Re: No safe efficient ways to do three-way string comparisons in Go

#22

Post by Dylan16807 »

jrockway wrote: post #18

This is really interesting. I never use three way string comparison, and so I wondered when other programmers use it. (The obvious use case is sorting, but in Go, sort.Interface expects a Less function and sort.Slice accepts a "Less" function, so you won't use it there.) I searched through my random checked out applications to see who calls strings.Compare, and why. Most of them are mistaken sorting. In gVisor, there…

> This is exceedingly interesting to me because you'd expect Compare to cost more than I would expect it to be the same within a couple nanoseconds, because "more stuff" is an extremely small amount of stuff.

The naive direct implementation of a 3 way compare does the exact same comparisons as a direct implementation of less than, it merely returns more information, which makes it more generally useful.

Re: No safe efficient ways to do three-way string comparisons in Go

#23

Post by throwawayabcdef »

travisby wrote: post #8
recursive wrote: post #4

Earlier quoted context omitted.

What's even the ideology here? It reads like someone's taking a stand, but I can't tell what the stand is. Like, how is someone supposed to alphabetize a list of names? Surely that's a basic task that programming languages should be able to to do.

Based on https://go-review.googlesource.com/c/go/+/3012?tab=comments , it sounds like they were originally focusing on _clearer_. (I interpret that) rsc considers the native binary operators to be clearer than a function with the name `Compare`. Honestly, I'd expect people to use `==` as well over `strings.Compare`. `==` _does_ work for strings, but I believe `[]byte` would try comparing memory addresses which is why…

https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9...

I interpret this as replacing a strange but more optimal call to the runtime with a straight forward but less fast stdlib implementation. rsc's comment seems more like a todo note than and ideological stance (to me at least). Something like: "I removed this weird fast way to do this that was breaking stuff b/c of linker things and replaced it with some straightforward code that's slower. If we want this to be more optimal in the future we can fix it at the compiler level.". But I'm just reading into it. Someone should ask him and tell him to explain himself :) It's been 8 years. What have you been doing?

Re: No safe efficient ways to do three-way string comparisons in Go

#24

Post by skybrian »

quelltext wrote: post #9

> Basically no one should use strings.Compare Others have already talked about the performance aspect but I'm just baffled at the comment basically saying nobody should use this function anyway. I expect the need for 3-way compares isn't that uncommon, why tell people not to use it? It's great to have this idea that the compiler should optimize all comparison situations but a) it doesn't yet and b) people still want…

The comment is confusing, but the idea seems to be that instead of calling this function, you should inline the code - that is, just write the comparisons yourself. You don't need a function call.

I guess this is for stylistic reasons, but I don't know why anyone would feel strongly about doing it one way or the other.

Re: No safe efficient ways to do three-way string comparisons in Go

#25

Post by jrockway »

Dylan16807 wrote: post #22
jrockway wrote: post #18

This is really interesting. I never use three way string comparison, and so I wondered when other programmers use it. (The obvious use case is sorting, but in Go, sort.Interface expects a Less function and sort.Slice accepts a "Less" function, so you won't use it there.) I searched through my random checked out applications to see who calls strings.Compare, and why. Most of them are mistaken sorting. In gVisor, there…

> This is exceedingly interesting to me because you'd expect Compare to cost more than I would expect it to be the same within a couple nanoseconds, because "more stuff" is an extremely small amount of stuff. The naive direct implementation of a 3 way compare does the exact same comparisons as a direct implementation of less than, it merely returns more information, which makes it more generally useful.

Yeah. To me, I just think it's weird to ask for two pieces of information and then throw one of them away. Sometimes it's not a performance hit, but I feel like it's one of those things where you should get a feeling "I might be doing this wrong". But if you don't know that < exists (and obviously searched for strings.Less), then you won't get that feeling. That's what I find so fascinating; if other people's feelings are similar to mine, then they simply didn't know that you were allowed to use < here.

Re: No safe efficient ways to do three-way string comparisons in Go

#26

Post by quelltext »

jrockway wrote: post #18

This is really interesting. I never use three way string comparison, and so I wondered when other programmers use it. (The obvious use case is sorting, but in Go, sort.Interface expects a Less function and sort.Slice accepts a "Less" function, so you won't use it there.) I searched through my random checked out applications to see who calls strings.Compare, and why. Most of them are mistaken sorting. In gVisor, there…

> so the documentation is trying to talk them out of...

What documentation though? There's an internal comment but it's not documentation and it's not really arguing against the use of this type of comparison (just against use of the implemented function).

If the documentation for this function went on along the lines of "we discourage the use of 3 way compares as we consider it an antipattern, do X instead, there's literally no reason to ever use 3 way compares, we know it, here's why..." maybe, but it doesn't.

Now, maybe 3 way comparison is not common but it is a distinct operation with known optimization opportunities. I wouldn't readily claim that the operation is not needed by anyone.

Re: No safe efficient ways to do three-way string comparisons in Go

#27

Post by Dylan16807 »

jrockway wrote: post #25
Dylan16807 wrote: post #22

Earlier quoted context omitted.

> This is exceedingly interesting to me because you'd expect Compare to cost more than I would expect it to be the same within a couple nanoseconds, because "more stuff" is an extremely small amount of stuff. The naive direct implementation of a 3 way compare does the exact same comparisons as a direct implementation of less than, it merely returns more information, which makes it more generally useful.

Yeah. To me, I just think it's weird to ask for two pieces of information and then throw one of them away. Sometimes it's not a performance hit, but I feel like it's one of those things where you should get a feeling "I might be doing this wrong". But if you don't know that < exists (and obviously searched for strings.Less), then you won't get that feeling. That's what I find so fascinating; if other people's feeling…

I don't see it as two pieces of information. It's returning one idea either way, but the tri-state tells you more than a boolean.

Re: No safe efficient ways to do three-way string comparisons in Go

#28

Post by quelltext »

skybrian wrote: post #24
quelltext wrote: post #9

> Basically no one should use strings.Compare Others have already talked about the performance aspect but I'm just baffled at the comment basically saying nobody should use this function anyway. I expect the need for 3-way compares isn't that uncommon, why tell people not to use it? It's great to have this idea that the compiler should optimize all comparison situations but a) it doesn't yet and b) people still want…

The comment is confusing, but the idea seems to be that instead of calling this function, you should inline the code - that is, just write the comparisons yourself. You don't need a function call. I guess this is for stylistic reasons, but I don't know why anyone would feel strongly about doing it one way or the other.

Yes, I mentioned that that's basically what it says. But why would you tell people to actively duplicate code? It's like "I don't get what this type of function does and have to look it up all the time, better to have everyone inline this so it's clearer".

To be fair, I agree that seeing bad examples of its use shown by one of the other folks here, some could have been avoided by them being forced to inline, but funnily those examples still exist despite the desires of the function author.

Nothing was achieved here.

Re: No safe efficient ways to do three-way string comparisons in Go

#29

Post by eru »

dhosek wrote: post #19

I’d argue that any string comparison which does not take into account collation is inherently broken. Even in the pure ASCII English-language case, a naïve comparison on values won’t give desirable results since abc123 will come before abc99 even though a reader would expect otherwise. Just because we’ve tolerated crappy string sorting for sixty years doesn’t mean we should continue to do so.

For some applications (eg sticking stuff in an ordered data structure), you just need any consistent ordering, but don't care too much about exactly which one.

Re: No safe efficient ways to do three-way string comparisons in Go

#30

Post by codedokode »

eru wrote: post #29
dhosek wrote: post #19

I’d argue that any string comparison which does not take into account collation is inherently broken. Even in the pure ASCII English-language case, a naïve comparison on values won’t give desirable results since abc123 will come before abc99 even though a reader would expect otherwise. Just because we’ve tolerated crappy string sorting for sixty years doesn’t mean we should continue to do so.

For some applications (eg sticking stuff in an ordered data structure), you just need any consistent ordering, but don't care too much about exactly which one.

Then you can use bytewise comparison instead of alphabetic comparison.
Post reply on HN