Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!ceco!garry
From: garry@ceco.ceco.com (Garry Garrett)
Newsgroups: comp.lang.c
Subject: Re: Execution time bottleneck: How to speed up execution?
Keywords: Execution time, would like to speed up. Alternatives?
Message-ID: <413@ceco.ceco.com>
Date: 23 Feb 91 16:44:13 GMT
References: <21658@yunexus.YorkU.CA> <1991Feb14.170400.8089@clear.com>
Organization: Commonwealth Edison Co., Chicago, IL
Lines: 62

In article <1991Feb14.170400.8089@clear.com>, rmartin@clear.com (Bob Martin) writes:
> >Execution time query:
> >
> >   for (j=1; j <= n; j++) {
> >      sum = 0.0;
> >      for (i=1; i<= n; i++) {
> >         sum += exp( con * (x[i]-x[j]) * (x[i]-x[j]) );
> >      }
> >      a[j] = k*sum;
> >   }
> >
> >This part of the algorithmn is a bottleneck. I want to make this as
> >quick as possible. What are my options? I have heard that assembler
> >would be faster. How much faster would assembler be? Would it be worth
> >the effort? Are there other alternatives that you can see?  Any
> >improvement would be welcome.
> 
> 	double x[MAXSIZE], a[MAXSIZE];
> 	register double *ip, *jp, *ap;
> 	double diff;
> 	register int j, i;
> 	int n = MAXSIZE; /* or whatever size you decide on */
> 
> 	for(j=n, jp=x, ap=a; j; j--, jp++, ap++) {
> 		sum = 0.0;
> 		for(i=n, ip=x; i; i--, ip++) {
> 			diff = *ip - *jp;
> 			sum += exp( con * diff * diff );

/* consider replacing the above 2 lines with:
 *			sum += exp( con * (diff = *ip - *jp) * diff);
 * the savings is in the fact that after diff = ... is calcualted,
 * the value (written out to the memory location that contains diff) is
 * still in a register, and need not be read back into the register.
 */

> 		}
> 		*ap = sum;
> 	}
> 
	[... or]
> 
> 	for (j=0; j<n; j++) {
> 		a[j] = 1;	/* put in the diagonal */
> 	}
> 
> 	for (j=0; j<(n-1); j++) { /* don't need to do the last row */
> 		for (i=j+1; i<n; i++) {  /* this excludes the i==j axis */
> 			diff = x[i] - x[j];
> 			s = exp(con * diff * diff);
/*	same comment applies here */
> 			a[j] += s;
> 			a[i] += s;
> 		}
> 	}
> 

	Hope it helps

Garry Garrett

(sorry, I have to add a bunch of <CR> 's or my mailer won't accept this)