Few ideas to reduce template bloat

[bearophile]

There are some ways to reduce the amount of binary code produced by templates in a language like D.


1) There are few situations where the types are different but the asm instructions inside the function are the same, like uint and int, but this situation probably is not common enough.


2) Even in function templates that get instantiated to a different asm there can be parts that are shared. If the shared part is at the end of the function the compiler can use a jump to use a single function exit point and remove some code duplication. I don't think this is a common situation.


3) There are more situations where a template type is one of several classes (OOP), this can produce the same duplicated asm. In this case the compiler can keep only one version in the final binary. This seems common enough.


4) C# avoids code bloat because it has a JIT and templates are instantiated at run-time. D can of course do the same if it uses the LLVM backend, but let's ignore this possibility for now.


5) Java generics don't cause code bloat because it removes the types at runtime and uses boxed values. This can be type-safe, but it's less flexible than C++/D templates, and the boxing-unboxing decreases performance. On the other hand programming practice shows that in most programs not all functions have to be top performance. So a compromise can be invented (I have never found this idea elsewhere). An attribute like @boxed can be used to mark what function template arguments are boxed (and don't multiply the template instances).

So for example this template function can be called with double or int values, so it gets intantiated in four versions:

T2 foo(T1, T2)(T1 x, T2 y) {...}
Instantiation 1: foo(1, 2)
Instantiation 2: foo(1, 2.0)
Instantiation 3: foo(1.0, 2)
Instantiation 4: foo(1.0, 2.0)

If foo() is not performance-critical, then the same function template with one @boxed type, and with the same inputs, gets instantiated just two times, halving its combinatorial explosion:

@boxed(T2) foo(T1, @boxed T2)(T1 x, T2 y) {...}
Instantiation 1: foo(1, 2)  and  foo(1, 2.0)
Instantiation 2: foo(1.0, 2)  and  foo(1.0, 2.0)

The first argument is like a normal template argument and created different instantiations, the second argument gets automatically boxed-unboxed, so it's like a single type.


Inside this version of the function foo() instructions like:
static if typeof(T2 == int) {...

are not allowed by the compiler (despite they are formally correct) because instances of T2 are objects and the compiler reminds you that you have to use a run time cast:
if (cast(Integer)T2 !is null) {...


There are ways to reduce code bloat with idioms used by the programmer, but that's good for C++ programmers. Programmers in a more modern language prefer something safer done by the compiler :-)

Bye,
bearophile