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

51–60 of 154 posts

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

#51

Post by oefrha »

cookiengineer wrote: post #42
eru wrote: post #29

Earlier quoted context omitted.

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.

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…

Yes, version string comparison is hard because people have all sorts of unstandardized ideas about version strings. Not sure why you seem to believe there’s golang-specific difficulty here.

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

#52

Post by somekyle2 »

userbinator wrote: post #33

So I think the strings.Compare should be implemented efficiently, to avoid breaking user expectations. Is Go forkable (for lack of a better word)? That's the only question that comes to mind when I read the article. You have the source code, and this shouldn't be a difficult change to make, so I think "fork-and-fix and see who follows along" should be the mentality to practice in this case.

If anyone finds "a standard library string comparison function, while quite fast in absolute terms, isn't as fast as it could be" to be practical justification for a fork, I'd be very surprised.

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

#53

Post by smt88 »

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?

> "intentionally nerf Compare() to discourage code the golang authors considered less clear"

If that's true, it further proves that I disagree with the philosophy of the Go designers on pretty much everything.

If your language provides multiple ways to do something, they should all be optimized in good faith. To do what you suggested is insane and user-hostile.

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

#54

Post by somekyle2 »

jbverschoor wrote: post #11

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

In the generated code, there is a length check. In implementation (which will often be inlined, so may vary contextually) it does a length check, and if equal does a memequal (tuned platform assembly). If that equality check fails, or the length check isn't equal, it does a runtime.cmpstring (tuned platform assembly). So, when strings are actually equal or are unequal in length, it's pretty much optimal. The bad case is when the strings are equal in length but not in content, as that can result in two scans of the strings. Still not slow in that case given that the work it's doing is being done quite efficiently, but some of that work is effectively wasted. On my local go install (2020 macbook, go) the difference is between about 2ns and 4ns for an 8-byte string that is different in the last byte. Naturally, could vary quite a bit based on cache and string size, but fast enough to not worry about until profiles show it matters.

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

#55

Post by Lvl999Noob »

It is easy to use a 3-way compare to implement normal comparison operators. It is much harder to recognize when some code is using comparison operators to implement an ad-hoc 3-way compare.

It would be harder still to know how those normal compare functions can be combined to implement an efficient 3-way compare. For strings and other built in types, this might be possible. But for user defined types that compare in weird ways, it could be very hard.

It's much better to let the programmer define the 3-way compare and use that to derive all the comparison operators.

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

#56

Post by somekyle2 »

smt88 wrote: post #53
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?

> "intentionally nerf Compare() to discourage code the golang authors considered less clear" If that's true, it further proves that I disagree with the philosophy of the Go designers on pretty much everything. If your language provides multiple ways to do something, they should all be optimized in good faith. To do what you suggested is insane and user-hostile.

Well, the question is what you want to optimize for. It's a library function that exists for consistency's sake; it's clear and simple, and reasonably fast (and near optimal in some cases).

For optimal performance but suboptimal clarity, they could use a runtime implementation, but ideally the clear code would be fast, so best not to compromise the clarity for performance unless it proves important.

I've been following Go content for years, this is the first I can recall hearing of it, so I'm mostly fascinated that people care, given that this seems to be doing what the most classic optimization advice suggests and not messing it up prematurely.

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

#57

Post by somekyle2 »

quelltext wrote: post #28
skybrian wrote: post #24

Earlier quoted context omitted.

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 funn…

This is a part of Go's rather odd perspective that I appreciate.

I've worked in codebases with library helpers for everything that mostly served to turn two clear lines into a function call. Once such functions exist, folks feel obligated to use them; after all, why duplicate code? So now, what would've been a couple dozen lines of self-contained straightforward code has 3 imports and 5 functions you need to be familiar with to understand it. It also makes compilation more expensive.

I'm not saying library functions are bad or anything like that, but there's value to keeping the typical vocabulary of code small, of not adding new dependencies to solve trivial problems. Especially in a standard library that is widely used and you expect to be maintained for years. Providing functions that solve problems that are impossible or tricky in the language is important; providing `Plus(a, b int) int` that wraps `+` makes the library worse.

I think there's a good argument for providing Compare() and Abs() and other fairly trivial functions even if it is perhaps less effort to not use them in most cases, but for a stdlib I can appreciate the logic of leaving out what isn't providing clear value.

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

#58

Post by crymer11 »

cookiengineer wrote: post #42
eru wrote: post #29

Earlier quoted context omitted.

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.

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…

> semantic versioning allows "1.2.3alpha"

Perhaps I missed it, but I thought [Semantic Versioning](https://semver.org/) required a “-“ between the patch number and a prerelease identifier since at least version 1.0.0 (with 1.0.0-beta allowing a “.” instead of a “-“), no?

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

#59

Post by kibwen »

cookiengineer wrote: post #42
eru wrote: post #29

Earlier quoted context omitted.

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.

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…

> semantic versioning allows "1.2.3alpha" and also 1.2.3-beta"

No, according to the spec, the hyphen is mandatory: "A pre-release version MAY be denoted by appending a hyphen and a series of dot separated identifiers immediately following the patch version."

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

#60

Post by alcover »

cookiengineer wrote: post #42
eru wrote: post #29

Earlier quoted context omitted.

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.

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…

  - Is 1.2.3 > 1.2.3omega? No
  - Is 1.2.3 > 1.2.3beta?  No
  - Is 1.2.3gamma > 1.2.3? Yes
I don't see ambiguity in your examples.
Post reply on HN