High performance large integers in .NET
When you’re playing with the sort of big integers used in, for example, cryptography, 64 bits just aren’t enough. In this post, I’ll compare and benchmark some of the alternatives that take .NET numerics beyond 64 bits. The benchmark results turn out to be a tale of the unexpected, to paraphrase Roald Dahl.
The test case is RSA signature verification, which uses the formula c=me mod n, where c, m and n are the same size as the RSA key (the public RSA key consists of n and e), typically 1024, 2048 or 3072 bits, while e usually is a mere 32 bits (usually holding the value 17 or 65537). In the test, I’ll use a 1024 bit key, because that conveniently enables me to reuse some F# code I wrote to verify RSA signed data written by EU digital tachographs.
Large integer libraries for .NET
System.Numerics.BigInteger and F# bigint
var a = BigInteger.Parse("1234567890123456789012345678901"); var b = BigInteger.Parse("9876543210987654321098765432109"); var c = a * b;
In F#, things are slightly more convenient, as you don’t have to mess with BigInteger.Parse(…) due to tighter language integration:
let a = 1234567890123456789012345678901I let b = 9876543210987654321098765432109I let c = a * b
As the example shows, usage is simple and straight forward in contrast to the higher performing GMP and MPIR libraries for C.
GMP is a well established C library for large integers, used by high end math software such as Mathematica and Maple. Though GMP’s main target platforms are Unix-type systems, the GMP website mentions that “it also is known to work on Windows in both 32-bit and 64-bit mode”, but there are very few instructions for how to compile the source code for Windows. There’s no forum where you could look for help either. There’s a mailing list, but you can’t browse/search it via Google Groups or anything similar. You’d have to use the mailing list archive available here. Looking for the search button? There isn’t any. If you need to search the mailing list, you have download the archives. One single month at a time. Gzipped in lots of tiny 15-30KB files. No, I’m not making this up.
Fortunately, there’s a GMP fork called MPIR that aims to make use in Windows projects painless, so I steered clear of GMP. Still, I felt that I had to mention it, because MPIR is based on it, and it’s a big name in multi precision libraries.
GMP for .NET
GMP for .NET, or Emil.GMP as it’s namespace is called, by Emil Stefanov combines the convenience of F# bigint with the speed of GMP. Unfortunately, it’s only available as a 32-bit version, but it’s just as easy and convenient to use as the System.Numerics.BigInteger, so I included it in the benchmarks. The C# usage examples looks almost identical to the System.Numerics.BigInteger example:
var a = new BigInt("1234567890123456789012345678901"); var b = new BigInt("9876543210987654321098765432109"); var c = a * b;
MPIR is a fork of GMP, that aims to make compilation on Windows painless. To qoute an MPIR contributor: “In contrast with GMP, the MPIR community welcomes native Windows development […]. Although many on the MPIR development team are dedicated Linux/GCC users, they are not hostile to native Windows development”. MPIR has a mailing list, and you can browse and search it on Google Groups.
Like GMP, MPIR is a C library, so some sort of wrapper containing a ton of either DLLImports or GetProcAddress assignments will be necessary in order to use if from .NET. As it happens, such a wrapper already exists in the form of X-MPIR, by Sergey Bochkanov of ALGLIB fame. Usage from C#:
var a = mpir.mpz_init_set_str("1234567890123456789012345678901", 10); var b = mpir.mpz_init_set_str("9876543210987654321098765432109", 10); var c = mpir.mpz_init(); mpir.mpz_mul(c, a, b); // c = a*b // ... mpir.mpz_clear(a); // Must be called after use, to mpir.mpz_clear(b); // avoid unmanaged memory leak. mpir.mpz_clear(c);
As you can see, this looks very much like C, including manual memory management (you must call mpz_clear to deallocate memory).
For the purpose of writing the benchmarks in this blog post, I’ve modified X-MPIR to introduce a new type, mpz_t, which implements IDisposable, in order to not have to bother with manual memory management.
Since the particular case of playing with big integers here, is RSA signature verification, I’ve included .NET’s built-in RSACryptoServiceProvider from the System.Security.Cryptography namespace. It’s not useful for handling large integers in general, but it was still interesting to compare its performance to that of the general practitioners in the big number business. Surely, it will have a speed advantage, considering that it’s specialized for RSA operations…or will it?
Benching the contenders
Benchmarking in .NET turns out to be weird, or in more technical terms, nondeterministic. I suspect that garbage collection has a life of its own that accounts for a lot of performance variation. The benchmark method I resorted to, was to measure the time of 50000 signature verifications, repeat this 1000 times, and pick the fastest time out of those 1000 measurements. My reasoning behind this, is that the best time is the one that is least disturbed by background processes and garbage collection. Before each measurement, garbage collection is forced and the thread sleeps for half a second, as a way to yield to other processes.
The benchmarks are run under Windows 7 64-bit on a 2.83GHz 4 core Q9550 system. I would have loved to run them on my new Haswell Thinkpad under Windows 8.1 as well, but it’s got a bricked motherboard (BIOS bug) and Lenovo has been sitting on it for weeks and will continue to do so for at least 2 weeks more. Their warranty service is slower than the seasons.
The benchmark shows a few unexpected results. One would expect the 64-bit versions of all libraries to be at least twice as fast as their 32-bit counterparts. In the case of BigInteger, this is far from the case. You only get 1.6 times the performance when you take the step to 64 bits. Furthermore, there is no performance to be gained by using the RSACryptoServiceProvider class instead of MPIR class in 32-bit mode, and in 64-bit mode, it’s a downright loss. RSACryptoServiceProvider turns out to be more than twice as fast in 64- as in 32-bit mode, at about 2.4 times the performance. Surprisingly, MPIR show a full 2.9 times performance increase in the 64-bit version.
It’s as plain as a pikestaff, that MPIR is the performance king among the tested libraries, while BigInteger and GMP for .NET are the winners from the usability perspective.
Clearly, what we would want is the performance of MPIR mated with the usability of GMP for .NET. And that is exactly what we shall have: Mpir.NET – NuGet package for high performance large integers.