c언어 restrict 한정어

포인터는 C/C++ 언어의 가장 큰 장점이지만 동시에 많은 버그의 원인이 되기도 한다. 포인터는 정말 강력한 도구로서 로우레벨의 접근을 용이하게 한다. 그래서 막연하게 포인터로 프로그래밍을 하면 최적화를 많이 할 수 있으리라 생각한다. 그러나 최적화라는 것을 컴파일러가 자동적으로 수행하는 것으로 한정지으면 이야기가 달라진다. 포인터는 컴파일러 최적화의 가장 큰 장애물이다.

컴파일러가 자동적으로 수행하는 최적화들은 여러가지가 있는데 간단하게는 쓸데 없는 코드 제거, 중복된 계산식의 축약, 내용이 짧은 코드는 인라인하기 정도가 있을 것이다. 보다 강력한 수준의 최적화는 메모리 레이턴시를 줄이기 위해, 또 루프에서 반복적으로 계산되는 것을 줄이기 위해, 코드 순서를 뒤 바꾸는 일을 할 수도 있다. (사실 gcc나 VC++ 컴파일러가 이 정도 수준의 최적화를 하는지는 잘 모르겠다)

1 : a = b + c;
2 : x = y + a;
3 : l = m / n;

위의 코드를 생각해보자. 1, 2번은 변수 a로 연결이 되어있어 서로 의존성 (true dependency)이 있다. 따라서 2번 명령은 결코 1번 보다 앞서 실행될 수 없다. 반면 3번은 1, 2번과 독립적이므로 병렬로 실행이 가능하고, 실제 x86 CPU 들은 그렇게 한다. 컴파일러가 최적화를 할 때도 이와 비슷한 것을 할 수 있다. 3번 명령을 1, 2번 위에다 놓아 미리 실행이 되도록 할 수 있다. 따라서 이런 최적화에 있어서 각 변수들과 메모리 주소간의 의존성을 푸는 것이 가장 기본적인 일이다.

그렇다면 포인터가 왜 문제인가? 위 코드는 모두 a, x, l과 같이 명확한 변수들, 즉 명확한 주소들이 사용되었다. 그러나 포인터는 임의의 주소를 가리킬 수 있다는 모호성을 가지고 있다. 위의 경우는 컴파일 할 때, 코드만 봐도 명령어들 사이의 의존성을 파악할 수 있지만 포인터는 여기에 들어올 주소가 동적인 시간에 바뀔 수 있으므로 의존성 파악이 매우 어려워진다.

1: *a = *b + *c;
2: *x = *y + *a;
3: *l = *m / *n;

첫 번째 코드와 비슷하지만 이제 모두 변수들이 포인터 타입으로 바뀌었다. 이제 3번 명령이 1, 2번과 서로 연관성이 없다고 말할 수가 없다. 포인터 m과 x가 동일한 메모리를 가리킬 수 있기 때문이다. 따라서 웬만한 똑똑한 분석을 동원하지 않는다면, 포인터는 모든 메모리 주소를 가리킬 수 있기 때문에 코드를 이동하는 것과 같은 고차원의 최적화가 불가능해진다.

이렇게, 어떤 경우는 컴파일을 할 때 포인터들이 서로 겹치지 않음을 완벽히 보일 수가 있을 것이고 (예를 들어, 잠시 사용되다 사라지는 포인터들), 어떤 것들은 항상 겹친다고 판단할 수도, 마지막으로 *겹칠지도 모른다* 라고 판단할 수 있다. 위의 경우도 이런 maybe에 해당하는 경우다. 컴파일러 최적화는 프로그램의 정확성을 보장해야하기 때문에 이런 경우 매우 보수적일 수 밖에 없다. 0.01% 가능성이 있더라도 항상 겹치는 것으로 간주할 수 밖에 없다. 그래서 사실상 포인터가 끼어들면 높은 수준의 최적화는 거의 불가능해진다.

그래서 등장하는 것이 speculative optimizations 이다. Speculation (예측)은 컴퓨터 구조에서 매우 많이 적용되는 기법이다. 한 마디로 요약하면, 일단 찍고 나서 무언가를 한 뒤에 문제가 생기면 다시 복구하는 것이다.

위와 같이 maybe인 경우도 그냥 안전하지 않더라도 하고싶은대로 코드를 이동해서 최적화를 해버린다. 그리고 그것이 아니라는 것이 판명이 되면 다시 되돌리는 것이다. 이런 것은 사실 하드웨어의 지원이 필요하다. 예를 들어, EPIC/VLIW 구조인 (VLIW는 간단하게 설명하면 하드웨어가 하는 일 중 많은 부분을 컴파일러에게 떠넘기고 하드웨어는 보다 간단히 만들어 고성능을 추구한다는 철학??) Intel의 IA-64 명령어에는 이런 것을 지원해주는 인스트럭션들이 있다.

1: *x = a + b;  // load &a; load &b; add a, b; store x;
2: c = *y + b;  // load y; load &b; add *y, b; store &c;

이런 코드가 있고, 포인터 x, y는 어떤 변수를 가리킬지 명확하지 않다. 그래서 2번 째 명령을 1번이 끝날 때 까지 기다릴 필요가 있을 수도 있다. 보다 자세히 말하면 y가 가리키는 메모리를 x가 가리키는 메모리가 다 쓰여질 때 까지 읽을 수가 없다. 그러나 IA-64의 명령어 중에는 어찌되었건 y를 speculative하게 load 하는 명령어가 있다. 만약, y의 메모리와 x의 메모리가 서로 겹치지 않는다면 찍기 성공. 성능 향상인 것이다. 만약 x, y가 서로 같은 메모리를 가리켰다면 삑사리. 다시 복구를 해야한다. 이럴 때, 이런 오류를 복구할 별도의 코드를 컴파일러가 생성하여 실행이 되게 한다. 따라서, x, y가 같은 메모리 주소를 가리킬 확률이 낮다면 이런 speculative optimization은 아주 이득일 것이다.

C 언어는 이런 것을 고려해서 포인터 앞에 특정 키워드를 줄 수도 있다. 바로 restrict pointers (C99)인데, 두 포인터가 가리키는 메모리가 결코 겹치지 않는다면 restrict 키워드를 추가하여 컴파일러가 보다 많은 최적화를 할 수 있도록 할 수 있다.

void vadd(const int* restrict px, const int* restrict py, int* restrict pz, int N)
{
   for (int i = 0; i < N; ++i)
    *pz++ = *px++ + *py++;
}

위 코드와 같이 두 벡터의 합을 계산하는 코드는 메모리가 겹칠 일이 없다 (보다 정확하게 루프 iteration 사이에서 겹칠일이 없으면 된다). 따라서 restrict 키워드를 줘서 포인터가 가리키는 메모리들은 모두 독립적이라고 알려줘서 루프를 빡세게 풀 수 있다 (loop unrolling). 만약, 이런 정보가 없다면, 루프 iteration 사이에 의존성이 있다고 가정해야하므로 최적화가 힘들어진다.

C언어가 등장한 것이 오래된 만큼, 이런 포인터의 복잡함을 해결하기 위핸 방법은 무수히 쏟아져 나왔다. 그러나 그 어떤 것도 완벽한 솔루션을 제공하지 못한다고 한다. 완벽하게 하려면 너무 많은 시간이 커져 큰 프로그램은 도저히 적용할 수 없거나 혹은 그 반대의 경우가 일어난다. 포인터는 정말 양날의 검이라는 표현이 딱 어울리는 존재라고 볼 수 있다.

참고문헌

A Probabilistic Pointer Analysis for Speculative Optimizations, (pdf) Jeffrey Da Silva and J. Gregory Steffan, International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 416–425, San Jose, CA, October, 2006.