my name is Tom Bachmann and I'm applying for the Google Summer of Code programme to the FLINT project. In case anyone isn't aware, FLINT is a fast library for number theoretic computations, written in C. That is to say, it implements arbitrary-precision data types, and arithmetic and higher operations on them. For example, it provides arbitrary precision integers (so no matter how many times you multiply by two, you never get an overflow; although the required memory will increase linearly). Of course you can add and multiply integers, etc. More interestingly, you can also factorize them. Basically, anything you might want to ask about particular elements of the ring of integers, FLINT should be able to do. Similar support exists for the rational numbers, finite fields, and polynomial and matrix rings over these.
Also a few words about summer of code: the google summer of code (henceforth GSOC for short) is an annual programme sponsored by google, where students obtain three months of funding to write code for a free software (aka "open source") project. This is pretty awesome both for students (who can spend the summer doing something interesting and worthwile, without having to worry about money) and for the free software projects, which tend to see a huge amount of activity over the summer in this way.
And this is precisely what I want to do. In order to be accepted to GSOC, students apply to a mentoring organization. In my case, I'm applying to the lmonade platform, which is an umbrella organization coordinating and packaging various open source projects related to scientific computations. One such project is FLINT, whence the circle closes.
So what is it that I want to do in particular? Well, as stated at the very beginning of this post, FLINT is written in C. That's a very reasonable choice. It is meant to be as fast as at all possible, so a compiled language is necessary, and then (in my experience) to only reasonable choices are C and C++ (well, let's not overlook fortran, but then let's try to forget about it as fast as possible). The advantage of C++ over C is greater expressiveness, and in particular object-oriented syntax and semantics. The great advantage of C is "being the lowest common denominator". Essentially any programming language that exists is able to call C functions. Since an arithmetic library is meant to be highly reusable, this is a pretty strong argument in favour of C. Others are that not everyone likes C++ as much as I do (as far as I can tell, this is mainly because C++ is much more complex, and hence takes a lot more effort to undarstand and apply properly), and that certainly more people know C than C++.
Nonetheless, now that FLINT is an established library, it seems like a good idea to implement various language wrappers, to allow it to be used natively in other programming languages. The most obvious candidates for first language wrappers are python (because it is used a lot by the scientific community) and C++ (for all the reasons mentioned above). The project I am applying for, then, is the construction of a C++ wrapper library for FLINT.
This is an interesting challenge. Indeed, the wrapper library should achieve performance as close to the C library as possible, and also should achieve performance as close to any hypothetical native C++ implementation as possible. This means, in particular, that arithmetic operations should compile as efficiently as possible into C calls. For example, an expression like a + b + c + d could naively be evaluated as tmp1 = a + b; tmp2 = c + d; res = tmp1 + tmp2. However, it would be more efficient to write this as res = a + b; res += c; res += d; yielding fewer temporaries. In general, unless one is very careful, innocious-looking expression will call operator overloads, which create many inefficient temporaries. This has been known for a long time, and there is a reasonably straight-forward solution: expression templates. Essentially, an expression of the form a + b + c + d does not actually immediately cause any computation at all. Instead, only upon assignment res = (the above) is the computation executed. Until then, the arithmetic operations are encoded in the type of the expression. So a + b + c + d may return an object of a type such as Add<mpz, Add<mpz, Add<mpz, mpz> > > where the template class Add<A, B> stores simply a pair of objects. (Ab)Using the type system like this may seem like an abomination at first, but is actually very powerful, and has become common practice in the C++ community. (In fact, the template system can be used to implement a turing machine at compile time. One might argue this is taking it a step too far...) The point is that by delaying execution like this, we can determine the most efficient way of evaluating an expression once it is known completely. We can then use an arbitrarily complicated strategy to decide in what order to execute operations, how many temporaries to allocate, etc. This construction has two important properties:
- All the extra logic is carried out at compile time.
- This requires nothing beyond a C++ compiler.
All this (designing an expression template domain-specific language to carry out arithmetic operations most efficiently) in and by itself is quite fun already. But there is another interesting dimension to the problem. Namely, FLINT developers want to write highly specialised algorithms in C, not deal with a language wrapper (be it for C++ or anything else). As such, the wrapper must be very easy to extend, and doing so should require as little knowledge of C++ as possible. For example, FLINT supports many rings (integers, rationals, ...), and will support more in future. Adding a new data type to the wrapper should be as painless as possible.
This is a highlevel summary of how I understand my application. I have written out all the glory details (or at least, more details than here) in my proposal in melange. The application phase is already closed; by now it just remains to sit back and wait.
