7 ms·
Faster Sorting with Go Generics
- giancarlostoro 5y agoAre 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.
- eliben 5y agoThe FAQ has some good information: https://go.dev/doc/faq#generics_comparison https://go.dev/doc/faq#generics_comparison and other sections around it
- ljloisnflwef 5y agoI 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.
- mjburgess 5y agoBetter 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.
- mjburgess 5y agoWhy 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.
- jhgb 5y agoYours 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.
- codebje 5y agoWhile 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.
- mjburgess 5y agoAs above, I was thinking of python in my choice of the `+` example.
- mjburgess 5y agoI'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.
- morelisp 5y agoAddition of ints is associative, addition of floats is not, yet generalizing over these two numeric types is a core ability people expect from generics.
- masklinn 5y agohttps://planetscale.com/blog/generics-can-make-your-go-code-slower https://planetscale.com/blog/generics-can-make-your-go-code-... made the rounds a few days ago.
- tedunangst 5y ago> 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.
- morelisp 5y agoYou'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.
- masklinn 5y ago> 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-slower 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.
- deleted 5y ago[deleted]
- rmk 5y agoThe article argues that even a function call to a “less” function benefits from the elimination of bounds checking.
- eliben 5y agoThe change mentioned at the top of the post (https://go-review.googlesource.com/c/exp/+/378134 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).
- 0des 5y ago
- deleted 5y ago[deleted]
- Eratosthenes 5y ago> do you want slow programmers, slow compilers and bloated binaries, or slow execution times? Why choose? With generics we can have all three!
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- doctor_eval 5y agoI LOL’d, but I think it’s a bit unfair. You can also have all three without generics.
- konnichimade 5y agoCould you elaborate?
- ljloisnflwef 5y ago
- tester756 5y ago>we've already learned that Go doesn't respect your freedom given its license choice What do you mean?
- deleted 5y ago[deleted]
- dilap 5y agoYeah 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.)
- rventure 5y agoThere 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).
- nasretdinov 5y agoI 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.
- glouwbug 5y agoWasn't templating something languages had in 80s?
- deleted 5y ago[deleted]