No safe efficient ways to do three-way string comparisons in Go • Hacker News Board

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

#131

Post by blincoln » Thu, Oct 27, 2022, 1:58 PM UTC

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…

Maybe the overuse of Compare instead of ==, is from enterprise devs who've done a lot of Java work? Every time I step away from Java for 5+ years and come back, I forget that one has to use string.equals() because using == will generate incorrect results. I imagine people who use it more frequently could easily have the opposite problem.

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

#132

Post by esprehn » Thu, Oct 27, 2022, 2:01 PM UTC

Beltalowda wrote: post #112

esprehn wrote: post #41

The optimal version does seem to exist here (per the comment too): https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03... So the goal was to intentionally nerf Compare() to discourage code the golang authors considered less clear. I'm not sure bad performance is really discouraging usage though, it just penalizes folks that use stdlib. I wonder if they'd accept a PR to switch to runtime.cmpstring today?

It actually used to call this, but was changed in 2015: https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9... I'm not entire sure if I see the problem or follow why just using runtime·cmpstring is such a bad thing; doesn't seem that "overengineered" to me.

Yeah, that's a pretty small amount of clean up. Someone should try to revert the patch and reland it.

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

#133

Post by sltkr » Thu, Oct 27, 2022, 2:10 PM UTC

scotty79 wrote: post #34

Dylan16807 wrote: post #21

Earlier quoted context omitted.

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.

What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?

You could call Long.signum(), but that's not the right solution here: you should not subtract the values, but call Long.compare(a, b) directly, which is clear, efficient and correct.

The reason to avoid subtraction is that you can get integer underflow if one operand is negative and one is positive, and then the result of Long.signum(b - a) is different from Long.compare(a, b).

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

#134

Post by daviddever23box » Thu, Oct 27, 2022, 2:21 PM UTC

tapirl wrote: post #123

daviddever23box wrote: post #99

The premise that three-way string comparisons are widely used is spurious at best.

Evidences are provided in the article: https://sourcegraph.com/search?q=context:global+switch+strin...

201 instances != widely used by multiple projects. Thank you for playing.

There are many ways to approach this type of problem, and–while I understand that some may want to lean on this approach, based on their experiences with another language–this is an academic comparison, and far less useful than one might believe when building performant code.

To each their own.

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

#135

Post by icholy » Thu, Oct 27, 2022, 2:22 PM UTC

Beltalowda wrote: post #112

esprehn wrote: post #41

The optimal version does seem to exist here (per the comment too): https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03... So the goal was to intentionally nerf Compare() to discourage code the golang authors considered less clear. I'm not sure bad performance is really discouraging usage though, it just penalizes folks that use stdlib. I wonder if they'd accept a PR to switch to runtime.cmpstring today?

It actually used to call this, but was changed in 2015: https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9... I'm not entire sure if I see the problem or follow why just using runtime·cmpstring is such a bad thing; doesn't seem that "overengineered" to me.

It's because people started putting "always use strings.Compare" in their style guides.

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

#136

Post by tapirl » Thu, Oct 27, 2022, 2:23 PM UTC

daviddever23box wrote: post #134

tapirl wrote: post #123

Earlier quoted context omitted.

Evidences are provided in the article: https://sourcegraph.com/search?q=context:global+switch+strin...

201 instances != widely used by multiple projects. Thank you for playing. There are many ways to approach this type of problem, and–while I understand that some may want to lean on this approach, based on their experiences with another language–this is an academic comparison, and far less useful than one might believe when building performant code. To each their own.

Do you mean it is rare?

Man, it is the key to do binary-searching.

> ... based on their experiences with another language ...

Sorry, this is language independent.

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

#137

Post by daviddever23box » Thu, Oct 27, 2022, 2:32 PM UTC

sethammons wrote: post #109

cookiengineer wrote: post #42

Earlier quoted context omitted.

I've been developing my own version string parser for a couple weeks now, in golang. It's ridiculous to what lengths you have to go to understand which part of a string comes earlier or later. Simple example: semantic versioning allows "1.2.3alpha" and also 1.2.3-beta", but which one comes first now... - Is 1.2.3 > 1.2.3omega? - Is 1.2.3 > 1.2.3beta? - Is 1.2.3gamma > 1.2.3? In the Linux world it gets even funnier ca…

I'd use capture regex to get the first three numerals and capture the remaining string. If the remaining string exists, you can easily ignore the expected leading dash and your malformed semver suffixes will work and those can be trivially compared/sorted. What about Go makes this different? That's how I'd solve this is any language

Agreed - especially when it is potentially unknown what might follow the first three numerals. Any performance hit would be mitigated by the corresponding reduction of the downstream logic.

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

#138

Post by tapirl » Thu, Oct 27, 2022, 2:55 PM UTC

icholy wrote: post #135

Beltalowda wrote: post #112

Earlier quoted context omitted.

It actually used to call this, but was changed in 2015: https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9... I'm not entire sure if I see the problem or follow why just using runtime·cmpstring is such a bad thing; doesn't seem that "overengineered" to me.

It's because people started putting "always use strings.Compare" in their style guides.

Even if strings.Compare is optimized, it is not always better than general comparison operators.

Both strings.Compare and comparison operators have their respective best use scenarios.

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

#139

Post by Someone » Thu, Oct 27, 2022, 3:02 PM UTC

gnfargbl wrote: post #128

Someone wrote: post #127

When I look at https://go.godbolt.org/z/8jqMPh135 , compiling for a few CPUs, recent compilers only generate a single call to runtime.cmpstring . ⇒ I think the comment is outdated, and there is a safe efficient way to do three-way string comparisons in go. Caveat: I’m not that good at reading modern assembly, and I do not understand why there also is a call to runtime.memequal in that code. ⇒ Corrections welcome.

I'm not that good at it either, but I think that the runtime.memequal call is coming from the if a == b test, and that it is the if a test that is being replaced with a call to runtime.cmpstring . If so, then I guess there's still a redundant call to runtime.memequal inserted by the compiler. It's hard to imagine any of this matters at all, in practice, which is probably why the go authors haven't bothered addressing…

Thanks! Never thought == could be a simple buffer comparison (after a length check, I guess). I thought locale and things being Unicode would make that harder.

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

#140

Post by bilekas » Thu, Oct 27, 2022, 3:04 PM UTC

iainmerrick wrote: post #103

bilekas wrote: post #101

Maybe I'm not understanding the articles premise exactly, but if you're using three-way comparisons frequently, why would you not just implement the `diff3` ? It's not that complicated and well documented, infact I'm sure someone has already done it in go. http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

It's not three-way as in comparing three strings; here they're comparing two strings, with a "three-way" result: a b

Okay that makes a bit more sense, I was sure something wasn't registering right with me reading it.