Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster Sorting with Go Generics

eli.thegreenplace.net

Post reply on HN
Print view View original

51–60 of 62 posts

Re: Faster Sorting with Go Generics

#51

Post by mustache_kimono »

tialaramex wrote: post #33
rventure wrote: post #17

Earlier quoted context omitted.

There is no language that writes code as beautiful code as go, at a lower level. C comes close, but C++/Rust are plain ugly, while C is older than some HN users and requires a lot of third-party dependencies for basic operations (e.g http requests).

Beauty is of course necessarily in the eye of the beholder, but Rust doesn't look ugly to me. One of the first things that jumps out is how little boiler plate Rust's canonical Hello World program has, Go doesn't do badly here either (certainly compared to C, C++ or Java), but it does introduce a bunch of ancillary stuff like packages and importing that are peripheral to our purpose in writing Hello, World!

> Beauty is of course necessarily in the eye of the beholder

This is so true. Not is disparage other languages, but golang isn't beautiful to me at all, and neither is python. Yet Rust is nearly perfect. I'm strange. I get it!

Re: Faster Sorting with Go Generics

#52

Post by eliben »

tedunangst wrote: post #34
eliben wrote: post #29

Earlier quoted context omitted.

The change mentioned at the top of the post ( https://go-review.googlesource.com/c/exp/+/378134 ) also has a benchmark to compare sorting structs using sort.Slice vs a new generic approach that uses a comparison function: name old time/op new time/op delta SortStructs-8 18.6ms ± 2% 15.9ms ± 3% -14.43% (p=0.000 n=10+10) 14.4% is the speedup of the generic version. The article explains why this happens (towards the end…

Unsolicited commentary: I think my commitment to a thorough reading was limited by my interest in the performance of bubble sort. On the other hand, the code for sort.Search also fits in a blog post, and it's a function I have called inside a loop.

That's a good point, thank you for bringing it up. Finding the right examples is really tricky. sort.Search is binary search and hence a bit tricky to benchmark properly because of how ridiculously fast it is. Only a handful of comparison calls are made even for huge slices.

Re: Faster Sorting with Go Generics

#53

Post by codebje »

jhgb wrote: post #41
mjburgess wrote: post #32

Earlier quoted context omitted.

Why not elaborate some more? I'm bored, so... 2 + 2 == 4 "Hello" + "World" == "Hello World" [2, 2] + [3, 4] == [2, 2, 3, 4] Should we bother reusing `+` for this? Why not, 2 intPlus 2 == 4 "Hello" strPlus "World" == "Hello World" [2, 2] arrayPlus [3, 4] == [2, 2, 3, 4] Well: the polymorphism `+` allows us to express a common idea, that of "appending". For each of these specific types: int, string, array we can speak…

Yours is a beautiful example of how to shoot yourself in the foot with reckless generalization. Addition of integers is commutative; concatenation of strings is not. That's not "a common idea". Compilers can transform a+b into b+a for one, if it suits them, but not for the other.

While integers with addition are an additive monoid and thus commutable it's still also a valid multiplicative monoid (or semigroup as described in the parent) and handy to be able to be passed to code that just needs an associative closed operation, maybe with an identity value.

Integer addition is a magma, semigroup, monoid, and group. It's _also_ a commutative version of each of those structures, but we can still definitely use it with functions only expecting multiplicative structures just fine.

The issue I take with using + for a multiplicative monoid like string concatenation is that readers of code should expect it to be commutative. Using x or * is probably better, using ⓧ is mathematically nice but a pain to type, so something like ++, , .., or some other new operator just for concatenation is imo best.

Re: Faster Sorting with Go Generics

#54

Post by mirceal »

socialdemocrat wrote: post #37
mirceal wrote: post #23

Earlier quoted context omitted.

if err != nil { return nil, err } code poetry right there. it's so good that you have to repeat this over and over again!

It sucks a bit, but I find the tradeoff quite good. The Go folks have managed to make a language which is quite low level and with a small fairly transparent feature set which still manages to produce code which is not too verbose. Java and C# for instance despite being much higher level languages tend to require far more verbose code. I have played with some crypto code and concurrency in all languages to compare an…

i think go (as any other language) shines in some use cases, is meh in some use cases and straight-up sucks in others. the problem i'm seeing is the cargo cult where basically go is the ultimate answer and everything has to be rewritten in it.

Re: Faster Sorting with Go Generics

#55

Post by mcronce »

maleldil wrote: post #43
esprehn wrote: post #35

Earlier quoted context omitted.

To be fair in rust you get to write .into() or Ok a lot. I do find Go's error handling annoying but rust seems similar for line noise. It's more compact noise, but it's all there.

Those are for the cases where you're creating or transforming an error. In those scenarios, Go's handling isn't that bad. The issue is having to write `if err != nil { return nil, err }` versus `func()?`. The former gets old really fast. Not to mention the other benefits of monadic error handling when compared to glorified error codes.

Even transforming an error is taken care of by ?

func()? desugars to (more or less)

    match func() {
        Ok(v) => v,
        Err(e) => return Err(e.into())
    }
I'm also not really sure what the complaint is. Go doesn't do any more implicit type conversion than Rust does. There are numerous solid arguments for Go over Rust, but error handling and automatic type punning aren't on the list.

Re: Faster Sorting with Go Generics

#56

Post by mjburgess »

jhgb wrote: post #41
mjburgess wrote: post #32

Earlier quoted context omitted.

Why not elaborate some more? I'm bored, so... 2 + 2 == 4 "Hello" + "World" == "Hello World" [2, 2] + [3, 4] == [2, 2, 3, 4] Should we bother reusing `+` for this? Why not, 2 intPlus 2 == 4 "Hello" strPlus "World" == "Hello World" [2, 2] arrayPlus [3, 4] == [2, 2, 3, 4] Well: the polymorphism `+` allows us to express a common idea, that of "appending". For each of these specific types: int, string, array we can speak…

Yours is a beautiful example of how to shoot yourself in the foot with reckless generalization. Addition of integers is commutative; concatenation of strings is not. That's not "a common idea". Compilers can transform a+b into b+a for one, if it suits them, but not for the other.

I'm not sure I see the reckless generalisation. I said `+` meant append, not add. We can use addition in the case of integers to serve as `append`, but its a special case of appending where A+B == B+A.

In python, where I take the example, `+` performs that role,

    [a() + a() for a in (str, bool, int, list, tuple)]
etc.

Re: Faster Sorting with Go Generics

#57

Post by mjburgess »

codebje wrote: post #53
jhgb wrote: post #41

Earlier quoted context omitted.

Yours is a beautiful example of how to shoot yourself in the foot with reckless generalization. Addition of integers is commutative; concatenation of strings is not. That's not "a common idea". Compilers can transform a+b into b+a for one, if it suits them, but not for the other.

While integers with addition are an additive monoid and thus commutable it's still also a valid multiplicative monoid (or semigroup as described in the parent) and handy to be able to be passed to code that just needs an associative closed operation, maybe with an identity value. Integer addition is a magma, semigroup, monoid, and group. It's _also_ a commutative version of each of those structures, but we can still…

As above, I was thinking of python in my choice of the `+` example.

Re: Faster Sorting with Go Generics

#58

Post by morelisp »

jhgb wrote: post #41
mjburgess wrote: post #32

Earlier quoted context omitted.

Why not elaborate some more? I'm bored, so... 2 + 2 == 4 "Hello" + "World" == "Hello World" [2, 2] + [3, 4] == [2, 2, 3, 4] Should we bother reusing `+` for this? Why not, 2 intPlus 2 == 4 "Hello" strPlus "World" == "Hello World" [2, 2] arrayPlus [3, 4] == [2, 2, 3, 4] Well: the polymorphism `+` allows us to express a common idea, that of "appending". For each of these specific types: int, string, array we can speak…

Yours is a beautiful example of how to shoot yourself in the foot with reckless generalization. Addition of integers is commutative; concatenation of strings is not. That's not "a common idea". Compilers can transform a+b into b+a for one, if it suits them, but not for the other.

Addition of ints is associative, addition of floats is not, yet generalizing over these two numeric types is a core ability people expect from generics.

Re: Faster Sorting with Go Generics

#59

Post by kaba0 »

jhgb wrote: post #41
mjburgess wrote: post #32

Earlier quoted context omitted.

Why not elaborate some more? I'm bored, so... 2 + 2 == 4 "Hello" + "World" == "Hello World" [2, 2] + [3, 4] == [2, 2, 3, 4] Should we bother reusing `+` for this? Why not, 2 intPlus 2 == 4 "Hello" strPlus "World" == "Hello World" [2, 2] arrayPlus [3, 4] == [2, 2, 3, 4] Well: the polymorphism `+` allows us to express a common idea, that of "appending". For each of these specific types: int, string, array we can speak…

Yours is a beautiful example of how to shoot yourself in the foot with reckless generalization. Addition of integers is commutative; concatenation of strings is not. That's not "a common idea". Compilers can transform a+b into b+a for one, if it suits them, but not for the other.

Just a nit, for floats it is not commutative either, not sure how much freedom do compilers have here. E.g. try summing many floats in decreasing value - chances are that adding a very small number in the end will not even change the value.

Re: Faster Sorting with Go Generics

#60

Post by tialaramex »

esprehn wrote: post #48
tialaramex wrote: post #40

Earlier quoted context omitted.

Hmm. I think you intended to link: https://spin.fermyon.dev/rust-components/ What's nice about "Hello, World!" is that it's a canonical example where we know exactly what it's supposed to do, in contrast these pages are showing off features of writing Spin components in different languages so that makes it much harder to compare. In each case they're using a popular existing HTTP library for its familiar APIs, but th…

The link was the correct one, scroll down and you'll see a simple hello world example that matches what the golang one does.

On second glance I think that Rust example is needlessly verbose, which is fine if that's what you meant, but the Go doesn't do that.
Post reply on HN