For measuring the runtime of a section of code in Java, the System.nanoTime() method is all you really need (see the documentation for a simple example).
Java uses several techniques that help your code run efficiently but that can can negatively affect runtime analysis experiments. The negative effects can typically be avoided with some foresight and planning, however.
JIT Compiler¶
Java code executes in a virtual machine
using a technique called Just-In-Time (JIT) compiling, which can cause problems when benchmarking.
In short, the JIT compiler is a system that makes code run more efficiently (faster), but it only activates after the code has been running for a while. That is, your code will run inefficiently for a while (on the order of milliseconds), and then the JIT compiler will kick in and make your code run more efficiently from then on. The issue here is that any runtimes recorded before the JIT compiler activates cannot be compared with runtimes measured after.
One solution to this problem is to make sure you only measure runtimes after the JIT compiler has activated. This can be done by running all of your to-be-measured algorithms several times before you start measuring runtimes. This “warms up” the JIT compiler, optimizing your code, so that when you do measure runtimes, it’s only running the optimized code.
The question becomes: How much is “several times?” There’s no clear answer to that, but I’d say that if you run each algorithm for roughly a second (or maybe half a second) each, that should be sufficient.
“Dead Code” Optimization¶
Another optimization Java performs, that it shares with most compiled languages, removes “dead code” from your program when it is compiled. “Dead code” is code that the compiler determines will not have any affect on the output of the program or its state in any way. For example:
void deadFunc(int x) { int b = x + 5; }
This function takes a value and adds 5 to it, but that computation has no effect on anything outside of the function. The function could thus be optimized away (so that nothing actually happens when it is called) with no effect on the program when it runs. The compiler will do this whenever it can to make the program run faster.
This can be an issue when benchmarking code because in a benchmarking situation, you typically do not have the program do anything with the results of the benchmarked functions. In the case of benchmarking algorithms, you’ll call the algorithm, but you won’t necessarily store its return value, because it isn’t needed for measuring runtime. The compiler may thus determine that your whole algorithm is dead code and optimize it out. That would result in an incorrectly fast runtime (because it takes almost no time to… do nothing).
Keep an eye out for this in your results. If any algorithm appears to always run incredibly fast, and it never gets slower with increasing input size, then you probably have run into dead code elimination. To avoid it in that case, make sure you store the result of the function each time it’s called. You may have to do something like add the result to a list or something as well, though most likely not.