Loop Unrolling (또는 Loop Unwinding) 은 프로그램의 loop 로직을 조금 수정함으로써 속도를 향상시킬 수 있는 방법이다.

loop 안의 내용을 일부 수작업으로 늘어놓는 일을 해야 하는데 이때 바이너리 코드가 약간 커질 수 있다. 즉 space 를 소비하여 time 을 절약하는 것이다. (space-time tradeoff)

코드는 대략 이런 식이 된다.

for ( int i = 0; i < 100; ++i )
{
    delete( i );
}

for ( int i = 0; i < 100; i += 5 )
{
    delete( i );
    delete( i + 1 );
    delete( i + 2 );
    delete( i + 3 );
    delete( i + 4 );
}

loop 본문이 간결할수록 수행시간의 대부분이 인덱스를 증가시키고 “end of loop” 의 조건을 체크하는데 소요된다. 따라서 순차적인 몇 개의 인덱스를 코드상으로 직접 inline 사용하게끔 하여 앞서 설명한 오버헤드를 줄이는 것이 Loop Unrolling 의 핵심 아이디어이다.

위의 예에서 normal 버전은 인덱스증가 및 조건체크를 100번 수행하는데 반에 Loop Unrolling 버전은 20번만 수행하게 된다. 다행히 loop 본문의 내용이 간결하기에 Loop Unrolling 최적화로 효율이 좋아지게 된다. 하지만 본문이 복잡해질 경우 효율이 오히려 나빠지기도 한다.

특정 컴파일러는 Loop Unrolling 을 자동으로 처리해주기도 한다.

장/단점

장점

• 프로그램 사이즈를 약간 증가시킴으로써 속도의 향상을 얻을 수 있다.
• branch penalty 를 최소화할 수 있다.
• loop 본문 내용이 서로간 독립적일 수 있다면 1) 이들 각각을 병렬로 처리할 수 있다.
• 컴파일 시점에 array 의 사이즈를 알 수 없어도 적절하게 처리할 수 있다.

단점

• 프로그램 코드 사이즈가 증가한다. 이건 특히나 embedded 어플리케이션에서는 치명적일 수 있다.
• 코드가 읽기 힘들어진다.
• loop 본문에 다른 함수 호출이 있다면 적용이 힘들 수 있다. Loop Unrolling 의 핵심은 인덱스 증가 및 체크조건 감소에만 있는게 아니라 cache miss 를 줄이는데도 있는데, 이를 만족하려면 내부 함수 호출이 존재하면 안된다. 따라서 loop 본문에 쓰여진 함수를 inline 으로 풀어써야 하는데 여건상 이것이 불가능할 수 있다. 프로그램의 사이즈가 너무 커지기 때문이다.
• loop 본문의 내용을 풀어쓰는 과정에서 임시 객체의 사용량이 많아진다면 register 의 사용량이 증가되고 이는 결국 퍼포먼스의 저하로 연결될 가능성이 있다.
• loop 본문에 분기문이 있다면 오히려 더 느려질 수 있다.

보면 알겠지만 loop 본문이 작고 간결해야 제대로 효과를 볼 수 있다.

테스트

두 가지 케이스를 두고 테스트를 해 보았다.

머신스펙은 Intel i5, 4.00GB ram, Windows7 64bit 이고, VS2010 에서 Release 로 컴파일하였다. Optimization: Maximize Speed(/O2)

단순 덧셈

첫번째로 단순 덧셈을 수행하는 코드로 비교

void sin_normal( float* a, float* b, int num )
{
    float req_3f = 1.0f / ( 3.0f * 2.0f * 1.0f );
    float req_5f = 1.0f / ( 5.0f * 4.0f * 3.0f * 2.0f * 1.0f );
    float req_7f = 1.0f / ( 7.0f * 6.0f * 5.0f * 4.0f * 3.0f * 2.0f * 1.0f );
 
    for ( int i = 0; i < num; ++i )
    {
        b[ i ] = a[ i ] -
            a[ i ] * a[ i ] * a[ i ] * req_3f +
            a[ i ] * a[ i ] * a[ i ] * a[ i ] * a[ i ] * req_5f -
            a[ i ] * a[ i ] * a[ i ] * a[ i ] * a[ i ] * a[ i ] * a[ i ] * req_7f;
    }
}

void sin_loop_unrolling( float* a, float* b, int num )
{
    float req_3f = 1.0f / ( 3.0f * 2.0f * 1.0f );
    float req_5f = 1.0f / ( 5.0f * 4.0f * 3.0f * 2.0f * 1.0f );
    float req_7f = 1.0f / ( 7.0f * 6.0f * 5.0f * 4.0f * 3.0f * 2.0f * 1.0f );
 
    const int vectorized_cnt = 4;
 
    int repeat = num / vectorized_cnt;
    int left = num % vectorized_cnt;
    int i = 0;
 
    while ( repeat-- > 0 )
    {
#define _LOOP_CONTENT( idx ) \
    dst[ idx ] = src[ idx ] - \
    src[ idx ] * src[ idx ] * src[ idx ] * req_3f + \
    src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * req_5f - \
    src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * src[ idx ] * req_7f
 
        _LOOP_CONTENT( i     );
        _LOOP_CONTENT( i + 1 );
        _LOOP_CONTENT( i + 2 );
        _LOOP_CONTENT( i + 3 );
 
        i += vectorized_cnt;
    }
 
    switch ( left )
    {
#define _SWITCH_MACRO( _case, idx ) case _case: _LOOP_CONTENT( idx )
 
    _SWITCH_MACRO(  3, i + 2 );
    _SWITCH_MACRO(  2, i + 1 );
    _SWITCH_MACRO(  1, i     );
    }
}

배열의 사이즈는 위와 동일하다.

normal 버전 수행시간는 평균 363.47 ns 였고

Loop Unrolling 하여 vectorized 한 수행성능 결과는 다음과 같다.

No.8 만 유일하게 성능 향상이 있었지만 거의 의미가 없는 수준이었다.

연산이 복잡해짐에 따라 cache miss 가 발생하고 이로인해 생기는 속도저하가 Loop Unrolling 으로 인해 얻는 속도이득을 모두 상쇄해 버리고 오히려 성능이 악화되는 것이다.

결론

위에 언급했다시피 Loop Unrolling 은 본문의 내용이 간략할 수록 효율이 좋아지게 된다.

본문의 내용을 여러 단계로 나눌 수 있다면 (물론 상호 의존성이 없고 독립적인 내용이어야 한다.) 각각을 나누어 적절한 vectorize 수치로 Loop Unrolling 을 따로 수행할 수도 있다.

그리고 구현을 적용하기 전에 반드시 테스트를 통해 성능향상이 있는지를 확인해야 한다.