Live data from Hacker News

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

go101.org

11–20 of 154 posts

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

#12
post #2

Ideological purity only works when you actually give people a good alternative. Otherwise you cause more harm than good. I see it in things like transportation, power generation, recycling. People refuse to use the best methods because then people will never switch - except they never offer the thing that you are supposed to switch to. I'm actually kinda surprised to see it in a programing language.

A very good point.

Until there are the resources and demand to redesign a system for an important goal, the current system should be optimized where it reasonably can be, to better meet the same goal.

Until there are the resources and demand for a deeper redesign, the current code should be optimized as much as it reasonably can be.

Sometimes local optimizations are not worth the cost to make them, a local benefit/effort maximum has been reached. Only a more global change can take things further. But this doesn't look like one of those cases.

It is also worth noting that it is very rare that actual global redesigns are ever economical. Virtually every improvement, in anything, at any scale, is a "local redesign" in some sense.

So "up with" economical local optimizations!

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

#13
post #8

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…

The native binary operators aren't a three way compare though.

The author seems to assume nobody needs a three way compare, which I feel is assuming a bit too much.

In particular because it is there because someone is using/needing it already.

Basically their comment actually says that everyone who does need a three way compare should just re-implement what they wrote there (and maybe they'll make sure everyone's code is optimized later). Sounds pretty bizarre to me to discourage code reuse. And if three way compares are a pattern they want to discourage in the first place it should be elaborated on in documentation.

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

#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 oldest.

More examples about the dangers with just ints: https://stackoverflow.com/questions/2728793/java-integer-com...

The comparable API in Java came from the C qsort API. It would have been better to just have a less-than method. Kind of surprised to see this in Go near a core API.

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

#15
post #10

I mean, from rsc's comment, it's a known issue. I'm guessing no one has cared enough to improve it. Making me think it's not that big of a deal that it does the extra comparison. If people really need the extra performance, they'll use unsafe to create byte slices backed by the strings, and then use bytes.Compare. Or they'll improve the compiler.

> If people really need the extra performance, they'll use unsafe to create byte slices backed by the strings, and then use bytes.Compare

...and thus very likely end up with buggy code.

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

#16

What I don’t understand is that they doing first check for lengths Strings are so common, it’s insane they don’t optimize

Wouldn't the normal implementation for == check lengths?

Edit: Never mind, it doesn't: https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03...

But checking lengths doesn't really help you: it only tells you when strings are not equal, and you would still have to walk the string to see which one is larger/smaller.

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

#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 is this in a test:

    ...
    cmpopts.SortSlices(func(a, b testEntryEventInfo) bool {
                  return strings.Compare(string(a.Addr), string(b.Addr)) 
This pattern shows up a bunch:

    // Less implements sort.Interface.
    func (s fooSlice) Less(i, j int) bool {
        return strings.Compare(s[i].Whatever, s[j].Whatever) == -1
    }
In Go's Snowflake library, there is this:

    if strings.Compare(s0, name) != 0 {
            t.Error("a file was not downloaded by GET")
    }
This is exceedingly interesting to me because you'd expect Compare to cost more than All in all, I get the impression that people coming from other languages to Go have different expectations about what the language can do. The documentation for strings.Compare is a logical place to correct them, but it doesn't bother. Just a comment that says "sucks if you use this".

BTW, there were a couple of correct uses. Gazelle has a sort function like this in a few places:

    sort.SliceStable(sortedFiles, func(i, j int) bool {
        if cmp := strings.Compare(sortedFiles[i].Path, sortedFiles[j].Path); cmp != 0 {
            return cmp 
Here they are punished for the inefficiency of strings.Compare; they would actually take advantage of it in the common case where the paths aren't equal over the easier approach of:

   if xs[i].Path != x[j].Path {
       return xs[i].Path 
Another correct use was in "goja" (a Javascript interpreter), which uses strings.Compare to implement Javascript's .compareTo(). Whether or not Javascript code is using compareTo correctly is an analysis I do not have the energy to do :)

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

#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.

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

#20

Really bizarre. It seems like it wouldn't have been much more work to just implement it properly. Instead people are supposed to wait until the compiler magically gets smart enough to optimize the pattern... but the pattern and method are both intentionally slow, so there will never be usage pressure to optimize it. A reasonable compromise would be to just implement a single pass three-way compare in native Go instea…

Any sort that doesn’t take into account Unicode collation isn’t Unicode correct.
Post reply on HN