für die Schleife optimieren in C

Question

Ich muss unten für Loop-Code optimieren. Wie kann ich? Irgendein Vorschlag? Ich habe versucht, für Loop zu entrollen, aber es hat nichts verändert. Danke.

G ist eine Matrix von Graphen (gerichtet oder ungerichtet graph) Code ist unten:

void col_convert(int dim, int *G) 
{ 
    int i, j; 
    for (i = 0; i < dim; i++) 
     for (j = 0; j < dim; j++) 
      G[j*dim+i] = G[j*dim+i] || G[i*dim+j]; 
} 

EDIT: Die häufigsten Dimension 8.

Answer 1

Ich beschleunigte mehr als 5,4 mal als der rohe Code. Danke für alles.

Dies ist die Antwort:

void col_convert(int dim, int *G) 
{ 

     int i, j,dimj,dimi,nj,ni; 

     for (i = 0; i <= dim-8; i +=8){ 
      ni = dim * i; 
      for (j = 0; j < dim; j++) 
      { 
       nj = j * dim ; 
       dimj = nj + i; 
       dimi = ni + j; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 

       dimj += 1; 
       dimi += dim; 
       G[dimj] |= G[dimi]; 
      } 
     } 

     // Use the normal loop for any remaining elements 
     for (; i < dim; i++){ 
     ni = i * dim; 

      for (j = 0; j < dim; j++){ 
      nj = j * dim; 
      dimj = nj + i; 
      dimi = ni + j; 
      G[dimj] |= G[dimi]; 
      } 
     } 

} 

Answer 2

Sie können die Anzahl der Iterationen halbieren durch zu bemerken, daß der Betrieb symmetrisch ist:

void naive_col_convert(int dim, int *G) { 
    for (int i = 0; i < dim; i++) { 
     G[i * dim + i] = G[i * dim + i] != 0; 
     for (int j = i + 1; j < dim; j++) { 
      G[i * dim + j] = G[j * dim + i] = G[j * dim + i] || G[i * dim + j]; 
     } 
    } 
} 

EDIT : Wenn der häufigste Wert 8 ist, versuchen Sie den folgenden Code mit -O3. Der Compiler sollte aus dem gleichen Quellcode effizienten Code für den Sonderfall generieren können.

void naive_col_convert(int dim, int *G) { 
    if (dim == 8) { 
    #define dim 8 
     for (int i = 0; i < dim; i++) { 
      G[i * dim + i] = G[i * dim + i] != 0; 
      for (int j = i + 1; j < dim; j++) { 
       G[i * dim + j] = G[j * dim + i] = G[j * dim + i] || G[i * dim + j]; 
      } 
     } 
    #undef dim 
    } else { 
     for (int i = 0; i < dim; i++) { 
      G[i * dim + i] = G[i * dim + i] != 0; 
      for (int j = i + 1; j < dim; j++) { 
       G[i * dim + j] = G[j * dim + i] = G[j * dim + i] || G[i * dim + j]; 
      } 
     } 
    } 
} 

Wenn die Leistungsverbesserung nicht signifikant ist, können Sie die Schleifen von Hand auf eine Folge von 36 Aussagen entrollen. Das Umordnen dieser Anweisungen kann zu zusätzlichen Verbesserungen für ausgewählte Architekturen und zu langsameren Operationen für andere führen.