7 ms·
Crimes with Go Generics
- BreakfastB0b 4y agoHow long before someone figures out how to encode lightweight higher kinded types[1] in Golang. There shall be weeping and gnashing of teeth. [1] https://ybogomolov.me/01-higher-kinded-types/ https://ybogomolov.me/01-higher-kinded-types/
- amscanne 4y agoIf the author is reading, I believe the problem noted at the end is actually that the code isn’t going through the thunk API and thus no memoization occurs. (Consider that there is no call to Set in the evaluation tree!) fib = func(n int) int { if cache[n].o.IsSome() { return *cache[n].o.val } return fib(n-1) + fib(n-2) } Should be: fib = func(n int) int { return cache[n-1].Force() + cache[n-2].Force() }
- deleted 4y ago[deleted]
- tsimionescu 4y agoIndeed, that works, and finishes in 0.00 time - here is a Go Playground to prove it (using *T instead of Optional[T]). https://go.dev/play/p/RxMjU34pjJQ https://go.dev/play/p/RxMjU34pjJQ
- hddqsb 4y agoUnfortunately Go's playground messes with the time, so it's always going to say 0.00s even for the slow version. Here is a hacky workaround to measure the actual time using a syscall: https://go.dev/play/p/kF6Bh048siE https://go.dev/play/p/kF6Bh048siE It shows 979ms for the original version and 0.212ms for the fast version.
- Groxx 4y agoIt does play with time, but essentially only wall-clock time which isn't relevant here. You can easily make tests show non-zero durations.
- hddqsb 4y agoNope. If you call `time.Sleep()` the reported duration will reflect that call, but it's only simulating the delay. The duration of a CPU-heavy task is always reported as 0.00s. Demo: https://go.dev/play/p/UZToqFseAwO https://go.dev/play/p/UZToqFseAwO Output: === RUN TestSleep // calls time.Sleep(2 * time.Second) Real duration: 554µs --- PASS: TestSleep (2.00s) === RUN TestBusyLoop // for i := 0; i < 1000000000; i++ { ... } Real duration: 390.826ms --- PASS: TestBusyLoop (0.00s) PASS The simulation is quite good: if you have multiple threads that use `time.Sleep()`, their output will be interleaved correctly. The output panel will even display the lines one at a time as if it's streaming them from the server, but in reality the entire output is received at once and the "streaming" effect is simulated on the client. Concurrency is one of Go's core features, so it figures the playground would allow some form of concurrency even when the clock is fake.
- Groxx 4y agoInteresting. I suppose that makes sense, to let them speed up execution... I am a bit curious how it'd affect concurrent behavior based on time changes (e.g. if it's cpu-bound for longer than the sleep, does the wake still occur in the middle? Or does it wait to advance time until everything's blocked? What if you runtime.Yield? etc?), but that's certainly an efficient option for a public execution environment like this.
- xena 4y agoOh dear. I pushed an addendum to the article: https://github.com/Xe/site/commit/05135edcbe5e474131c15c24766e0266285fa514 https://github.com/Xe/site/commit/05135edcbe5e474131c15c2476... Thanks for pointing that out!
- reflexe 4y agoMaybe I am missing something here but as someone who is not an expert in go generics, I don't see any obvious "crimes" with the Option and Queue implementations. I also could not find where the author explains their "crimes". What I am missing here?
- progbits 4y agoNot a Go person either but I think the joke with the queue is that Go channels are already exactly that - MPMC queue, and with "generics" baked into the language. The Option is just a good idea and sum types should have been in the language from the beginning to handle errors instead of product types. But that ship has sailed and sunk.
- ImprobableTruth 4y agoAn Option type without pattern matching is just as useless. Before unwrapping the value, you should check if its None and if you fail to do that, you get a panic. That's literally how pointers already work.
- masklinn 4y ago> That's literally how pointers already work. With the huge difference that Go’s pointers don’t statically require checking if they’re `null`. Furthermore, you can add functor and monadic APIs to `Option` which provide completely safe (and somewhat efficient) usage patterns even if you build the option out of product types. Though that isn’t the case here, an other interesting item is that you can build an option type out of non-pointer, thus avoiding the indirection and allocation (though hopefully unlike the C++ committee you don’t do it just so you have a pointer without an allocation)
- ImprobableTruth 4y agoThere is no meaningful null check enforcement like with pattern matching, if you try to access the Option value and fail to handle the error correctly, you either get a panic (from the following null deref) or in this blogpost the zero initialized value (which is honestly worse than an instant crash). >Furthermore, you can add functor and monadic APIs to `Option` There's nothing preventing you from defining these functions directly on pointers, they'd be just as safe.
- nx7487 4y agoGo 1.18 added generics to the language. This allows you to have your types take types as parameters so that you can create composite types (types out of types). This lets you get a lot of expressivity and clarity about how you use Go. Aren't structs already composite types?
- Koiwai 4y agoI guess the author meant "types of types".
- honkycat 4y agoShe? They? the website is called christine.website so it is probably not a man
- Koiwai 4y ago
- honkycat 4y ago
- Koiwai 4y agoI don't normally care about the author's gender, but I'd argue assuming that is a man is a honest mistake, as long as women in the tech industry is still a minority. Do you really need to go that far? I think that shows how fragile you're.
- honkycat 4y agowhen i make a mistake, i apologize and correct it. Especially one as minor as misgendering, which inevitably happens and is easily fixed with a quick: "oh, they*! My apologies!" so your assertion "i don't care" comes off as flippant and aggressive.
- Kostarrr 4y agoI don’t think the Option presented here is sufficient (it is indeed a “crime”) as you cannot express Some(nil). But you could probably achieve that using go's not-well-known sum types, e.g. like this https://github.com/FSMaxB/type-safe-builder-experiment/blob/master/go/builder/staticOptional.go https://github.com/FSMaxB/type-safe-builder-experiment/blob/...
- jchw 4y agoI’m pretty sure that’s an interface union, not a sum type. That said, you could definitely do an option type using interfaces, but it would be less efficient than pointers directly because of the itab overhead.
- tsimionescu 4y ago> I’m pretty sure that’s an interface union, not a sum type. It's a kind of sum type, but it can only be used to constrain types for a generic parameter. That is, you can define `func foo[T StaticOptional[int]](x T)` and then call it as `foo(StaticNone{})` or `foo(StaticSome[int]{123})`, but you can't do `func foo() StaticOptional[int]` or even `func foo[T StaticOptional[int]]() T {return StaticNone{} }`.
- jchw 4y agoI think that still eats the itab penalty so as long as the structures wind up with the same gcshape? But now I wonder.
- tsimionescu 4y agoWell, that doesn't really work, as "StaticOptional[T]" can't be used as the type of a variable. It can only be used to create another generic function. For example, this doesn't work [0]: //compilation error: interface contains type constraints func TryParse123(s string) StaticOptional[int] { if s == "123" { return StaticSome[int]{123} } return StaticNone{} } [0] https://go.dev/play/p/1CnieCLqESC https://go.dev/play/p/1CnieCLqESC
- Koiwai 4y agoThe fibonacci should use an array/slice for storage instead of a map(hashmap).
- CraigJPerry 4y agoCrimes with Go Generics really is the perfect title for this article. I chuckled at the juxtaposition of the “expressivity and clarity” comment: >> you can create composite types (types out of types). This lets you get a lot of expressivity and clarity about how you use Go Followed by long winded code: >> However, we can make this a lot more complicated with the power of the Thunk[T] type And confusion: >> Why is this so much slower? This article touches on a lot of the frustration i see with abuse of static typing. You’re going to write more code and take longer to write it and longer to change it (read: you’re going to cost me more money to build and maintain this code), for the unproven claim that you’ll write less bugs. The author then goes on to write a logic bug in their memoization code. But only after they’ve created a generic MPMC queue type by taking an already generic MPMC queue type (a go channel) then writing logic that breaks it (can’t handle an empty queue state) which they code their way out of by throwing more code i have to own.
- mopierotti 4y agoI'm not sure if you're talking about static typing in Go specifically, but imho static typing and generics make code easier to change. I dread refactoring code that hasn't made extensive use of types, because it makes it harder to know if you've missed anything conceptually (typing reduces the potential behaviors of a piece of code) or literally (e.g. forgot to update a class).
- CraigJPerry 4y agoWe’re replying to an article where the author also claimed that but then encountered a bug only in their generic version.
- dolmen 4y agoAbout "Why is this so much slower?" this article is a must-read: https://planetscale.com/blog/generics-can-make-your-go-code-slower https://planetscale.com/blog/generics-can-make-your-go-code-...
- nirui 4y ago> Why is this so much slower? Just a side note: Go test supports benchmarking (https://dave.cheney.net/2013/06/30/how-to-write-benchmarks-in-go https://dave.cheney.net/2013/06/30/how-to-write-benchmarks-i...) which gives you few useful tools such as `b.ReportAllocs()` and `go test -bench . -cpuprofile cpu.out -memprofile men.out`. These tools can give you far better information than just the execution time of a test case.
- dolmen 4y agoAlso this article is a must-read to understand about the shortcomings of Go 1.18 implementation of generics: https://planetscale.com/blog/generics-can-make-your-go-code-slower https://planetscale.com/blog/generics-can-make-your-go-code-...
- marsven_422 4y ago
- RamblingCTO 4y agoThe design isn't very reader-friendly to be honest. I really don't like the trend of terminal-inspired designs. Yeah, looks nice and nerdy, but isn't really useful for reading. Monospaced fonts aren't very good for running text as well.
- svnpenn 4y agoI think author has gotten out of hand with the avatars. They now have three talking to each other. One was fine, but at this point it's just a distraction. Just write the article.
- mrlonglong 4y agoIain M. Banks once wrote this: "It's brains, not gonads that matters".