loop 의 비용
Computing 2009. 9. 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 초럼) 프로그램을 만들어 왔다. 그런데, 엊그제 문득 위와 같은 생각이 들어서 실제로 테스트를 해 보니 내가 생각한 바와 같이 루프를 두 번 도는 것이 비효율적이긴 하나 그렇게 비효율적이지도 않다는 결론이 나왔다. 나름대로 고정관념이나 선입견을 잘 피해 간다고 자신하고 있었지만, 전혀 그렇지 않았다는 사실을 깨닫고는 충격을 받았다.