최적화와 수학

애자일 블로그에 올라온 프로그래머와 수학을 읽고 전에 경험했던 것을 짧게 써 봅니다.

프로그램을 하다보면, 뭔가 하고 있는 것이 비효율적인 것 같은 느낌이 약간은 들지만, 최적화가 충분히 되어있다고 느낄 때가 많습니다. 더 속도가 필요하다면, 더 빠른 언어와 여러 트릭을 동원해서 빠르게 하곤 합니다. 극단적인 경우를 예를 들어서, 항상 예제로 많이 쓰이는 피보나치 수열을 한 번 보겠습니다. 실제 프로그래밍이 피보나치 수열처럼 간단한 루틴일 리도 없고 그렇게 반복적으로 호출될 일은 없겠지만, 그래도 극단적인 예를 보면, 그 특징을 다른 곳에서 활용할 수 있을테니까요~

일반적으로 피보나치 수열 n번째를 구하는 루틴은 파이썬으로 이렇게 합니다.

만약 피보나치 수열의 200005번째 수 “주변”의 것이 정확할 필요는 없고 대충의 값이 필요해서 호출한다면, 제 컴퓨터에서는 대충 2.82초 정도가 걸립니다. 그런데, 이런 루틴이 적어도 초당 100번 이상은 호출되어야 하는 상황이 왔다고 치면 보통 이런 대안을 생각합니다.

• 파이썬이 느리니까 C로 하자!
• a, b는 터플이 묶였다가 풀리면서 메모리 할당을 하니까 따로 따로 하게 2줄로 분리해 보자.
• 내가 요새 어셈블리에 재미를 붙였는데, 어셈블리로 하면 레지스터도 충분히 활용하고 빠르지 않을까?
• 루프를 매번 돌리는 것은 비효율적이니까, 16번에 한번씩 돌게 풀어쓰면(unroll) 빨라질거야!

자.. 그런데, C로 하면 과연 얼마나 빨라질까요. 200005번째 피보나치 수는 64비트로 커버가 안 되는 수이기 때문에, 빅넘버 라이브러리를 쓰다보면 결국 시간이 제법 걸리고, 속도도 생각보다는 별로 빠르지 않습니다. 어셈블리로 하면? 과연 오늘 퇴근 할 수 있을까요..

여기서 경험많은 프로그래머는 알고리즘을 휙 보고, 이런 코드로 최적화를 합니다.

200005번째 수를 주는데 걸리는 시간이 눈깜짝할 새 입니다. 아이 그런데, 또 주변의 수가 더 필요해졌습니다. 그래서, 좀 더 많은 범위에서 캐시를 할 수 있게 데코레이터도 쓰고 해서 멋있는 캐시를 넣어서 정말 더 빨라졌습니다. 그랬더니 이제는 메모리를 너무 많이 먹습니다! 결국에는 캐시 관리 기능에 메모리가 얼마인지 보게도 만들어서, 이 프로그래머는 주변의 존경을 받습니다.

그러나, 이때 옆에서 보던 한 수학자가 종이에 뭘 끄적거리더니, 이렇게 하면 안 되겠냐고 조심스럽게 코드를 한손가락으로 톡톡 쳐줍니다.

아! 아.. 프로그래머는 뭔가 속은 기분이 들었습니다. 그래서 유심히 보니까, 실행해 보면 정확한 값이 나오지는 않았습니다. 그래서 따져보고 싶었지만 필요한 것은 그냥 대충 화면 좌표를 잡는 것이라 유효숫자 6개 정도만 하면 넘칠정도라는 사실에 슬펐습니다.

컴퓨터 전공 학생들은 대부분 4학년 되면, 적분기호를 까먹을 정도로 수학을 쓸 일이 없습니다. 그런데, 간단한 프로그래밍의 수준을 지나면 생각보다 훨씬 수학을 활용할 수 있는 일이 늘어나는 것 같습니다. 물론 굳이 수학 뿐만 아니라, 넓게 봐서 논리의 흐름과 여러가지 알고리즘적인 방법, 패턴 등이 있겠죠.

모니터 가까이에서 코드를 보고 있으면, 앞에서 본 C로 하면 무조건 제일 빠를거야!, 터플 때문에 괜히 메모리 할당하는 것을 줄이면 정말 빠를거야! 라는 생각을 늘 하게 되기에 마련이지만, 가끔은 좀 멀리서 최적화에 조바심을 내지 않으면서 코드를 볼 기회도 가져봄 직 할 것 같습니다.

“Real efficiency comes from elegant solutions, not optimized programs.
Optimization is always just a few correctness-preserving transformations
away.” – Jonathan Sobel, 《Is Scheme Faster than C?》에서

붙임: 중간에 든 예가 좀 과장이 심해서 죄송 -ㅇ-; 글의 원래의도가 피보나치 수열을 최적화하자는 것은 아닙니다. ^^;