プログラムを改良して高速化したい

以下のプログラムを機能を変えずに高速化したいのです。
制約として画像のメモリは動的に確保し、N_REPEATとDIM1,2,3の数は変えられません。
自分の考えとして、
ポインタを使用する
ループを見直す
grayscale関数の四捨五入を整数で行う
ということをすれば消費時間は短くなるとは思うのですがどのようにプログラムに落とし込めばいいのかわかりません。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
typedef unsigned char UCHAR;
#define DIM1  960
#define DIM2  1280
#define DIM3  3
#define N_REPEAT 1000 
void read_ppm_cip_mem(UCHAR ***, char *, int *, int *); /* ファイル入出力 */
void write_ppm_cip_mem(UCHAR ***,char *,int ,int);
UCHAR *malloc1Duchar(int); /* メモリー確保、開放 */
UCHAR **malloc2Duchar(int ,int);
UCHAR ***malloc3Duchar(int ,int ,int);
void free1Duchar(UCHAR *);
void free2Duchar(UCHAR **);
void free3Duchar(UCHAR ***);
void error1(char *);
void grayscale(UCHAR **, UCHAR ***, int, int);
void edge_extraction(UCHAR **, UCHAR **, int, int);
void composition(UCHAR ***, UCHAR ***, UCHAR **, int, int);
int main(int argc, char *argv[])
{
  int i,g,r;
  int max_gyou,max_retu;
  char in_fname[200];
  char out_fname[200];
  UCHAR ***org;
  UCHAR **gray;
  UCHAR **edge;
  UCHAR ***res;
  
  if(argc < 2)
  {
    printf("usage: a.out filename\n");
    exit(1);
  }
  strcpy(in_fname,argv[argc-1]); /* 入力画像のファイル名 */
  org=(UCHAR ***)malloc3Duchar(DIM1,DIM2,DIM3); /* 原画像(入力画像) */
  gray=(UCHAR **)malloc2Duchar(DIM1,DIM2); /* グレースケール画像 */
  edge=(UCHAR **)malloc2Duchar(DIM1,DIM2); /* エッジ画像 */
  res=(UCHAR ***)malloc3Duchar(DIM1,DIM2,DIM3); /* 結果画像 */
  read_ppm_cip_mem(org, in_fname, &max_gyou, &max_retu); /* 画像をファイルより読み込み */
  if((max_gyou != DIM1) || (max_retu != DIM2))
    error1("Irregal image size");

  for(g=0;g<DIM1;g++)
   for(r=0;r<DIM2;r++)
      edge[g][r]=0;
    //時間測定のため1000回行う．
  for(i=0;i<N_REPEAT;i++){
    grayscale(gray,org,DIM1,DIM2); /* グレースケール画像作成 */
        edge_extraction(edge,gray,DIM1,DIM2); /* エッジ画像作成 */
        composition(res,org,edge,DIM1,DIM2); /* 赤>200の領域とエッジ画像の合成画像作成 */
  } 
    /* 出力ファイル名設定 */
  in_fname[strlen(in_fname)-4]='\0'; /* .ppmを除く */
  sprintf(out_fname,"%s_res.ppm",in_fname); /* 結果画像 */
  write_ppm_cip_mem(res,out_fname,DIM2,DIM1); /* 画像をファイルへ出力 */
  free2Duchar(gray);
  free2Duchar(edge);
  free3Duchar(org);
  free3Duchar(res);
  
  return 0;
}
/* カラー画像からグレスケール画像作成(平均して四捨五入) */
void grayscale(UCHAR **ans, UCHAR ***data, int n_gyou, int n_retu)
{
  int g,r;
  
  for(g=0;g<n_gyou;g++)
    for(r=0;r<n_retu;r++)
    {
      ans[g][r]=(UCHAR)((data[g][r][0]+data[g][r][1]+data[g][r][2])/3.0+0.5);
    }
  
}
void edge_extraction(UCHAR **ans, UCHAR **data, int n_gyou, int n_retu)
{
  int g,r;
  int tmp;
  
  for(g=1;g<n_gyou-1;g++)
    for(r=1;r<n_retu-1;r++)
    {
      tmp=40*data[g][r]-10*data[g-1][r]-10*data[g+1][r]-10*data[g][r-1]-10*data[g][r+1];
      if(tmp < 0)
 tmp =-tmp;
      if(tmp > 255)
 ans[g][r]=255;
      else
 ans[g][r]=tmp;
    }
}

void composition(UCHAR ***ans, UCHAR ***data, UCHAR **gdata, int n_gyou, int n_retu)
{
  int g,r,k;
  for(g=0;g<n_gyou;g++)
    for(r=0;r<n_retu;r++)
    {
      if(data[g][r][0] > 200)
 for(k=0;k<3;k++)
   ans[g][r][k]=data[g][r][(k+1)%3];
      else
 for(k=0;k<3;k++)
   ans[g][r][k]=gdata[g][r];
    }
}

void write_ppm_cip_mem(UCHAR ***data_buf,char *fname,int width,int height)
{
  FILE *fp;
    
  if((fp = fopen(fname, "wb")) == NULL) {
    fprintf(stderr, "file(%s) can't open\n", fname) ;
    exit(1) ;
  }
  fprintf(fp, "P6\n") ;   /* カラー画像かつバイナリーデータの記号 */
  fprintf(fp, "%d %d\n", width, height) ; /* 画像の幅(列数)と高さ(行数) */
  fprintf(fp, "255\n") ;  /* 最大値 */
  fwrite(&data_buf[0][0][0], sizeof(UCHAR), width*height*3, fp);
  fclose(fp) ;
}

UCHAR *malloc1Duchar(int dim1)
{
    UCHAR *c1;
    if((c1 = (UCHAR *)malloc(dim1*sizeof(UCHAR))) == NULL)
 error1("END UCHAR1D");
    return c1;
}
UCHAR **malloc2Duchar(int dim1,int dim2)
{
    int i;
    UCHAR **c1,*c2;
    if((c1 = (UCHAR **)malloc(dim1*sizeof(UCHAR *))) == NULL)
 error1("END UCHAR_2D");
    if((c2 = (UCHAR *)malloc(dim1*dim2*sizeof(UCHAR))) == NULL)
 error1("END UCHAR_2D");
    for(i=0;i<dim1;i++)
    {
 c1[i]=c2+dim2*i;
    }
    return c1;
}
UCHAR ***malloc3Duchar(int dim1,int dim2,int dim3)
{
  int i,j;
  UCHAR ***c1,**c2,*c3;
  if((c1 = (UCHAR ***)malloc(dim1*sizeof(UCHAR **))) == NULL)
    error1("can't allocate in malloc3Duchar");
  if((c2 = (UCHAR **)malloc(dim1*dim2*sizeof(UCHAR *))) == NULL)
    error1("can't allocate in malloc3Duchar");
  for(i=0;i<dim1;i++)
    c1[i]=c2+dim2*i;
  if((c3 = (UCHAR *)malloc(dim1*dim2*dim3*sizeof(UCHAR))) == NULL)
    error1("can't allocate in malloc3Duchar");
  for(i=0;i<dim1;i++)
    for(j=0;j<dim2;j++)
      c1[i][j]=c3+(dim2*i+j)*dim3;
  return c1;
}

void free1Duchar(UCHAR *point)
{
  free(point);
}
void free2Duchar(UCHAR **point)
{
  free(point[0]);
  free(point);
}
void free3Duchar(UCHAR ***point)
{
  free(point[0][0]);
  free(point[0]);
  free(point);
}
void read_ppm_cip_mem(UCHAR ***data_buf, char fname[], int *height, int *width)
{
  FILE *fp ;
  char str_buf[128] ;
  char magic_num[8] ;
  int max_val ;
  int c, i, m, n ;
  int inc = '0' ;
  int flg = 0 ;
  int com_flg = 0 ;
  int break_flg = 0 ;
  UCHAR *val;
  int p;
    
  if((fp = fopen(fname, "rb")) == NULL) {
    fprintf(stderr, "file(%s) can't open.\n", fname) ;
    exit(-1) ;
  }
  
  i = 0 ;
  while(1) {
    c = getc(fp) ;
    if(com_flg) {
      if(c == '\n')
 com_flg-- ;
    }
    else {
      if(c == '#') {
 com_flg++ ;
 continue ;
      }
      if(!flg) {
 if(((c == ' ') || (c == '\t') || (c == '\n')) && (i > 0))
   flg++ ;
 else if(((c == ' ') || (c == '\t') || (c == '\n')) && (i == 0))
   continue;
 else
   str_buf[i++] = (char)c ;
      }
      if(flg) {
 str_buf[i] = '\0' ;
 i = 0 ;
   
 switch(inc) {
 case '0':
   strcpy(magic_num, str_buf) ;
   if(strcmp(magic_num, "P6") != 0) {
     fprintf(stderr, "read_ppm: ERROR: magic number(%s) not match.\n", magic_num) ;
     exit(-1) ;
   }
   inc++ ;
   break ;
 case '1':
   *width = atoi(str_buf) ;
   inc++ ;
   break ;
 case '2':
   *height = atoi(str_buf) ;
   inc++ ;
   break ;
 case '3':
   max_val = atoi(str_buf) ;
   break_flg++ ;
   break ;
 }
 flg-- ;
      }
    }
    if(break_flg)
      break ;
  }
  val = (UCHAR *)malloc1Duchar(*width*3);
  for( m = 0; m < *height; m++) {
    fread(val, sizeof(UCHAR), *width*3, fp) ;
    n = 0 ;
    p=0;
    while(n < *width) {
      data_buf[m][n][0] = val[p++];
      data_buf[m][n][1] = val[p++];
      data_buf[m][n][2] = val[p++];
      n++ ;
    }
  }
  free1Duchar(val);
  fclose(fp) ;
}
/* エラーメッセージを表示し、終了する */
void error1(char *errtxt)
{
    fprintf(stderr,"Error: %s. Aborting.\n",errtxt);
    exit(1);
}

コンパイルはWallとO2のオプションを付けppm拡張子の画像を用いて時間を計測します。

行動規範の内容に同意します

回答4件

現時点でできるアドバイスが、2つほどあります。

その1：本当にそのコードは自分で書く必要がありますか？

画像処理のような、よく行われる処理については、すでに第三者がライブラリを書いていることがあります。たとえば行列演算のルーチンでは、CPUメーカーが極限までチューニングしたバージョンを作っていて、手で書くより手間も少なければ速度も圧倒的に速い、なんてことがあります。

徹底的に速度を優先するのであれば、自分で書かずにそういう「チューニング済みライブラリ」を使うというのも有効な選択肢です。

その2：推測より計測

どうしてもこのプログラムを改善しないといけないとなれば、まずやるべきことはプロファイリングです。実際に時間がかかっているところを割り出して初めて、どこを改善すべきか見えてきます（たとえば、「実はメモリ不足でmallocがスワップしていた」となれば、それはもはやコードと別次元の問題ですし）。

投稿2017/06/13 07:59