재귀호출 vs 루프문

재귀호출을하나 루프로 바꾸나 요새 cpu에선 성능 차이 별로 안난다고 생각했었다.
틀렸다. 그렇지 않다. 재귀호출이 훨씬 느리다.

재귀호출을 해도 전체적으로 보면 크게 성능이 떨어지지 않는거지 루프문만큼 빠른것은 아니다.

예의 8x8x8복셀에서 한 면에서 출발해서 x,y,z축에 대해 반대편 면까지 뚫린 구멍이 있는지 탐색하는 코드가 있다.
어떤 복셀 오브젝트의 인접한 오브젝트에 의해 가려질 수 있는가를 체크하기 위한 코드이다. 나는 이걸 터널찾기라 부른다.
그런데 이 터널찾기 코드의 성능에 만족할만큼 나오지 않았다.

오브젝트를 편집할때마다 터널찾기를 수행해서 주변 오브젝트가 가려지는지를 갱신해야한다.
또한 클라이언트가 서버에 접속했을때 대량으로 오브젝트 리스트를 받아오고 섹터간 이동을 할때마다 또 다수의 오브젝트 리스트를 받아온다. 터널찾기 코드도 수신한 오브젝트 개수만큼 호출해줘야하는데 오브젝트 개수가 많으면 성능에 영향을 많이 준다.
그래서 이벤트 발생시만 서버에서 오브젝트 각각에 대해 계산해두고 패킷으로 전달받은 클라이언트는 별도 처리를 하지 않게 하려고 했다.
하지만 이렇게 하면 일단 동기화 코드가 더 복잡해진다. 그리고 서버에서의 불필요한 성능하락이 예상된다.

가장 간단한 해결방법 터널찾기 코드를 빠르게 만드는 것이다.
이 코드를 처음 작성할때는 생각하기 편하다는 이유로 재귀호출을 사용해서 작성했다. 이런저런 최적화를 해서 성능을 올리긴 했지만 여전히 만족스러운 정도는 아니었다.
남은건 재귀호출을 루프문으로 바꾸는 방법 뿐이었다.
그래서 이걸 재귀호출에서 stack+루프문으로 바꿨다.

결과는…

debug build에서
재귀호출 : 16970 clock
루프문 : 14992 clock

release build에서
재귀호출 : 13010 clock
루프문 : 1374 clock

debug빌드에서도 10-20%루프문이 빠르고 release빌드에선 10배 빠르다.

재귀호출 가능하면 피하는 편이었는데 이건 생각하기가 좀 복잡해서 그대로 재귀호출로 놔둔것이 실수였다.
진작에 재귀호출을 루프로 바꿨으면 성능 문제로 고민할 필요가 없었다.

같은 알고리즘이라도 어떻게 코딩하느냐에 따라 성능차이 많이 난다.


재귀호출 vs 루프문”에 대한 답글 1개

  1. 글 읽다 궁금한게 생겨서 질문해 봅니다.
    재귀함수를 루프문으로 바꿀때 Debug 빌드가 Release보다 성능차이가 많이 나는 이유가 뭔가요?

    좋아요

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중