ReRe: performance - some details (and shellsort)

[Norman Hendrich]

Hello Jeff,

> A couple of things...
> First, you don't say how much memory you have installed, or how large
> the process grows.  Is there any chance of swapping during the tests?

My machine is a Cyrix-MII/300 (233MHz) with 64 MByte and 512K L2 cache. 
The Shellsort demo uses up to ~48 MByte with the JDK, a little less with gcj.
My "slow apps" use less than 10 MByte. No swapping involved.

> Second, what heap parameters are you passing to the JDK?  As I mentioned
> earlier in this thread, memory-intensive code can benefit from a large
> initial heap.  The current libgcj has no mechanism for specifying the
> initial heap size, however, so if you are using a large -ms value it
> isn't a fair comparison.

Yes, I do know the effect of the -ms parameter. However, it doesn't have
much effect for the ShellSort demo. Most cpu time is spend in the
shellsort() algorithm, not in the object allocation.  Naturally, I had 
to use -mx48M for the ShellSort 1000000 demo, all others were run with 
the 16 MB default.

> I'm not sure whether a GC cycle took place during any of the tests,
> which could have a big impact on the results.  (It'd be really nice to
> have a way to profile GC activity in libgcj, much like -verbosegc does
> for the JDK.)

The JDK probably didn't GC, because the shellsort demo allocates all
arrays at program start and doesn't request objects afterwards.
I don't know about gcj.

> libgcj doesn't normally fork processes.  On Linux, individual threads
> show up as separate entries in the process table (and thus in /bin/ps)
> even though they belong to the same process.

OK, it may be a second thread instead of a separate process. The curious
thing, however, is that the CPU time of that thread does not show up
in the user-time of the 'time ./a.out' command...


> Is your code multithreaded by any chance?

I don't have any idea what the mysterious second thread does, except
spending CPU cycles. The code is not multithreaded, see below.
For copyright-reasons, I cannot post our 'problematic' apps.

- Norman



---------------- cut here --------
/* ShellSort.java - class hades.utils.ShellSort */ 

//package hades.utils;

/**
 * sort double array A[] and permute array O[] on the fly.
 */
public class ShellSort {


  /**
   * Shellsort algorithm (Sedgewick 89).
   * Sort the double array A[] and permute object O[] on the fly.
   */
  public static void shellSort( double A[], Object O[] ) {
    int i, j, h, N = A.length;
    double v;
    Object w;

    for( h=1; h <= N/9; h = 3*h+1 )
      ;
    for( ; h > 0; h /= 3) {
      for( i = h+1; i <= N; i++ ) {
        v = A[i-1];
        w = O[i-1];

        j = i-1;
        while( j > h-1 && A[j-h] > v ){
          A[j] = A[j-h];
          O[j] = O[j-h];
          j -= h;
        }
        A[j] = v;
        O[j] = w;
      }
    }
  } /* end shellSort */


  private static void msg( String msg ) {
    System.out.println( msg );
  }


  /**
   * main(): simple but efficient self test for the Shellsort algorithm.
   * This will generate and sort n random numbers.
   *
   * Usage: java Shellsort <arraylength> [doPrint]
   */
  public static void main( String argv[] ) {
    System.out.println( "Shellsort self test started..." );
    int N = 0;
    if (argv.length < 1) {
       System.out.println( "Usage: java Shellsort <arraylength> [doPrint]" );
       return;
    }
    else {
       N = Integer.parseInt( argv[0] );
    }

    System.out.println( "...generating random numbers..." );

    double d[] = new double[N];
    Object o[] = new Double[N];
    double sum = 0.0;

    for( int i=0; i < N; i++ ) {
       d[i] = (int) (1000000 * Math.random());
       o[i] = new Double( d[i] );
    }
    for( int i=0; i < N; i++ ) sum += d[i];

    System.out.println( "...sorting..." );
    shellSort( d, o );

    System.out.println( "...checking..." );

    double sum2 = 0, ovalue;
    for( int i=0; i < N; i++ ) {
       ovalue = ((Double) o[i]).doubleValue();
       if (d[i] != ovalue) msg( "d[i] != o[i]: " + d[i] + " " + o[i] );
       if ((i > 0) && (d[i] < d[i-1])) 
          msg( "not sorted: " + d[i] + " " + d[i-1] );

       sum2 += ovalue;
    }

    if (sum != sum2) msg( "checksum mismatch: " + sum + " " + sum2 );

    if (argv.length >= 2) {
       for( int i=0; i < N; i++ ) {
          System.out.println( i + " " + d[i] + " " + o[i] );
       }
    }

    System.out.println( "ok." );
  } 
} /* end class ShellSort */