Introduction

Programmers typically learn to abstract over values with looping, recursion, and function parameters, before moving onto abstracting over functions and types [1]. The facility to abstract over types in a programming language significantly reduces the need to rewrite code for data structures and algorithms that deal with multiple types. In statically typed programming languages all types must be concrete at the time of execution, whereas generics represent abstract types that can be compiled to concrete types by substituting “type parameters” with concrete types.

C++, Java, and C# (.NET) are the most commonly used object-oriented languages in industry at the time of writing [2]. In most cases, C++ is compiled to native machine code before execution, Java is compiled to a bytecode which is then compiled to native machine code by a virtual machine, and .NET commonly uses both strategies [3–5]. Each of the languages uses static typing, which therefore requires all types to be concrete and known at compile time.

For the remainder of this discussion, types will be used to collectively refer to both value types, which describe the bit layout of data structures, and reference types, which are pointers to values [4]. In C++, Java, and .NET a reference is word-sized pointer, so a generic type or function can be compiled to be compatible with any reference type by ignoring the type, and just treating it as a raw pointer. This strategy, called type erasure, is adopted by both .NET and Java [6].

Value types, however, can vary in size and it is therefore not possible to use a single implementation of a generic class or function efficiently (in a statically typed language). At compilation time (whether ahead-of-time or just-in-time) a common approach is to instantiate non-generic classes with their generic parameters replaced with the identities of concrete types. Both C++ and .NET allow user-defined value types, but the JVM currently only supports user-defined reference types. Java therefore uses boxing to wrap value types in lightweight objects in order to use them with generics [8].

C++

C++ implements generic classes, methods, and functions through templates, which cause the compiler to compile separate copies of the code for each unique set of type arguments [9]. Consider a simple generic class Box:

template<typename T>
class Box {
public:
    Box(T value) { _value = value; }
private:
    T _value;
};

Later, when a function declares an instance of Box it will be required to supply the name of a type for the type parameter T:

Box<int> intBox(42);
Box<std::string> stringBox("Hello, world!");

For each unique set of type arguments used per compilation unit, which is generally a single C++ file, instances are created by replacing T with the appropriate type and compiling the generated code. In this case, copies of Box will be generated with T replaced by int and std::string. The generated code is then type checked, to ensure that all used methods, fields, and operators are accessible. For example, the Standard Template Library function std::sort is generic across all types, but will only compile when used with a type that overloads the < operator [10]. As described later, C++ doesn’t enforce requirements such as these in the signatures of generic methods (but still enforces them at compile time).

A key advantage of C++’s approach is that there is no runtime performance cost compared to handwritten code, although it does come at the cost of increased code size and compilation time [11–12]. As each template is instantiated for each code unit that uses it, there can be a multiple copies of the same instantiation per executable. For example, Box<int> could be used by a.cpp and b.cpp, and therefore the constructor for Box<int> would appear in the object files for both a.cpp and b.cpp. If the two object files are linked into the same executable this is unnecessary, and one copy can be eliminated. It is the responsibility of the linker to eliminate the equal instantiations from the final executable [13]. An alternative technique, which doesn’t rely on linker optimisations, is to explicitly instantiate certain instances to ensure that equal instances are only compiled once.

C++ further allows programmers to provide alternative specializations of generic classes, for types where it may be more efficient to do so. For example, the Standard Template Library specializes std::vector<bool> to represent boolean values with a single bit, rather than as a single byte [10–14]. C++ templates also allow specialization based on values, so the type std::array<int, 7> is distinct from the type std::array<int, 42> [15].

Java

The initial release of Java in 1995 did not include generics. The Generic Java (GJ) project [16], started in 1998, was integrated into the language in 2004 [17]. As a result of the relatively late inclusion of generics, the authors of Generic Java were conscious that it would be necessary to maintain compatibility for existing code that used non-generic interfaces for classes, such as common collections, that could now be implemented using generics.

Prior to the introduction of generics, collections APIs used Object, Java’s root reference type, as their element type [18]. The Generic Java project therefore chose to ‘erase’ the generic type parameters by replacing them with Object in order to compile the generic class, and introduce the appropriate casts in client code. The following generic code:

public class Box<T> {
    public T value;
    public Box(T value) {
        this.value = value;
    }
}
//Client code
Box<Integer> intBox = new Box<Integer>(42);
Integer intFromBox = intBox.value;

Is therefore compiled to:

public class Box {
    public Object value;
    public Box(Object value) {
        this.value = value;
    }
}
//Client code
Box intBox = new Box(new Integer(42));
Integer intFromBox = (Integer)intBox.value;

A consequence of type erasure is that it restricts the type parameters to reference types, and as such it is not possible to create an instance of Box<int>, for example [6]. In order to get around this, Java provides boxed classes which contain a field for Java’s eight primitive value types [8]. In Oracle’s HotSpot JVM, this comes with the disadvantage that a Java object contains a header of one or two words, and to access any field at least one pointer traversal is required [19]. There is therefore the initial cost of allocating memory on the heap for boxed instance, the memory cost of the object’s header, the cost of traversing at least one pointer to get the boxed value, and the cost of garbage collecting the instance. In many cases it is difficult to efficiently use generics with primitive types.

Project Valhalla [20], a recent effort to “incubate advanced Java VM and language features”, supports the introduction of value types and generic specialisation to the language in order to make these cases more efficient.

Furthermore, without reflection it is not possible to create new instances of the generic argument either, i.e. object creation via new T() is not possible.

.NET

Most C++ compilers compile to native code “ahead of time” (AOT), whereas Java byte-code is compiled “just in time” (JIT) by a virtual machine, but .NET software can be compiled using either method. Typically, however, execution is via the JIT-compiled Common Language Runtime. At runtime, generic types are instantiated as they are required, so generics can be used with value and reference types. A single instance is shared for all reference types - effectively using type erasure like Java - but separate instances are created for value types. Rather than completely erasing types at compile time, the metadata section of .NET “portable executables” encodes the generic parameters of a type or method, allowing these to be replaced, and the method can then be JIT compiled [4]. After an instance has been compiled it will be reused, and the generated native code remains in memory whilst the application is executed.

For most types found in .NET applications (references), this approach will offer similar performance to Java, as appropriate casts between the base reference type and the expected reference type must be inserted. Meanwhile, the .NET approach offers a significant advantage for value types as a separate instantiation is natively compiled for each value type used by the program, which avoids the need for boxing or unboxing, hence offering better performance [21].

Despite using type erasure for reference types, .NET allows new T() in generic methods [4] by automatically using reflection methods, provided that a given type has the default constructor available [23].

As well as providing a JIT-environment for .NET applications, Microsoft provides a tool that compiles .NET bytecode assemblies to native code [24]. This improves performance of .NET applications by removing the need for JIT compilation, and also reduces memory requirements.

Unlike native C++, .NET executables typically consist of multiple assemblies that are dynamically linked at runtime (either by the JIT or OS services). Suppose an assembly A.dll exposes the generic type List<T>, which is instantiated as List<string> and List<int> in both B.dll and C.dll, and that D.exe links to both B.dll and C.dll.

In the JIT environment the bytecode for List<T> will only be included in A.dll, but the native environment presents a greater challenge. The first option would be to include native code for List<string> and List<int> in the natively compiled B.dll and C.dll, but this violates .NET’s principal that equal types should be identical [4].

In order to counteract this problem, Kennedy and Syme [21–25] introduce further rules for the “home” of a particular instantiation:

• The assembly that defines a generic type includes the instantiation for all reference types, like Java. In the case described above A.dll would include List<ref>
• If an assembly needs a value type instantiation, then include it in the assembly. B.dll and C.dll would therefore require their own implementations of List<int>, but they could both use the implementation of List<ref> in A.dll for List<string>, as string is a reference type in .NET
• At link time do not link to a generic type if an equal instantiation has already been linked to. The implementation of List<int> in C.dll would therefore be ignored if B.dll had already been linked in D.exe, thus resolving the identity issue

Type system features

Some generic algorithms or data structures have to be restricted to certain concrete types. For example, a sorting algorithm only works with types that are comparable so that a partial order can be formed. Both .NET and Java allow programmers to restrict generic types to concrete types that implement certain interfaces, similar to type classes in Haskell [26–28]. This restriction is applied in the type signature of the generic class or method.

C++ doesn’t have interfaces, and therefore the generic code is only type-checked when it is instantiated with a concrete type. Bjarne Strousoup, the creator of C++, considers this a disadvantage of C++’s template system, as it requires programmers to program against the implementation of a generic class, rather than the interface [29]. As such, there is an effort to introduce “concepts” to C++ to add these restrictions before the template is instantiated with a concrete type [30].

All of the languages described support subtype polymorphism, however their treatment of subtyping of generic types varies. For example, in OCaml if Cat were a subtype of Animal, then “list of Cat” is a subtype of “List of Animal” [31]. There are three possible behaviours for the subtype relation:

• Invariant: There is no subtype relationship between different instantiations of a generic class, irrespective of the subtype relationship between the type arguments. This is the default approach used by all three programming languages [4–32–33]
• Covariant: “list of Cat” is a subtype of “list of Animal”, so the order of types is preserved. This approach can be used in .NET [4]
• Contravariant: The subtyping order is reversed. Again, .NET supports additional annotations to generics to support contravariance

Conclusion

Generics are a useful addition to many programming languages, and there are further efforts to add higher-order “kinds” (a generalisation of parametrized types) to functional programming languages such as Haskell [34]. The compilation techniques described above are used by main other programming languages, although recent languages such as Go remain resistant to their addition, citing increased compilation time and executable size as drawbacks [35].

The native code generated by compilers for statically typed languages is unlikely to change due to the stability of computer architectures, OS calling conventions, and memory layouts. Recent research and development into generics instead focusses on adding restrictions to the types that can be used with generics to increase type safety and programmer productivity whilst reducing the complexity of the compiler.

The appendix contains implementations of a simple generic Box class, with examples of the code generated by common compilers for each of the three platforms.

Appendix

C++

template<typename T>
class Box
{
    public:
        Box(T value) { _value = value; }
        T _value;
};

int main() {
    Box<int> box(42);
    return 0;
}

Before compiling to native code, the LLVM compiler generates an intermediate representation (similar to the byte code representation used by Java and .NET). By compiling similar C and referring to the documentation [36], the output has been labelled:

; Metadata for the size and layout of the type
%class.Box = type { i32 }

define i32 @main() #0 {
  ; alloca ensures there is enough stack space
  ; and returns the address of the instance
  %1 = alloca %class.Box, align 4
  ; Call the constructor
  call void @_ZN3BoxIiEC2Ei(%class.Box* %1,
    i32 42)
  ret i32 0
}

; Constructor of Box<int>
; linkonce_odr allows inlining and prevents
; duplication of this generic instance
define linkonce_odr void @_ZN3BoxIiEC2Ei
  (%class.Box*,  i32) unnamed_addr #2 align 2 {
  ; getelementptr returns the address of a field
  %3 = getelementptr inbounds %class.Box,
    %class.Box* %0, i32 0, i32 0
  ; Copies the int into the class' _value field
  store i32 %1, i32* %3, align 4
  ret void
}

The above shows that a single instance of Box is instantiated with T replaced by int, and no other instances are compiled.

Java

//Box.java
public class Box<T> {
    public T mValue;
    public Box(T value) {
        this.mValue = value;
    }
}
//App.java
public class App {
    public static void main(String[] args) {
        Box<Integer> boxInteger = new Box<>(42);
    }
}

Java is compiled to a bytecode, but it is possible to use the javap tool to output a textual representation of the bytecode [37]. Some irrelevant information has been removed from the output for brevity’s sake.

//Box.class disassembly
public class Box<T extends java.lang.Object>
  extends java.lang.Object
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #4.#17
   #2 = Fieldref           #3.#18
   #3 = Class              #19
   #4 = Class              #20
   #5 = Utf8               mValue
   #6 = Utf8               Ljava/lang/Object;
   ...
   #8 = Utf8               TT;
   #9 = Utf8               <init>
   ...
   #13 = Utf8              (TT;)V
   #14 = Utf8
     <T:Ljava/lang/Object;>Ljava/lang/Object;
   ...
   #17 = NameAndType       #9:#21
   #18 = NameAndType       #5:#6
   #19 = Utf8              Box
   #20 = Utf8              java/lang/Object
   #21 = Utf8              ()V
{
  //Note that the type descriptor is just
  //Object as the type is erased
  public T mValue;
    descriptor: Ljava/lang/Object;
    flags: ACC_PUBLIC
    Signature: #8

  public Box(T);
    descriptor: (Ljava/lang/Object;)V
    flags: ACC_PUBLIC
    Code:
      stack=2, locals=2, args_size=2
         //Object init()
         0: aload_0
         1: invokespecial #1
         //Sets mValue
         4: aload_0
         5: aload_1
         6: putfield      #2
         9: return
    Signature: #13
}
Signature: #14

//App.class disassembly
public class App
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #6.#15
   #2 = Class              #16
   #3 = Methodref          #17.#18
   #4 = Methodref          #2.#19
   #5 = Class              #20
   #6 = Class              #21
   #7 = Utf8               <init>
   #8 = Utf8               ()V
   ...
   #15 = NameAndType       #7:#8
   #16 = Utf8              Box
   #17 = Class             #22
   #18 = NameAndType       #23:#24
   #19 = NameAndType       #7:#25
   #20 = Utf8              App
   #21 = Utf8              java/lang/Object
   #22 = Utf8              java/lang/Integer
   #23 = Utf8              valueOf
   #24 = Utf8              (I)Ljava/lang/Integer;
   #25 = Utf8              (Ljava/lang/Object;)V
{
  public App();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1
         4: return

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=3, locals=2, args_size=1
         0: new           #2
         3: dup
         4: bipush        42
         6: invokestatic  #3
         9: invokespecial #4
        12: astore_1
        13: return
}

.NET

namespace GenericApp
{
    public class Box<T>
    {
        public T Value;

        public Box(T val)
        {
            this.Value = val;
        }
    }

    public class Program
    {
        public static void Main
            (string[] args)
        {
            var box = new Box<int>(42);
        }
    }
}

The above C# compiles to the Common Intermediate Language, which is typically represented in a byte-code format. The below is an alternative text representation, created by the Mono Project’s disassembler [38] and labelled based on the runtime specification [4]. Note that some irrelevant sections of the output have been removed.

.namespace GenericApp
{
  //`1 indicates that the class has only 1
  //generic parameter
  .class public auto ansi beforefieldinit
    Box`1<T>
    extends [mscorlib]System.Object
  {
    //!0 refers to the first parameter
    .field  public  !0 Value

    .method public hidebysig specialname
           instance default void '.ctor' (!T val)
           cil managed
    {
      .maxstack 8
      //Constructs the instance and sets
      //this.Value (field 0)
      ldarg.0
      call instance void object::'.ctor'()
      ldarg.0
      ldarg.1
      stfld !0 class GenericApp.Box`1<!0>::Value
      ret
    }
  }
}

.namespace GenericApp
{
  .class public auto ansi beforefieldinit
    Program extends [mscorlib]System.Object
  {
    .method public static hidebysig
           default void Main (string[] args)
           cil managed
    {
      .entrypoint
      .maxstack 1
      //Encodes the local type
      .locals init (
        class GenericApp.Box`1<int32> V_0)
      //HEX 2a = DEC 42
      ldc.i4.s 0x2a
      newobj instance void class
        GenericApp.Box`1<int32>::'.ctor'(!0)
      stloc.0
      ret
    }
  }
}

References