research!rsc: The Generic Dilemma (original) (raw)
The Generic Dilemma
Posted on Thursday, December 3, 2009.
Generic data structures (vectors, queues, maps, trees, and so on) seem to be the hot topic if you are evaluating a new language. One of the most frequent questions we've had about Go is where the generics are. It seems like there are three basic approaches to generics:
- (The C approach.) Leave them out.
This slows programmers.
But it adds no complexity to the language. - (The C++ approach.) Compile-time specialization or macro expansion.
This slows compilation.
It generates a lot of code, much of it redundant, and needs a good linker to eliminate duplicate copies. The individual specializations may be efficient but the program as a whole can suffer due to poor use of the instruction cache. I have heard of simple libraries having text segments shrink from megabytes to tens of kilobytes by revising or eliminating the use of templates. - (The Java approach.) Box everything implicitly.
This slows execution.
Compared to the implementations the C programmer would have written or the C++ compiler would have generated, the Java code is smaller but less efficient in both time and space, because of all the implicit boxing and unboxing. A vector of bytes uses significantly more than one byte per byte. Trying to hide the boxing and unboxing may also complicate the type system. On the other hand, it probably makes better use of the instruction cache, and a vector of bytes can be written separately.
The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?
I would be happy to learn about implementations that somehow manage to avoid all three of these bad outcomes, especially if there were good written descriptions (papers, blog posts, etc.) about what was hard and why it's a good approach. I'd also be interested to see good written descriptions of trying one of those approaches and what went wrong (or right).
Please leave comments with pointers. Thanks.