4 ms·

~~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 th

~~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 ago
I’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 ago
  yes, interfaces have a memory redirection https://research.swtch.com/interfaces https://research.swtch.com/interfaces
  - morelisp 5y ago
    This 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.
zelphirkalt 5y ago
It depends on the semantics of 'any'. The compiler could look at your code and figure out all types ever used with that 'any' and the optimize each case. The types could be known at compile time in some cases, if the semantics of 'any' allow for such a check and do not simply tell the compiler to not optimize for the types of that 'any'.
kgeist 5y ago
> 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.

paulgb 5y ago

I’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 ago
yes, interfaces have a memory redirection https://research.swtch.com/interfaces https://research.swtch.com/interfaces
- morelisp 5y ago
  This 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.

zelphirkalt 5y ago

It depends on the semantics of 'any'. The compiler could look at your code and figure out all types ever used with that 'any' and the optimize each case. The types could be known at compile time in some cases, if the semantics of 'any' allow for such a check and do not simply tell the compiler to not optimize for the types of that 'any'.

kgeist 5y ago

> 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.