Here’s some problems with the basic boxing approach: Type Stack struct ), pre-generics Java ( Object), pre-generics Objective-C ( id) Type-erased boxed generics
Let’s start with an example of the basic boxing approach in Go: Some languages like Rust and C# even provide both options! Boxing
It’s also worth noting that in some larger programs the performance advantage of monomorphization might be canceled out by the additional instruction cache misses from all the extra generated code.Įach of these schools of generics has many directions it can be extended in to add additional power or safety, and different languages have taken them in very interesting directions.
#IPICTURE VTABLE ALL INSTANCES CODE#
They also differ in how they can be extended: Extensions to boxing allow more dynamic behavior at runtime, while monomorphization is more flexible with how different instances of generic code can differ. Overall the tradeoff is basically that boxing leads to better compile times but can hurt runtime performance, whereas monomorphization will generate the fastest code but takes extra time to compile and optimize all the different generated instances. In C this corresponds to defining your entire data structure in a macro and calling it for each type you want to use it with. This produces the fastest possible code, but comes at the cost of bloat in code size and compile times as the same code with minor tweaks is compiled many times. This way each instance of the code can directly use the size and methods of the data it is working with, without any dynamic lookups. Monomorphization is where we copy the code multiple times for the different types of data we want to store. In C this corresponds to making your data structure store void* pointers and just casting your data to and from void* (allocating on the heap if the data isn’t already on the heap). We can make pointers to all different types act the same way so that the same code can deal with all data types! However this can come at the cost of extra memory allocation, dynamic lookups and cache misses. This is usually done by allocating things on the heap and just putting pointers in the data structure. These two ideas form the basis of the two major classes of solutions to generics: “boxing” and “monomorphization”.īoxing is where we put everything in uniform “boxes” so that they all act the same way.
#IPICTURE VTABLE ALL INSTANCES HOW TO#
Two ideas for how to get around this are to find a way to make all data types act the same way in our data structure, or to make multiple copies of our data structure with slight tweaks to deal with each data type the correct way. The problem is that each function and type definition we write only works for data that’s the same size, is copied the same way, and generally acts the same way. Let’s say we’re programming in a language without a generics system and we want to make a generic stack data structure which works for any data type. I made a flow chart of all the systems I discuss to give you an overview of what this post will contain and how everything fits together: As evidence I’ll describe how three different fully general metaprogramming methods can be seen as extensions from different directions in the space of generics systems: dynamic languages like Python, procedural macro systems like Template Haskell, and staged compilation like Zig and Terra. One reason I think generics are an interesting case is that they’re a simple case of the general problem of metaprogramming: writing programs that can generate classes of other programs. I’ll start from how languages without a special generics system like C solve the problem and then I’ll show how gradually adding extensions in different directions leads to the systems found in other languages. In this post I’m going to take you on a tour of the generics systems in many different languages and how they are implemented. Different programming languages have come up with all sorts of solutions to this problem: From just pointing people to existing general features that can be useful for the purpose (e.g C, Go) to generics systems so powerful they become Turing-complete (e.g. In some domains of programming it’s common to want to write a data structure or algorithm that can work with elements of many different types, such as a generic list or a sorting algorithm that only needs a comparison function. Models of Generics and Metaprogramming: Go, Rust, Swift, D and More
0 kommentar(er)
