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

81–90 of 154 posts

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

#81

Post by [deleted] »

llanowarelves wrote: post #75
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…

It is like Demo deprecating fs.exists().[1] [1] https://github.com/denoland/deno_std/discussions/2102

[deleted]

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

#83

Post by echlebek »

xmprt wrote: post #64
somekyle2 wrote: post #57

Earlier quoted context omitted.

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

I would understand that if the method was left out. But in this case, a strings.Compare method is provided but the implementation says not to use it. That's the worst of both worlds. The stdlib still has this extra method and users will feel obligated to use it because it exists but the method is inefficient.

The standard library can't ever remove anything because of the Go compatibility promise, and a certain percentage of it is mistakes. Once some functionality is later realized to be poor or incorrect, and the design prevents fixing it, there is not much that can be done other than telling people not to use it anymore. What you refer to as the worst of both worlds is unfortunately inevitable, but at least it's in service of a greater goal.

edit: clarity

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

#84

Post by philosopher1234 »

lamp987 wrote: post #82
philosopher1234 wrote: post #72

The go designers are brilliant. This is exactly the right priority. We would all do better it think more the way they do.

This was a joke right?

No I’m being sincere. Clarity is more important than performance. This is a very thoughtful decision, it relieves devs of the idiotic pressure to micro optimize.

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

#85

Post by philosopher1234 »

codeflo wrote: post #71
somekyle2 wrote: post #56

Earlier quoted context omitted.

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

“Avoid premature optimization” means to do the cleanest/clearest thing now, and only optimize later when you have the full picture. Arguably, that advice doesn’t apply to standard library functions anyway, at least not to the same extent. But if it did: How is adding a new, “bad” implementation any clearer than simply calling the already existing optimized one that the GP linked to?

You should optimize when it’s net useful, not just because you know how. Making a random function faster and harder to maintain is bad engineering if the speed isn’t useful.

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

#86

Post by doctor_eval »

verisimilitudes wrote: post #66
masto wrote: post #63

Earlier quoted context omitted.

I seem to recall one of go’s creators snapped back at a similar question about code duplication with “what’s the matter, are your fingers broken?” I think that sums up the philosophy, though maybe not as well as “Nothing was achieved here”, which I would like to translate into Latin and get on some stickers.

Quoted post unavailable.

Such a bizarre comment for a language designed - by the creator of Unix no less - to work well with tools and to be easily parsed. High likelihood it was posted from a Unix device too.

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

#87

Post by tsimionescu »

cookiengineer wrote: post #73
alcover wrote: post #60

Earlier quoted context omitted.

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

> - Is 1.2.3gamma > 1.2.3? Yes I wrote this example, because I knew the answer. And your interpretation (the same as my initial one) is wrong :) > Pre-release versions have a lower precedence than the associated normal version. [1] https://semver.org/#spec-item-9

1.2.3gamma is not a pre-release version, it is a malformed version string (assuming SemVer). A proper SemVer is something like [0-9]+[.][0-9]+[.][0-9]+(-[0-9a-zA-Z]+)?([+][0-9a-zA-Z]+)?

> 2. A normal version number MUST take the form X.Y.Z where X, Y, and Z are non-negative integers, and MUST NOT contain leading zeroes. X is the major version, Y is the minor version, and Z is the patch version.

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

#88

Post by rbehrends »

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…

> I never use three way string comparison, and so I wondered when other programmers use it.

Three-way comparisons show up naturally when doing a binary search or implementing binary trees.

Interestingly, the binary search implementation in the Go stdlib doesn't need it, but that's because it's only doing part of what you'd normally expect a binary search function to do and shifts the responsibility for the actual equality check to the caller [1].

[1] https://go.dev/src/sort/search.go

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

#89

Post by adwn »

philosopher1234 wrote: post #85
codeflo wrote: post #71

Earlier quoted context omitted.

“Avoid premature optimization” means to do the cleanest/clearest thing now, and only optimize later when you have the full picture. Arguably, that advice doesn’t apply to standard library functions anyway, at least not to the same extent. But if it did: How is adding a new, “bad” implementation any clearer than simply calling the already existing optimized one that the GP linked to?

You should optimize when it’s net useful, not just because you know how. Making a random function faster and harder to maintain is bad engineering if the speed isn’t useful.

> Making a random function faster and harder to maintain is bad engineering if the speed isn’t useful.

1) It's not some random function, it's part of the standard library.

2) Three-way string compares are far from uncommon, and string comparisons are relatively expensive. Therefore, a speedup would be useful.

Optimizing this function would not count as "premature".

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

#90

Post by adrian_b »

somekyle2 wrote: post #54
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…

This way of doing string comparisons does not seem to be the right one.

The obvious way of comparing strings is to do a comparison of the content for the minimum of their lengths (which should be computed in a branchless way), and that should be done in an optimized assembly loop, for which suitable SIMD instructions are available in most modern CPUs. In many C standard libraries the function memcmp already provides such an optimized implementation, which should be used for the comparison of strings of equal length.

Then, only when the result of the comparison is equal, the 2 string lengths are compared, to provide the final comparison result.

Therefore, when a good memcmp is already available, a string comparison consists of a minimum computation, a memcmp invocation and an optional integer comparison of the lengths.

Post reply on HN