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

#61

Post by somekyle2 » Thu, Oct 27, 2022, 4:28 AM UTC

kevingadd wrote: post #7

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

It was previously implemented as a special internal function 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.

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

#62

Post by snotrockets » Thu, Oct 27, 2022, 4:33 AM UTC

_AzMoo wrote: post #48

diceduckmonk wrote: post #44

Earlier quoted context omitted.

> it is designed to be friendly to enterprises who have to produce code Our two person engineering team has found this to be the ultimate form of user-friendliness as our goal is to pragmatically deliver software.

I think what they're saying is that you need more code in Go, which is inherently unfriendly to developers, to produce an equivalent output in other languages. And to a certain extent that is true, but it disregards the intangible benefits of Go, such as it's balance between simplicity and the ability to make it perform.

No. I'm rephrasing the design intent for the language, as outlined in various talks. For example, here: https://go.dev/talks/2012/splash.article

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

#63

Post by masto » Thu, Oct 27, 2022, 4:40 AM UTC

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…

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.

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

#64

Post by xmprt » Thu, Oct 27, 2022, 4:47 AM UTC

somekyle2 wrote: post #57

quelltext wrote: post #28

Earlier quoted context omitted.

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

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

#65

Post by raggi » Thu, Oct 27, 2022, 4:54 AM UTC

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

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

#66

Post by verisimilitudes » Thu, Oct 27, 2022, 5:07 AM UTC

masto wrote: post #63

quelltext wrote: post #28

Earlier quoted context omitted.

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…

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.

No post body was provided.

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

#67

Post by somekyle2 » Thu, Oct 27, 2022, 5:11 AM UTC

quelltext wrote: post #15

chrsig wrote: post #10

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.

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

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.

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

#68

Post by chrsig » Thu, Oct 27, 2022, 5:14 AM UTC

somekyle2 wrote: post #67

quelltext wrote: post #15

Earlier quoted context omitted.

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

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

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

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

#69

Post by masklinn » Thu, Oct 27, 2022, 5:16 AM UTC

irogers wrote: post #14

People try to get cute with 3-way compares. A real Java bug that inspired: 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 old…

But of course the real solution is to use a strong and composable type for your comparison result, rather than remove the entire thing because you originally designed the API wrong.

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

#70

Post by codeflo » Thu, Oct 27, 2022, 5:27 AM UTC

barsonme wrote: post #46

quelltext wrote: post #28

Earlier quoted context omitted.

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…

I think manual three-way comparisons are very clear. But so is strings.Compare. For better or worse, copying code is a pretty normal thing to do in Go. See "A little copying is better than a little dependency." [0] [0]: https://www.youtube.com/watch?v=PAAkCSZUG1c&t=9m28s&themeRef...

I even somewhat agree with that principle, but it don’t think it applies to using the standard library, which is (a) not little and (b) not a new dependency you add to the project.

If that’s the justification to keep an implementation bad on purpose (which I’m not sure is the actual intention, but is at least that’s what the referenced comment claims), then I’m not even sure I speak the same language as the people who made that decision.