Faster Sorting with Go Generics | Hacker News Reader

Faster Sorting with Go Generics

eli.thegreenplace.net

117 pointstodsacerdoti52 comments

I think what people often overlook when discussing generics in Go and code performance that uses generics, is that... the most important thing here is that the code that uses generic sort implementation is: 1. much shorter and more straightforward 2. actually type safe. Even if performance of such code is the same or a bit lower, it does not matter, because the main benefit is that you finally don't have to rely on interfaces (especially an empty one in case of sort.Slice) and have fewer possibilities of runtime panics thanks to that.

> Even if performance of such code is the same or a bit lower, it does not matter

I’m being somewhat pedantic, but that clearly depends on the application.

You have the freedom to not use generics when the application has stricter performance requirements.

Are there any good write ups on Go Generics vs other languages for those of us who are familiar with Go but do not write it on a day to day basis? I pick up Go every few months to try new things cause its infinitely easy to setup a web server in Go since it is built-in.

The FAQ has some good information: https://go.dev/doc/faq#generics_comparison and other sections around it

https://planetscale.com/blog/generics-can-make-your-go-code-... made the rounds a few days ago.

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.

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.

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

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.

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.

A nit's nit, float addition is commutative. It is not associative.

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.

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

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.

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

You'll still have a dynamic Less() equivalent - unless the sorting function gets inlined, which sounds unlikely. But sort.Slice() relies on reflection to do the swapping, which performs even worse than a call to a virtual Swap(). That would now be an ordinary index swap within the sort function. So you'll probably still see major speedups with bubbleSortFunc or some equivalent.

> You'll still have a dynamic Less() equivalent - unless the sorting function gets inlined, which sounds unlikely.

Sorting or ordering?

Using a custom comparator is covered later on, and shows that the ordering function (the custom comparator) is not inlined because of how Go 1.18 groups GC shapes.

However an article from a few days ago (https://planetscale.com/blog/generics-can-make-your-go-code-...) showed that it can be made to work, in some cases, by parametrising the function on the callback. This leads to the sorting function being monomorphised on the callback, and thus the callback (likely) getting inlined.

The article argues that even a function call to a “less” function benefits from the elimination of bounds checking.

> do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

Why choose? With generics we can have all three!

I LOL’d, but I think it’s a bit unfair. You can also have all three without generics.

Could you elaborate?

Wasn't templating something languages had in 80s?

Reply on news.ycombinator.com