퍼포먼스 최적화의 기본 (3편)

[본 글은 Naver 맥부기 Cafe의 리겔님의 글을 정리한 것입니다.]

 

void FlipImage(img_type * pDst, img_type * pSrc)
{
  unsigned int x, y;
  unsigned int srcwidth, srcheight;

  unsigned short * pDstBuf, * pSrcBuf;

 

  srcwidth = pSrc->width;
  srcheight = pSrc->height;

  pDstBuf = pDst->imgBuf;

  pSrcBuf = pSrc->imgBuf;

  pDst->width = srcheight;
  pDst->height = srcwidth;
 
  for (y = 0; y < srcheight; ++y)
  {
    for (x = 0; x < srcwidth; ++x)
    {
       pDstBuf[x*srcheight + y] = pSrcBuf[x + y*srcwidth];
    }
  }
}

=====================================================================

2편에서는 메모리 참조를 줄이는 것 만으로 상당한 속도개선을 달성할 수 있음을 알아보았다.

이번에는 1석 2조를 보여주겠다. Random access를 Sequential access로 바꿈과 동시에 불필요한 곱셈 연산을 제거하는 것이다.

루프 내부를 보면 pScrBuf에서 읽어오는 과정과 pDstBuf에 써 주는 과정이 모두 random access 이다. 그리고 random은 sequential에 비하여 모든 면에서 불리하다.
sequential에서 1~2 사이클에 처리되는 기능이 random에서는 4~5 사이클이 소요되는 경우가 많다.

요약하자면 random access는 배열에서 몇몇 데이터를 조준하여 가져오거나 써 주는 경우를 제외하고는 사용하지 않는 편이 좋다.

예제 함수는 다량의 데이터를 순차적으로 처리하는 것이 핵심이므로 random access가 전혀 어울리지 않는 경우이다. 일단 pSrcBuf에서 읽어오는 부분은 간단하게 변경 가능하다. 처음부터 끝까지 순차적으로 16비트씩 읽어오기 때문이다.

pDstBuf[ x*srcheight + y ] = *pSrcBuf++;

좌표 계산식이 모조리 사라져서 코드가 짧아지고 가독성 또한 향상되었다.
여기서 얻은 것은
1. 곱셉 연산
2. 더셈 연산
3. random access

이렇게 세 가지를 덜어낸 것이다.

특히 곱센 연산을 제거한 것이 비중이 높다. 덧셈이나 뺄셈 등 ALU 명령어는 ARM에서 1사이클에 처리되는 반면 곱셉은 2사이클 소요하고, delay가 있기에 최대 3사이클을 소요한다. 여기서 delay는 곱셈의 결과물을 바로 다음 줄에서 사용 하는 경우 1사이클 wait이 들어가는 것을 뜻하고, 이를 전문용어로는 pipelock, ghrdms pipeline hazard라 표현한다.

요즘 컴파일러가 똑똑해졌다는 것은 대부분 이러한 pipeline interlock이 발생하지 않도록 명령어들을 적당히 섞어주는 것인데, 도저히 피할 수 없는 경우가 상당히 많다.

요약하자면 곱셈은 가급적 사용하지 않는게 좋다는 것이다.

pSrcBuf는 간단히 sequential로 전환이 가능하였지만 pDstBuf는 다소의 생각을 필요로 한다.

메모리에 순차적으로 써 주는 것이 아니라 매트릭스에서 수직으로 순차적으로 끝가지 써 준 후 행 변경을 해야하기 때문이다.

void FlipImage(img_type * pDst, img_type * pSrc)
{
  unsigned int x, y;
  unsigned int srcwidth, srcheight;

  unsigned short * pDstBuf, * pSrcBuf;

  unsigned int gap; 

  srcwidth = pSrc->width;
  srcheight = pSrc->height;

  pDstBuf = pDst->imgBuf;

  pSrcBuf = pSrc->imgBuf;

  pDst->width = srcheight;
  pDst->height = srcwidth;
 

  gap = srcwidth * srcheight;

  gap -= 1;

  for (y = 0; y < srcheight; ++y)
  {
    for (x = 0; x < srcwidth; ++x)
    {
       *pDstBuf = *pSrcBuf++;

       pDstBuf += srcheight;
    }

  pDstBuf -= gap;
  }
}

=====================================================================

자, 이제 최적화의 마지막 단계를 소개하고자 한다.

당신이 가장 선호하는 루프는 어떤 것인가?

대부분 while이나 for 루프를 많이 사용한다. 특히 for루프는 while에 비하여 간편하기에 선호도가 높다. 그러나 모든 CPU에서 모든 루프를 통틀어서 가장 효율적인 것은 0까지 카트 다운 하는...

do... while 루프이다.

고급언어에서 goto의 사용은 범죄행위에 속한다. 그러나 모든 루프는 기계어로 번역 될 때 일종의
if... goto 형태로 구현이 된다.,

그리고 if는 공짜가 아니다.

if는 어셈블리 cmp (compare)에 해당하는데, 이는 1~2사이클을 소요한다.,

예를 들어 예제 함수에서 x 루프 하단은 대략 다음과 같이 컴파일 된다.

add x,x, #1
cmp x, srcwidth
blo start_of_x_loop

C언어로 보면 대략 다음과 같다.

x = x + 1;
temp = x - srcwidth;
if( temp < 0 ) goto start_of_x_loop;

반면 제로 터미네이트, 카운트 다운 do ... while 루프는 다음과 유사하게 컴파일 된다.

subs x, x, #1
bne start_of_x_loop

이처럼 cmp 명령어를 뺄 수 있다. ARM을 비롯한 모든 CPU는 연산 결과물이 0이 되는 것을 자동으로 감지하기 때문이다.
(정확히 말하자면 ARM은 명령어 뒤에 subs처럼 s를 붙여줘야만 결과물을 감지합니다. )

void FlipImage(img_type * pDst, img_type * pSrc)
{
  unsigned int x, y;
  unsigned int srcwidth, srcheight;

  unsigned short * pDstBuf, * pSrcBuf;

  unsigned int gap; 

  srcwidth = pSrc->width;
  srcheight = pSrc->height;

  pDstBuf = pDst->imgBuf;

  pSrcBuf = pSrc->imgBuf;

  pDst->width = srcheight;
  pDst->height = srcwidth;
 

  gap = srcwidth * srcheight;

  gap -= 1;

  y = srcheight;

  do
  {
    x = srcwidth;

    do
    {
       *pDstBuf = *pSrcBuf++;

       pDstBuf += srcheight;
    } while (--x);

  pDstBuf -= gap;
  } while (--y);
}

=====================================================================

이상이 고급언어에서 가능한 최적화의 한계이다.
(여기서 더 최적화 하려면 어셈블리로 작성해야만 한다.)