Paper shelf
Veldhuizen thesis
A short companion to the Veldhuizen thesis on active libraries and C++ templates. The thesis is the longer-form treatment of the same ideas behind Blitz++ and the Turing-completeness paper, applied to scientific computing.
What the thesis is
The Veldhuizen thesis is a doctoral dissertation on active libraries - libraries that behave differently depending on how they are used, using the C++ template system to resolve as many decisions as possible at compile time rather than at runtime.
The file is at /ubigraph/content/Papers/pdf/VeldhuizenThesis.pdf.
What an active library is
A conventional library is passive. You call it with data and instructions. It does what you ask. The library does not know whether you are calling it from a tight numerical loop or an interactive program.
An active library knows more. It uses the template system to inspect how it is being used at the point of use. It can specialise itself for a specific data layout, a specific loop structure, or a specific set of constraints. The result is code that reads like high-level library code but compiles to the same tight loops you would write by hand.
The idea is that the library itself participates in optimisation rather than leaving all of that work to the compiler or the programmer.
What the thesis covers
The thesis develops the theory of active libraries and provides several worked examples in the scientific computing domain. Blitz++ is one of the examples. The thesis goes further than the Blitz++ paper and the Turing-completeness paper by framing both as instances of the same design pattern.
A few topics from the thesis that are worth knowing:
- Expression templates in depth. The mechanics of how an array expression like
c = a + b * dcan be transformed at compile time into a single efficient loop. - Template metaprogramming as compilation. The case that template instantiation is a form of partial evaluation, and what that means for library design.
- Limits and failure modes. The thesis is honest about where the technique breaks down and what it costs in build time and compiler compatibility.
How it connects to graph tooling
The thesis is the most directly relevant of the three papers on this shelf for someone thinking about graph library design.
A graph library has the same design problem the thesis is about. It needs a data structure that is flexible (sparse graphs, dense graphs, labelled edges, weighted edges) and fast (the inner loop has to be tight). It needs an API that reads well at the point of use and compiles to code that does not pay for the abstraction.
The active library pattern is one of the better answers to that design problem. A graph library built on these techniques can specialise its force computation, its traversal order, and its representation based on the kind of graph you are working with, all at compile time.
A reading path
The thesis is longer than the papers. A practical reading path:
- Read the introduction. Get the definition of an active library and the central claims.
- Read the Blitz++ section. It is the most worked example and the one with the most concrete detail.
- Skim the formal treatment. Pick up the vocabulary even if you do not follow every proof.
- Read the conclusion. See where the author thinks the limits are.
The thesis is not an easy read. It is a careful one. It rewards the time.