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.
This is correct. When a function/struct accepts an interface value, it should be able to work with values of any underlying type. Underlying types can have vastly different sizes (from 0 to N bytes), and at the same time, we want to have a single machine code implementation per function, and a single memory layout per struct, known at compile time, to avoid massive code bloat (which we would have if we tried to account for all possible sizes). The simplest way to do it is to make an interface value store a pointer to actual data - pointers are always of the same size, no matter what the underlying type is. A pointer means "escaping to the heap", i.e. we can't safely store data on the stack anymore, because the pointer can be saved somewhere else and used later, when the original stack frame is long gone, which would be unsafe (we'd access dangling/overridden data).
So the main overhead is additional GC pressure because we have to allocate on the heap. Type checking has its overhead, too, but IIRC it's just a conditional branch.
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/86df0003850acaf3039c2d6...
Edit: I wrote that before you added the second paragraph, which sounds right to me.
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
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.
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.
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.
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.
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 :)