[컴] 컴파일러에서 사용하는 최적화 방법, loop unrolling, inlining, vectorization

벡터 / 룹 최적화 / optimization

컴파일러에서 사용하는 최적화 방법, loop unrolling, inlining, vectorization

loop unrolling

loop 을 만약에 100번 돌아야 하면, 이것을 50번만 돌도록 만든다. 이것이 loop unrolling 이다.

loop 을 전개(펼치는, unrolling)하는 것인데, 예를 들면 다음처럼 print()를 10번해야 하는 경우, 한번의 loop 마다 print 를 2번 넣어서 loop 의 횟수를 줄인다.

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

for(var i = 0 ; i<10; i+=2){
    print(i)
    print(i+1)
}

이러면, i 를 증가시키는 연산의 횟수는 줄지않겠지만(print 에서 i+1을 하니), loop 의 condition 을 확인하는 부분(i<10) 을 덜 수행하게 된다.

inlining

inlining 은 c/c++ 의 inline function 을 생각하면 된다. 함수호출을 없애고, 함수의 code를 대신 넣는 것이다. 예를 들면 다음과 같다. 이렇게 하면 function call 로 인해 생기는 overhead 가 줄어든다.

function call 을 하면 stack 또는 register에 argument들을 넣고, branch instruction 을 실행하지만, inline 을 하면 이런것들을 할 필요가 없다.(Function prologue and epilogue) 그리고 return 할 때 일어나는 일들(Return statement) 도 필요없다. function prologue, then at return the function epilogue, the return statement

또한, 함수가 하나의 큰 함수가 되기 때문에, 이것이 좀 더 optimization 을 할 여지를 준다. 그래서 이전보다 더 최적화가 될 수 있다.(참고: ref. 2, Effect on performance)

자세한 이야기는 ref. 2 를 참고하자.

function add(a,b){
    return a+b
}

var c = add(a,b)

var c = a + b

vectorization

SIMD(single instruction multiple data) 로 처리하는 방법이다. 다음과 같이 변환할 수 있다.

for (i = 0; i < 1024; i++)
    c[i] = a[i] * b[i];

# a[i] ~ a[i+3] 까지의 data 를 한번에 처리하는 것이다.
for (i = 0; i < 1024; i += 4)
    c[i:i+3] = a[i:i+3] * b[i:i+3];

Reference

1. Loop unrolling - Wikipedia
2. Inline expansion - Wikipedia
3. Automatic vectorization - Wikipedia