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

31–40 of 62 posts

Re: Faster Sorting with Go Generics

#31

Post by klabb3 »

tedunangst wrote: post #4

> The first thing to note is that there is no dynamic dispatch to the Less method. Each loop iteration invokes cmpstring directly. Except about 95% of the arrays I sort aren't comparable with just <. It's less clear how the unmentioned sort.Slice() will improve.

My understanding is that pointer types all use dynamic dispatch in practice, because they share the same "gcshape" under the hood, today. Obviously this is very coarse grained.

However, the article points out this will likely change in the future, since the compiler now has enough information to do so. The Go team made a good call imo resisting to optimize this. Now, they can observe how generics are used in the global Go community and then optimize using real world code.

In fact, optimize is an understatement, because dyn dispatch vs monomorphization is a trade-off between compilation time + binary size vs speed (as C++ and Rust programmers know too well). Optimizing early based on microbenchmarks would likely have given an advantage in favor of monomorphization, but may not be suitable for average-to-large binaries in the a generic-heavy future. I assume the team wants to find a good balance for the 99%, and avoid compiler flags, hint-syntax, profile guided optimizations and so on if they can..

Re: Faster Sorting with Go Generics

#32

Post by mjburgess »

mjburgess wrote: post #20
ljloisnflwef wrote: post #10

Earlier quoted context omitted.

I encourage you to explore why generics exist in the first place by exploring topics such as Parametric Polymorphism, Higher Kinded Types, & Higher Kinded Polymorphism. The truth will set you free.

Better to start with the problem than the most abstract formulation of its solution-- which only makes sense after successive encounters with ever more complex problems. Simply, of course, we can begin with why it should be that data structures have operations in common -- rather than, say, having each their own specific versions.

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 in the application-domain of "appending" whilst in the programming domain of "+"ing if we introduce an interface for `+`, that of "appendable",

    interface Appendable[A] {
      A + A -> A
      A + 0 -> A
    }
This interface allows us to use `+` generically in a principled way, the technical name for Appendable is `Monoid`, but i prefer Appendable (incidentally, Monad is `Sequencable` or `Nestable`).

Polymorphism is just the ability to speak as generically in the programming-domain as we speak in the application domain, ie., to use the double-meanings of ordinary thinking in programming.

Re: Faster Sorting with Go Generics

#33

Post by tialaramex »

rventure wrote: post #17
dilap wrote: post #14

Earlier quoted context omitted.

Yeah Go is all about "simple, fast enough , compiles fast" So I'd say knobs to control this, which, if you get them wrong, lead to slow compiles, would defnly be contra the spirit of Go. And in cases where absolute max performance really matters, nothing is stopping you from monomorphizin by hand. (But if absolute max perf really matters, you probably picked the wrong language.)

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!

Re: Faster Sorting with Go Generics

#34

Post by tedunangst »

eliben wrote: post #29
tedunangst wrote: post #4

> The first thing to note is that there is no dynamic dispatch to the Less method. Each loop iteration invokes cmpstring directly. Except about 95% of the arrays I sort aren't comparable with just <. It's less clear how the unmentioned sort.Slice() will improve.

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.

Re: Faster Sorting with Go Generics

#35

Post by esprehn »

mirceal wrote: post #23
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).

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

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.

Re: Faster Sorting with Go Generics

#36

Post by esprehn »

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!

Spin showed up on HN recently as an interesting example of Go vs Rust hello world:

(Rust) https://spin.fermyon.dev/ Vs (Go) https://spin.fermyon.dev/go-components/

The Go example seems a lot simpler without the Ok/Some/.into()/? That are unrelated to sending hello world. There's also no macro magic to understand.

In general my observation is the ancillary stuff (and in general number of things you need to understand) is greater in rust. That's paired of course with greater expressivity.

Re: Faster Sorting with Go Generics

#37

Post by socialdemocrat »

mirceal wrote: post #23
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).

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 and was pleasantly surprised by how much more compact Go code ended up being while also being easy to read and using fairly simple constructs.

You can often get smaller Java and C# code but at the expense of using far more complex and abstract concepts.

There is a sense of good balanced taste in how Go featured and libraries are made which often lacks in many other languages.

Re: Faster Sorting with Go Generics

#38

Post by avgcorrection »

esprehn wrote: post #35
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!

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.

> To be fair in rust you get to write .into() or Ok a lot.

Sure. If “fair” means “not comparable at all”.

if-condition-return using two variables is not comparable to one function/macro call.

Re: Faster Sorting with Go Generics

#39

Post by mustache_kimono »

esprehn wrote: post #36
tialaramex wrote: post #33

Earlier quoted context omitted.

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!

Spin showed up on HN recently as an interesting example of Go vs Rust hello world: (Rust) https://spin.fermyon.dev/ Vs (Go) https://spin.fermyon.dev/go-components/ The Go example seems a lot simpler without the Ok/Some/.into()/? That are unrelated to sending hello world. There's also no macro magic to understand. In general my observation is the ancillary stuff (and in general number of things you need to understand)…

I've never really understood why the lack of Result/Option types are somehow spun as a good thing. Other things about Rust can be complex and can require some diligence to learn, but Result/Option types over golang's way of handling the same thing? Seriously? That's the argument for golang?

Re: Faster Sorting with Go Generics

#40

Post by tialaramex »

esprehn wrote: post #36
tialaramex wrote: post #33

Earlier quoted context omitted.

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!

Spin showed up on HN recently as an interesting example of Go vs Rust hello world: (Rust) https://spin.fermyon.dev/ Vs (Go) https://spin.fermyon.dev/go-components/ The Go example seems a lot simpler without the Ok/Some/.into()/? That are unrelated to sending hello world. There's also no macro magic to understand. In general my observation is the ancillary stuff (and in general number of things you need to understand)…

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 the chosen APIs are of course not the same in Go and Rust.

The Go API (from net/http) follows typical Go style, it assumes success, and doesn't worry too much about errors. If you write any data to the ResponseWriter (which this example does), you get a 200 OK response anyway. You don't need to set types, it'll guess, likewise you don't need to care about binary data, it'll guess. This is cheerful and will mostly work, if it doesn't work you can probably learn what you did wrong and try again.

The Rust API (from the http crate) follows more typical Rust style. You must say whether you succeeded with Ok, so that failures can be handled appropriately. You can choose whether your response has a body we do have a body here so hence we need to write Some. Finally HTTP bodies are binary data, and we'd like to return a string, so we use the Into trait to get the UTF-8 encoded text out of the string as bytes, this is how Rust stores strings anyway so it will be trivial.

The Rust code sets header "foo" to "bar" for some reason, and also prints (to console) all the information about the request, presumably because that's trivial to do in Rust, the Go code doesn't do either of these things.

I agree that there certainly is a lot more Rust, it's just that I'd say it's beautiful rather than ugly, a matter of opinion.

Post reply on HN