Execution Time Measurement [Java]
Time MeasurementTo measure execution time of your code in java use the 'System.nanoTime ()' command (see java API for details). To measure how long some codes takes to execute use:
long start_time = System.nanoTime ();In order to obtain reliable execution times, repeat the measurement a few times (say 5 to 10 times) and report the average time. You may try more sophisticated statistical analysis of the execution time, but this is beyond the scope of this course. However, when you are measuring the time make sure your system is "quiet", i.e. there are not any computational intensive tasks running that keep the CPU busy. To check the load of your system use a system monitor. Also, when you compare the execution time of some code, make sure you use the same platform (hardware and software environment) to get comparable timing results. Timing may differ between different platforms, so mixing platforms mixes comparing execution speed on different platforms and between different algorithms which leads to inconclusive results (only either compare different platforms or different codes).
// ... code being measured
long execution_time = System.nanoTime () - start_time;
Memory, Heap SizeTo test your program with large data sets you may have to expand the heap size of the JVM. You can use command line options to extend the heap size:
- Java heap memory is part of the memory requested by the JVM from the operating system to store your objects.
- Java heap memory is divided into three regions (or generations) for garbage collection: new generation, old/tenured generation, perm space.
- You can change (increase) the size of the heap space using the JVM command line option -Xms, -Xmx and -Xmn. Add "M" or "G" after specifying the size to indicate Mega or Giga. E.g. you can set java heap size to 512MB by 'java -Xmx512m MyProgram'
- -Xms sets the initial java heap size
- -Xmx sets the maximum java heap size
- -Xmn sets the size of the heap for the new generation
- For time measurement of code that requires a larger heap set the minimum -Xms and maximum -Xmx heap sizes to the same value. For efficient garbage collection, the -Xmn value should be lower than the -Xmx value.
- You can use either JConsole or Runtime.maxMemory(), Runtime.totalMemory(), Runtime.freeMemory() to get the heap size in Java. You can further use 'jmap' to create a heap dump and 'jhat' to analyze that heap dump.
- Heap space is not the same than the stack. The stack stores the call hierarchy and local variables. The stack size is set with -Xss.
- The java garbage collector is responsible for reclaiming memory from unused objects and returns it to the free heap space. You have very little control over when garbage collection takes place and it may be a good idea to initially create all the objects you need to obtain space from the heap and do the run time measurement on these objects without dropping any of them out of use to avoid that garbage collection distorts your time measurements.
Analysing Runtime Results
In order to evaluate run time results, it is usually a good idea to write out your run times over different algorithm runs, say for different problem sizes, as comma-separated-values (CSV). These can easily be read by a spreadsheet application such as gnumeric, libreoffice or excel to quickly analyse your results and draw some graphs. In most cases plots of the execution time over the problem size will give you a good idea of the performance. Alternatively you can also try to evaluate the time it takes for a basic operation. E.g. if you have two next loops from 1 to n, dividing the total time bywill give you an estimate of the average run time for the loop body (which may or may not be constant over the squared problem size ). You may also wish to divide the execution time by the number of memory accesses or simply by the problem size or the expected order of complexity to better see what is going on. Most of the time you will be using a linear scale for the plots, but for some problems it may also be helpful to use a logarithmic scale for the run-time or even a double-logarithmic scale for the runtime and problem size axes. In general choose the representation that best represents your findings about the algorithm. Changing the representation may sometimes help you to see specific issues more clearly.
Matlab to analyse and plot results
For some more advanced analysis you may also use matlab. For this write your results in the matlab matrix format, e.g.
A = [ 1, .1; 2, .4; 3, .8; ];
where the first column is the problem size and the second column is the (average measured) execution time. Store this in a file with a .m suffix, e.g. timings.m. Then run matlab in the same directory and load the timings simply by typing 'timings'. This will generate a matrix A in matlab. To easily analyse this matrix, store the values in columns, on the command line:
N = A(:,1); T = A(:,2);
To plot this you can then the command
Furthermore, you can for instance fit a curve to it using matlab's curve fitting tool by executing
Various more advanced data analysis is also possible (beyond what you can do with standard spreadsheet programs). For more details on this see the matlab documentation.