5 ms·
Generics shouldn't make something faster... If they do, then there is a bug or missed optimization in the compiler.
by londons_explore 5y ago
Generics shouldn't make something faster... If they do, then there is a bug or missed optimization in the compiler.
- leeuw01 5y agoWhy?
- nokamok 5y agoThe way I understood it the “slowness” came from using interface{} in the queue implementation. With generics you get a performance boost from annihilating the run-time overhead. Yes?
- masklinn 5y ago> With generics you get a performance boost from annihilating the run-time overhead. Yes? I don't know whether creating an interface{} has a runtime cost (though it may if the type pointer has to be looked up at runtime?), however there's also a memory overhead: I didn't look at everything but the first two benches (pushfront and pushbach) use `int` values, which are 32 bits. But interface{} is 2 words (128 bits). This quadruples the memory requirements, meaning the backing buffer may well need either more reallocations, or to make larger allocations & have to span multiple cache lines.
- nokamok 5y agoI think you’re on to something. Just reread this article: https://blog.gopheracademy.com/advent-2018/interfaces-and-reflect/ https://blog.gopheracademy.com/advent-2018/interfaces-and-re... And there’s definitely an overhead associated with the interface type due to run-time reflection. I guess generics does away with this.
- ogogmad 5y ago~~If the type of something is "any", then that means your types are only truly known at runtime, and you therefore have to check the type of everything while the program is running. Am I off here? I don't use Go.~~ Maybe it's not so much runtime type checking, as the fact that a type of "any" means that the compiler doesn't know anything about what objects are in the deque. If you're using arrays to represent your deques, then this means you can't actually store the entries of the deque in the array, but only pointers to those entries, no? I think the keyword for what I'm saying is boxing/unboxing.
- paulgb 5y agoI’m also not much of a Go programmer, but looking at the benchmark code[1] it doesn’t actually use the values after they are retrieved, so if the compiler is smart it may never have to check the type at runtime. It does, however, have to wrap the primitive in the `any` type, which seems to be what’s making it slow. Question for Go programmers: does using the `any` type result in an additional memory lookup if the wrapped type is a sized primitive like an int, or is the value stored directly alongside the type information? [1] https://github.com/sekoyo/deque/blob/86df0003850acaf3039c2d603cec858846816fac/deque_test.go#L578 https://github.com/sekoyo/deque/blob/86df0003850acaf3039c2d6... Edit: I wrote that before you added the second paragraph, which sounds right to me.
- omegabravo 5y agoyes, interfaces have a memory redirection https://research.swtch.com/interfaces https://research.swtch.com/interfaces
- morelisp 5y agoThis article is outdated; the second thing it says under "Memory Optimizations" does not happen anymore, and that's what's being asked about.
- morelisp 5y ago> does using the `any` type result in an additional memory lookup if the wrapped type is a sized primitive like an int, or is the value stored directly alongside the type information? The answer to this question is complicated because it's changed several times. Prior to Go 1.4, it stored word-sized or smaller values directly without allocation. Go 1.4 started a big GC rework, part of which required fields not contain possibly-pointer-possibly-other-values. https://github.com/golang/go/issues/8405 https://github.com/golang/go/issues/8405 Obviously this made people unhappy, so it kicked off several rounds of optimizations to claw back common cases over several versions, the most recent of which was 1.15's introduction of 256 interface constants which are automatically used for any numeric value that fits in a single byte (including booleans). 1.9 also made constant strings preallocate matching constant interfaces if it sees them passed as an interface. This is also why there's so much benefit to inliner improvements; any inlining improvement translates rapidly into devirtualization improvements.
- makapuf 5y agoNot for a given development effort and API complexity. Sure you can reimplement a list sort for each of your types.
- masklinn 5y agoGenerics absolutely (can) make things faster, if the collection is generic in the first place: the lack of generics would require RTTI and possibly boxing, the article specifically mentions the use of `interface{}` so that seems overwhelmingly likely. Hell the first benchmark just pushes a bunch of `int` onto the stack, with generics it just does that, without it has to pack the int into an interface{} quadrupling its size. The performance difference may well just come from the increase in allocations (and reallocation), and cache pressure, that sort of things. Nothing complicated, really. > missed optimization in the compiler. Go's compiler is pretty simplistic and not a heavily optimising one, so it'd also be unsurprising if type erasure also hindered it.
- ankurdhama 5y agoThese generics are not the way Java generic works. These are essentially specialized code genereted for each type (just like C++/Rust). You can have a look at the essembly code generated by Go program while using a slice of interface{} vs using slice of specific type on compiler explorer. Edit: Removed C ... somehow have a habit of writing C/C++ together :)
- moogly 5y agoC doesn't have reified generics. You could put C# in that list though.
- ankurdhama 5y agoYup... old habit of writing C/C++ :)
- tomp 5y agoDo you even know how generics work? Any implementation of generics should at least remove the type checks that a dynamic (interface{}) implementation has to incur.
- zarzavat 5y agoIt’s the other way around. The use of opaque references instead of generics means that the compiler does not have type information to make optimizations. The classic example is qsort in C vs std::sort in C++ - the generic version of the algorithm in C++ is faster because the compiler has the type information required to optimize it properly.
- amelius 5y agoThere are compiler optimizations that infer/invent types at compile time.
- captainbland 5y agoIt will if it means that the compiler can generate code which uses static dispatch rather than dynamic dispatch - it can be an improvement over using interface{} which I understand is the common way of dealing with cases that need generic behaviour in Go (with alternatives being code generation and simply copy-pasting). As far as I understand, with interface{} the compiler can't just decide to generate static dispatch based code because there's not enough information to generate that in a generalisable way (the code can depend on information that is only available at run-time rather than compile-time) and it would be bad for programmers who expect dynamic dispatch to be used because they're optimising for something else e.g. binary size or compilation speed. Obviously generics wouldn't be a performance improvement over using, say, code generation or doing a bunch of copy-pasting (and, given Go's lack of function overloading, a bunch of annoying renaming and some logic to dispatch to those methods which actually might cause more of a performance hit...) but those approaches tend to cause other problems.