[HN Gopher] Faster Sorting with Go Generics
___________________________________________________________________
Faster Sorting with Go Generics
Author : todsacerdoti
Score : 87 points
Date : 2022-04-02 13:31 UTC (9 hours ago)
(HTM) web link (eli.thegreenplace.net)
(TXT) w3m dump (eli.thegreenplace.net)
| 0des wrote:
| [deleted]
| glouwbug wrote:
| Wasn't templating something languages had in 80s?
| [deleted]
| tedunangst wrote:
| > 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.
| rmk wrote:
| The article argues that even a function call to a "less"
| function benefits from the elimination of bounds checking.
| eliben wrote:
| 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).
| klabb3 wrote:
| 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..
| morelisp wrote:
| 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.
| masklinn wrote:
| > 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.
| [deleted]
| nasretdinov wrote:
| 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.
| klysm wrote:
| > 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.
| menzoic wrote:
| You have the freedom to not use generics when the application
| has stricter performance requirements.
| Eratosthenes wrote:
| > do you want slow programmers, slow compilers and bloated
| binaries, or slow execution times?
|
| Why choose? With generics we can have all three!
| [deleted]
| [deleted]
| giancarlostoro wrote:
| 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.
| masklinn wrote:
| https://planetscale.com/blog/generics-can-make-your-go-code-...
| made the rounds a few days ago.
| ljloisnflwef wrote:
| 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.
| mjburgess wrote:
| 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.
| mjburgess wrote:
| 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.
| eliben wrote:
| The FAQ has some good information:
| https://go.dev/doc/faq#generics_comparison and other sections
| around it
| ljloisnflwef wrote:
| tester756 wrote:
| >we've already learned that Go doesn't respect your freedom
| given its license choice
|
| What do you mean?
| dilap wrote:
| 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.)
| rventure wrote:
| 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).
| timcavel wrote:
| mirceal wrote:
| if err != nil { return nil, err }
|
| code poetry right there. it's so good that you have to
| repeat this over and over again!
| pjmlp wrote:
| Object Pascal, Modula-2, Active Oberon.
|
| Just for starters.
| [deleted]
___________________________________________________________________
(page generated 2022-04-02 23:01 UTC)