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

31–40 of 154 posts

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

#31

Post by coding123 »

Dylan16807 wrote: post #27
jrockway wrote: post #25

Earlier quoted context omitted.

Yeah. To me, I just think it's weird to ask for two pieces of information and then throw one of them away. Sometimes it's not a performance hit, but I feel like it's one of those things where you should get a feeling "I might be doing this wrong". But if you don't know that < exists (and obviously searched for strings.Less), then you won't get that feeling. That's what I find so fascinating; if other people's feeling…

I don't see it as two pieces of information. It's returning one idea either way, but the tri-state tells you more than a boolean.

But that is more useful, we should agree, for implementing binary trees or sorting algorithms.

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

#32

Post by eru »

Spivak wrote: post #3

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.

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.

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

#33

Post by userbinator »

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.

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

#34

Post by scotty79 »

Dylan16807 wrote: post #21
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…

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.

What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?

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

#35

Post by jrockway »

quelltext wrote: post #26
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…

> so the documentation is trying to talk them out of... What documentation though? There's an internal comment but it's not documentation and it's not really arguing against the use of this type of comparison (just against use of the implemented function). If the documentation for this function went on along the lines of "we discourage the use of 3 way compares as we consider it an antipattern, do X instead, there's…

> What documentation though?

Yeah, sorry about that. I read the actual documentation and nothing is mentioned. I realized later on in my comment though ;)

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

#36

Post by slaymaker1907 »

scotty79 wrote: post #34
Dylan16807 wrote: post #21

Earlier quoted context omitted.

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.

What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?

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

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

#37

Post by Dylan16807 »

scotty79 wrote: post #34
Dylan16807 wrote: post #21

Earlier quoted context omitted.

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.

What's the right conversion in this case? How to narrow down negative long to negative int without loosing a sign?

For this situation you want it to saturate. Clamp the value between int_min and int_max.

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

#38

Post by mplewis »

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.

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.

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

#39

Post by snotrockets »

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…

No post body was provided.

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

#40

Post by snotrockets »

codedokode wrote: post #30
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.

Then you can use bytewise comparison instead of alphabetic comparison.

Assuming you normalized the strings before.
Post reply on HN