계산기 프로그램에서 

-info 를 치면 성능을 평가한다.

malloc 함수가 얼마나 호출 되었는가 (동적할당 얼마나 쳐했나)

eval 함수가 얼마나 호출되었는가 (평가함수가 얼마나 재귀를 돌았나)

방금 호출한 함수가 어느시간에 계산을 했는가


특히 내가 성능 향상을 위해서 

가장 참고를 했던 함수가 바로 PI? 함수이다.

트리가 한쪽으로만 계속 가지를 뻗는데 

함수가 꽤 큰 트리이다.

((i PI/2 limit) def (
(((4 * (i * i)) / 
(((2 * i) - 1) * ((2 * i) + 1))) * ((i + 1) PI/2 limit)) 
if(i < limit) 
1));

if가 함수몸통의 최상의 루트인데 이걸 기준으로 왼쪽가지 트리는 굉장히 큰데

오른쪽은 그냥 1... 작다.

그리고 큰쪽으로 계속 재귀호출 되기 때문에

성능 테스트하기에 적당했다.


PI? 함수는 내부적으로 8100번 재귀호출 된뒤 2를 곱해서 나온 값이다.

하지만 최적화? 작업을 하기전에는 15번 호출까지는 되는데 16번 호출에 

뻗어버렸다. 무려 400배 넘게 호출횟수가 지금과 차이가 났다.


아직도 함수 8100번 호출에 malloc이나 eval 함수가 20만번 씩이나 호출되는거 보면

이 계산기는 메모리 잡아먹는 괴물인것을 알수 있다.



SCIP에서 공부했던 개념이였는데 이런것이 있었다.

재귀에 대해서 설명하는데


1.트리? 를 있는대로 전부 펼친후에 평가하기 (lazy eval 맞나?)

2.즉시 평가하기.


이걸 만들어보면서 이해가 갔다. 

내가 만든놈은 트리를 있는대로 다 펼치고 난후에 

그때부터 평가를 시도한다. 


최적화 이전에는

재귀호출로 파라미터로 들어가는 값들..

내가 파라미터로 트리 자체를 넣기 때문에

만일

((x sum y) def ((x + ((x - 1) sum y)) if(x > 0) 0));

이 함수를 선언했을때


x 가 10 이라면

첫번째 sum 호출에서 10 값을 넣을때는 파라미터가 10 이지만

두번째 sum 호출에서는 (10 - 1) 이라는 파라미터가 들어간다.. 값이 아니라 수식트리로 들어간다.

세번째는  ((10 - 1) - 1) 파라미터...

....
열번째는 (((((((((10 - 1) - 1) - 1) - 1) - 1) - 1) - 1) - 1) - 1) 이라는 수식이 파라미터로 들어간다.

나중가면 파라미터 하나가 엄청난 크기로 변해버린다.

이게 전부 동적할당 되어있는셈이다...


괜히 16번 호출만에 뻗어버리는것이 아니었다...

이 문제는

파라미터로 들어가야할 값은 어차피 정해져 있으므로 굳이 수식트리 형태로 들어가지 않아도 된다.

그래서 함수 호출시에 미리 파라미터를 계산한뒤에 호출하게 하니

50배의 호출횟수가 증가했다.


그리고 eval 함수내에서 쓰이는 지역변수가 은근히 많았는데

eval도 재귀 호출 하므로

계속 스택에 쌓여서 부담이 되는것이다.


지역변수를 전부 전역변수로 빼고 싶었지만

꼭 스택에 쌓아야할 값이 있다 (재귀시  호출 상태에서 평가된 값)

그리고 이 값을 넣기 위해서 안의 내용이 마구 바껴도 상관없는 더블포인터변수하나를 선언했다.

그러면 한 함수가 쓰는 스택에서 변수가 쓰는 공간이 double형과 더블포인터형  (8 + 4)  12바이트 정도 되겠다.

예전에는 값이 고정되어야 하는 double변수  값이 변해도되는 double변수.. 그외 나머지 지역변수들..

로 이루어졌었는데  이걸 최적화 하고 나니 약 3~4배 정도 호출횟수가 늘어났다.


그리고 if문을 평가한 다음에는 이미 진행방향이 결정되어  ifs 필드의 조건식이나 다른쪽 트리 는 필요없게 된다.

그래서 지워버린다


이런식으로 최적화를 실시하여 그나마 이정도의 성능을 내게 되었는데

너무 코드가 복잡해져 이제 내가 건드리지도 못하겟다.




Posted by 멍충한아싸

댓글을 달아 주세요