Wednesday, June 19, 2013

Analyzing FizzBuzz Performance on Java and Scala

Recently, I attended a technical interview for a Java developer role. The first problem that was given to me was to solve the FizzBuzz test.
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
While the FizzBuzz test is apparently a popular interview problem, I've never encountered it before. And to be honest, I did not find the problem too challenging so this worried me a bit (more often than not, easy interview problems are trick questions).

My policy when writing code is that the simplest solution is usually the best solution. So, I gave them the most straight-forward solution I can think of.
for (int i=1; i <= 100; i++) {
    if (i % 3 == 0 && i % 3 == 5)
        println("FizzBuzz")
    else if (i % 3 == 0)
        println("Fizz")
    else if (i % 5 == 0)
        println("Buzz")
    else
        println(i)
}
As expected, the interviewers asked me to improve my code. It's obvious that the mod expressions are duplicated so I assigned them to variables.
for (int i=1; i <= 100; i++) {
    boolean fizz = i % 3 == 0
    boolean buzz = i % 5 == 0
    if (fizz && buzz)
        println("FizzBuzz")
    else if (fizz)
        println("Fizz")
    else if (buzz)
        println("Buzz")
    else
        println(i)
}
I was pretty happy with this solution especially because it made the intentions code easier to read. However, the comment from the interviewers was that in order to get to the most common case (divisible by neither 3 nor 5), I would have to evaluate 3 branch statements.

To solve this, I added an initial check if the number is divisible by neither 3 nor 5.
for (int i=1; i <= 100; i++) {
    boolean fizz = i % 3 == 0
    boolean buzz = i % 5 == 0
    if (!fizz && !buzz) {
        println(i)
    } else {
        if (fizz && buzz)
            println("FizzBuzz")
        else if (fizz)
            println("Fizz")
        else
            println("Buzz")
    }
}
I personally did not like this solution, I feel that the added check is redundant and made the intention of the code less obvious. In fact, I told the interviewers that I was choosing my 1st solution over this one.

I can tell that the interviewers are not completely convinced; but we already spent too much time on this problem so we moved on. Quite frankly, I didn't think I can improve my solution any further at that point.

As soon as I reached home, I tried thinking of a better solution but couldn't come up with one. So, I did the natural thing and searched the internet! I was pleased to see that most people came-up with the same solution as I did.

However, I found a blog with an interesting solution.
for (int i=1; i <= 100; i++) {
    boolean fizz = i % 3 == 0
    boolean buzz = i % 5 == 0
    if (!fizz && !buzz) {
        print(i)
    } else {
        if (fizz)
            print("Fizz")
        if (buzz)
            print("Buzz")
    }
}
Notice that the above code (a rough translation to Java) is mostly equivalent to my 2nd solution except for a major twist -- that is, it eliminated the branch for "FizzBuzz" by concatenating the results of both "Fizz" and "Buzz" branches.

In my opinion, the intention of the above code is even less obvious than my 2nd solution (at quick glance, I wouldn't think that it prints "FizzBuzz" at all); but since we are aiming for an optimized solution, this one seemed better.

I was curious how these solutions differ in terms of performance, so I decided to write an actual test.

I wrote my tests in both Java and Scala (for practice mostly). To make an "apples to apples" comparison, all solutions will be calling print rather than println (otherwise the 3rd solution would require an extra step to print a new line every iteration). Also, to eliminate the I/O overhead, I used a PrintWriter as a substitute to System.out.

Below is my Java implementation.
private static void fizzBuzz1(int n) {
    PrintWriter writer = new PrintWriter(new StringWriter());
    for (int i = 1; i <= n; i++) {
        boolean fizz = i % 3 == 0;
        boolean buzz = i % 5 == 0;
        if (fizz && buzz)
            writer.print("FizzBuzz");
        else if (fizz)
            writer.print("Fizz");
        else if (buzz)
            writer.print("Buzz");
        else
            writer.print(i);
    }
}

private static void fizzBuzz2(int n) {
    PrintWriter writer = new PrintWriter(new StringWriter());
    for (int i = 1; i <= n; i++) {
        boolean fizz = i % 3 == 0;
        boolean buzz = i % 5 == 0;
        if (!fizz && !buzz) {
            writer.print(i);
        } else {
            if (fizz && buzz)
                writer.print("FizzBuzz");
            else if (fizz)
                writer.print("Fizz");
            else
                writer.print("Buzz");
        }
    }
}

private static void fizzBuzz3(int n) {
    PrintWriter writer = new PrintWriter(new StringWriter());
    for (int i = 1; i <= n; i++) {
        boolean fizz = i % 3 == 0;
        boolean buzz = i % 5 == 0;
        if (!fizz && !buzz) {
            writer.print(i);
        } else {
            if (fizz)
                writer.print("Fizz");
            if (buzz)
                writer.print("Buzz");
        }
    }
}
Below is my Scala implementation.
  def fizzBuzz1(n: Int) = {
    val writer = new PrintWriter(new StringWriter)
    for (i <- 1 to n) {
      val fizz = i % 3 == 0
      val buzz = i % 5 == 0
      if (fizz && buzz) writer.print("FizzBuzz")
      else if (fizz) writer.print("Fizz")
      else if (buzz) writer.print("Buzz")
      else writer.print(i)
    }
  }

  def fizzBuzz2(n: Int) = {
    val writer = new PrintWriter(new StringWriter)
    for (i <- 1 to n) {
      val fizz = i % 3 == 0
      val buzz = i % 5 == 0
      if (!fizz && !buzz) {
        writer.print(i)
      } else {
        if (fizz && buzz) writer.print("FizzBuzz")
        else if (fizz) writer.print("Fizz")
        else writer.print("Buzz")
      }
    }
  }

  def fizzBuzz3(n: Int) = {
    val writer = new PrintWriter(new StringWriter)
    for (i <- 1 to n) {
      val fizz = i % 3 == 0
      val buzz = i % 5 == 0
      if (!fizz && !buzz) {
        writer.print(i)
      } else {
        if (fizz) writer.print("Fizz")
        if (buzz) writer.print("Buzz")
      }
    }
  }
My test involves executing the 3 solutions 100,000 times to ensure that the HotSpot JVM is properly "warmed-up". I measured the performance by recording the average elapsed time of each iteration. I then used these averages to calculate the percentage difference in performance.
val range = 100
val iterations = 100000

val totalFizzbuzz1 = run(fizzBuzz1, range, iterations)
val totalFizzbuzz2 = run(fizzBuzz2, range, iterations)
val totalFizzbuzz3 = run(fizzBuzz3, range, iterations)

val aveFizzbuzz1 = totalFizzbuzz1.toDouble / iterations
val aveFizzbuzz2 = totalFizzbuzz2.toDouble / iterations
val aveFizzbuzz3 = totalFizzbuzz3.toDouble / iterations

val maxAve = List(aveFizzbuzz1, aveFizzbuzz2, aveFizzbuzz3).
    reduceLeft((l, r) => if (r > l) r else l)

def run(f: (Int) => Unit, range: Int, iterations: Int) = {
  var startTime: Long = 0
  var totalTime: Long = 0
  for (i <- 1 to iterations) {
    startTime = System.nanoTime()
    f(range)
    totalTime += (System.nanoTime() - startTime);
  }

  totalTime
}
Note that the above test is repeated several times to check for consistency.

On my machine (i7-2600 @ 3.40 GHz x 8 Cores + 8 GB RAM), I got the following result:
=== Round 1 ===

Iterations: 100000
Range: 100

- Averages -
Solution 1 = 6862.5038 ns.
Solution 2 = 6071.6055 ns.
Solution 3 = 6112.7298 ns.

- Statistics -
Solution 1 = 0% faster
Solution 2 = 11.5249% faster
Solution 3 = 10.9257% faster

=== Round 2 ===

Iterations: 100000
Range: 100

- Averages -
Solution 1 = 5732.6164 ns.
Solution 2 = 5735.8125 ns.
Solution 3 = 6069.4501 ns.

- Statistics -
Solution 1 = 5.5497% faster
Solution 2 = 5.497% faster
Solution 3 = 0% faster

=== Round 3 ===

Iterations: 100000
Range: 100

- Averages -
Solution 1 = 4690.641 ns.
Solution 2 = 4126.3942 ns.
Solution 3 = 4331.1555 ns.

- Statistics -
Solution 1 = 0% faster
Solution 2 = 12.0292% faster
Solution 3 = 7.6639% faster

=== Round 4 ===

Iterations: 100000
Range: 100

- Averages -
Solution 1 = 3985.0794 ns.
Solution 2 = 4201.1156 ns.
Solution 3 = 4299.2292 ns.

- Statistics -
Solution 1 = 7.3071% faster
Solution 2 = 2.2821% faster
Solution 3 = 0% faster

=== Round 5 ===

Iterations: 100000
Range: 100

- Averages -
Solution 1 = 3994.3317 ns.
Solution 2 = 4103.4171 ns.
Solution 3 = 4293.0744 ns.

- Statistics -
Solution 1 = 6.9587% faster
Solution 2 = 4.4177% faster
Solution 3 = 0% faster
What is immediately noticeable is that my test is unable to arrive at a consistent result! More so, what's surprising is that the 3rd solution performed worst 3 out of the 5 runs (2, 4, 5). The 1st solution however, performed best 3 out of the 5 runs (2, 4, 5).

Note that the above results do not imply that the 1st solution is the fastest and that the 3rd solution is the slowest. What can be concluded from the above results however, is that the performance of these solutions do not matter -- in fact, my test written in Java yielded similar results. The performance difference from these solutions are so negligible that we are better off with the most straightforward solution (the 1st solution, in my opinion).

This is exactly what is meant by avoiding premature optimization. By optimizing code without bothering to measure the actual performance, readability suffers and more harm is done. Rather than focus on optimizing at code level, efforts are better spent designing an architecture that is built for performance.

No comments :

Post a Comment