C 코드 최적화

yundream7의 이미지

원문 : http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/C/Documents/COptimization
이 문서는 계속 추가/수정 됩니다.

1 소개
얼마전에 모바일기기에서 일정수준의 품질을 유지하면서 실행되는 JPEG라이브러리를 만드는 프로젝트를 진행한적이 있었다. 이 프로젝트를 진행하면서, 여러가지 방법으로 프로그램을 더 빨리 만들 수 있다는 사실을 경험적으로 알게 되었다. 이 문서는 C로된 코드를 속도와 메모리 양측모두에서 최적화하기 위한 경험적인 정보들을 포함하고 있다.

물론 여러분은 C 코드를 최적화 하는 방법에 대한 참고문서를 어렵지 않게 획득할 수 있을 것이다. 그러나 대부분의 문서가 팁수준에서 문제에 접근할 뿐으로, 컴파일러나 기계수준에서 어떻게 프로그래밍을 해야 하는지에 대한 정보는 담고 있지 않다.

보통 프로그램의 속도를 높이게 되면 코드의 크기가 늘어나게 된다. 코드의 크기가 늘어나면 프로그램이 복잡해지고, 읽고 이해하기 어려워진다. 메모리 자원이 넉넉한 개인PC혹은 서버 컴퓨터라면 문제가 되지 않겠지만 PDA와 같은 제한된 메모리 자원을 가진 기기일 경우 심각한 문제가 될 수 있다. 1%의 속도향상을 위해서 코드의 크기가 10%만큼 늘어난다면 분명 문제가 될 것이다. 이런 이유로 속도와 코드크기 모두에 대한 최적화를 수행하기로 결정을 했다.

2 선언
내가 진행하는 프로젝트가 ARM 플랫폼에서 진행된 관계로, ARM 최적화와 관련된 팁들이 필요했었다. 나는 인터넷을 통해서 ARM 최적화와 관련된 많은 문서를 검색하고 이중 유용한 것들 중심으로 수집해서 테스트를 했었다. 그러나 대부분의 문서들이 나에게는 도움이 되지 않았음을 고백한다. 이러한 실수를 줄이기 위해서 유용하고 효과적인 몇개의 팁만을 모으기로 결정했다.

3 어디에 필요한가
토론의 주제를 명확히 하고 넘어가자. 컴퓨터 프로그램을 최적화하기 위한 가장 중요한 것은 프로그램을 이루는 각각의 모듈중 어느 부분이 느리게 작동하거나, 큰 메모리를 소비하는지를 찾아내는 것이다. 이들 각각의 부분을 최적화하면 프로그램이 전체적으로 빨라질 것이기 때문이다. 이러한 모듈단위의 최적화는 최적화를 위한 부분을 비교적 쉽게 찾고, 쉽게 해결할 수 있다는 장점을 가진다.

The optimizations should be done on those parts of the program that are run the most, especially those methods which are called repeatedly by various inner loops that the program can have.

일반적으로 경험이 풍부한 프로그래머들은 아주 쉽게 프로그램이 요구하는 최적화될 필요가 있는 핵심을 쉽게 찾아낼 수 있을 것이다. 가장 좋은 최적화 방법은 경험많은 프로그래머를 고용하는 것이다. 그러나 경험많은 프로그래머는 매우 비싸며, 경험이 많다고 해도 더 좋은 결과를 위해서는 최적화를 위한 좋은 툴을 사용할 필요가 있다. Visual C++ 과 같은 통합 개발환경은 함수단위로 프로그램의 소비시간을 측정할 수 있는 profiler를 제공한다. 리눅스의 경우에는 gprof와 같은 profiler를 사용할 수 있다. 혹은 Intel Vtune와 같은 프로그램을 사용할 수 있는데, 이들 프로그램을 사용하면 프로그램의 어느부분이 가장 많은 시간을 소비하는지를 확인할 수 있다. 개인적인 경험으로 루프 혹은 third party 라이브러리 메서드를 호출하는 영역이 프로그램을 느리게 하는 경우가 많았다.

4 정수
우리가 사용할 값이 음수가 아니라면 int 형대신에 unsigned int형을 사용해야 한다. 어떤 프로세스들은 unsigned integer의 연산이 signed 연산보다 매우 빠르다. 또한 나누기/나눗셈 작업의 경우에도 음수가 필요 없다면 unsigned 를 명시해주는게 좋다.

루프에 사용될 변수라고 한다면, 다음과 같이 깔끔하고 효율적으로 선언할 수 있을 것이다.

register unsigned int variable_name;

기억해야할 또다른 점은 floating point 연산은 매우 느리다라는 점이다. floating point 데이터 타입은 자바와 함께 하는 컴퓨터과학문 서를 참고하기 바란다. 척 봐도 floating point 숫자는 다루기가 꽤나 복잡하다는 것을 알 수 있을 것이다. 만약 여러분이 소숫점 2자리까지의 정확도를 유지하는 회계프로그램을 만든다면, 모든 값에 x100을해서 int 형으로 바꾼다음 연산을 하도록 한다. 가능하면 외부의 수학라이브러리를 사용하지 않도록 한다. FPUs와 같은 라이브러리는 매우 느리다.

5 나눗셈 그리고 나머지
표준적인 프로세서에서의 분모와 분자의 32bit 나눗셈은 20~140의 실행 사이클을 가지고 있다. 나눗셈을 이용하면 다음과 같은 시간이 소비된다.

Time (numerator / denominator) = C0 + C1* log2 (numerator / denominator)
= C0 + C1 * (log2 (numerator) - log2 (denominator)).

널리 쓰이는 버젼은 약 20+4.3N의 사이클을 보여준다. ARM 뿐만 아니라 프로세서를 막론하고 이런 연산은 피하는게 바람직하다. 나눗셈연산은 가능하다면 곱셈으로 대체해서 사용하기 바란다.

예를들어 (a/b) > c 는 b * c가 integer 범위안이라는 것을 안다면 a > (c * b)로 다시 쓰일 수 있다.

6 Combining division and remainder
나눗셈 (x/y) 그리고 나머지(x%y)둘다 종종 필요한 케이스이다
그러한 케이스에 비추어보아 나눗셈펑션을 컴파일러에 결합하는것이좋다 왜냐하면 나눗셈펑션은 항상 나눈값과 나머지를 리턴하기 필요하다 만약둘다 필요하다면 우리는 이와같은 예제를 같이 쓸수있어야한다

int func_div_and_mod (int a, int b) {
        return (a / b) + (a % b);
    }

7 2의 배수로 나누기
나누기를 할 때 2의 배수를 분자로 함으로써, 코드를 더 효율적으로 만들 수 있다. 이경우에 컴파일러는 나누기 연산대신에 shift 연산을 할 수 있기 때문이다. shift 연산은 가장빠른 연산중의 하나다. 그러므로 가능하면 2의 배수로 나눌 수 있도록 스케일을 조절할 필요가 있다. (예를 들어 66으로 나누어야 한다면 64로 나눌 수 있도록 스케일을 조절하라).

typedef unsigned int uint;
 
 uint div32u (uint a) {
   return a / 32;
 }
 int div32s (int a){
   return a / 32;
 }

이경우에도 signed 값보다는 unsigned 로 나누어질 수 있도록 함수를 조절할 필요가 있다. signed의 경우에는 더많은 시간이 소비된다. 왜냐하면 오른쪽으로 쉬프트 시킬경우 가장왼쪽의 비트를 0으로 만들어주는 연산이 한번더 들어가기 때문이다.

#include <stdio.h>
 
int main()
{
  unsigned int a = 1024;
  unsigned b, c;
  b = a/32;    // --- 1
  c = a >> 5;  // --- 2
}

1과 2는 동일한 결과를 보여주며, 컴파일러내에서도 동일하게 shift 처리된다. 다음은 intel 프로세서에서 gcc로 컴파일된 어셈블리어중 1과 2에 해당되는 부분의 코드다.

movl    $1024, -12(%ebp)
movl    -12(%ebp), %eax
shrl    $5, %eax           # b = a / 32
movl    %eax, -8(%ebp)
movl    -12(%ebp), %eax
shrl    $5, %eax           # c = a >> 5

8 배열을 이용한 index 생성
특정값에 대응되는 문자를 변수에 입력하는 코드를 만든다면 다음과 같이 switch 문을 사용할 것이다.

switch ( queue ) {
  case 0 :   letter = 'W';
     break;
  case 1 :   letter = 'S';
     break;
  case 2 :   letter = 'U';
     break;
}

혹은 if else 문을 사용할 수도 있을 것이다.

 if ( queue == 0 )
   letter = 'W';
 else if ( queue == 1 )
   letter = 'S';
 else
   letter = 'U';

다음과 같이 문자의 배열을 인덱스화 하면 더 빠른 접근이 가능하다. - 사용하기도 쉽다 -

static char *classes="WSU";
letter = classes[queue];

9 나머지 연산자의 대체
우리는 나눗셈의 나머지를 알기 위해서 나머지 연산자 %를 사용한다. 이경우 % 연산대신 판단문을 사용해서 시간을 줄일 수 있다. 아래의 두 코드를 비교해 보기 바란다.

uint modulo_func1 (uint count)
{
   return (++count % 60);
}
 
uint modulo_func2 (uint count)
{
   if (++count >= 60)
  count = 0;
  return (count);
}

if 문은 나머지 연산자보다 빠른코드를 생성한다. 주의 할점은 2번째 함수의 경우 0에서 60사이의 값에 대해서만 제대로 측정이 된다는 점이다.

10 전역 변수
전역 변수는 절대 레지스터에 할당할 수 없다. 포인터를 사용하여 간접적으로 할당하거나 함수호출을 이용해서 전역변수를 변환할 수 있다.

따라서 컴파일러는 전역변수의 값을 레지스터에 올려서 캐쉬할 수 없게 되고 때문에 글로벌 변수를 이용할 때마다 다시 읽어들이는 오버로드가 생기게 된다. 그러므로 가능하면 글로벌 변수를 직접 호출하는 대신에, 로컬변수를 이용해서 필요한 연산을 하고 그 결과를 글로별 변수에 할당하는 방법을 사용해야 한다.

int f(void);
int g(void);
int h(void);
int errs;
 
void test1(void)
{
  errs += f();
  errs += g();
  errs += h();
}
 
void test2(void)
{
  int localerrs = errs;
  localerrs += f();
  localerrs += g();
  localerrs += h();
  errs = localerrs;
}

test1은 매번 전역변수를 로드해야 한다. 반면 test2의 경우 레지스터에 등록된 localerrs에 값을 저장하고 마지막에 한번만 전역변수에 접근함을 알 수 있다.

11 Using Aliases
아래의 코드를 보기 바란다.

  void func1( int *data )    {
      int i;
 
     for(i=0; i<10; i++) 
     {
            anyfunc( *data, i);
     }
  }

*data 가 결코 변하지 않는다고 하더라도, anyfunc 함수를 호출하는 컴파일러는 이걸 알 수가 없다. 그래서 변수가 사용될 때마다 메모리로 부터 다시 읽어들이게 된다. 이 문제는 지역변수를 하나더 둠으로써 해결할 수 있다.

  void func1( int *data )
  {
      int i;
      int localdata;
 
      localdata = *data;
      for(i=0; i<10; i++)
      {
          anyfunc ( localdata, i);
      }
  }

12 데이터 타입
C 컴파일러는 char, short, int, long, float, double 등의 다양한 원시 데이터 타입을 제공한다. 필요한 영역에 필요한 수준의 데이터 타입을 사용하도록 하자.

13 지역변수
가능하면 지역변수로 char 이나 short를 사용하지 않도록 한다. char와 short가 사용될 경우 컴파일러는 값을 저장하기 위해서 8bit 혹은 16bit를 할당한 후, 남는 크기를 줄이는 작업을 하게 된다. 이는 24bit, 16bit 만큼을 shift 시키는 연산을 하게 됨을 의미한다. 그러므로 입력되는 데이터가 8 혹은 16 비트라고 하더라도, 32bit로 연산을 하도록 함수를 만들 필요가 있다.

int wordinc (int a)
{ 
   return a + 1;
}
 
short shortinc (short a)
{ 
    return a + 1;
}
 
char charinc (char a)
{ 
    return a + 1;
}

3번째 코드가 가장 빠른결과를 보여줄 것이라고 생각할지도 모르지만, 1번째 코드가 가장 빠르게 작동한다.

14 포인터
구조체를 그대로 넘길경우 구조체의 모든 값이 스택에 올라가기 때문에 느리게 작동한다. 그래서 구조체의 포인터를 넘기는 경우가 많다. 나는 수 kbyte의 구조체를 넘기는 프로그램을 본적이 있다. 이런 경우 포인터를 쓰도록 하자.

포인터를 통해서 구조체를 넘길때, 구조체의 멤버를 수정할일이 없다면 상수로 선언해서 넘기도록 하자.

void print_data_of_a_structure ( const Thestruct  *data_pointer)
{
   ...printf contents of the structure...
}

이렇게 하면 컴파일러는 인자로 넘어온 포인터가 수정할 수 없는 외부 구조체라는 것을 알게 된다. 이렇게 되면, 값이 사용될 때마다 다시 읽혀질 필요가 없어지게 된다. 또한 이러한 코드는 실수로 구조체 멤버의 변수를 바꾸는 것과 같은 실수를 하지 않도록 해준다.

15 Pointer chains
구조체내의 정보에 접근하려다 보면 포인터의 chain을 사용해야 할 때가 있다. 다음과 같은 경우다.

typedef struct { int x, y, z; } Point3;
typedef struct { Point3 *pos, *direction; } Object;
 
void InitPos1(Object *p)
{
   p->pos->x = 0;
   p->pos->y = 0;
   p->pos->z = 0;
}

이럴 경우 p->pos 를 다른 포인터에 할당해서 접근하도록 하자. 이렇게 하면 p->pos 가 캐쉬되므로 좀더 효율적으로 작동하게 된다.

void InitPos2(Object *p)
{ 
   Point3 *pos = p->pos;
   pos->x = 0; 
   pos->y = 0;
   pos->z = 0;
}

코드가 좀더 보기 좋아진다는 효과도 노릴 수 있다.

16 Binary Breakdown
여러개의 조건을 검사하다 보면, if와 else if를 여러개 사용하는 경우가 생긴다.

if(a==1) { 
} else if(a==2) { 
} else if(a==3) { 
} else if(a==4) { 
} else if(a==5) { 
} else if(a==6) { 
} else if(a==7) { 
} else if(a==8) 
 
{ 
}

이경우 2개로 나누어서 조건 검사를 하도록 한다.

if(a<=4) { 
    if(a==1)     { 
    }  else if(a==2)  { 
    }  else if(a==3)  { 
    }  else if(a==4)   { 
 
    } 
} 
else 
{ 
    if(a==5)  { 
    } else if(a==6)   { 
    } else if(a==7)  { 
    } else if(a==8)  { 
    } 
}

이렇게 하면 최악의 경우 비교횟수가 절반이 됨을 알 수 있다. 필요에 따라서는 아래와 같이 3중루프 코드로 만들 수도 있다. 좀더 빠르게 동작하긴 하겠지만 코드가 보기 어려워진다는 단점이 생긴다.

if(a<=4) 
{ 
    if(a<=2) 
    { 
        if(a==1) 
        { 
            /* a is 1 */ 
        } 
        else 
        { 
            /* a must be 2 */ 
        } 
    } 
    else 
    { 
        if(a==3) 
        { 
            /* a is 3 */ 
        } 
        else 
        { 
            /* a must be 4 */ 
        } 
    } 
} 
else 
{ 
    if(a<=6) 
    { 
        if(a==5) 
        { 
            /* a is 5 */ 
        } 
        else 
        { 
            /* a must be 6 */ 
        } 
    } 
    else 
    { 
        if(a==7) 
        { 
            /* a is 7 */ 
        } 
        else 
        { 
            /* a must be 8 */ 
        } 
    } 
}

17 Switch 대신 lookup table 를 사용하라
switch는 다음과 같은 경우 사용한다.

* 여러개의 함수중 하나를 호출해야할 필요가 있을 때
* 다양한 리턴값을 넘겨받고 이를 처리해야 할때
* 여러개의 코드중 하나를 실행시켜야 할때

예를 들어서 조건값을 입력받아서 거기에 맞는 문자열을 리턴하는 아래와 같은 코드가 있다고 가정해보자.

char * Condition_String1(int condition) {
  switch(condition) {
     case 0: return "EQ";
     case 1: return "NE";
     case 2: return "CS";
     case 3: return "CC";
     case 4: return "MI";
     case 5: return "PL";
     case 6: return "VS";
     case 7: return "VC";
     case 8: return "HI";
     case 9: return "LS";
     case 10: return "GE";
     case 11: return "LT";
     case 12: return "GT";
     case 13: return "LE";
     case 14: return "";
     default: return 0;
  }
}

위의 코드는 아래와 같이 좀 더 효율적인 코드로 만들 수 있다. 덤으로 보기에도 편하다.

char * Condition_String2(int condition) {
   if ((unsigned) condition >= 15) return 0;
      return
      "EQ\0NE\0CS\0CC\0MI\0PL\0VS\0VC\0HI\0LS\0GE\0LT\0GT\0LE\0\0" +
       3 * condition;
}

첫번째 루틴은 240byte가 필요하지만 두번째 루틴은 72바이트만 소모되고 있다.

18 루프
루프는 모든 프로그램에서 사용되는데, 많은 경우 루프에서 과다한 시간을 소비하게 된다. 여러번 실행되는 루프틔 특성상 조그마한 시간의 낭비가 게속 누적되기 때문이다.

18.1 Loop termination
루프를 종료시키기 위한 검사는 항상 count-down-to-zero 방식을 사용하도록 한다. 이것은 좀더 적은 시간을 소비한다. 아래의 두개의 예제는 동일한 일을한다. 다른점이 있다면 첫번째 코드는 루프를 증가시킨다는 점이고 두번째는 루프를 감소시킨다는 점이다.

int fact1_func (int n)
{
    int i, fact = 1;
    for (i = 1; i <= n; i++)
      fact *= i;
    return (fact);
}
 
int fact2_func(int n)
{
    int i, fact = 1;
    for (i = n; i != 0; i--)
       fact *= i;
    return (fact);
}

18.2 더욱 빠른 for 문
다음은 0부터 10까지의 숫자를 연산하기 위해서 for 문을 사용한 일반적인 예다.

for (i = 0; i < 10; i++) {...}

i는 0,1,2,3,4,5,6,7,8,9 로 1씩 증가할 것이다.

가능하면 아래와 같이 숫자를 감소시키는 방향으로 for 문을 사용하라.

for (i = 10; i--;) {...}

첫번재 코드보다 두번째 코드가 더 빠른 수행능력을 보여준다.

두번째 코드는 i가 0이 아니면 i를 감소시키고 다음 코드를 진행하라의 의미인데, 조건 검사의 경우 0인지 아닌지를 비교하는데 더 작은 시간이 소비되기 때문이다. 그러므로 두번째 코드는 아래와 같이 재작성할 수 있다. 두번째 예제코드 보다는 아래의 코드가 더 보기 쉬우므로, 아래의 코드를 사용하는게 가독성 측면에서 유리할 것이다.

for (i = 10; i ; i--) { }

혹은

for (i = 10; i!=0; i--) { }

이들은 모두 동일한 수행능력을 보여준다.

18.3 Loop jamming

18.4 함수 루프
함수는 호출되기 위한 분명한 오버헤드가 존재한다. 실행해야될 함수가 있는 포인터만 변경하는게 아닌, 값들을 stack에 push하는 것과 새로운 변수의 할당과 같은 작업이 수행되기 때문이다. 때문에 루프에서 함수를 호출하는 등의 코드는 작성하지 않는게 좋다. 이런류의 코드는 반대로 함수에서 루프를 수행하도록 변경하는걸 추천한다.

for(i=0 ; i<100 ; i++) 
{ 
    func(t,i); 
} 
- 
- 
- 
void func(int w,d) 
{ 
    lots of stuff. 
}

위의 코드는 아래처럼 바꿀 수 있다. 동일한 일을 좀더 빠르게 수행할 수 있다.

func(t); 
- 
- 
- 
void func(w) 
{ 
    for(i=0 ; i<100 ; i++) 
    { 
        //lots of stuff. 
    } 
}

18.5 Population count - 비트 계수하기
아래의 코드는는 주어진 값에 1bit가 몇개인지를 검사하는 코드다. 0000 1010 이라면 2를 리턴하는 식이다. 이러한 비트필드는 일정한 범위의 값이 참인지 거짓인지를 빠르게 체크하기 위해서 널리 사용될 수 있다.

다음과 같이 1씩 오른쪽으로 쉬프트 하면서, & 연산을 한다.

int countbit1(uint n)
{
  int bits = 0;
  while (n != 0)
  {
    if (n & 1) bits++;
    n >>= 1;
   }
  return bits;
}

이 코드는 다음과 같이 4만큼 쉬프트 하는 식으로 바꿔서, 성능을 높일 수 있다.

int countbit2(uint n)
{
   int bits = 0;
   while (n != 0)
   {
      if (n & 1) bits++;
      if (n & 2) bits++;
      if (n & 4) bits++;
      if (n & 8) bits++;
      n >>= 4;
   }
   return bits;
}

18.6 Earyl loop breaking
루프를 사용하다보면, 일정 조건이 만족되면 뒤의 프로세스가 더이상 필요 없어지는 경우가 있다. 이 경우에는 break를 이용해서 루프를 벗어나도록 한다.

found = FALSE; 
for(i=0;i<10000;i++) 
{ 
    if( list[i] == -99 ) 
    { 
        found = TRUE; 
    } 
} 
 
if( found ) printf("Yes, there is a -99. Hooray!\n");

위의 코드는 -99가 포함되어 있는지 아닌지를 확인하는 프로그램이므로, 일단 발생이 되었다면, 루프를 돌 필요가 없다. 아래와 같이 break 문으로 빠져나가면 쓸데없는 루프의 낭비를 줄일 수 있다.

    found = FALSE; 
    for(i=0; i<10000; i++) 
    { 
        if( list[i] == -99 ) 
        { 
            found = TRUE; 
            break; 
        } 
    } 
    if( found ) printf("Yes, there is a -99. Hooray!\n");

18.7 Loop unrolling

19 함수 디자인
함수를 작고 가볍게 많드는건 좋은 생각이다. 이렇게 함으로써 컴파일러는 register 할당과 같은 영역에서 좀더 쉽게 최적화 할수 있게 된다.

19.1 함수 호출 Overhead
프로세서에서 함수의 호출은 예상과 달리 그리 큰 비용이 들지는 않는다. 함수가 호출되면 register에 함수의 인자를 넘기게 된다. 이 인자들은 char, short, int, float, structure등 이 올 수 있다. 이들 인자는 실제 4개만을 전달할 수 있다는 한계를 가진다. 이 이상으로 인자가 넘어가게 되면, stack를 이용해서 함수의 인자를 넘기게 된다. 당연히 함수를 호출함에 있어서 OverHead가 발생하게 된다. 함수호출시 발생하는 인자의 제한에 대해서는 Linux에서의 Assembly문서를 참고하기 바란다.

예제코드

    int f1(int a, int b, int c, int d) { 
       return a + b + c + d;
    }
 
    int g1(void) {
       return f1(1, 2, 3, 4);
    }
 
 
    int f2(int a, int b, int c, int d, int e, int f) {
      return a + b + c + d + e + f;
    }
 
    ing g2(void) {
     return f2(1, 2, 3, 4, 5, 6);
    }

6개의 인자를 사용하는 f2와 g2함수는 스택에 저장되어 있는 인자를 꺼내기 위해서 2번의 메모리 접근이 더 발생하게 된다.

19.2 가능한 인자의 수를 줄여라
그러므로 가능한 적은 수의 인자를 넘겨받도록 함수를 설계할 필요가 있다.

* 4개 이하의 인자를 가지도록 함수를 설계하라. 4개가 넘어가면 스택을 통해서 인자를 넘기게 된다.
* 만약 함수가 4개 이상의 인자가 사용되면, 스택을 통해서 인자를 넘기게 되고 스택의 크기만큼 메모리 접근이 발생하게 된다.
* 이럴 경우 구조체를 선언하고, 구조체에 대한 포인터를 넘기는 방식을 사용하도록 한다.
* 구조체를 사용하면 인자의 양을 줄일 수 있으며, 코드 활용성도 높아지게 된다.
* 인자에 사용되는 자료형은 long크기 이상으로 하도록 하자.
* Avoid functions with a variable number of parameters. Those functions effectively pass all their arguments on the stack.

19.3 인라인 함수
__inline키 워드를 이용하면 함수를 인라인화 할 수 있게 된다. 이것은 일종의 매크로 처럼 작용을 하며, 함수가 호출되는 대신 함수의 본체가 직접 치환이 되어 버린다. 이렇게 함으로써, 함수를 호출하는데 드는 비용을 줄일 수 있게 된다. 반면 코드가 모두 치환되어 버리므로, 코드의 크기가 커지게 된다.

    __inline int square(int x) {
       return x * x;
    }
 
    #include <MATH.H>
 
    double length(int x, int y){
        return sqrt(square(x) + square(y));
    }

comment:
Thanks for very good and intersting postings! (Sorry, can't type Korean). I have some comments:

9) I'm not sure how many cycles are needed to compute % operator; however, IMHO, this would be better than branchness. Including ARM processors, most modern processros are exploiting branch predctions for aggressive dynamic scheduling. So, branch mis-prediction should be considered to minimize negative effects. If branch mis-predctions occur in the second code, I'm pretty sure that this code is slower than the first one. In other words, removing branchness is better.

I think you can replace % operator with & operator for calculating remainder. & should be quite faster than % and branch.

15) Unless we have a really stupid compier, I don't think that this kind of replacement would bring a better performance. A comper will automatically uses *cached* (more precisely, cached into a register) value in computing others unless a variable is declared as volatile.

17) Really good!! I've never seen that.

18) Absolutely agree with you. I'm always using * for (i = n - 1; i >= 0; --i) * insted of * for (i = 0; i < n ; ++i) *

Forums: 
ohhara의 이미지


http://www.azillionmonkeys.com/qed/optimize.html
이 글을 읽어보시면 아마 느끼시는게 많이 있으실 듯... :)

여러가지 명언이 나옵니다.
Memory in modern computers is most definitely NOT "random access".
라던가...

나름대로 감동적으로 읽은 글. :)

Taeho Oh ( ohhara@postech.edu , ohhara@plus.or.kr ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
Digital Media Professionals Inc. http://www.dmprof.com

Taeho Oh ( ohhara@postech.edu ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
Alticast Corp. http://www.alticast.com

권순선의 이미지

<code>...</code> 태그를 제가 추가하였습니다. :-)

yundreamm의 이미지

// 오하라님
좋은 글 감사합니다. 함 읽어봐야 겠네요.

// 권순선님
고맙습니다. 훨씬 보기 좋군요.
약간의 귀차니즘만 극복하면 될건데 -.-;

blkstorm의 이미지

예전에 회사 다닐 때 ARM프로세서 강사로 오셨던 분의 강의 내용과 아주 흡사하군요. @.@

17번은 인상적이군요. @.@

오랜만에 보니깐 재미있네요... ^^;;

조성현의 이미지

재미있군요. :) 앞으로 프로그래밍 할 때, 많은 도움이 될 것 같습니다.
----
MyWiki http://linu.sarang.net
MyBlog http://ntames8.linuxstudy.pe.kr
----
;p $ rm -rf ~ && mkdir ~ && wget $열정 and $연애

kalstein의 이미지

미세 성능 높이기 관련 아티클이네요...

요즘은 제가 C++ SW design쪽에 관심을 가지면서...약간 덜해지긴했지만...그래도 몇가지 추가 및 수정을 하자면...

일단 객체뒤에 ++ 를 쓰는것 보다는 (postfix) 앞에 쓰는것이 좋습니다 (prefix)
i++ 보다는 ++i 라는거지요. 이유는...i++의 경우는 temp로 리턴될 값을 저장해야 하기 때문인데요...아마 int 형태일 경우에는 컴파일러가 order를 뒤바꿈으로써 최적화를 할테지만...C++에서 객체사용중이라면 좀 비효율적이 됩니다. (MEC++ 책에 나옵니다 ^^;)

그리고...18.5를 좀 더 개선해 보도록 하지요. 그냥 내용 자체는...loop unrolling인가? 하는 기법같은데요...그렇게 하지말고 이런 방식은 어떨까요?

int countbit3(uint n)
{
  int bits = 0;
  while (n != 0)
  {
    bits += n & 1;
    n >>= 1;
  }
  return bits;
}

이 방식은 루핑 횟수는 많겠지만, 분기문이 없으므로 캐쉬미스가 없습니다. 상위 2개의 샘플보단 빠르겠죠?

^^

ps : 근데...countbit2가 countbit1에 비해...월등히 분기문이 많은데...;; 과연 성능 향상이 어느정도인지 궁금하네요...


------------------------------------------
Let`s Smart Move!!
http://kalstein.tistory.com/

owlet의 이미지

while문에서도 분기가 일어난다는것을 잊으신것같습니다. 루프 언롤링을 사용하는 이유가 분기 횟수를 줄이기 위함입니다. 32bit가 체킹된다고 가정했을때 분기 횟수를 비교해보면
countbit1 : while = 33, if = 32, total = 65
countbit2 : while = 5, if = 32, total = 37
countbit3 : while = 33, if = 0, total = 33
3이 2보다 total은 적지만 무조건 분기하는 while보다는 조건에 따라서 분기하지 않을수도 있는 if문이 더 유리할것같아 보입니다. 또한 3에서는 n & 1의 결과를 레지스터에 저장한 후 bits에 더해야 하기때문에 환경에 따라서 손실이 더 있을수도 있을것같습니다.

kalstein의 이미지

아차차...while문 분기는 생각을 안했군요 ㅎㅎ

레지스터에 저장한 후 bits에 더하는 문제는...if문안에서 도 어차피 AND연산의 결과를 어딘가에 저장한 후에 0인지 아닌지 비교하니까 큰 문제는 없을꺼 같아요.

countbit3을 제시한 이유가...분기문 자체는 적으면 적을수록 컴파일러가 최적화 시키는게 편하다고 하더군요. 그쪽 분야는...워낙 대단한 분들이 많아놔서리 ㅎㅎㅎ


------------------------------------------
Let`s Smart Move!!
http://kalstein.tistory.com/

ohhara의 이미지

약간 다른 얘기긴 한데...

max, abs, min을 분기 안 쓰고 구현하는 것도 다음과 같이 가능하다더군요. 분기 안 쓰고 구현하려는 처절함이 느껴지는 -_-;;;

static int int_max(int a, int b) {
b = a-b;
a -= b & (b>>31);
return a;
}

static int int_abs(int a) {
return a - ((a+a) & (a>>31));
}

static int int_min(int a, int b) {
b = b-a;
a += b & (b>>31);
return a;
}

Taeho Oh ( ohhara@postech.edu , ohhara@plus.or.kr ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
Digital Media Professionals Inc. http://www.dmprof.com

Taeho Oh ( ohhara@postech.edu ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
Alticast Corp. http://www.alticast.com

magingax의 이미지

그럼 global 변수를 애용하는게 비효율적이란 건가요?

덩어리가 크고 자주 쓰이는 클래스를 global로 좋고 각 함수에서 여러번

사용하는 구조를 애용했는데..이건 아닌건가요?

LISP 사용자모임
http://cafe.naver.com/lisper
방송기술 개발업체
http://playhouseinc.co.kr

큰괭이의 이미지

"unsigned가 signed보다 효율적이고 parameter pointer를 직접 Access하지 않고. Local에 pointer변수를 만들어서 casting해서 쓰고"

사실 이런 원리의 중요성은 그 사람이 어떤일을 하느냐에 따라서 이런 fact의 중요도가 결정되는 것 같습니다.
저도 Embedded하는 사람입니다만.
driver를 작성할때는 되도록 이런 부분에 대해서 신경을 씁니다만.
Application을 할때 이런 부분까지 고민하면서 코딩을 하면... 코드 짜기 정말 힘들죠.
(혹은 이런데 신경쓰는 것보다 다른 관점의 것을 신경쓰는것이 App코딩에서 더 성능향상을 가져올 수 있습니다.
ex) File Access를 최소화 한다던가, MemAlloc을 최소화 할 수 있도록 코딩한다던가...)

실제 Driver작성시/DSP Code작성시/Kernel 코드 작성시/Assembler코드 작성시 일때는 이러한 부분이 많이 생각해서
읽기 쉽고 최적화된 코드를 작성해야겠지요.

Global변수가 비효율적이다 라는 관점은 Application Level로 올라가면 무의미 할것 같습니다 ^^.

?

tj의 이미지

int global;

void myfn()
{
        global++;
        some_function();
        global++;
}

누구나 global을 바꿀 수 있고, some_function()이 global을 바꿀지 안바꿀지를 컴파일러가 알 수 없어서 레지스터에 값을 캐싱할 수가 없는건데, 원글에서처럼 스택 변수에 캐싱을 해도 되고 아니면 컴파일러에게 some_function()이 pure function이라는 걸 __attribute__로 알려줘도 됩니다.

음, 마이크로 최적화가 필요한 부분이 있긴 하지만 아키텍쳐 의존적인 부분도 많고, 컴파일러들도 똑똑한데다가, 무작정 적용해선 대부분의 경우 의미있는 성능 차이로 나타나지 않거나 오히려 성능이 나빠지는 경우도 있습니다 (최적화한다고 쓰는 코드들이 원래 코드보다 빨라보이지만 크기는 커지는 경우가 많아요. 결과적으론 더 느리죠). 가독성을 목표로 코드를 쓰는게 훨씬 나으리라 생각합니다. 마이크로 최적화는 코드 돌리면서 oprofile로 보고 정말 hot path들만 해줘도 충분해요.

ㅡ,.ㅡ;;의 이미지

16번..if문에 대해서...
>>16 Binary Breakdown
>>여러개의 조건을 검사하다 보면, if와 else if를 여러개 사용하는 경우가 생긴다.

이부분... 그와같은경우는 switch 문이 더빠름.

그리고..8번.
>>8 배열을 이용한 index 생성
default 처리가 어렵다.. 즉, 범위이상의 값이 들어오면 메모리에러로 바로죽어버리는 매우위험한방법입니다.
또한 그리큰이득은 얻기힘들다.사실어느것이 우월한지 잘모르겠네요..
인덱스는 포인터계산이 한번들어가니..

>>11 Using Aliases
>>아래의 코드를 보기 바란다.
이부분도...좀...이상한거같네요..
함수호출은 이미 문법의 의미상 값을 복사하도록합니다. 포인터를쓰던 로컬변수를 쓰던말이죠..그러나.컴파일러에의해
최적화를 기대하셨다면.. 글쎄요.. 요즘컴파일러는또어떨지.. 아니면 조만간 가까운미래의 컴파일러는또어떨지..
그럴경우..로컬변수카피는 오히려 부하를 가중시키게될텐데요..

다른건 안봤는데 그냥 눈에띄는거같아...적어봤습니다.
----------------------------------------------------------------------------
C Library Development Project


----------------------------------------------------------------------------

소타의 이미지

어떻게 쓰느냐에 따라 많은 if 문 보다는 switch가 편하고 더 빠른건 맞는것 같습니다.
문자열 비교로 HTTP 파서를 만들때
if (strncasecmp) 이런걸 자주 써야 하는데 좀 느린감이 있었는데

switch (요청헤더[0]) {
 case 'c':
 case 'C':
  switch (요청헤더[1]) {
   case 'o':
   case 'O':
    //Connection: 헤더 처리
    if (strncasecmp(&(요청헤더[2])))
   break;
  }
 break;
}

이런식으로 풀어서 많은 성능 향상을 맛본적이 있습니다

그리고 8번 같은 경우는 저도 자주 쓰는데 그전에 범위에 대한 처리는 미리 해야겠죠. 그부분은 사전에 해야 하는 작업이거나 또는 임베디드나 모바일 쪽이라 한정적인 환경이라 생략하신것 같네요 ㅎㅎ

cronex의 이미지

16번.
비교하는 값이 한가지라면 당연히 switch 가 좋겠지만...
여러가지 값을 비교해가면서 상황이나 대상을 분류해나가는 if 문이라면
당연히 if ... else if를 여러개 써야만 하는경우가 생깁니다.
(윤드림 님의 예가 좀 너무 단순한 면이 없지는 않습니다만...)
(만약 0이하일 때, 0일때, 1~30일때, 31~100일 때 , 101~300일때, 301~1000 일때, 1001~3000일 때 3001~10000 일때, 10001 이상일 때 등으로 분류해야 할때 과연 switch 로 해결할 수 있을까요?)

8번 값의 범위를 벗어나는 처리는 배열 사용 앞에서 체크를 해줘야겠지요.

11번
윤드림 님이 말씀하신건 함수가 아니라 for문 앞에 local variable을 선언하는 것을
말씀하신 겁니다. 포인터 값의 원래값을 가져다 쓰려면 메모리 참조를 2번하게 됩니다.
따라서 그 값을 local에다가 저장해두고 그 값을 가져다 쓰는 것이
메모리 참조 횟수를 줄일 수는 있지요. 저게 루프를 10번 도는게 아니라
한 1000번쯤 도는 거라고 생각하면 엄청난 차이가 생깁니다.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

ㅡ,.ㅡ;;의 이미지

설사 스트링이라하더라도 저렇게 if 를 문기할것이라면 switch가 유리하죠.
그러나 매우 잦은호출이 일어 나지 않는다면 스트링은 그냥 if else로 줄줄이 씁니다..
11번은 포인터참조를줄인다는말이었던가요.. 잘못이해했네요..

>17 Switch 대신 lookup table 를 사용하라
>switch는 다음과 같은 경우 사용한다.
>예를 들어서 조건값을 입력받아서 거기에 맞는 문자열을 리턴하는 아래와 같은 코드가 있다고 가정해보자.
>위의 코드는 아래와 같이 좀 더 효율적인 코드로 만들 수 있다. 덤으로 보기에도 편하다.
>첫번째 루틴은 240byte가 필요하지만 두번째 루틴은 72바이트만 소모되고 있다.

이것도 코딩량은 줄어들었으나 성능은떨어짐..

----------------------------------------------------------------------------
C Library Development Project


----------------------------------------------------------------------------

cronex의 이미지

댓글을 수정해서 설명했지만 단순 값의 비교가 아닌
값의 범위가 설정되는 경우는 if ~ else if를 쓸 수밖에 없다고 생각합니다.

17번의 경우는 코딩량이 아니라 코드가 컴파일 됐을 때
메모리에서 차지하는 양을 의미합니다.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

ㅡ,.ㅡ;;의 이미지

물론 아예 if else 를 쓰지말라는게 아니죠.. 써야할곳이 있죠 그러나 예제에서 보면 그렇다는겁니다.
상황에 맞게 써야죠. 저도 if else 더많이 씁니다.
제가 게을러서 궂이 작은 성능개선을 위해서 switch 쓰고 싶지 않거든요..
적절히 쓰죠.. 그러나 글쓰신분은 성능을위해 더 힘든? 코드를 마다하지 않으셨기에 그렇것같으면 차라리 switch가
성능도 더좋고 보기도 더좋지 않냐는것입니다.

17번
윗글에도 코드량이 적다는건 이미 말씀드린거구요..
컴파일됬을때 덩치가 더커지는지는 해보지 않아 어느것이 많은지는 모르겠습니다만.
위의 다른내용들을보면 성능을위해서 더많은 코드를 마다하지 않고 있죠...
그런의미에서 말한겁니다.

----------------------------------------------------------------------------
C Library Development Project


----------------------------------------------------------------------------

cronex의 이미지

최적화라는 건 성능 최적화와 메모리 최적화가 있을 수 있습니다.
하지만 어느 경우에도 trade-off라는게 있어서 항상 성능 최적화만을 추구할 수도 없고
항상 메모리 최적화만을 추구할 수도 없습니다.

어느 부분은 메모리 사용량을 절반 이하로 줄여도 성능이 아주 약간 떨어질 뿐인 반면
어느 부분은 메모리 사용량을 10%만 줄여도 성능이 두배 이상으로 느려지는 경우도 종종 있죠.
반대로 성능을 10% 향상 시키기 위해 메모리 사용량을 두배를 투자해도 힘든 경우도 있고
약간의 캐시를 두는 것만으로도 성능이 두배로 향상되는 경우도 있습니다.

따라서 상황에 맞는 최적화를 수행해야 해야 합니다.
윤드림님의 글은 최적화를 수행하고자 할 때 기존의 코드를 고칠 수 있는 방법들을 소개하고 있을 뿐..
모든 경우에 대해서 꼭 이렇게 해야만 모든 경우와 상황에서 항상 최적화된 코드가 나온다는
메뉴얼이나 무슨 법칙같은 걸 써놓으신게 아닙니다. 이건 본문 처음에도 나와있지요.

yundream7 wrote:
보통 프로그램의 속도를 높이게 되면 코드의 크기가 늘어나게 된다. 코드의 크기가 늘어나면 프로그램이 복잡해지고, 읽고 이해하기 어려워진다. 메모리 자원이 넉넉한 개인PC혹은 서버 컴퓨터라면 문제가 되지 않겠지만 PDA와 같은 제한된 메모리 자원을 가진 기기일 경우 심각한 문제가 될 수 있다. 1%의 속도향상을 위해서 코드의 크기가 10%만큼 늘어난다면 분명 문제가 될 것이다. 이런 이유로 속도와 코드크기 모두에 대한 최적화를 수행하기로 결정을 했다.

윗글의 내용은 단순한 경험적인 예들일 뿐입니다. 명제들이 아니구요.
어느 경우에는 단순히 성능이나 메모리만 잡아먹는 코드 일 수도 있고
어느 경우에는 둘다 잡을 수 있는 좋은 해법일 수도 있는 거죠.
다 쓰기 나름일 것입니다. 다만 글의 일부가 맘에 안드신다면 그건 안쓰시면 되겠습니다.
부디 본문의 목적과 지향하는 바를 이해해주셨으면 하네요.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

tj의 이미지

cronex님 말씀에 대부분 동의하구요. 약간 부연하면, 요즘 포로세서들의 경우엔 메모리 최적화와 성능 최적화가 같이 가는 경우가 많습니다. 캐시 미스 레이턴시가 워낙 크기 때문에, 작은 코드가 빠른 코드인 경우가 많고, 소프트웨어가 어느정도만 복잡해지면 마이크로 밴치시 성능이 좋아졌던 코드를 실제에 적용하면 캐시 사용량 문제로 전체 속도에 떨어지는 경우도 생깁니다. 좀 더 장기적으로 생각하면, 아키텍쳐나 프로세서 세대 변화에 따라 득이 되던게 해가 될 수도 있고, 컴파일러에게 의도가 아니라 구현을 설명하게 되서 컴파일러가 최적화할 수 있는 가능성을 떨어뜨립니다. 특수 환경이나, 프로세싱 시간의 대부분을 사용하는 tight loop이 아니면 가독성을 떨어뜨리는 최적화는 최선을 다해 피하는게 좋습니다.

익명사용자의 이미지

음, 제 생각에는 범위를 벗어나는 값이 들어왔을 때 바로 죽어버리는 게 아주 안전하고 좋은 방법입니다. (물론, "범위를 벗어나는 값이 들어오지 않는다"라고 약속이 되어 있을 때.) 그러면 왜 죽었는지 core 떠보고 바로 디버깅을 할 수 있죠.

범위를 벗어난 값이 원래 들어오면 안되는데도 불구하고 죽지 않으면 오히려 그만큼 버그 발견이 늦어집니다. 최악의 경우, 들어오면 안되는데 일부러 default를 써서 안 죽게 만들어 놓으면, 이건 버그를 숨기는 코드가 되는 거죠. QA에서 테스트할 때까지 잘 돌다가 고객 앞에서 장렬히 산화하게 됩니다. -.-

그리고 11번은 확실히 차이가 있습니다. 포인터를 쓰면 aliasing의 가능성 때문에 컴파일러가 매번 메모리에서 읽어와야 합니다. 예제로 나온 코드의 경우 메모리를 열 번 참조해야 하죠. 하지만 로컬 변수로 복사하면 (레지스터가 넉넉하단 전제 하에) 메모리에서 단 한번만 읽어오면 되고, aliasing이 없다는 게 보장이 되기 때문에 최적화의 가능성이 훨씬 넓어집니다.

컴파일러는 무슨 최적화를 해도 절대 원래 코드와 동작이 달라지면 안되기 때문에 아주 보수적으로 (최악의 가능성을 항상 생각하면서) 작업할 수밖에 없죠. 로컬 변수는 aliasing 가능성을 없애줘서 optimizer의 운신의 폭을 넓혀줍니다.

예를 들어 다음과 같은 코드를 보죠.

void foo(int *a, int *array)
{
  while (*a) { array[*a] = (어쩌구); (*a)--; }
}

이 경우 a와 array가 겹치지 않는다는 보장이 없으므로 컴파일러는 루프를 돌 때마다 a를 다시 읽어와야 하는 것은 물론, array에 값을 넣는 순서도 순차적이 아닐 수 있다고 가정해야 하죠.

하지만 *a를 먼저 로컬 변수에 복사해 놓고 시작하면, 컴파일러는 a가 하나씩 감소하여 0이 될 때까지 루프를 돈다는 것을 알 수 있으므로 loop를 위해 최적화된 기계어 명령을 쓸 수도 있고, array에 값이 순서대로 들어가는 게 보장되므로 이 경우에 특화된 각종 최적화를 수행할 수 있습니다. (예를 들어 x86이라면 string instruction 등을 쓸 수도 있겠죠.)

- jick

ㅡ,.ㅡ;;의 이미지

개인적인 의견이라하셨지만...약간반론을 달자면....

메모리 범위가 넘어서면 바로 안죽습니다.. 죽는거는 잡아도 안죽으면 나중에실상황에서 죽겠죠..

>>default를 써서 안 죽게 만들어 놓으면, 이건 버그를 숨기는 코드가 되는 거죠. QA에서 테스트할 때까지 잘 돌다가 >>고객 앞에서 장렬히 산화하게 됩니다
이건좀...ㅡ,.ㅡ;;
default로들어오면 당연히 에러로 빠지든지하지 그걸 머어떻게 해놓길래 테스트때 안죽고 고객앞에서 죽는다는건지 이해할수 없군요.. 전 일부러 만들려해도 힘들것같군요..

----------------------------------------------------------------------------
C Library Development Project


----------------------------------------------------------------------------

시지프스의 이미지

11 Using Aliases
int *data가 결코 변하지 않으면 const int *data라고 하면 되지 않나요? 이렇게 되면 *data가 상수니까 알아서 한 번만 읽어 올 것 같은데요.
아니면 int * restrict data라고 하면 되지 않나요?

begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}

cronex의 이미지

포인터 값이 변경되서는 안되기 때문에 const int *data 를 쓰는 것과는 별개의 문제 입니다.
즉, int형 포인터인 data가 가리키는 값(즉 *data)을 읽어오기 위해서
값 참조를 2번 해야 한다는 것이 문제지요.

즉, 변수 data 에 저장된 포인터 값을 읽어와서(1)
그 포인터가 가리키는 메모리 위치에 있는 실제 int 값을(2)
읽어오기 때문이죠.

하지만 만약 저 data 값을 로컬 변수에 저장하면
포인터의 위치를 참조할 필요 없이 바로 로컬 변수에 접근해서 값을 읽을 수 있습니다.

물론 단 한번만 쓰고 끝날 값이라면 이렇게 할 필요가 없겠지만
루프내에서 사용되거나 비교문에서 중첩되서 사용되는 경우라면
로컬 변수로 저장하는 편이 좋습니다.

그리고 restrict와는 그다지 관련이 없는 것 같습니다.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

전웅의 이미지

> > 11 Using Aliases
> > int *data가 결코 변하지 않으면 const int *data라고 하면 되지 않나요?

const 라는 형한정어는 값이 변하지 않음을 보장해 주는 역할을 하는 것이
아닙니다. 단지 "해당 포인터를 통해서 값을 변경할 수 없음"을 의미하는
것뿐입니다 - 아래 코드를 생각해 보시기 바랍니다.

void f(const int *a, int *b)
{
    int temp = *a;
    *b = 0;
    printf("%d, %d\n", temp, *a);
}
 
int i = 100;
f(&i, &i);

> > 이렇게 되면 *data가 상수니까 알아서 한 번만 읽어 올 것 같은데요.
> > 아니면 int * restrict data라고 하면 되지 않나요?
> >

넵, 맞습니다. 바로 restrict 가 해당 포인터가 가리키는 변수는 그
포인터를 통해서만 접근이 된다는 사실을 분명히 해주기 위한 것입니다!
만약, 위의 제 예에서 a, b 포인터를 restrict 로 한정할 경우, f(&i, &i)
라는 호출 자체가 잘못된 행동(undefined behavior)이 됩니다. 따라서
컴파일러는 함수 f 안에서 안전하게 *a 와 temp 가 결국 같은 값이라는
가정을 할 수 있게 되는 것입니다.

>
> 포인터 값이 변경되서는 안되기 때문에 const int *data 를 쓰는 것과는 별개의 문제 입니다.
> 즉, int형 포인터인 data가 가리키는 값(즉 *data)을 읽어오기 위해서
> 값 참조를 2번 해야 한다는 것이 문제지요.
>
> 즉, 변수 data 에 저장된 포인터 값을 읽어와서(1)
> 그 포인터가 가리키는 메모리 위치에 있는 실제 int 값을(2)
> 읽어오기 때문이죠.
>
> 하지만 만약 저 data 값을 로컬 변수에 저장하면
> 포인터의 위치를 참조할 필요 없이 바로 로컬 변수에 접근해서 값을 읽을 수 있습니다.
>
> 물론 단 한번만 쓰고 끝날 값이라면 이렇게 할 필요가 없겠지만
> 루프내에서 사용되거나 비교문에서 중첩되서 사용되는 경우라면
> 로컬 변수로 저장하는 편이 좋습니다.
>

11번 항목의 핵심은 포인터의 위치를 추가로 참조하냐 안 하느냐의 문제가
아닙니다.

void a(int *a, int *b)
{
    ...
    for (i = 0; i < N; i++)
        process(*a);
    ...
}

이 코드에서 컴파일러가 "포인터 a 가 가리키는 변수가 다른 포인터나
변수에 의해 aliasing 되었는지 알기 어렵기 때문에" *a 를 고정된 값으로
치환해 최적화할 수 없다는 뜻입니다. 즉, a 가 가리키는 변수가 맨 처음
보인 예에서 처럼 다른 포인터나 변수 등을 통해 수정될 수 있기 때문에
매번 a 가 가리키는 변수의 현재 저장된 값을 확인해야 하는 문제가 발생
한다는 것입니다 - 물론, data flow analysis 등을 통하면 aliasing 에
대한 사실을 확인하는 것도 가능합니다만, 항상 가능한 문제도 아닐 뿐더러
쉽지 않은 과정입니다.

이 문제는 위에서 언급했듯이 restrict 를 적절히 도입해 해결할 수 있는
문제입니다. 즉, 포인터 a 가 가리키는 변수가 aliasing 되지 않았음을
컴파일러에 알려주면 컴파일러가 문제의 코드를 "맘놓고" 최적화할 수 있게
됩니다. 즉, 위의 코드를

void a(int * restrict a, int * restrict b)
...

로 써줄 경우 컴파일러는 aliasing 에 대한 걱정 없이 루프 수행 전 *a 의
값을 한번만 확인해 process() 호출에 사용할 수 있게 됩니다.

임시 변수를 직접 도입해 사용하는 것은 restrict 를 통한 이러한 최적화를
손수 해주는 것으로 볼 수 있습니다. 지원된다면 restrict 를 사용하는
것이 바람직하겠지만, restrict 가 지원되지 않거나 지원하더라도 이를
통한 최적화가 형편 없는 (제 컴파일러 같은 --;) 컴파일러일 경우에
유용한 팁으로 생각할 수 있습니다.

> 그리고 restrict와는 그다지 관련이 없는 것 같습니다.
>

고로 restrict 와 관련된 문제입니다.

그럼...

--
Jun, Woong (woong at icu.ac.kr)
Web: http://www.woong.org (서버 공사중)

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

시지프스의 이미지

Quote:
const 라는 형한정어는 값이 변하지 않음을 보장해 주는 역할을 하는 것이
아닙니다. 단지 "해당 포인터를 통해서 값을 변경할 수 없음"을 의미하는
것뿐입니다 - 아래 코드를 생각해 보시기 바랍니다.

전혀 생각하지 못한 부분이었네요.
Quote:
임시 변수를 직접 도입해 사용하는 것은 restrict 를 통한 이러한 최적화를
손수 해주는 것으로 볼 수 있습니다. 지원된다면 restrict 를 사용하는
것이 바람직하겠지만, restrict 가 지원되지 않거나 지원하더라도 이를
통한 최적화가 형편 없는 (제 컴파일러 같은 --;) 컴파일러일 경우에
유용한 팁으로 생각할 수 있습니다.

그런데 gcc는 restricted pointer를 지원하지 않나요? http://gcc.gnu.org/c99status.html에는 지원한다고 나오는데, syntax 에러가 나네요.
      1 #include <stdio.h>
      2
      3 void noname(int * restrict a);
      4
      5 int main(void) {
      6         int *a = malloc(sizeof (int));
      7         *a=8;
      8         noname(a);
      9         return 0;
     10 }
     11
     12 void noname(int * restrict a) {
     13         printf("%d",*a);
     14 }

rest.c:3: error: syntax error before "a"
rest.c:12: error: syntax error before "a"
rest.c: In function `noname':
rest.c:13: error: `a' undeclared (first use in this function)
rest.c:13: error: (Each undeclared identifier is reported only once
rest.c:13: error: for each function it appears in.)

begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}

전웅의 이미지

>
> 임시 변수를 직접 도입해 사용하는 것은 restrict 를 통한 이러한 최적화를
> 손수 해주는 것으로 볼 수 있습니다. 지원된다면 restrict 를 사용하는
> 것이 바람직하겠지만, restrict 가 지원되지 않거나 지원하더라도 이를
> 통한 최적화가 형편 없는 (제 컴파일러 같은 --;) 컴파일러일 경우에
> 유용한 팁으로 생각할 수 있습니다.
>
> 그런데 gcc는 restricted pointer를 지원하지 않나요? http://gcc.gnu.org/c99status.html에는 지원한다고 나오는데, syntax 에러가 나네요.
>
> 1 #include
> 2
> 3 void noname(int * restrict a);
> 4
> 5 int main(void) {
> 6 int *a = malloc(sizeof (int));
> 7 *a=8;
> 8 noname(a);
> 9 return 0;
> 10 }
> 11
> 12 void noname(int * restrict a) {
> 13 printf("%d",*a);
> 14 }
>
> rest.c:3: error: syntax error before "a"
> rest.c:12: error: syntax error before "a"
> rest.c: In function `noname':
> rest.c:13: error: `a' undeclared (first use in this function)
> rest.c:13: error: (Each undeclared identifier is reported only once
> rest.c:13: error: for each function it appears in.)
>

-std=c99 옵션이 필요합니다.

--
Jun, Woong (woong at icu.ac.kr)
Web: http://www.woong.org (서버 공사중)

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

yarmini의 이미지

도움이 많이 되는 글이었습니다^^

항상 최적화와 가독성 두 갈래에 있는 데 둘 다 잡는 팁도 많네요^^

언 제 나 멋 진

언 제 나 멋 진

익명 사용자의 이미지

장문의 좋은 글이네요.

부족하게나마 저도 나름대로 아래 블로그에 정리를 해보았습니다.

http://a.tk.co.kr/126

Kyuseo의 최적화 원칙:

- CPU 부하가 큰 반복작업은 최대한 최적화 코드로 작성하라.

- 코딩 수정으로 최적화를 하지 말고 알고리즘으로 최적화를 하라.

- 더 빠른 속도가 필요하다면 어셈블리(Assembler) 언어를 사용하라

- 코드의 최적화보다는 코드의 유지보수를 우선하라.

- 사소한 최적화에 시간과 노력을 투자하지 말아라.

- 중복코드를 최소화 하라.

- inline을 활용하라.

익명 사용자의 이미지

일단 좋은 글 잘읽었습니다. (아직 다는 못읽었지만ㅎㅎ)
위의 것들 중 몇가지는 gcc에서 자동으로 최적화가 되는 것들이 있긴 하지만
개인적으로 저런 코딩 습관을 들이는건 꽤 중요하다고 생각을 하네요.
compiler-dependent한 코드야말로 기피해야 하지 않을지...
또 위의 것들이 가독성에 그닥 영향을 미치는 것 같지도 않고요..^^

큰 의미가 없다는 댓글들도 있던데,
위의 대부분의 것들은 결코 가볍게 넘길순 없는 것들이라고 봅니다.
몇개를 실제로 컴파일해서 돌려도 보고, 어셈블리 코드를 살펴보기도 했는데,
저는 10번의 경우가 인상적이더군요
글로벌 변수를 피해야 하는 이유가 여러가지가 있지만,
레지스터 캐싱은 실제 코딩할때 전혀 신경쓰지 않았던 부분이었습니다.
실제로 돌려보면 gcc에서 O3옵션을 써도 7배가량의 성능차가 있네요

익명 사용자의 이미지

18번에서 한가지 의문점이 있는데..
한마디로 equal-zero 명령어가 compare 명령어보다 클럭 소모가 덜하니
count down 방식을 사용하라는것 같은데요
어차피 compare 명령이나 equal-zero명령이나 클럭 소모는 1 clock cycle이라서
차이는 없다고 생각합니다.
compare도 결국엔 subtraction을 하는거니.. 웬만한 플랫폼에서는 subtraction의 클럭 소모는 1 cycle밖에 안되니까요.
혹시 틀린점이 있다면 지적 부탁드립니다.

swirlpotato의 이미지

답글 달아주신 덕에 오래된 좋은 글이 올라오게 되서 읽게 되었네요.
감소 하는 방법으로 쓰면 결과가 0이 되면 zero flag가 설정되어 추가적인 compare를 하지 않아도 되기 때문입니다.
만약 loop가 10까지 돌아야 한다면 branch가 있기 전에 값이 10인지 아닌지 확인해야 합니다.

익명 사용자의 이미지

18번에서 한가지 의문점이 있는데..
한마디로 equal-zero 명령어가 compare 명령어보다 클럭 소모가 덜하니
count down 방식을 사용하라는것 같은데요
어차피 compare 명령이나 equal-zero명령이나 클럭 소모는 1 clock cycle이라서
차이는 없다고 생각합니다.
compare도 결국엔 subtraction을 하는거니.. 웬만한 플랫폼에서는 subtraction의 클럭 소모는 1 cycle밖에 안되니까요.
혹시 틀린점이 있다면 지적 부탁드립니다.

익명 사용자의 이미지

특정값(N)으로 loop를 도는 경우
loop:
ADD a
CMP a,N
BEZ loop

zero로 loop를 도는 경우
loop:
SUB a
BEZ loop

익명 사용자의 이미지

알고도 실천을 귀차니즘으로 실천을 안 한 부분도 많고, 몰라서 못썻던 부분도 있네요.
아주 많은 도움 되었습니다.

익명 사용자의 이미지

이정도 최적화 작업들은 컴파일러가 요즘은 똑똑해져서 웬만하면 해준다고 하던데..
안하는것만 못하다는 소리가 있던데.....

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.