Big Ints Between Python, PyPy, Go and Java

April 14, 2013

One of the challenges I set in the Computer & Network Security course's Wargames is factorisation. If you can factor a composite number n = pq where p and q are primes, then you can break RSA. The size of n we use in Wargames is quite small compared to the real world and it's mainly a bit of fun for students. As a given value of n is solved, we replace n with a number twice the difficulty.

Big Integers and Factorisation

Most computer architectures work most efficiently with 32 or 64 bit integers. Unless your computer is ancient. If you're browsing this on an 8 or 16 bit architecture, I commend you and would love to know!

The integers used for cryptography start at 128 bits and go up. RSA is even more resource intensive, requiring working with integers a minimum of 1024, 2048 or 4096 bits long. As such, the performance of big integer operations is quite important for number theoretic cryptography.

This is where I came across a surprising snag -- the low performance of Google Go's big integer library. The performance was poor compared to not just Java, known for being reasonably performant, but even PyPy and CPython. This was a shock as many suggest turning to Google Go for high performance. Whilst Google Go can certainly be highly performant in certain areas, I discovered it's not safe to assume it will be for a specific task.

Naive Factorisation

To get students going, I mentioned that the current value could be solved in only a few seconds using a naive Python program. Python isn't the fastest language but it is readable and has minimal boilerplate. For this task, CPython should also do reasonable well speed wise too: most of the work takes place in compiled CPython code, rather than Python itself.

The simplest way to find a factor for a given integer n is trial division:

    n = ...
    # If n is even, 2 is a factor, otherwise...
    i = 3
    while True:
      print i
      break
    i += 2

There are far more efficient methods, even for trial division, but this is the simplest in terms of lines of code and understanding. As such, I used it to demonstrate to students how to get started for this challenge, leaving them to discover the more complex methods.

This forms the basis of the benchmark.

Big Integer Performance Across CPython, PyPy, Java and Go

To test the performance of Big Integers across CPython, PyPy, Java and Go, I created a set of small benchmarks.

The challenge was to factorise n = 273966616513101251352941655302036077733021013991 (around 157 bits). As CPython and PyPy can "cheat" on small tests (they use 32 or 64 bit integers until Big Integers are required), we couldn't start on a small i and move up incrementally. As such, we tried to find the factor starting from i = 496968652506233112158689 (around 78 bits) and going up. The starting point i is only 10e6 away from one of the primes p so is equivalent to running the loop 5e6 times.

You can check out the code here.

What's most impressive here is that CPython performs so well. In this task, the majority of the computational work takes place deep in the depths of CPython, using compiled and optimised C code. Java performs admirably as you'd expect from the battle tested JVM. PyPy does quite well considering that the big integer code is written in RPython and don't have add any special cases.

Conclusion

Google Go is a promising language and I expect great things from the future. For certain tasks, specifically anything that can utilise goroutines, it can make your code faster and simpler than ever before. Assuming that it is generally high performance, however, is a mistake. Benchmark, benchmark and benchmark before dedicating any time pushing a CPU intensive task into Go or any other language.

Over time, this situation will improve. Whilst I need to look into the situation in more detail, it appears Go's 6g compiler had an implementation of the big package with assembler implementations that hadn't been ported to gccgo.