How do C++ compilers optimize template code?

Question

How do compilers avoid linear growth in the size of the compiled binary with each new type instantiation of a template?

I don't see how we can avoid making a copy of all the templated code when a new instantiation is used.

I feel that compile times and binary sizes would be made extremely unwieldy for all but the simplest templates in a reasonably large code base. But their prevalence suggests that compilers are able to do some magic to make them practical.

Answer 1

Many template functions are small enough to inline effectively, so you do get linear growth in the binary - but it is no more than you would get with equivalent non-template functions.

The One Definition Rule is important here, as it allows the compiler to assume that any template instantiation with identical template parameters generates identical code. If it detects that the template function has already been instantiated earlier in a source file, it can use that copy instead of generating a new one. Name mangling makes it possible for a linker to recognize the same function from different compiled sources. None of this is guaranteed since your program shouldn't be able to tell the difference between identical copies of a function, but compilers do harder optimizations than this every day.

The one time that duplicates are required to be filtered out is when a function contains a static variable - there can only be one copy. But that can be achieved either by filtering out the duplicate functions, or filtering out the static variables themselves.

Answer 2

There are multiple things which result in multiple instantiations not being too harmful to the exacutable size:

1. Many templates are just passing things through to another layer. Although there may be quite a bit of code it mostly disappears when the code is instantiated and inlined. Note inlining [and doing some optimizations] can easily result in bigger code, though. Note that inlining small functions often results in smaller (and faster) code (basically because the otherwise necessary calling sequence often requires more instructions than what is inlined and the optimizer gets a better chance to further reduce the code by a more holistic view of what's going on).
2. Where template code isn't inlined, duplicate instantiations in different translation units need to be merged into just one instantiation. I'm not a linker expert but my understanding is that, e.g., ELF uses different sections and the linker can choose to include only those sections which are actually used.
3. In bigger executables you'll need some vocabulary types and instantiations which used in many places and effectively shared. Doing everything using a custom type would be bad idea and type erasure is certainly an important tool to avoid too many types.

That said, where possible it does pay off to preinstantiate templates, especially if there are only a small number of instantations which are generally used. A great example is the IOStreams library which is unlikely to be used with more than 4 types (typically it is used with just one): moving the template definitions and their instantiations into separate translation units may not reduce the executable size but will certainly reduce the compile time! Starting with C++11 it is possible to declare template instantiations as extern which allows the definitions to be visible without getting implicitly instantiated on specializations which are known to be instantiated elsewhere.

Answer 3

I think you're misunderstanding how templates are implemented. Templates are compiled on a need-to-use basis into a corresponding class/function.

Consider the following code...

template <typename Type>
Type mymax(Type a, Type b) {
    return a > b ? a : b;
}

int main(int argc, char** argv)
{
}

Compiling this, I get the following assembly.

    .file   "example.cpp"
    .text
    .globl  main
    .type   main, @function
main:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movq    %rsi, -16(%rbp)
    movl    $0, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size   main, .-main
    .ident  "GCC: (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1"
    .section    .note.GNU-stack,"",@progbits

You'll notice it only contains the main function. Now I update my code to use the template function.

int main(int argc, char** argv)
{
    mymax<double>(3,4);
}

Compiling that I get a much longer assembly output including the template function to handle doubles. The compiler saw the template function was being used by the type "double" so made a function to handle that case.

    .file   "example.cpp"
    .text
    .globl  main
    .type   main, @function
main:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $32, %rsp
    movl    %edi, -4(%rbp)
    movq    %rsi, -16(%rbp)
    movabsq $4616189618054758400, %rdx
    movabsq $4613937818241073152, %rax
    movq    %rdx, -24(%rbp)
    movsd   -24(%rbp), %xmm1
    movq    %rax, -24(%rbp)
    movsd   -24(%rbp), %xmm0
    call    _Z5mymaxIdET_S0_S0_
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size   main, .-main
    .section    .text._Z5mymaxIdET_S0_S0_,"axG",@progbits,_Z5mymaxIdET_S0_S0_,comdat
    .weak   _Z5mymaxIdET_S0_S0_
    .type   _Z5mymaxIdET_S0_S0_, @function
_Z5mymaxIdET_S0_S0_:
.LFB2:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movsd   %xmm0, -8(%rbp)
    movsd   %xmm1, -16(%rbp)
    movsd   -8(%rbp), %xmm0
    ucomisd -16(%rbp), %xmm0
    jbe .L9
    movq    -8(%rbp), %rax
    jmp .L6
.L9:
    movq    -16(%rbp), %rax
.L6:
    movq    %rax, -24(%rbp)
    movsd   -24(%rbp), %xmm0
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE2:
    .size   _Z5mymaxIdET_S0_S0_, .-_Z5mymaxIdET_S0_S0_
    .ident  "GCC: (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1"
    .section    .note.GNU-stack,"",@progbits

Now let's say I change the code to use that function twice.

int main(int argc, char** argv)
{
    mymax<double>(3,4);
    mymax<double>(4,5);

}

Again, let's look at the assembly it creates. It's comparable to the previous output because most of that code was just the compiler creating the function mymax where "Type" is changed to a double. No matter how many times I use that function, it will only be declared once.

    .file   "example.cpp"
    .text
    .globl  main
    .type   main, @function
main:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $32, %rsp
    movl    %edi, -4(%rbp)
    movq    %rsi, -16(%rbp)
    movabsq $4616189618054758400, %rdx
    movabsq $4613937818241073152, %rax
    movq    %rdx, -24(%rbp)
    movsd   -24(%rbp), %xmm1
    movq    %rax, -24(%rbp)
    movsd   -24(%rbp), %xmm0
    call    _Z5mymaxIdET_S0_S0_
    movabsq $4617315517961601024, %rdx
    movabsq $4616189618054758400, %rax
    movq    %rdx, -24(%rbp)
    movsd   -24(%rbp), %xmm1
    movq    %rax, -24(%rbp)
    movsd   -24(%rbp), %xmm0
    call    _Z5mymaxIdET_S0_S0_
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size   main, .-main
    .section    .text._Z5mymaxIdET_S0_S0_,"axG",@progbits,_Z5mymaxIdET_S0_S0_,comdat
    .weak   _Z5mymaxIdET_S0_S0_
    .type   _Z5mymaxIdET_S0_S0_, @function
_Z5mymaxIdET_S0_S0_:
.LFB2:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movsd   %xmm0, -8(%rbp)
    movsd   %xmm1, -16(%rbp)
    movsd   -8(%rbp), %xmm0
    ucomisd -16(%rbp), %xmm0
    jbe .L9
    movq    -8(%rbp), %rax
    jmp .L6
.L9:
    movq    -16(%rbp), %rax
.L6:
    movq    %rax, -24(%rbp)
    movsd   -24(%rbp), %xmm0
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE2:
    .size   _Z5mymaxIdET_S0_S0_, .-_Z5mymaxIdET_S0_S0_
    .ident  "GCC: (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1"
    .section    .note.GNU-stack,"",@progbits

So basically templates don't affect the exec size any more than writing the functions by hand. It's just a convenience. The compiler will create a function for one or more uses of a given type so if I use it 1 or 1000 times, there will only be one instance of it. Now if I update my code to also handle a new type like floats, I'll get another function in my executable, but only one no matter how many times I use that function.