제 9장은, 코드 튜닝에 관한 부분입니다. 이 책에 실린 내용은 전반적으로 까다롭습니다만, (물론 제가 머리가 나빠서 그럴지도 모릅니다) 특히 9장에 실린 내용은 더 까다로운 편입니다. 하지만 그 까다로움을 넘어서면, 이거다 싶어서 무릎을 치게 되는 일이 생기죠.

9장을 보면 이진 탐색이라는 문제에 대한 초기 해법을 어떻게 가다듬어 보다 좋은 성능을 내는 알고리즘으로 변모시킬 수 있는 지가 나옵니다. 저정도면 나도 할 수 있겠다 싶은 대목도 있습니다만, 그렇지 않은 부분도 많습니다. 아래의 알고리즘을 한 번 보죠. 179페이지부터 180페이지에 걸쳐 나오는 알고리즘입니다. 이진 탐색을 할 대상 수 집합의 크기가 1000이라는 점을 이용하는 코드입니다. 같은 수가 여러 개 있는 상황을 허용하고, 그 중 첫 번째 수의 위치를 찾는 것을 목표로 하고 있기 때문에, 흔히 보던 이진 탐색 알고리즘과는 좀 다를 수 있습니다.

i = 512
l = -1

if x[511] < t
    l = 1000 - 512
while i != 1
    /* invariant : x[l] < t && x[l+i] >= t && i = 2^j */
   
nexti = i / 2
    if x[l+nexti] < t
        l = l + nexti
        i = nexti
    else
        i = nexti
/* assert i == 1 && x[l] < t && x[l+i] >= t */
p = l + 1
if p > 1000 || x[p] != t
    p = -1

여기서 저자는 빨간 색으로 표시된 부분의 코드를 똑똑한 컴파일러라면 어떻게 최적화할지를 묻고, 그에 대한 답을 보여줍니다. (컴파일러가 최적화하는 순서를 보이지는 않습니다.) 사람이라면 어떻게 최적화할까요?

(1)
nexti = i / 2
if [l + nexti] < t
    l = l + nexti
i = nexti

i = nexti를 하는 부분은 if 블럭과 else 블럭에 공통적이니까 굳이 if-else 블럭 안에 둘 필요는 없습니다. 밖으로 끄집어 내면 되죠.

(2)
i = i / 2
if [l + i] < t
    l = l + i

if 블럭 안에서 nexti에 대해 side-effect를 발생시키는 부분이 없으므로, i에 nexti를 대입하는 부분은 if 문 위쪽으로 끌어올릴 수 있습니다.

이 정도는 뭐 나도 쉽게 할 수 있겠다, 싶습니다만, 막상 코드를 작성하다 보면 그렇지 않은 경우도 많습니다. 알고리즘을 차근차근 뜯어볼 시간적 여유가 주어지지 않는 경우도 많거든요. 이 책이 갖는 강점은, 독자에게 그런 류의 사고를 할 수 있는 드문 기회를 제공한다는 점입니다.

이 코드의 마지막 버전은 더 재미있습니다. 저자는 "심장이 약한 사람은 보지 말 것"을 권하고 있기도 합니다. 이 코드는, 루프 선체를 펼쳐서 루프를 도는 데 드는 오버헤드와, i를 2로 나누는 연산을 제거해버렸습니다.

l = -1
if ( x[511] < t ) l = 1000 - 512
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+256] < t ) l += 256
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+128] < t ) l += 128
if ( x[l+64] < t ) l += 64
if ( x[l+32] < t ) l += 32
if ( x[l+16] < t ) l += 16
if ( x[l+8] < t ) l += 8
if ( x[l+4] < t ) l += 4
if ( x[l+2] < t ) l += 2
    /* assert x[l] < t && x[l+2] >= t */
if ( x[l+1] < t ) l += 1
    /* assert x[l] < t && x[l+1] >= t */

p = l + 1
if p > 1000 || x[p] != t
    p = -1

이런 코드 튜닝은, 코드 튜닝이 어떤 일을 할 수 있는지를 보여주는 '극한의' 사례라고 할 만 합니다. 이렇게 튜닝된 코드는 원래 버전의 이진 탐색에 비해 36% 향상된 속도를 보여준다고 합니다.

이 정도로 코드를 다듬는 것이 항상 가능하지는 않고, 그럴 필요가 없을 때도 있습니다만, 속도가 문제가 되는 상황은 생각보다 자주 발생합니다. 그럴 때에는 가능한 옵션을 찾아 이리저리 프로파일링을 해 보게 마련인데요. 프로파일링을 하면 병목구간을 찾아낼 수는 있는데, 발견된 병목구간을 어떻게 해소할 지는 분명하지 않은 경우가 많습니다. 병목구간을 해소하는 방법으로 많은 경우 구조적인 해결방법(architectural solution)을 최우선으로 고려하게 되는데, 그런 해결 방법은 의외로 높은 비용을 요구할 때도 있죠.

그러므로 정말 속도가 문제가 된다면, 이런 해법이라도 모색해보는 편이 좋겠습니다. 물론, 이런 코드 튜닝은 굉장히 많은 경험을 요구합니다.

가령, 이 9장의 8번 연습문제를 보면, 추가의 메모리를 사용해서 삼각함수 계산비용을 낮추는 사례가 소개되어 있습니다. 이 사례는 "본 프로그램은, 5도 배수의 인자에 대해서만 삼각함수 계산을 요구한다"는 단순한 사실에서 출발해서, "테이블 형태의 메모리 테이블을 구성하고, 그 테이블을 조회하는 함수"를 구현하여, 삼각함수 계산 비용을 낮추었습니다. 즉, "알고리즘의 실행 환경"을 면밀히 분석한 다음, "그 실행 환경이 갖는 특이성"을 적극적으로 이용하여 성능을 개선한 것입니다. 이런 일이 가능하려면, 프로파일링을 공격적으로 하는 것 뿐 아니라, 사실(fact)을 적극적으로 공략하는 마음가짐이 중요합니다.

수학적인 사고도 요구될 때가 있습니다. 가령 연습문제 12의 경우,

y_{0} = a_{n}
y_{1} = x * a_{n} + a_{n-1}
        = x * y_{0} + a_{n-1}
...
y_{m} = x * y_{m-1} + a_{n-m}

을 유도할 수 있으면 2n이 아닌 n짜리 알고리즘을 만들어 실행시간을 반으로 줄일 수 있습니다. 대부분의 프로그래머는 이정도는 하실 수 있겠습니다만, 저처럼 머리가 나빠서 앉은 자리에서 생각을 해 낼 수가 없다면 실행시간의 반을 까먹는 일이 생기게 되겠죠.

그러니 결국 좋은 알고리즘을 위해서는 Fact에서 출발해 Context에 대한 Assumption을 만들고, 거기에 Experience를 섞어서 Solution을 찾아야 하는 셈입니다. 약자를 다 모으면 FACES로군요. ㅋㅋ 세상 문제들의 다양한 측면들(Faces)을 두루 볼 수 있어야 그 문제에 대한 좋은 알고리즘이 나온다는 뻔한 결론이랄까요.

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^