13 ms·

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

175 points by tapirl 4y ago

ars 4y ago
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.
- recursive 4y ago
  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.
  - suprfsat 4y ago
    well the comment says it's faster to use the built-in string comparison operators ==, <, >, and so on. the reason it's faster is because the function is intentionally slow, but
  - ori_b 4y ago
    Sort only uses '<'.
  - travisby 4y ago
    Based on https://go-review.googlesource.com/c/go/+/3012?tab=comments 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 `bytes.Compare` version exists and is optimized (some assembly version, probably costly to maintain per arch?).
    - quelltext 4y ago
      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.
    - throwawayabcdef 4y ago
      https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f97ba43ae36df215a5 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?
- Nevermark 4y ago
  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!
Spivak 4y ago
I’m so confused? Why wouldn’t you make Compare fast and add the optimization? I’m sure someone will run into a logically equivalent to a 3-way compare situation that the compiler can’t detect. Hiding language features in optimization passes is a dangerous game. It’s one of the reasons I don’t like implicit tail calls.
- eru 4y ago
  At least tail calls are rather easy to detect purely syntactically. But yes, an annotation that forces the compiler to optimize them (or give you a warning or even error when unable to do so) can be useful.
kevingadd 4y ago
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 instead of optimized assembler, and then if users keep requesting it be optimized, at that point make the compiler improvements or write the hand-tuned assembler version. Otherwise what you're going to get is people using messy workarounds to do a 3-way compare, like doing a byte-wise compare that isn't unicode-correct. Blech.
- dhosek 4y ago
  Any sort that doesn’t take into account Unicode collation isn’t Unicode correct.
- somekyle2 4y ago
  It was previously implemented as a special internal function https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f97ba43ae36df215a5 https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9... So, making it a simple Go function was more work (at least, as an individual change) because they could've left it. A three-way compare in native Go would likely be slower in most cases than the "slow" version that exists there, because in actually equal or size varying cases the "slow" one gets sent directly to optimized platform-tuned assembly, and the other cases still end up with tuned multibyte comparison stuff that likely wouldn't be possible in the stock Go compiler without clever bounds check removal. A compiler that can make that three-way quite fast is desirable, and there are reasons to do that independent of that function, but even Rust uses unsafe and farms out to builtin tuned memcmp stuff for 3 way compare of strings. My theory is that strings.Compare _was_ known to be faster, and people starting preferring it because it was faster, and that in part prompted the change. Most engineers use a faster approach if available, even if it is a bit clunkier and not necessary (as this comment section shows, many folks are outraged at the idea of code not optimized for maximal performance). Encouraging bad use because a function is unintentionally faster than the naive thing is a bug in a stdlib.
quelltext 4y ago
> 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 a 3-way compare function anyway. Basically it's saying "don't use a function at all", or even "write your own copies of this function". Even if the compiler one day becomes smart enough to optimize you still end up with tons of code duplication if people followed the advice. And for people who care about performance it means they'll use a 3rd party library or implement their own "optimizations" that might not be effective or even buggy. Literally nobody is benefiting from this. What's the point of providing this function but actually thinking nobody should use it, in a comment no less instead of documentation? Now, there may be other reasons, e.g. the author thinking 3-way compare is a bad pattern in the first place. If argued well, maybe I could agree. But that argument isn't made here. I'm also not saying they needed to optimize this off the bat. A comment saying "we don't think there is a big demand yet, will optimize when we see the demand" would've been acceptable.
- thayne 4y ago
  > you still end up with tons of code duplication if people followed the advice. Code duplication is the go way
- skybrian 4y ago
  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.
  - quelltext 4y ago
    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.
chrsig 4y ago
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.
- quelltext 4y ago
  > 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.
  - somekyle2 4y ago
    If you're having trouble because generating a 3 way string compare in Go isn't fast enough and delegating to bytes is hard to get correct, my recommendation would be to file an issue with Go. It's not difficult for them to make strings.Compare faster, and I imagine real world evidence that it'd be substantially helpful would be enough to motivate it. Though, if 3 way compare is the bottleneck, it seems like a real possibility that there are algorithmic optimizations that may be more effective than a faster 3 way compare, like using native comparison operators, hashing, using byte slices, etc. Or maybe not; I don't think I've seen a case where it's a bottleneck so I might be inaccurately imagining the cases where it'd happen.
    - chrsig 4y ago
      > my recommendation would be to file an issue with Go. It's not difficult for them to make strings.Compare faster, and I imagine real world evidence that it'd be substantially helpful would be enough to motivate it. I agree. Squeaky wheel gets the grease.
jbverschoor 4y ago
What I don’t understand is that they doing first check for lengths Strings are so common, it’s insane they don’t optimize
- tylerhou 4y ago
  Wouldn't the normal implementation for == check lengths? Edit: Never mind, it doesn't: https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03eb3d15ffbfc0b4/src/internal/bytealg/compare_generic.go 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.
  - orlp 4y ago
    > 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. Only for a three-way comparison. If all you care about is equality different lengths gives a fast path for inequality.
- somekyle2 4y ago
  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.
  - jbverschoor 4y ago
irogers 4y ago
People try to get cute with 3-way compares. A real Java bug that inspired: https://errorprone.info/bugpattern/BadComparable 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-compareto-why-use-comparison-vs-subtraction 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.
- Dylan16807 4y ago
  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.
  - scotty79 4y ago
    What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?
    - slaymaker1907 4y ago
      It could or for integer types less than 4 bytes. For integers, while I don't think Java has this built in, you could use saturating subtraction (so it goes to INT_MIN or something on underflow).
    - Dylan16807 4y ago
      For this situation you want it to saturate. Clamp the value between int_min and int_max.
    - wiml 4y ago
whateveracct 4y ago
I hate paternalistic non-optimization like this. Just optimize it - your code sucks and you should improve it!
jrockway 4y ago
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)) < 0 }), ... 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 < (it does more stuff), and yet people are somehow baited into writing it. I'm guessing what happens is that people don't know that "<" works for strings, and they reach for strings.Compare, so the documentation is trying to talk them out of a program that doesn't actually make sense. In the case of "!= 0", they just wanted "s0 != name", which I take to mean they had absolutely no idea that strings in Go are comparable at all. 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 < 0 } return sortedFiles[i].DefName < sortedFiles[j].DefName }) 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 < xs[j].Path } return xs[i].DefName < xs[j].DefName Another correct use was in "goja" (a Javascript interpreter), which uses strings.Compare to implement Javascript's <string>.compareTo(<string>). Whether or not Javascript code is using compareTo correctly is an analysis I do not have the energy to do :)
- Dylan16807 4y ago
  > This is exceedingly interesting to me because you'd expect Compare to cost more than < (it does more stuff), and yet people are somehow baited into writing it. 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.
dhosek 4y ago
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.
- eru 4y ago
  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.
  - codedokode 4y ago
    Then you can use bytewise comparison instead of alphabetic comparison.
    - snotrockets 4y ago
      Assuming you normalized the strings before.
      - simiones 4y ago
        Why would that matter, if you only want some well-defined order?
        snotrockets 4y ago
        Because with (Unicode) strings, "\u006e\u0303" is defined to be equal to "\u00f1", for example. If you'd do bytewise comparison, as the above comment suggested, you may not reach the same result ¯\_(ツ)_/¯
        simiones 4y ago
        Whether those two strings are or are not equivalent depends on the context. If we're assuming (as the GP did) a very generic context where we simply want to store arbitrary strings in a sorted data structure, then there is no reason to assume they are supposed to be interpreted as Unicode. For a simple example, perhaps this is a list of strings that require Unicode normalization to be properly interpreted as human text that you are storing into a TreeMap for efficient retrieval. When you are adding "\u00f1" to the list, you wouldn't want the collection to say that it's already there because it already had "\u006e\u0303".
userbinator 4y ago
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.
- mplewis 4y ago
  No one will follow along. If you want to implement strings.Compare better, you can write a package and publish it for other folks to import. The function is not particularly special.
  - userbinator 4y ago
    No one will follow along. "The only sure path to failure is to not even try." Or are you both implying the power of and supporting the massive monopoly that Google already has?
    - TillE 4y ago
      Encouraging people to use a different language entirely (Rust, whatever) is much much more likely to succeed than getting them to use some random Go fork.
    - robertlagrant 4y ago
      > Or are you both implying the power of and supporting the massive monopoly that Google already has? This is not a reasonable assessment. Golang is massive; why would anyone switch to not-Golang which isn't backed by a large organisation and just has one string comparison optimisation? And why would anyone trust a forking entity that forked a runtime to make a change that could be packaged as a library, as the comment you're replying to already suggests?
- somekyle2 4y ago
  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.
esprehn 4y ago
The optimal version does seem to exist here (per the comment too): https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03eb3d15ffbfc0b4/src/internal/bytealg/compare_generic.go#L39 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?
- smt88 4y ago
  > "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.
  - somekyle2 4y ago
    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.
    - codeflo 4y ago
      “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?
Lvl999Noob 4y ago
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.
raggi 4y ago
You could type all six lines, or you could link the runtime func and yolo.
philosopher1234 4y ago
The go designers are brilliant. This is exactly the right priority. We would all do better it think more the way they do.
- lamp987 4y ago
  This was a joke right?
  - philosopher1234 4y ago
    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.
    - frou_dh 4y ago
      It's amusing to mention clarity, given the topic. Because the cargo-cult of this kind of function having return type 'int' is lack of clear thinking manifest. Int has 4-billion distinct values and all they want is three. Here's clarity: datatype order https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.order:TY https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.o... function compare https://smlfamily.github.io/Basis/string.html#SIG:STRING.compare:VAL https://smlfamily.github.io/Basis/string.html#SIG:STRING.com... case String.compare(a, b) of | LESS => ... | EQUAL => ... | GREATER => ...
smasher164 4y ago
Another option is to use `go:linkname` and call the runtime function yourself. //go:linkname cmpstring runtime.cmpstring func cmpstring(a, b string)
daviddever23box 4y ago
The premise that three-way string comparisons are widely used is spurious at best.
- tapirl 4y ago
  Evidences are provided in the article: https://sourcegraph.com/search?q=context:global+switch+strings.Compare+lang:Go+&patternType=literal https://sourcegraph.com/search?q=context:global+switch+strin...
  - daviddever23box 4y ago
    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.
    - tapirl 4y ago
      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.
bilekas 4y ago
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 http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf
- iainmerrick 4y ago
  It's not three-way as in comparing three strings; here they're comparing two strings, with a "three-way" result: a<b, a==b, a>b
  - bilekas 4y ago
    Okay that makes a bit more sense, I was sure something wasn't registering right with me reading it.
beeforpork 4y ago
Go spaceship!
insanitybit 4y ago
This is just Go's philosophy of "we're delivering a language for bad programmers, we know what's best for them".
- philosopher1234 4y ago
  They're allowing devs to resist foolish performance pressure. This is a language for good developers, built by good designers.
johndfsgdgdfg 4y ago
Well, it was desgined by Google. What did you expect?
- seanw444 4y ago
  Google generally engineers their stuff well. I don't like them much either, but calling them incompetent at building a very popular language, to which their reputation is attached and at risk, is rather presumptuous.
Someone 4y ago
When I look at https://go.godbolt.org/z/8jqMPh135 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.
- gnfargbl 4y ago
  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 < b 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 the issue.
  - Someone 4y ago
    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.
    - gnfargbl 4y ago
      Ah, this confuses everyone: strings in Golang are really just read-only byte slices. They can contain Unicode, but they don't have to, and the == operator just does a byte comparison.

175 points by tapirl 4y ago

ars 4y ago

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.

recursive 4y ago
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.
- suprfsat 4y ago
  well the comment says it's faster to use the built-in string comparison operators ==, <, >, and so on. the reason it's faster is because the function is intentionally slow, but
- ori_b 4y ago
  Sort only uses '<'.
- travisby 4y ago
  Based on https://go-review.googlesource.com/c/go/+/3012?tab=comments 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 `bytes.Compare` version exists and is optimized (some assembly version, probably costly to maintain per arch?).
  - quelltext 4y ago
    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.
  - throwawayabcdef 4y ago
    https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f97ba43ae36df215a5 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?
Nevermark 4y ago
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!

Spivak 4y ago

I’m so confused? Why wouldn’t you make Compare fast and add the optimization? I’m sure someone will run into a logically equivalent to a 3-way compare situation that the compiler can’t detect. Hiding language features in optimization passes is a dangerous game. It’s one of the reasons I don’t like implicit tail calls.

eru 4y ago
At least tail calls are rather easy to detect purely syntactically. But yes, an annotation that forces the compiler to optimize them (or give you a warning or even error when unable to do so) can be useful.

kevingadd 4y ago

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 instead of optimized assembler, and then if users keep requesting it be optimized, at that point make the compiler improvements or write the hand-tuned assembler version. Otherwise what you're going to get is people using messy workarounds to do a 3-way compare, like doing a byte-wise compare that isn't unicode-correct. Blech.

dhosek 4y ago
Any sort that doesn’t take into account Unicode collation isn’t Unicode correct.
somekyle2 4y ago
It was previously implemented as a special internal function https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f97ba43ae36df215a5 https://github.com/golang/go/commit/fd4dc91a96518fdbb47781f9... So, making it a simple Go function was more work (at least, as an individual change) because they could've left it. A three-way compare in native Go would likely be slower in most cases than the "slow" version that exists there, because in actually equal or size varying cases the "slow" one gets sent directly to optimized platform-tuned assembly, and the other cases still end up with tuned multibyte comparison stuff that likely wouldn't be possible in the stock Go compiler without clever bounds check removal. A compiler that can make that three-way quite fast is desirable, and there are reasons to do that independent of that function, but even Rust uses unsafe and farms out to builtin tuned memcmp stuff for 3 way compare of strings. My theory is that strings.Compare _was_ known to be faster, and people starting preferring it because it was faster, and that in part prompted the change. Most engineers use a faster approach if available, even if it is a bit clunkier and not necessary (as this comment section shows, many folks are outraged at the idea of code not optimized for maximal performance). Encouraging bad use because a function is unintentionally faster than the naive thing is a bug in a stdlib.

quelltext 4y ago

> 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 a 3-way compare function anyway. Basically it's saying "don't use a function at all", or even "write your own copies of this function". Even if the compiler one day becomes smart enough to optimize you still end up with tons of code duplication if people followed the advice. And for people who care about performance it means they'll use a 3rd party library or implement their own "optimizations" that might not be effective or even buggy. Literally nobody is benefiting from this. What's the point of providing this function but actually thinking nobody should use it, in a comment no less instead of documentation? Now, there may be other reasons, e.g. the author thinking 3-way compare is a bad pattern in the first place. If argued well, maybe I could agree. But that argument isn't made here. I'm also not saying they needed to optimize this off the bat. A comment saying "we don't think there is a big demand yet, will optimize when we see the demand" would've been acceptable.

thayne 4y ago
> you still end up with tons of code duplication if people followed the advice. Code duplication is the go way
skybrian 4y ago
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.
- quelltext 4y ago
  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.

chrsig 4y ago

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.

quelltext 4y ago
> 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.
- somekyle2 4y ago
  If you're having trouble because generating a 3 way string compare in Go isn't fast enough and delegating to bytes is hard to get correct, my recommendation would be to file an issue with Go. It's not difficult for them to make strings.Compare faster, and I imagine real world evidence that it'd be substantially helpful would be enough to motivate it. Though, if 3 way compare is the bottleneck, it seems like a real possibility that there are algorithmic optimizations that may be more effective than a faster 3 way compare, like using native comparison operators, hashing, using byte slices, etc. Or maybe not; I don't think I've seen a case where it's a bottleneck so I might be inaccurately imagining the cases where it'd happen.
  - chrsig 4y ago
    > my recommendation would be to file an issue with Go. It's not difficult for them to make strings.Compare faster, and I imagine real world evidence that it'd be substantially helpful would be enough to motivate it. I agree. Squeaky wheel gets the grease.

jbverschoor 4y ago

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

tylerhou 4y ago
Wouldn't the normal implementation for == check lengths? Edit: Never mind, it doesn't: https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03eb3d15ffbfc0b4/src/internal/bytealg/compare_generic.go 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.
- orlp 4y ago
  > 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. Only for a three-way comparison. If all you care about is equality different lengths gives a fast path for inequality.
somekyle2 4y ago
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.
- jbverschoor 4y ago

irogers 4y ago

People try to get cute with 3-way compares. A real Java bug that inspired: https://errorprone.info/bugpattern/BadComparable 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-compareto-why-use-comparison-vs-subtraction 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.

Dylan16807 4y ago
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.
- scotty79 4y ago
  What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?
  - slaymaker1907 4y ago
    It could or for integer types less than 4 bytes. For integers, while I don't think Java has this built in, you could use saturating subtraction (so it goes to INT_MIN or something on underflow).
  - Dylan16807 4y ago
    For this situation you want it to saturate. Clamp the value between int_min and int_max.
  - wiml 4y ago

whateveracct 4y ago

I hate paternalistic non-optimization like this. Just optimize it - your code sucks and you should improve it!

jrockway 4y ago

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)) < 0 }), ... 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 < (it does more stuff), and yet people are somehow baited into writing it. I'm guessing what happens is that people don't know that "<" works for strings, and they reach for strings.Compare, so the documentation is trying to talk them out of a program that doesn't actually make sense. In the case of "!= 0", they just wanted "s0 != name", which I take to mean they had absolutely no idea that strings in Go are comparable at all. 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 < 0 } return sortedFiles[i].DefName < sortedFiles[j].DefName }) 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 < xs[j].Path } return xs[i].DefName < xs[j].DefName Another correct use was in "goja" (a Javascript interpreter), which uses strings.Compare to implement Javascript's <string>.compareTo(<string>). Whether or not Javascript code is using compareTo correctly is an analysis I do not have the energy to do :)

Dylan16807 4y ago
> This is exceedingly interesting to me because you'd expect Compare to cost more than < (it does more stuff), and yet people are somehow baited into writing it. 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.

dhosek 4y ago

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.

eru 4y ago
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.
- codedokode 4y ago
  Then you can use bytewise comparison instead of alphabetic comparison.
  - snotrockets 4y ago
    Assuming you normalized the strings before.
    - simiones 4y ago
      Why would that matter, if you only want some well-defined order?
      - snotrockets 4y ago
        Because with (Unicode) strings, "\u006e\u0303" is defined to be equal to "\u00f1", for example. If you'd do bytewise comparison, as the above comment suggested, you may not reach the same result ¯\_(ツ)_/¯
        simiones 4y ago
        Whether those two strings are or are not equivalent depends on the context. If we're assuming (as the GP did) a very generic context where we simply want to store arbitrary strings in a sorted data structure, then there is no reason to assume they are supposed to be interpreted as Unicode. For a simple example, perhaps this is a list of strings that require Unicode normalization to be properly interpreted as human text that you are storing into a TreeMap for efficient retrieval. When you are adding "\u00f1" to the list, you wouldn't want the collection to say that it's already there because it already had "\u006e\u0303".

userbinator 4y ago

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.

mplewis 4y ago
No one will follow along. If you want to implement strings.Compare better, you can write a package and publish it for other folks to import. The function is not particularly special.
- userbinator 4y ago
  No one will follow along. "The only sure path to failure is to not even try." Or are you both implying the power of and supporting the massive monopoly that Google already has?
  - TillE 4y ago
    Encouraging people to use a different language entirely (Rust, whatever) is much much more likely to succeed than getting them to use some random Go fork.
  - robertlagrant 4y ago
    > Or are you both implying the power of and supporting the massive monopoly that Google already has? This is not a reasonable assessment. Golang is massive; why would anyone switch to not-Golang which isn't backed by a large organisation and just has one string comparison optimisation? And why would anyone trust a forking entity that forked a runtime to make a change that could be packaged as a library, as the comment you're replying to already suggests?
somekyle2 4y ago
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.

esprehn 4y ago

The optimal version does seem to exist here (per the comment too): https://github.com/golang/go/blob/d28bf6c9a2ea9b992796738d03eb3d15ffbfc0b4/src/internal/bytealg/compare_generic.go#L39 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?

smt88 4y ago
> "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.
- somekyle2 4y ago
  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.
  - codeflo 4y ago
    “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?

Lvl999Noob 4y ago

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.

raggi 4y ago

You could type all six lines, or you could link the runtime func and yolo.

philosopher1234 4y ago

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

lamp987 4y ago
This was a joke right?
- philosopher1234 4y ago
  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.
  - frou_dh 4y ago
    It's amusing to mention clarity, given the topic. Because the cargo-cult of this kind of function having return type 'int' is lack of clear thinking manifest. Int has 4-billion distinct values and all they want is three. Here's clarity: datatype order https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.order:TY https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.o... function compare https://smlfamily.github.io/Basis/string.html#SIG:STRING.compare:VAL https://smlfamily.github.io/Basis/string.html#SIG:STRING.com... case String.compare(a, b) of | LESS => ... | EQUAL => ... | GREATER => ...

smasher164 4y ago

Another option is to use `go:linkname` and call the runtime function yourself. //go:linkname cmpstring runtime.cmpstring func cmpstring(a, b string)

daviddever23box 4y ago

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

tapirl 4y ago
Evidences are provided in the article: https://sourcegraph.com/search?q=context:global+switch+strings.Compare+lang:Go+&patternType=literal https://sourcegraph.com/search?q=context:global+switch+strin...
- daviddever23box 4y ago
  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.
  - tapirl 4y ago
    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.

bilekas 4y ago

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 http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

iainmerrick 4y ago
It's not three-way as in comparing three strings; here they're comparing two strings, with a "three-way" result: a<b, a==b, a>b
- bilekas 4y ago
  Okay that makes a bit more sense, I was sure something wasn't registering right with me reading it.

beeforpork 4y ago

Go spaceship!

insanitybit 4y ago

This is just Go's philosophy of "we're delivering a language for bad programmers, we know what's best for them".

philosopher1234 4y ago
They're allowing devs to resist foolish performance pressure. This is a language for good developers, built by good designers.

johndfsgdgdfg 4y ago

Well, it was desgined by Google. What did you expect?

seanw444 4y ago
Google generally engineers their stuff well. I don't like them much either, but calling them incompetent at building a very popular language, to which their reputation is attached and at risk, is rather presumptuous.

Someone 4y ago

When I look at https://go.godbolt.org/z/8jqMPh135 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.

gnfargbl 4y ago
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 < b 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 the issue.
- Someone 4y ago
  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.
  - gnfargbl 4y ago
    Ah, this confuses everyone: strings in Golang are really just read-only byte slices. They can contain Unicode, but they don't have to, and the == operator just does a byte comparison.