3. Hi, how can I optimize the following code?

Hi, how can I optimize the following code?

  • Q

    I'm trying to use multiple thread to optimize my following code, but met some problems, anyone can help me?

    r[3][500] are initialized.

    int computePot() {
   int i, j;

   for( i=0; i<500; i++ ) {
      for( j=0; j<i-1; j++ ) {
        distx = pow( (r[0][j] - r[0][i]), 2 );
        disty = pow( (r[1][j] - r[1][i]), 2 );
        distz = pow( (r[2][j] - r[2][i]), 2 );
        dist = sqrt( distx + disty + distz );
        pot += 1.0 / dist;
      }
   }

    I doubt that If this code really can be optimized?

    0
  • B

    You can change this

    distx = pow( (r[0][j] - r[0][i]), 2 );

    into

    distx = (r[0][j] - r[0][i]) * (r[0][j] - r[0][i]);

    pow is slower than a normal multiplication.

    0
  • C

    you could replace your postfix increment operators in the "for loops" by prefix increment operators (i++ ==> ++i)

    0
  • ?
     

    int computePot() {
   int i, j;

   for( i=0; i<500; i++ ) {
      int k = i-1;
      for( j=0; j<k; j++ ) {
       [...]
      }
   }

    [/quote]

    Its not much, but change the second for-loop condition like so. Reason: The calculation (i-1) probably will be executed on every iteration of the loop. Than again this are roughly 125k iterations, so every single bit counts 😉

    0
  • D

    Use a function for computing the inverse square root, for example:

    float InvSqrt( float f )
{
	float y, r;
	int i;

	y = f * .5f;
	i = *reinterpret_cast< int *>( &f );
	i = 0x5f3759df - ( i >> 1 );
	r = *reinterpret_cast< float *>( &i );

	r = r * ( 1.5f - r * r * y );

	return r;
}

    Now the division can be removed from your code:

    pot += InvSqrt( distx + disty + distz );
    0
  • Q
     

    int computePot() {
   int k;
   for(k=0;k<p;k++){
      _beginthread(compute_quarter_pot,0,(void *)(k)); 
   } 
   while(true)
   {
	   if(complete == p)
		   break;
	   continue;
   }
   for(k=0;k<p;k++){ 
      pot+=pots[k];
   } 
   complete = 0;

   return 0;
}

void compute_quarter_pot(void* quarter){
	int m = (int)quarter;
   for(int i = m;i<NPARTS/2;i+=p){ 
       pots[m]+=compute_single_pot(i)+compute_single_pot(NPARTS-1-i); 
   } 
   complete++; 
   _endthread();
}

double compute_single_pot(int i){ 
   double pot=0,x, y, z; 
   int j;
   int k = i -1;
   for( j=0; j<k; j++ ) { 
      x = POW2(r[0][j] - r[0][i]); 
      y = POW2(r[1][j] - r[1][i]); 
      z = POW2(r[2][j] - r[2][i]); 
      pot += 1.0 / sqrt( x + y + z ); 
   } 
   return(pot); 
}

    this is my way to accelerate the code, it works when config as debug, but will be block(without any response and mistake) when config as release. I'm confused. anyway, thanks you guys who reply me. and sorry for my poor english, I'm come from China.

    0

  • Ah. You have to use some kind of synchronization here.
    Option 1: use events/condition variables
    Option 2: use a barrier (if available)
    Option 3: use interlocked instructions (but only if you have to)

    A condition variable should be exactly what you need. If you're working with Win32 you can easily use an EVENT in this situation.

    A barrier is not 100% what you need, but it comes close, and it should be very easy to use. It blocks all threads that "hit" the barrier (i.e. call the "hit" function or however it's called) until exactly N threads have hit the barrier (where N is configurable e.g. upon creation). When the N-th thread hits the barrier, all N threads will continue (i.e. the N-th thread will just "run through" the barrier, releasing all others).

    0
  • _

    Checker&Murckser schrieb:

    you could replace your postfix increment operators in the "for loops" by prefix increment operators (i++ ==> ++i)

    Sry, but that's a common misbelief. There's no difference in the perfomance of pre- or postfix operators with POD types.
    It only gives you a benefit when using iterators.
    But it's good practice to always use prefix operators as there's no sideeffect in this case.

    0
Anmelden zum Antworten