On Fri, Jul 1, 2016 at 8:34 PM, Andrew Mezoni <andrew.mez...@gmail.com>
wrote:
> >> The generic dilemma is this: *do you want slow programmers, slow
> compilers and bloated binaries, or slow execution times?*
>
> (The Java approach.) Box everything implicitly.
> This slows execution.
>
> I just want to add some clarification.
> This does not slows a whole execution.
> All that works fast will remain the same fast.
>
> Of course, new (generic) code will be slightly slower by the following
> reasons.
> 1. Information about the types will be obtained not at the compile time
> but at the runtime (this requires a some time to access this information).
> 2. Type checking will be performed not at compile time but at the runtime
> (this also requires a some time to comparsion).
>
> This is true but...
> 1. Information about the types can obtained at the compile time very fast
>
No, it can't, unless you go the C++ way. That is the point. When a package
declares a function taking a generic Type T, the compiler can not know
anything about T. Because a parameter will be declared in a different
package, so in a different compilation unit. The only way to make this
work, is to instantiate a function per type or type size or something like
that and that is the C++ way.
> 2. Requirements of performing the type checking at the runtime will not
> occur so often
>
One of the most cited reasons for generics is iterators and generic
datastructurs. No, it's not going to "not occur so often". People are
talking about replacing the most central pieces of their code with
generics, otherwise they aren't particularly useful. That's the most
fundamental dilemma about generics: For them to actually be useful, you
need to replace often used code by a single generic implementation. It
doesn't make sense to have generics and *not* call into generic code all
the time.
> Generic programming divides the code (which uses generic types) on the two
> different kinds:
> - Generic code
> - Parametrized code
>
> Parametrized code used even in C language and, of course, it used
> currently on Go language.
>
> Eg.
>
> func set(slice []string, int i, val string) {
> slice[i] = val
> }
> func Set(list List<string>, int i, val string) {
> list.Set(i val)
>
> }
>
> This is identical (in purpose) parametrized source code.
> Everything (both of them) are computed by the compiler and everything
> compiled into very effective and very fast binary code without the
> requirements to perform some additional work at the runtime (such as the
> type checking).
>
> In contarst, this is a generic code (information about types is not known
> at the compile time).
>
> func (r *List) Set(i int, val E) {
> r.slice[i] = val
> }
>
>
> Compiler, in this generic code, does not know what type of value will have a
> variable `val E` at runtime.
>
> Here arrives is a reasonable question: "Should compiler perform type checking
> before performing such assignment?".
>
> My answer is: ". No. In such case compiler should not perform type checking
> at runtime All required type checks already was performed previously."
>
>
> Here is a proof:
>
>
> type List<E> struct {
> slice []E
> }
>
>
> This means that the compiler is the guarantor of that the for some instance
> of the type `List<E>` the field `slice []E` with some type assigned to `E` of
> `List` will have the same type assigned to `E`.
>
>
> Here is a proof:
>
>
> list := &List<string>{}
> // or
>
> list := NewList<string>()
> // where `NewList` is
> func NewList<E>() *List<E> {
> i := &List<E>{}
> i.slice = make([]E, 5)
> return i
> }
>
>
> In both cases the compiler ensures that the every member of the generic type,
> which has the type `E`, will be assigned only to the specified type argument
> (in our case, `string`).
>
>
> Now look again on our questionable code which possible can be slow.
>
>
> func (r *List) Set(i int, val E) {
> r.slice[i] = val
> }
>
>
>
> What we (and compiler) know about it?
>
> - The receiver (r *List) has some unknown type
>
> - The parameter (val E) has some unknown type but we know that this type is
> the same as `E` in `List<E>`
>
> - The field (List<E>.slice []E) of the receiver has some unknown type but we
> know that this type is the same as `E` in `List<E>`
>
>
> Should compiler perform some (possible slow) type checking at runtime to
> compare the type `E` with type `E`?
>
> What does this means?
>
>
> This means that this generic code also can fast as it possible.
>
> I don't know what argument you are trying to make. I don't think you are
making the one you think you are making.
func (r *List) Set(i int, val E) {
r.slice[i] = val
}
How does the compiler know the address of r.slice[i], to put E into? Or the
size of E, to copy it there? This is a very simple question, don't sidestep
it. Try to answer it and you will realize, that you are either going the
C++ way, or the Java way.
For non-generic code, the compiler knows the size of E, because it knows
it's type, basta. So r.slice[i] is simply r.slice.ptr + sizeof(E) * i. If
it doesn't know the size at compile time, as it can't, a priori, if E is
generic and can be any time, it will need to replace sizeof(E) by something
appropriate. And you then either let the compiler put in the size when it
sees a call to Set and generates a function with the appropriate size (so
it specializes the current code for concrete types once per size, the C++
way), or it needs to create a generic implementation of Set, which takes
the size of E as a parameter, this is boxing, the java way.
You have to choose one and you need to give an argument why your choice is
the correct one. That is the point of Russ' post, that there *is* no
obviously right choice here.
> P.S.
>
> The slow code mostly goes in the instantiation process but all the benefits
> from the use of new types cost to put up with it (and this is not very slow,
> and do not forget that arrays and maps in Go also has the "generics code" but
> it hidden from programmers).
>
> No. You are wrong. The only generic code in regards to slices and maps is
the make function. The types itself *are not generic*. There is no []T
type, there is only a []int, a []string and a []Foobar. At every point in
your program where you use a slice, the type of the element type is *known
at compile time*. The concrete type and everything. make/append is generic
on the surface. Go chooses the C++ way here. But it also limits the
different use-cases, so the increase in compile size is at most linear in
the number of types used.
>
> Finally.
>
>
> Question: "Does this code (with two parametrized types) requires the runtime
> type checks?"
>
>
> var slice []int{}var list List<int>{}var v1 int
>
> v1 = slice[1]
> v1 = list.Get(1) // List<E> with the argument `E` set to `int` always returns
> the `int`
>
>
> No. But will be executed sligtly slower than this code:
>
>
> v1 = funcWhichAlwaysReturnsOnlyInt(1)
>
>
> But why?
>
> This is because generic function always returns the pointers that need to
> dereference:
>
> How does the generic function know the size of the return value? It needs
to make sure, there is enough space allocated to return a pointer to. As
list.Get is generic, it doesn't know it is going to return an int in a
call, so how does it know how much to allocate?
You can not side-step the issue. A generic function *needs to know the size
of the type parameter from somewhere*. And, to reiterate, you either do
that by instantiating it per type and then make it a compile-time constant
(C++ way), or you pass the size (java way) and thus incur a runtime cost,
because you can't use specialized instructions and constant folding and in
the end using a constant will always be faster.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
