1

I am trying to make a program in Java which measure the complexity of a specific program with respect to its run time. Let's take a problem and code that problem in all possible ways with respect to time complexity, let's say we can write code for a specific problem in O(n), O(log(n)), O(n log(n)) and O(n^2).

I will record the run time of each case and I will make a scale with these values to measure the time complexity of other's solution. Like

  1. O(n) -> 2-3 ms
  2. O(log(n)) -> 1-2 ms etc.

Now if other code has run time 2.3 ms, then my Java program will say that given solution has time complexity of the order O(n).

Now problem is that, as my code is in Java, whenever I run any program using Ubuntu commands through Java code , each time I get the different run time, and the run time has very huge range from 0.364246 to 0.902362.

Why it is happening and what can I do to make a efficient scale?

Here is my code: 

import java.io.*;

class ps_ef
{
    public static void main(String args[])
{
    String s=null,file_name,extension;
    int pos = args[0].lastIndexOf(".");

    extension = args[0].substring(pos+1);
    file_name = args[0].substring(0,pos);

    int lang = 0; //  1 -> c,c++ , 2 -> java

    try
    {   

        Process compile = null;

        switch(extension)
        {
            case "c"    :    compile = Runtime.getRuntime().exec("gcc -g "+ args[0] + " -o "+file_name);
                        lang = 1;           
                        break;
            case "c++"  :    compile = Runtime.getRuntime().exec("g++ -g "+ args[0] + " -o "+file_name);
                        lang = 1;
                        break;
            case "java" :    compile = Runtime.getRuntime().exec("javac "+ args[0]);
                        lang = 2;
        }

        BufferedReader stdError = new BufferedReader(new InputStreamReader(compile.getErrorStream()));

        if((s = stdError.readLine()) != null)
        {
            System.out.println("Compile Time Error OR Warning : ");

            System.out.println(s);
            while((s = stdError.readLine()) != null)
            {
                System.out.println(s);
            }
        }

        double startTime, run_time;
        Process run;

        if(lang == 1)
        {
             startTime = System.nanoTime();

             run = Runtime.getRuntime().exec("./"+file_name);

             run_time = (System.nanoTime()-startTime)/(double)Math.pow(10,6);
        }
        else
        {

            startTime = System.nanoTime();

             run = Runtime.getRuntime().exec("java "+file_name);

             run_time = (System.nanoTime()-startTime)/(double)Math.pow(10,6);
        }

        System.out.println("RunTime : "+ run_time+" ms");

        BufferedReader run_stdInput = new BufferedReader(new InputStreamReader(run.getInputStream()));

        BufferedReader run_stdError = new BufferedReader(new InputStreamReader(run.getErrorStream()));

        if(( s = run_stdError.readLine()) != null)
        {
            System.out.println("Runtime Error : ");

            System.out.println(s);

            while((s = run_stdError.readLine()) != null )
            {
                System.out.println(s);
            }
        }
        else if((s = run_stdInput.readLine()) != null)
        {
            String s_string = null;
            int failed = 0;

            File fs = new File(file_name+".txt");

            BufferedReader br  = new BufferedReader(new FileReader(fs));

            if((!s.equals(s_string = br.readLine())))
            {
                failed = 1;
            }

            while(((s = run_stdInput.readLine()) != null) & ((s_string = br.readLine()) != null) & (failed == 0))
            {
                if(!s.equals(s_string) )
                {
                    failed = 1;
                    break;
                }
            }

            if((failed == 1) || s != null || s_string != null)
            {
                System.out.println("Submmision Failed : ");
                System.out.println("Either Output Is Wrong.\nOR\nYour Output Is Not According To The Given Format. ");
                System.exit(0);

            }
            else
            {
                System.out.println("Submission Successful.");
            }

        }
    }   
    catch(IOException e)
    {
        System.out.println("Some Error Has Occured : ");
        e.printStackTrace();
        System.exit(-1);
    }

}

}

Here is my output of run time: enter image description here

Improve this question
2
  • 7
    Your question is anwered at How do I write a correct micro-benchmark in Java? over on Stack Overflow. Basically because writing a meaningful microbenchmark is non-trivial. Commented Dec 29, 2013 at 11:27
  • Thank you Joachim! Its my first time when i am listening the term "Benchmark". Thank you. Commented Jan 1, 2014 at 15:39

2 Answers 2

Reset to default
12

Benchmarking is a difficult science. It seems that your computer is conspiring against you:

  • Your CPU keeps often-requested data in caches. As accessing memory in a cache is faster than using other memory, this can warp benchmarks.
  • Your OS may cache files in memory rather than loading them from disk. Obviously this hasn't happened the first time you run a program. Subsequent runs should be faster.

  • Time-sharing operating system kernels like Linux, Mach or Windows NT juggle multiple processes at the same time. This means that other processes may be executed in between of execution phases of your benchmarked program. Therefore measuring the elapsed time is inaccurate (it likely also includes execution time from other processes). You should be measuring the used CPU time instead. On the other hand that become inaccurate if the benchmark isn't CPU-bound.

    Measuring elapsed time vs. CPU time is also important when considering multi-threaded programs that run on multiple cores. A multi-threaded program can run “faster”, but use more CPU time than a single-threaded solution.

    Scheduling not only affects how the times should be measured, but can also invalidate caches.

Benchmarking programs written on the JVM is even more complicated because

  1. It has a massive start-up time that has to be subtracted to get the actual run time
  2. It may interpret the program (slow) or compile it to highly optimized machine code (takes a moment, then extremely fast), or may revert back to interpreting. So while for many uses, Java is slower than C, it can potentially be faster.
  3. Garbage collection may halt the execution at any time to analyze the memory.

There are many settings that can affect JVM performance; doing this correctly is difficult.

Now let's say you have figured out how to obtain correct measurements. We can then solve issues around file caching by simply running the program multiple times and discarding the first run. Issues around scheduling can be minimized by running the benchmarks in a controlled environment with few processes (e.g. running in single-user mode without a graphical environment).

We can now collect a series of data points for each program. Especially on the JVM it is important to run the code repeatedly until all optimizations have kicked in so that the measurements have roughly converged onto one level. An useful tool for this is the mean value of the last n measurements.

When reporting the average run time, we not only report the mean value of all runs, but also the standard deviation (sometimes called sigma) that shows how coherent the measurements are. A smaller value is preferable. The SD is normalized on the mean value, so it is only comparable for the same mean value, not between runs with different means.

If you want to show that a program has a specific algorithmic time complexity, you have to run it with inputs of different sizes (e.g. n = 0, …, 1.000.000 items in steps of 100.000). For each input size you will record one or more measurements, and then fit different equations to the data set:

O(1):       t = a
O(log n):   t = a * log(n)/log(b) + c    likely special cases a=2 or a=e
O(n):       t = a * n   + b
O(n log n): t = a * n * log(n)/log(b) + c
O(n^2):     t = a * n^2 + b
O(n^3):     t = a * n^3 + b
O(a^n):     t = a^(b * n) * c + d    likely special case of a=2
...

For each fit, you can then calculate the square distance between the fit and the data set. The complexity class with the smallest square distance to the data set is probably the complexity class of the used algorithm.

Implementing curve fitting yourself is almost as non-trivial as correct benchmarking, so you should probably use an existing implementation (I use Python with scipy for this kind of work).

Note that in complex cases the observed run time can be the sum of run times of algorithms with different complexities, but the largest complexity class should dominate on sufficiently large input.

Improve this answer
1
  • Thank you amon. First time i have listened the term "benchmark". Commented Jan 1, 2014 at 15:40
1

Don’t benchmark milliseconds. Run the code a few thousand times so you measure seconds, then list the results for ten consecutive runs.

For example, each core on my computer runs at one of ten speeds in GHz and the speed can change at any time, mostly depending on processor temperature and battery status. So the benchmark results can change any time.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.