Strings are so common, it’s insane they don’t optimize
No safe efficient ways to do three-way string comparisons in Go
11–20 of 154 posts
Re: No safe efficient ways to do three-way string comparisons in Go
#12Ideological 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.
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
#13Earlier 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 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
#14public 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
#15I 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.
...and thus very likely end up with buggy code.
Re: No safe efficient ways to do three-way string comparisons in Go
#16What I don’t understand is that they doing first check for lengths Strings are so common, it’s insane they don’t optimize
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
#17Re: No safe efficient ways to do three-way string comparisons in Go
#18I 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
#19Re: No safe efficient ways to do three-way string comparisons in Go
#20Really 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…