Saturday, May 16, 2015

Asymptotic Benchmark in Java

Most of the time when we analyze performance of different programs, we use Big O Notation and run performance tests for a single input size N, which measures execution time.

Both of these methods have disadvantages.
Big O Notation is theoretical (has no code verification).
Time based performance tests are not very reliable (it's hard to make assertions on them) and don't show the actual asymptotic function behind the programs.

Here I present a slightly different approach, which is a combination of those 2 techniques.
It uses explicit instruction counting, samples programs for different input sizes and tries to guess asymptotic function behind them.
It also plots the result as a chart using HTML and Google Visualization JavaScript Library.

Note that it's more of a toy for visualization than something one could use in the industry for real world projects.

First we start by implementing an example program (Binary Counter), which we want to measure. It'll extend a base class Benchmark, which looks like this (full source code is available on github: https://github.com/rafalrusin/abench):

public abstract class Benchmark {
    private int instructionCount = 0;

    protected void incrementInstructionCount() {
        instructionCount++;
    }

    public void resetInstructionCount() {
        instructionCount = 0;
    }

    public int getInstructionCount() {
        return instructionCount;
    }

    protected abstract Object run(int n);
}

It has abstact method "run", which takes input size as argument. This will be provided by the benchmark framework for different executions. 
Binary Counter implementation looks like this:

public class BinaryCounter extends Benchmark {
    @Override
    protected Object run(int n) {
        int[] counter = new int[64];
        for (int i = 0; i < n; i++) {
            int p = 0;
            while (counter[p] == 1) {
                counter[p++] = 0;
                incrementInstructionCount();
            }
            counter[p] = 1;
            incrementInstructionCount();
        }
        return counter;
    }
}

It is a 64 bit binary counter, which starts from 0 and increments values N times by one. Theoretically it should run in O(n) time. We'll verify that. 

We need to run it through the framework using following code:

public class Main {
    public static void main(String[] args) {
        BenchmarkRunner benchmarkRunner = new BenchmarkRunner();
        benchmarkRunner.addFormatter(new TextResultFormatter(new PrintWriter(System.out)));
        benchmarkRunner.addFormatter(new HtmlResultFormatter(new File("out")));

        for (Benchmark benchmark : new Benchmark[]{
                new BinaryCounter(),
                ...
                ) {
            benchmarkRunner.run(benchmark, 1);
        }
    }

Here's the chart generated for Binary Counter along with guessed function behind it:


In this case the guessed function is linear, which is what we expected. For input size of 5.6 millions, the instruction count was 11 million.

The guessing process is an iteration over all samples and optimization of Mean Squared Error.
It is implemented in BenchmarkRunner class. 
You can add more functions by extending Function interface. Here's an example of N log N function:

public class NLogNFunction implements Function {
    @Override
    public float eval(float x) {
        return (float) (Math.log(x) * x);
    }
}

Here's some more benchmarks: MergeSort (expected asymptotic function is N log N) and NestedLoop (N^2). 




Implementing reliable performance tests is not a very well solved problem today. I think that the idea of instruction counting is something one can try to use in real world projects. It can be used for testing performance of isolated chunks of code, within unit tests, and can give predictable results. 

20 comments:

  1. Keep up the great work, I read few blog posts on this site and I believe that your website is really interesting and has loads of good info.
    Loadrunner Training in Chennai
    Hadoop Training in Chennai
    JAVA Training
    Best JAVA Training institute in Chennai
    Java Courses in Chennai
    J2EE Training in Chennai

    ReplyDelete

  2. Howdy, would you mind letting me know which web host you’re utilizing? I’ve loaded your blog in 3 completely different web browsers, and I must say this blog loads a lot quicker than most. Can you suggest a good internet hosting provider at a reasonable price?
    AWS Training in Rajaji Nagar | Amazon Web Services Training in Rajaji Nagar
    Best AWS Training Institute in BTM Layout Bangalore ,AWS Coursesin BTM
    Amazon Web Services Training in Tambaram, Chennai|Best AWS Training in Tambaram, Chennai

    ReplyDelete
  3. Wow it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot. it is really explainable very well and i got more information from your blog.
    microsoft azure training in bangalore
    rpa interview questions and answers
    automation anywhere interview questions and answers
    blueprism interview questions and answers
    uipath interview questions and answers
    rpa training in bangalore

    ReplyDelete
  4. Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.
    Best Devops Training in pune
    Devops Training in Bangalore
    Power bi training in Chennai

    ReplyDelete
  5. Thanks for sharing such a great information..Its really nice and informative..

    sap fico tutorial
    sap fi training

    ReplyDelete
  6. I am very enjoying to read your well-written article posts. It seems that you devote a great deal of hard work and time onto your own blog.Learn PMP Training in Hyderabad 360DigiTMG

    ReplyDelete
  7. Thanks a lot for sharing great post with us. I’m happy that you shared this useful info with us. We are Ethnicitywiki provides information about Ethnicity, Race of famous Personalities, Businessman, and Wiki's Celebrities of Famous Personalities. Get all of the world news of celebrities and stars.

    Visit now www.ethnicitywiki.com

    Thanks again for sharing helpful information with us.

    Have a nice week ahead.

    ReplyDelete
  8. Hello! I know this is kinda off topic however , I’d figured I’d
    ask. Would you be interested in trading links or maybe guest writing a blog article or vice-versa?

    My blog addresses a lot of the same subjects as yours and I believe we could greatly benefit from each other.
    If you are interested feel free to shoot me
    an email. I look forward to hearing from you! Fantastic blog by the way!Click Me Here슬롯추천


    5YANGSKIE

    ReplyDelete
  9. Vacancysquare: Govt Scheme In India, Government Jobs, Government Scheme 2021, Latest Govt Yojana updates from Central Government Scheme, State Government Scheme, Public Sector Companies Yojana, Govt Scheme Notifications, Vacancy & Results, Sarkari Naukri, Private Job Notification, Syllabus with Complete Government Employment News. All Government Scheme / Jobs / Yojana / Sarkari Naukri Recruitment Notifications. Find here all government yojana list, job and government scheme with latest news only at: "https://vacancysquare.com/".

    ReplyDelete
  10. IFDA Institute in Delhi and kalkaji
    Ifda institute is India's No1 Digital Marketing Institute in Delhi and Kalkaji
    Digital Marketing Institute

    ReplyDelete
  11. C Language Course
    IFDA is India's No 1 IT-Training Institute in Delhi
    IFDA is Located in Delhi, Kalkaji and Badarpur
    IFDA Offers Wide Range of Professional Courses

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

    devops training in bangalore
    devops course in bangalore
    aws training in bangalore

    ReplyDelete