для оптимизации цикла в C

Question

Ниже я хочу оптимизировать код цикла. Как я могу сделать? Любое предложение? Я попытался сделать цикл для цикла, но ничего не изменил. Спасибо.

G представляет собой матрицу графа (направленной или неориентированного графа) код приведен ниже:

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]; 
} 

РЕДАКТИРОВАТЬ: Наиболее распространенный размер составляет 8.

Answer 1

Я ускорил более 5,4 раза, чем исходный код. Спасибо вам за все.

Это ответ:

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

Вы можете вдвое сократить число итераций заметив, что операция является симметричным:

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]; 
     } 
    } 
} 

РЕДАКТИРОВАТЬ :, если наиболее распространенное значение равно 8, попробуйте код ниже с -O3. Компилятор должен иметь возможность генерировать эффективный код для специального случая из того же исходного кода.

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]; 
      } 
     } 
    } 
} 

Если улучшение производительности не имеет существенного значения, вы можете раскатать петли вручную на последовательность из 36 утверждений. Переупорядочение этих операторов может привести к дополнительным улучшениям для выбранных архитектур и более медленной работе с другими.