Type-level integers are used often as template arguments in D language, for various purposes, and they will be a good improvement for Rust (despite the complexity increase they bring). In D you can also use many other things as template arguments, but integers are the most useful (after type arguments, of course).
Two of the ways to use them in D are:
- To improve performance (sometimes using them with compile-time tuples) of some code.
- To increase static safety (often for the lengths of fixed-length arrays);
Below I explain something about both usage patterns, using D code for the explanations.
One performance improvement comes from replacing one or more than one of the run-time arguments of a function with template arguments, as you can see in the first D program here:
If you take a look at the function signatures:
auto findNearest(size_t k, F)(KdTree!(k, F) t, in Point!(k, F) p) pure nothrow @nogc {
static KdNode!(k, F)* nk2(size_t split)(Point!(k, F)[] exset) pure {
Here split is a compile-time argument that in a precedent version of the code was a run-time one. The n-dinsional data is stored inside arrays in the Go language version:
// point is a k-dimensional point.
type point []float64
But the D code uses a fixed size array:
struct Point(size_t k, F) if (isFloatingPoint!F) {
F[k] data;
The recursive call for the other coordinates is done at compile-time:
enum nextSplit = (split + 1) % d.length;//cycle coordinates
return new KdNode!(k, F)(d, split,
nk2!nextSplit(exset[0 .. m]),
nk2!nextSplit(exset[m + 1 .. $]));
Similar code, where one or more run-time function arguments are replaced by integer template arguments can be used where you have bounded recursion (you can also mix, unrolling the recursion calls statically up to a point, and then using regular function arguments for the rest of the recursion arguments, using a new function with run-time arguments instead of template arguments, and dispatching using a "static if"). This sometimes generates larger program binaries, but also sometimes huge speedups in my D code.
I have written a 15-problem solver in D that uses such coding pattern to partially unrolls the recursive search, generating few thousand functions in the binary (that I think the D compiler compiled in less than a minute), that was much faster (or much shorter to write for the programmer) than a regular search with run-time arguments.
To use type-level integers well perhaps you need the "static if" of D, and few other things.
Another common way to use type-level integers is to increase compile-time safety of the code (and again this also gives more static information to the compiler).
Here you can see an example, matrix multiplication with fixed-size arrays:
The first part is:
alias TMMul_helper(M1, M2) = Unqual!(ForeachType!(ForeachType!M1))
[M2.init[0].length][M1.length];
void matrixMul(T, T2, size_t k, size_t m, size_t n)
(in ref T[m][k] A, in ref T[n][m] B,
ref T2[n][k] result) pure nothrow @safe @nogc {
Unqual!() is a template that strips away most qualifiers from a type.
ForeachType!() gives the type of the items of the given array type.
M2.init[0].length gives the lengths of the rows of the M2 2D fixed-size array.
TMMul_helper helps you compute the type of the result:
TMMul_helper!(typeof(a), typeof(b)) result = void;
Most of the memory used by the matrixMul() templated function is allocated outside.
The type-level integers of matrixMul() make sure the size of input/output arrays are correctly sized.
One problem with matrixMul() is that the D compiler generates a new instance of matrixMul() for each possible type and each possible size of input arrays. This bloats the binary.
So in Rust I'd like an optional way to make the type-level integers ghosts. So a generic function like matrixMul() becomes parametrized only on the type of the items (and all the arrays become slices with run-time length).
(In C++/D you can fake that idea and reduce bloat using a wrapper function with full compile-time typing, that calls a private function with just run-time arguments. But I'd like to avoid writing the wrapper and to have many compiled wrappers inside the binary. On a related note, Bjarne Stroustrup wrote a paper where he proposed an annotation for C++ to be used inside template classes, to specify that some of the member functions are templated only according to a subset of the template arguments, to reduce template bloat. This is different from just letting the compiler spot where it can avoid bloat, because that annotation a contract between programmer and compiler).
