This author is making the case in terms of improved performance, which I find interesting.
This author is making the case in terms of improved performance, which I find interesting.
If you have a layer of indirection (i.e., no genetics so you need to dispatch at runtime) then you wind up with an additional jump instruction.
While modern processors and branch prediction make jumps relatively cheap, they can’t avoid instruction cache misses if the dispatch is happening frequently.
By removing the layer of indirection, the compiler can choose to inline the implementation instead of using a jmp; this keeps our icache clean, and can lead to faster execution.
However, there’s a real cost to this! Inlining is, in broad strokes, often faster; but that’s not always true if you’re e.g. inlining a large number of instructions into a tight loop. As with all performance, profile to know the truth.
Note, this is not just generics. Java could use overloading for years before generics to get similar benefits. Common LISP has type annotations that can give similar benefits. Generics is just a much easier/stronger to use construct for this in many cases.
Ultimately generic typing is a way of better expressing the constraints of a program to a compiler, which means the compiler can do a better job of generating code for specific instances. The downside is that the compiler needs to generate code explicitly for each concrete instance of a generic function or type, which means that it takes more compile time and code size is larger.
Edit: I'd also like to point out that JIT compilers and sufficiently-smart AOT compilers can do this sort of inlining if they can prove that for any combination of run time types passed into a sort() they have the same comparison function and inline it as needed. That said it's the same (or higher) complexity as a generics system, with more pitfalls (for example, if they can't prove it but make a guess the sort function never changes, then get the guess wrong, they have to de-optimize).
PUSH x
PUSH y
CALL compare
CMP x y
POP
You end up with CMP x y
Of course this will vary based on the type that you're optimizing for but in all cases you're removing the need to push and pop the stack for every comparison. I'm not smart enough to talk about other optimizations enabled by generics though.Essentially, imagine you have custom routines for your ints and floats and your language doesn't support generics. You'll have a code like this
if type is INT:
answer = optimizedRoutineForInt();
else type is FLOAT:
answer = optimizedRoutineForFloat();
This happens at run-time. There's an overhead.With generics, there's zero overhead. Your code will look something like
answer = optimizedRoutine<Type>();
and if optimizedRoutine<Float> can be inlined at this site, there are no conditions or jumps in the code.The post goes in detail about how for sorting, this sort of comparison function is called so frequently it has a massive impact on performance