[ Programming - 한발 더 나아가기 ] Compiler & Optimization

 요즘 대부분의 경우 compiler의 optimization만으로도 충분하다.

 그렇지만 몇몇 특수한 경우, compiler는 알 수 없지만, programmer는 알고 있는 것들을 적극적으로 이

용할 필요가 있다. 이 글에서는 다음의 내용들을 소개하고자 한다.

* memory barrier
 compile은 file단위로 이루어진다. 그러므로, 비록 programmer가 thread-safety에 대해 고려 하고

coding을 했더라도, compiler가 optimization 과정에서 이를 깨는 경우가 많다.
    가장 대표적인 예가 아래의 경우이다.

    ...
    struct stA {
        int a;
        int b;
        int c;
    };
    ...
    replace (const struct stA* p) {
        struct stA* np = malloc(sizeof(struct stA));
        np->a = 10;
        np->b = 20;
        np->c = 30;
        // <-- A --->
        p = np; // assumes that assign-operation is atomic.
    }
    ...

 programmer는 multi-threading환경에서의 race condition을 고려해서 replace함수를 구현했지만 -

"p = np;"가 가장 아래에 위치해 있다. - compiler의 Out Of Order Optimization으로 인해 programmer의

이러한 의도가 지켜지지 못할 수도 있다.
 (단, 여기서 CPU의 Hardware적인 Out Of Order Execution과 거기에 대응하는, Hardware적인 memory

fence/barrier는 논외로 한다.)
 이런 경우, mutex를 이용해서 해결할 수도 있지만 mutex는 상당히 cost가 비싼 operation이니 만큼

되도록이면 이용하지 않는것이 좋다. 이런 경우 memory barrier를 이용하면 된다.
 memory barrier (membar, memory fence 혹은 fence instruction)에 대한 자세한 내용은 다른 여러

곳에서 잘 설명되어 있으니 따로 언급하지 않겠다.
 다만, 위의 경우 'A'의 위치에 barrier를 두면 mutex를 사용하는 overhead없이 위 문제를 해결할 수

있다.

* compiler hint

 이미 앞서 이야기한대로, compiler는 알지 못하지만, programmer는 알고 있는 내용들을 이용하는 또 다른 방법이 'compiler hint'이다.

 compiler hint는 branch문 - 특히 if/else - 에서 많이 쓰이는데, programmer가, runtime에 분기하는 빈도수가 높은 쪽을 compiler에게 미리 hint를 주는 것이다. 예를 들면, "if (<cond>) { A } else { B }" 이고, runtime에 대다수의 경우 B쪽으로 분기하게 된다는 것을 programmer가 안다면, <cond>에 이러한 힌트를 함께 언급해 주는 것이다.

 그럼 왜 branch문에 이런 compiler hint가 많이 쓰이는 것일까? 그리고 어떠한 잇점이 있는 걸까?

 대부분의 Architecture - 특히 RISC - 에서, 성능향상을 위해, pipeline을 사용한다. 그리고 일반적으로 이 pipeline의 단계를 늘림으로서 성능향상을 기대할 수 있다.

 그런데, pipelining을 위해서, 다음에 수행할 instruction을 미리 읽어오는 방법을 쓰게 되는데 - instruction prefetch - branch문에서는 다음에 어떤 쪽으로 수행될지가 runtime에 결정되기 때문에 - 즉 compiler가 알지 못한다 -  compiler는 자체적으로 판단하여 prefetch를 수행할 쪽을 결정하고, 이를 반영해서 compile하게 된다. 이런 예측이 옳은 경우는 pipeline이 깨어지지 않고 잘 수행되어 별 문제가 없는데, branch가 예측한 곳과 다른 곳으로 일어나게 되면, 미리 prefetch했던 instruction이 무효한 것이 되므로 이 순간 pipelining이 깨어지게 된다. (앞의 내용들이 이해가 되지 않는다면, pipeline에 대해서 wikipedia등을 이용하길 바란다.) 즉, performance측면에서 손해를 보게 되는 것이다.

 이런 손해를 최소화 하기 위해서, programmer가 어느 쪽으로 분기하는 경우가 많은지를 compiler에게 hint를 줄 필요가 있는 것이다.

 아래의 예는 Linux kernel에서 볼 수 있는 'likely/unlikely'를 사용한 예이다.

#define likely(x) __builtin_expect((x),1)
#define unlikely(x) __builtin_expect((x),0)

if (likely(n > 1)) {
    // 자주 수행되는 routine
} else {
    // 상대적으로 적은 빈도로 수해오디는 routne
}

if (unlikely(n > 1)) {
    // 상대적으로 적은 빈도로 수해오디는 routne
} else {
    // 자주 수행되는 routine
}

ㅇㅇㅇㅇ