[H-GEN] Which is better?

Tue Apr 27 20:14:30 EDT 2004

On Tue, 2004-04-27 at 23:13, Adrian Sutton wrote:
> insignificant portion of the time taken and profiling will show this 
> quite easily.  You've fallen into the premature optimization trap 
> again, it will be faster with the second example but not for the reason 
> you think, and then *only* if that method is called more than once and 
> is on the critical path.

> In the past 5 years of programming in Java there has only been one 
> occasion where excessive memory allocation was a significant 
> contributor to the slowness of the application.  In that case it was in 
> the border painter for a HTML layout engine - there were some 1000 

I have a different point of view.  I use C#, Java, and tools written in
C.  Now its very hard to sift out the truth from all the religious rants
out there.  For some reason the promoters ofJava and GC seem to be more
religious than most.  But there is one java'ism I tend to believe as
people produce reasonable benchmarks to support it.  It is that memory
allocation and initialisation time aside, modern Java JIT's execute Java
as fast as C.

But if that is true, how do you explain how a tool like say JBuilder is
so much slow that similar tools written by Borland in C?  My gut feel is
that it is slower by a factor of 3..5.  If is not speed of code
execution, then what the hell it is?  Some people blame swing, others
defend it viciously.

It turns of the same thing effects C#.  It is particularly noticable in
in things like bringing up a form, an operation that does 1000's of
memory allocations.  The interesting thing about C# is that you can't
blame the GUI this time - its all done by Windows.  If you assume the
JIT is as good as Java's (that possibly is a big assumption), then that
only leaves one thing, doesn't it?  Memory allocation.

> If you haven't profiled it, you don't know what you're talking about.

Excellent advice.  So lets profile it, shall we?  God knows, there have
been enough people preaching about "premature" optimisation on this
thread, so lets actually do some testing rather than just waffling on. 
At the very end of this post is a java program.  It runs some tests and
times them.  Under java 1.4.1 this is its output:

  dim unoptimised:     32212
  dim optimised:        1482
  format unoptimised: 343447
  format optimised:    90374
  Array unoptimised:    1570
  Array harry:          1439
  Array aj:             1456
  Array david1:         1432
  Array david2:         1457
  Array david3:         1523

A few points:

  - Moving the "new size()" outside of the loop speed up the loop
    by a factor of 20.  A huge speed up, as expected.  IMHO, a
    programmer who doesn't do this as a matter of course as he
    writes the code is a poor programmer.

  - Optimising the date format loop speed it up by a factor of 3.5.
    Note that the date loop took a loooong time - I had to reduce
    the number of iterations by a factor of 100.  Another large
    speed up - same comments as above.

  - Harries optimisation speed up by a factor of 14%.  This was
    surprising to me.  It means the JIT was not doing any
    global flow analysis.

  - Aj's optimisation was not quite as good as Harries, but still
    an improvement.  The old C coding tricks still work in java
    evidently.  Harry - if you still feel the urge to optimise
    your for loops use this.  It doesn't harm readability and is
    faster.

  - The real surprise came from testing David's conjecture.  I would
    of predicted that given a modern compiler there should be no
    difference.  The intent of the code should be obvious to any
    compiler.  Yet the results differ markedly.  This puts a dent 
    in the argument that optimisation should be left to the compiler.
    I am not sure Java is doing any.  A far better argument is that
    machines run so quickly nowadays that optimising your code is not
    worth the effort.

Anyway - the lesson I take from all this is that it is still worth
applying coding patterns like AJ's.  Its gives you a minor speed up to
your program at no expense in readability.  All bullshit aside memory
allocation in Java is a relatively expensive operation, and like all
expensive operations should be reduced where possible.  Not at the
expense of good design, of course, but then a good algorithm tend to
avoid expensive operations so the two goals don't totally conflict. 
Unfortunately, the term "at the expense of" is subjective, and a feel
for it only comes with experience.

By the by, I wrote the "dim unoptimised" test in C.  It ran 5,000 times
faster than the Java version.  Source code appears at the end.

======================== Main.java ========================

package allocdemo;

interface Test {
  void test();
}

public class Main {

  public static void main(String[] args) {
    runTest("dim unoptimised", dim_unopt);
    runTest("dim optimised", dim_opt);
    runTest("format unoptimised", format_unopt);
    runTest("format optimised", format_opt);
    runTest("Array unoptimised", array_unopt);
    runTest("Array harry", array_harry);
    runTest("Array aj", array_aj);
    runTest("Array david1", array_david1);
    runTest("Array david2", array_david2);
    runTest("Array david3", array_david3);
  }

  static void runTest(String description, Test test) {
    long start = System.currentTimeMillis();
    System.out.print(description + ": ");
    System.out.flush();
    for (int i = 0; i < 10; i += 1)
      test.test();
    for (int i = 0; i < 100000; i += 1)
      test.test();
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }

  static Test array_unopt = new Test() {
    public int[] array = new int[10000];
    public void test() {
      for (int i = 0; i < array.length; i += 1)
	continue;
    }
  };

  static Test array_harry = new Test() {
    public int[] array = new int[10000];
    public void test() {
      int l = array.length;
      for (int i = 0; i < l; i += 1)
	continue;
    }
  };

  static Test array_aj = new Test() {
    public int[] array = new int[10000];
    public void test() {
      for (int i = array.length - 1; i >= 0; i -= 1)
	continue;
    }
  };

  static Test array_david1 = new Test() {
    public int[] array = new int[10000];
    public void test() {
      for (int i = array.length - 1; i >= 0; --i)
	continue;
    }
  };

  static Test array_david2 = new Test() {
    public int[] array = new int[10000];
    public void test() {
      for (int i = array.length - 1; i >= 0; i--)
	continue;
    }
  };

  static Test array_david3 = new Test() {
    public int[] array = new int[10000];
    public void test() {
      for (int i = array.length - 1; i >= 0; i -= 1)
	continue;
    }
  };

  static Test dim_unopt = new Test() {
    public void test() {
      for (int i = 0; i < 10000; i += 1) {
	java.awt.Dimension d = new java.awt.Dimension();
      }
    }
  };

  static Test dim_opt = new Test() {
    public void test() {
      java.awt.Dimension d = new java.awt.Dimension();
      for (int i = 0; i < 10000; i += 1)
	continue;
    }
  };

  static Test format_opt = new Test() {
    public void test() {
      java.util.Date d = new java.util.Date();
      java.text.SimpleDateFormat myFormat =
        new java.text.SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
      for (int i = 0; i < 100; i += 1)
	myFormat.format(d);
    }
  };

  static Test format_unopt = new Test() {
    public void test() {
      for (int i = 0; i < 100; i += 1) {
	java.text.SimpleDateFormat myFormat =
          new java.text.SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
	myFormat.format(new java.util.Date());
      }
    }
  };
}

======================== x.c ========================

#include <stdio.h>
#include <time.h>
#include <malloc.h>

int main()
{
  long t = time(0);
  int i;
  for (i = 0; i < 100000000; i += 1)
    free(malloc(16));
  printf("elapsed = %d\n", time(0) - t);
  return 0;
}