According to this page (near the bottom), when Java 1.3 switched from using a native BigInteger implementation to a purely-Java implementation, it gained an increase in speed of "as much as 5x or more." This has led many people to believe that Java’s BigInteger class is comparable in speed to the popular Bignum and GMP C-libraries.
I recently got to work with both BigInteger and Bignum for a project implementing a signing scheme related to RSA, so I decided to go a bit out of my way and compare the speeds of each on my machine. In addition, I needed a list of the first 16-million odd prime-numbers, so I implemented a simple Sieve (pronounced "siv," not "seeve") in both Java and C, with some surprising benchmarks.
The Setup
I used the current latest versions of the Java runtime (1.6.0.07) and OpenSSL (0.9.8i) in conducting these tests. They were run on an HP Pavilion dv9720us laptop with a dual-core Turion64 TL-60 (2 GHz) under Windows XP. Neither program was written to explicitly take advantage of the dual-core setup, and as far as I could tell (observing Windows task-manager), neither of them did.
BigInteger vs Bignum
The following table summarizes the results. Note that when I say small exponentiation, what I mean is a large (1024-bit) base to a small (32-bit) power, with a large modulus.
| BigInteger vs. Bignum (smaller is better) | ||
| BigInteger (Java) | Bignum(C) | |
| 16-million small multiplies and a large exponentiation | 62.94 seconds | 16.42 seconds |
| 2-million small exponentiations | 1892.92 seconds | 553.41 seconds |
Also, here are some graphs for those of you who can’t stand to read a blog-post with no pictures:
Sieve of Eratosthenes
Perhaps the previous results should have been expected; after all, Bignum is written mostly in pure assembly, and I’m sure there’s some crazy assembly voodoo that can dramatically increase the speed of adding and multiplying large numbers. However, surely with all the amazing advancements in JIT technology I hear about so often, a plain ol’ prime-number generator in Java will perform almost as fast as, if not faster than (the JIT does, after all, have more information available to it than a normal compiler) its half-brother, C … right?
Sieve of Eratosthenes on 16-million numbers (smaller is better) | |
| Java | C |
| 30.94 seconds | 7.80 seconds |
And the graph, for those of you who dun’ do numbers so good:
Conclusion
What can I say? Everyone knows that for calculation-intensive tasks, native programs run faster than those that run under a VM – but I believe we’ve all been drastically misled as to the difference in speed between the two. Perhaps you should keep this in mind the next time you’re doing requirements analysis for your next project.
2 Comments
That is, of course, assuming your project is more computationally-intensive and less (for example) database-intensive..
I’d love to have the bechmark source, so I could run it.