Cam's Cyberspace

Recent Notes

Five Answers to the Same Question

Properties3
descriptionOne generic definition has five shipped implementations. Java erases, the CLR reifies, Rust and C++ monomorphize, Go stencils by GC shape and passes a dictionary, and Racket checks a contract at the boundary with no static types at all.
tagscs, languages, compilers, type-theory
aliases

9 min read

Write a function that returns the smaller of two values. You want it to work on integers, on floating point numbers, and on anything else with an order. The abstraction every answer implements is parametric polymorphism, and there are five distinct implementations of it in production right now. They do not differ because some language designers were smarter. They differ because each team was optimizing a different constraint, and the constraint that decided the answer was usually not performance.

The two-pole version of this story, monomorphization against erasure, is told in Generics, Monomorphization vs Erasure. This note is the full board, and two of the five answers are not on that axis at all.

The idea

The implementation of generics is a choice about where the type information goes, and there are five live answers: throw it away and cast (Java), keep it in the runtime as a first-class thing (the CLR), duplicate the code so the type is baked into each copy (Rust, C++), duplicate the code only per memory shape and pass the rest in a side table (Go), or never have static types and check the obligation as the value crosses a module boundary (Racket). The non-obvious part is that the deciding constraint differs each time. Java’s was a deployed platform it could not break. Go’s was build time. Racket’s was that it has no static type parameters at all, so the check had to move somewhere else entirely.

Erase it: Java

Java’s generics arrived onto a platform that already carried a large body of non-generic libraries and compiled bytecode. The compiler therefore applies type erasure, replacing all type parameters in generic types with their bounds, or with Object when the parameters are unbounded, so that the produced bytecode contains only ordinary classes, interfaces, and methods. Casts go in where needed to preserve type safety, and bridge methods are generated to preserve polymorphism in extended generic types.

The payoff Oracle names is narrow and precise: erasure ensures that no new classes are created for parameterized types, so generics incur no runtime overhead. The real payoff is compatibility. Raw types show up in legacy code because lots of API classes, such as the Collections classes, were not generic prior to JDK 5.0, and for backward compatibility assigning a parameterized type to its raw type is still allowed. A pre-generics Vector and a generic Vector<String> are the same class file. That is the whole design goal, and every irritation Java programmers have with generics descends from it.

The bill: the type is gone at runtime, so nothing downstream can ask for it.

Reify it: the CLR

The CLR did not carry Java’s constraint, so the type parameter could become a runtime entity rather than a compile-time fiction. The common language runtime provides new opcodes and prefixes to support generic types in common intermediate language, and support for generics was added to the System.Reflection namespace for examining generic types and generic methods. A reified type parameter can be recovered: you get an array containing the generic type arguments using the GetGenericArguments method, and you can build a constructed type by binding type arguments to the type parameters of a generic type definition.

The win is layout, not reflection. Generic collection types generally perform better for storing and manipulating value types because there is no need to box the value types. A List<int> in .NET holds machine integers. A List<Integer> in Java holds pointers to heap objects, which is a different cache behavior on every traversal.

The bill: the type arguments have to survive into the runtime’s metadata, and the specialization work lands where the runtime constructs the type rather than where the compiler emits the assembly.

Duplicate it: Rust and C++

Rust performs monomorphization, which the Book defines as the process of turning generic code into specific code by filling in the concrete types that are used when compiled. The compiler looks at all the places where generic code is called and generates code for the concrete types the generic code is called with. Because Rust compiles generic code into code that specifies the type in each instance, the program pays no runtime cost for using generics.

C++ templates are the same strategy, older, with the build model left exposed. A specialization is instantiated when it is referenced in a context requiring a complete object type or a function definition, and the definition of a class template must be visible at the point of implicit instantiation, which is why template libraries typically provide all template definitions in the headers. At link time, identical instantiations from different translation units are merged, the linker cleaning up duplication the model guarantees.

The bill lands entirely at build time, and it is not small.

Stencil by shape and pass a dictionary: Go

Go is the interesting one, because it refused both poles on purpose. Pure stenciling would mean a distinct function instantiation for every set of type arguments, so instead the implementation passes a dictionary along with every call to a generic function or method, and the dictionary provides the information about the type arguments that allows a single function instantiation to run correctly for many distinct type arguments. But full dictionary passing costs speed, so the compiler shares an instantiation among sets of type arguments that have the same gcshape: two concrete types are in the same gcshape grouping if and only if they have the same underlying type or they are both pointer types.

That rule is why every pointer type in a Go program collapses into one instantiation, and it is doing real work for the collector, which needs to know which words in a frame are pointers. Each dictionary is statically defined at compile time, so this is a compile-time side table rather than runtime reflection, and it is a compromise placed deliberately between the two poles.

Check it at the boundary: Racket

Racket has no static type parameters to erase, reify, or stencil. Its answer is a runtime obligation attached where code changes hands. A contract establishes a boundary between two parties, and whenever a value crosses this boundary, the contract monitoring system performs contract checks, making sure the partners abide by the established contract. Racket encourages contracts mainly at module boundaries. When a value violates one, the monitoring system signals a violation of the contract and blames the module for breaking its promises.

Blame is the part with no analogue in the other four. An erased Java cast that fails tells you a cast failed. A contract violation names the guilty module, which is the difference between a stack trace and an accusation.

Every one of these is called zero cost by somebody

Rust means no runtime cost, paid for in build time and binary size. Java means no new classes per instantiation, paid for in lost runtime type information. Go means a bounded number of instantiations, paid for in a dictionary indirection on constrained calls. Racket means no compile-time cost at all, paid for on every boundary crossing. When a language advertises zero cost, the question that separates the claims is which resource absorbed it.

Read a new language’s generics this way and the syntax stops mattering. Ask what happens to T after type checking, and the reflection story, the code size, and whether a library can ship as a binary all follow from the answer.

Sources

Graph View

Backlinks