Passion is like genius; a miracle.

Knuth는 그의 책 Selected Papers on Computer Science에서 array[0]을 sentinel로 사용하는 sequential scan의 개선안에 대해 이야기했습니다. (그리고 제 기억이 맞다면 TAOCP 1권에도 이 내용이 나옵니다.) sequential scan은 다음과 같이 이루어집니다.

INPUT: 검색할 값 TARGET, 검색할 대상인 array, array내 원소의 수 n
1. i = n
2. If i = 0, report “NOT FOUND” and terminate
3. If array[i] = TARGET, report i and terminate
4. Decrement i by 1 and goto 2.

문제는 2번단계가 불필요해보인단 것이죠. Knuth가 보인 해결책은 다음과 같습니다.

INPUT: 검색할 값 TARGET, 검색할 대상인 array, array내 원소의 수 n
1. array[0] = TARGET
2. i = n
3. If array[i] = TARGET, report i and terminate
4. Decrement i by 1 and goto 3.

두번째 방법에서는 array[0]에 TARGET을 저장해두었으므로, 배열의 끝을 지나쳐나가지 않게됩니다. 결국 i = 0 인가의 비교가 제외되므로 속도가 20% 향상된다고 그는 지적하였습니다. 그래서 한번 테스트를 해봤습니다. 특히 && 를 사용한 shortcut evaluation 의 영향도 고려하기 위해 standard sequential scan에서 조건의 순서를 바꿔가며 테스트해봤습니다.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    const int NUM_LOOPS = 1000000;
    const int ARRAY_SIZE = 100000;
    int array[ARRAY_SIZE];
    for (int i = 1; i < ARRAY_SIZE; ++i)
        array[i] = rand();

    int target_index = rand() % ARRAY_SIZE;
    int target = array[target_index];

    int answer_idx;

    // Use array[0] as sentinel
    array[0] = target;
    time_t start_time = time(NULL);
    for (int i = 0; i < NUM_LOOPS; ++i)
        for (answer_idx = ARRAY_SIZE - 1; array[answer_idx] != target; --answer_idx);
    time_t end_time = time(NULL);
    cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;

    // Standard sequential scan
    start_time = time(NULL);
    for (int i = 0; i < NUM_LOOPS; ++i)
        for (answer_idx = ARRAY_SIZE - 1; i >= 1 && array[answer_idx] != target; --answer_idx);
    end_time = time(NULL);
    cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;

    // Standard sequential scan #2
    start_time = time(NULL);
    for (int i = 0; i < NUM_LOOPS; ++i)
        for (answer_idx = ARRAY_SIZE - 1; array[answer_idx] != target && i >= 1; --answer_idx);
    end_time = time(NULL);
    cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;

    return EXIT_SUCCESS;
}

결과 입니다.

[mkseo@mkseo-desktop ~/tmp]$ g++ scan.cpp
[mkseo@mkseo-desktop ~/tmp]$ ./a.out
elapsed=176 target_index=58275 answer=58275
elapsed=195 target_index=58275 answer=58275
elapsed=194 target_index=58275 answer=58275

분명 19초 정도가 향상되지만 루프가 1,000,000회 수행되었음에 주목할 필요가 있습니다. (즉 거의 성능향상이 없다.) 물론 이와 같은 코딩 테크닉상의 성능향상은 중요한 최종 튜닝 포인트가 될 수 있습니다. 하지만, 다음에 보인 바와 같이 그러한 튜닝작업을 잘 짜여진 컴파일러보다 더 잘할 수 있을지는 의문입니다.

[mkseo@mkseo-desktop ~/tmp]$ g++ -O3 scan.cpp
[mkseo@mkseo-desktop ~/tmp]$ ./a.out
elapsed=65 target_index=58275 answer=58275
elapsed=68 target_index=58275 answer=58275
elapsed=57 target_index=58275 answer=58275