loop 의 비용

Computing 2009.09.24 14:25

아래와 같은 두 개의 프로그램이 있다. 어느쪽이 더 빠를까?


물론 source 2 가 빠르다.


이처럼 당연한 것을 가지고 질문을 하는 데에는 이유가 있다.

source 2 로 만든 코드보다 source 1 으로 만든 코드가 훨씬 읽기 쉬운 코드라고 가정하자. 그럴 경우 아래와 같은 취사 선택의 문제가 발생한다 :

source 1 으로 얻을 수 있는 코드의 가독성을 위해서 source 2 로 얻을 수 있는 성능을 희생할 것인가,
아니면 source 1 으로 얻을 수 있는 코드의 가독성을 희생해서라도 source 2 의 성능을 선택할 것인가?

물론 경우에 따라 해야만 하는 선택이 다르다. 그래서 각각의 경우 어떤 선택을 하는 것이 최선일지 판단하기 위해 다음과 같은 실험을 해 보았다:

우선 소스 코드를 리스팅하자.

물론 clee 님의 포스팅에 나온 소스도 가능하겠지만, 그 소스의 경우, 컴파일러가 루프 안의 내용을 최적화해버리는 데다가, 메모리 접근이 거의 전혀 없는, 오로지 register 에서만 루프 안의 동작이 발생하므로 위의 source 2 처럼 만드는 것이 훨씬 더 빠르며, 그같은 경우에는 당연히 source 2 처럼 프로그램을 만들어야 한다. clee 님이 테스트에 사용한 소스를 이용해 테스트를 하면 source 2 처럼 만드는 것이 두 배 가량 빠른데, 당연한 결과이다. 컴파일러의 최적화 등으로 인해 루프를 도는 비용이 프로그램 실행 전체 비용의 대부분을 차지하게 되어 버렸기 때문에, 루프를 두 번 돌면 당연히 두 배의 비용이 들게 된다.

그러나 나는 보다 일반적인 경우를 테스트하고자 하였기 때문에 루프 안에서 inline 시킬 수 없는 다른 object file 에 있는 함수를 호출하도록 하였다. 그리고, 소스를 약간 다듬다 보니,, Makefile 과, command line argunemt 까지 받도록 하는 프로그램이 되어 버렸는데... (직업병이다 -_-) 아무튼, 보다 일반적인 경우를 테스트하고자 하는 의도로 위에서처럼 복잡한(!) 테스트코드를 만들었다.

어디, 그럼 실험 결과를 체크해 보자 :

shawn.ygdrasil:~/work/loop$ make all
gcc -c -o a.o a.c
gcc -c -o loop.o loop.c
gcc -o a a.o loop.o
gcc -c -o b.o b.c
gcc -o b b.o loop.o
shawn.ygdrasil:~/work/loop$ time ./a > /dev/null

real    7m42.794s
user    7m34.228s
sys    0m2.209s
shawn.ygdrasil:~/work/loop$ time ./b > /dev/null

real    7m44.419s
user    7m34.048s
sys    0m2.304s

shawn.ygdrasil:~/work/loop$ time ./a --noio

real    0m10.286s
user    0m9.625s
sys    0m0.032s
shawn.ygdrasil:~/work/loop$ time ./b --noio

real    0m8.734s
user    0m8.259s
sys    0m0.026s

어라... 이것 참... io 를 사용한 경우에는 두 개의 루프를 사용한 a 가 더 좋은 성능을 보였다 -0-
물론, io 를 사용하지 않은 경우에는 예상한 대로 루프를 하나만 사용한 b 가 더 좋은 성능을 보였다.
이거.. 뭔가 잘못되었나 ... 다시 한번.

shawn.ygdrasil:~/work/loop$ time ./a > /dev/null

real    7m42.785s
user    7m34.448s
sys    0m2.473s
shawn.ygdrasil:~/work/loop$ time ./b > /dev/null

real    7m42.235s
user    7m33.867s
sys    0m2.430s

비슷한 결과치가 나왔다. 역시 io 가 들어가니 정확한 측정은 힘든 모양이다.
그래서 수회 같은 실험을 반복했지만, a 나 b 가 별반 차이 없이 비슷한 시간이 걸린 것으로 측정되었다.

--noio 옵션을 주었을 경우에는 평균적으로 b 가 1.5초 정도 빠른 성능을 보였다.

여기서 얻을 수 있는 결론은, (당연하겠지만) 루프 안에서 실행하는 루틴에 소요되는 시간이 루프 그 자체를 도는 시간 보다 훨씬 큰 경우라면, source 1 처럼 루프를 나누어서 여러번 돌게 해도 별반 차이가 없으며, 루프 자체를 도는 비용과 루프 안에서 실행되는 루틴의 비용이 큰 차이가 나지 않는 경우라면 source 2 처럼 루프를 한번만 돌게 하는 것이 더 좋다는 결론이다.

특히, 위의 분홍색 실험 결과처럼 중간에 io 가 끼어 있는 경우라면 루프를 나누든지 하나로 하든지 아무런 차이를 느끼지 못하는 결과를 얻을 수 있다.

좀 더 정량적으로 각 함수가 사용한 시간을 알아 보기 위해서 gprof 로 분석을 해 보았다. gprof 를 쓰기 위해서는 gcc 에 -pg 옵션만 추가해 주면 된다.

먼저, noio 옵션으로 실행시킨 결과이다 :

./a --noio 의 결과

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls  ns/call  ns/call  name   
 42.05      3.88     3.88 1000000000     3.88     3.88  loop1_noio
 39.21      7.49     3.62 1000000000     3.62     3.62  loop2_noio
 17.61      9.12     1.62                             main
  1.97      9.30     0.18                             loop2_io
  0.00      9.30     0.00        1     0.00     0.00  process_arg

granularity: each sample hit covers 2 byte(s) for 0.11% of 9.30 seconds
index % time    self  children    called     name
                                                 <spontaneous>
[1]     98.0    1.62    7.49                 main [1]
                3.88    0.00 1000000000/1000000000     loop1_noio [2]
                3.62    0.00 1000000000/1000000000     loop2_noio [3]
                0.00    0.00       1/1           process_arg [5]
-----------------------------------------------
                3.88    0.00 1000000000/1000000000     main [1]
[2]     41.7    3.88    0.00 1000000000         loop1_noio [2]
-----------------------------------------------
                3.62    0.00 1000000000/1000000000     main [1]
[3]     38.9    3.62    0.00 1000000000         loop2_noio [3]
-----------------------------------------------
                                                 <spontaneous>
[4]      2.0    0.18    0.00                 loop2_io [4]
-----------------------------------------------
                0.00    0.00       1/1           main [1]
[5]      0.0    0.00    0.00       1         process_arg [5]
-----------------------------------------------
20억번의 loop 에 소요된 시간은 1.62초였다. main 함수의 다른 부분은 무시해도 좋다.
전체 수행 시간에서 순수하게 loop 를 돌기위해 소요된 시간은 17.61%

./b --noio 의 결과

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls  ns/call  ns/call  name   
 46.30      4.07     4.07 1000000000     4.07     4.07  loop1_noio
 38.89      7.48     3.41 1000000000     3.41     3.41  loop2_noio
 11.60      8.50     1.02                             main
  3.22      8.78     0.28                             loop2_io
  0.00      8.78     0.00        1     0.00     0.00  process_arg

granularity: each sample hit covers 2 byte(s) for 0.11% of 8.78 seconds
index % time    self  children    called     name
                                                 <spontaneous>
[1]     96.8    1.02    7.48                 main [1]
                4.07    0.00 1000000000/1000000000     loop1_noio [2]
                3.41    0.00 1000000000/1000000000     loop2_noio [3]
                0.00    0.00       1/1           process_arg [5]
-----------------------------------------------
                4.07    0.00 1000000000/1000000000     main [1]
[2]     46.3    4.07    0.00 1000000000         loop1_noio [2]
-----------------------------------------------
                3.41    0.00 1000000000/1000000000     main [1]
[3]     38.9    3.41    0.00 1000000000         loop2_noio [3]
-----------------------------------------------
                                                 <spontaneous>
[4]      3.2    0.28    0.00                 loop2_io [4]
-----------------------------------------------
                0.00    0.00       1/1           main [1]
[5]      0.0    0.00    0.00       1         process_arg [5]
-----------------------------------------------
10억회의 loop 에 소요된 시간은 1.02 초였다. main 함수의 다른 부분은 무시해도 좋다.
전체 수행 시간에서 순수하게 loop 를 돌기위해 소요된 시간은 11.60%

루프를 두번 도는 것과 한번 도는 것의 차이는 전체 수행시간에서 불과 6% 밖에 나지 않는다. 그것도 10억번씩이나 돌린 루프인데 말이다. 게다가, 루프 안에서 실행되는 함수 또한 정말 간단한 일을 수행한다. 그런데도 각 함수(loop1_noio, loop2_noio) 의 총 수행 시간이 main 의 수행시간보다 큰 것은 오히려 함수 호출 비용이 함수 본체를 수행하는 비용보다 더 컸기 때문이 아닌가 하는 생각이 든다.

제일 처음에 제기했던 아래의 취사 선택 문제에서 :

source 1 으로 얻을 수 있는 코드의 가독성을 위해서 source 2 로 얻을 수 있는 성능을 희생할 것인가,
아니면 source 1 으로 얻을 수 있는 코드의 가독성을 희생해서라도 source 2 의 성능을 선택할 것인가?

대부분의 경우 전자를 선택하는 것이 합리적인 선택이라는 결론에 다다를 수 있다.

다시 한번 결론을 확인하면, 루프 안에서 함수 호출 없이 모든 계산이 이루어지는 루프는 당연히 한번만 루프를 돌도록 프로그램을 만들어야 하겠으나, 일반적으로 프로그램을 만들 때에는 루프 안에서 꽤나 많은 함수 호출이 있게 된다. 그럴 경우 만약 로프를 "단계별로" 두번, 세번 돌게끔 프로그램을 작성하는 편이 코드의 가독성이 좋다면, 루프를 한번만 돌게끔 해서 얻는 눈꼽만큼의 (정말 눈꼽만큼이다!!!) 성능 이득은 과감히 버리는 편이 합리적인 선택이라는 것이다.


여태껏 나는 당연히 루프를 두 번 돌면 비효율적일 것이라는 선입견을 가지고 깊이 생각해 보지도 않은 채 후자처럼 (source 2 초럼) 프로그램을 만들어 왔다. 그런데, 엊그제 문득 위와 같은 생각이 들어서 실제로 테스트를 해 보니 내가 생각한 바와 같이 루프를 두 번 도는 것이 비효율적이긴 하나 그렇게 비효율적이지도 않다는 결론이 나왔다. 나름대로 고정관념이나 선입견을 잘 피해 간다고 자신하고 있었지만, 전혀 그렇지 않았다는 사실을 깨닫고는 충격을 받았다.

tags :
Trackbacks 1 : Comments 3
  1. BlogIcon cman 2009.09.24 15:08 신고 Modify/Delete Reply

    위에서 기술한 바와 같이 루프 안에서 실행하는 루틴에 소요되는 시간이 루프 그 자체를 도는 시간 보다 훨씬 큰 경우에 대해서만 고려되어 있지만,
    실제 현실에서는 루프 안에서 조건을 검사해서 루틴에 전혀 들어가지 않거나 한두번 루틴에 들어가는 등 루프 그 자체만 동작할 경우도 있겠지요.

    머,, 암튼, 재미있는 실험이었습니다만, 아마도 나중에 또 돌아보면 이렇게 아니면 또 저렇게 생각되지 않을까 싶습니다.

    • BlogIcon Orchistro 2009.09.24 15:10 신고 Modify/Delete

      그렇습니다. 정답은 없고요, 그때그때 다르겠지요 ㅎㅎ
      상황에 맞는 방법으로 프로그램을 작성해야 할 것입니다.

  2. BlogIcon han9kin 2009.09.25 12:15 신고 Modify/Delete Reply

    저는 아무리 성능이 빨라도 가독성이 현저히 떨어지면 쓸모없다고 생각합니다.
    소스코드 가독성은 소프트웨어의 지속가능성을 결정지을 수 있는 아주 중요한 요소 중 하나라고 봐집니다만,
    성능은 한순간 잠깐의 영광일 뿐이죠.
    설마 회사에서 상용 소프트웨어를 개발하면서 지속가능성을 포기하시렵니까? 요즘같이 변화가 빠른 세상에~
    ㅋㅋ

    컴퓨터를 위한 소프트웨어 말고 사람을 위한 소프트웨어를 만들어주세요~

Write a comment