[SP] Optimizing a program with a hardware independent perspective

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

몇 번 말했던 것 같다. 요즘은 정말 포스팅 하는 재미에 산다. 으하하 오늘도 재밌는 내용을 가져왔으니 독자분께서는(계...계시나요?) 잘 읽어주세요.

지금 내가 공부하고 있는 책은 Computer Systems : A Programmer's Perspective이다. 프로그래머  관점에서의 컴퓨터 시스템이다. 그렇다. 오늘은 프로그램을 돌려볼 것이다. 예전에 교수님께서 최적화해보라고 내주셨던 과제 프로그램도 있지만 그것보다는 책에 있는 내용을 가지고 예를 들며 설명해보려고 한다. 

이번 포스팅에서 아래의 프로그램을 최대한 개선해보고자 한다.

위 프로그램을 따로 설명하지는 않겠다. 다들 C코드는 어느 정도 이해할 수 있을 것이라고 가정하고 가자. 아래의 코드를 참고하여 알아서 이해해보도록 하자.

이 프로그램을 실행하면 대략 100000us 정도의 시간이 소요된다. 상당히 느리다. 

우리가 개선할 부분은 바로 위에 있는 combine이라는 함수이다. 우선 필요없는 함수 호출을 줄여보자. 가장 눈에 띄는 것은 for loop에서의 vec_length(v)이다. 이는 v라는 구조체의 길이를 리턴해주는 함수로 항상 같은 값을 리턴하게 되어있다. 앞에서 procedure call에서 아주 자세하게 설명했듯이 함수를 호출하는 것은 CPU입장에서 굉장히 많은 시간을 소모하는 일이다. 따라서 없애는 것이 현명하다. 어짜피 같은 값을 리턴하므로 아래와 같이 vec_length(v)값을 length라는 integer 변수에 뽑아내자.

이와 같이 개선하면 100000us가 80000us정도로 개선이 된다. 대략 20%정도 개선된 것이다. 함수 호출을 줄인 효과이다. 위의 코드와 같이 length라는 변수에 접어넣는다면 assembly code에서는 그냥 단순히 register에 값을 집어넣고 접근하면 되기 때문에 빠른 접근이 가능해진다.

그 다음에 개선할 부분은 다음과 같다. for loop 안의 get_vec_element(v, i, &val) 함수이다. 여기에서도 쓸데 없이 계속 함수를 호출하고 있다. 어떻게 이 함수를 안 쓰고 할 수 있냐고? 배열이다. 저 함수는 v라는 구조체에 선언되어있는 v->data의 i번째 값을 val이라는 변수에 저장하라는 함수이다. 이것을 위해서 함수를 호출해야 하고 함수 내에서는 memory access를 도대체 몇번을 해야하는가? 그것이 비효율적이라는 것이다. 따라서, 우리는 새로운 함수 하나를 선언하겠다.

이 함수는 v라는 구조체의 data의 주소를 return하는 함수가 되겠다. 그 값이 무엇인가? 바로 v->data 의 시작 주소이다. 이 부분에 대해서 내가 따로 블로깅을 해두진 않았지만, v->data[i]의 값을 접근하기 위해서는 v->data의 시작 주소를 알고 그 값을 기준으로 한 칸씩 이동하는 것이다. 아래와 같다. 

이와 같이 v->data의 시작 주소를 알았으니 이 값을 가지고 마음껏 memory 연산을 통해 값을 접근하면 된다. 아직 memory 접근을 해야하지만 적어도 함수 호출은 없앴다. 개선된 combine함수는 아래와 같다.

get_vec_start(v) 함수로 얻은 data 값을 가지고 data[i]와 같이 마음껏 접근할 수 있다. 이렇게 해주면 35000us와 같이 절반 이상의 성능 개선을 볼 수 있다. 오 엄청난 개선이다. 여기서 또 어떻게 개선할까? for 문 안을 봐서 아직 한 번도 손대지 않은 메모리 접근을 찾아보자. *dest이다. *dest로 되어있기 때문에 매번 loop를 돌 때마다 메모리 연산을 해줘야 하는데, 이 시간이 또 우리는 싫다는 것이다. *dest 처음 값을 변수에 저장해놓자. 아래의 코드를 보자. 

우와 엄청난 개선이 이루어질 것 같다. 그런데 막상 프로그램을 실행시켜보면 35000us로 성능 개선이 보이지 않았다. 학교에서 배웠던 것을 생각해보면 여기에서 60%정도의 성능개선이 나타난다고 했다. 그런데 왜 나타나지 않을까?

이럴 때를 위해서 우리는 어셈블리어를 공부했다. (이유는 무엇이든 좋다.) 바로 위의 코드를 combine4로 하고 그 위에 있는 코드를 combine3라고 하고 아래의 그림을 봐보자.

combine3에 대한 어셈블리코드는 아래와 같다.

여기서 보면 L9 영역이 바로 for문 안의 부분이다. 메모리 연산 개수를 보면 8개이다. 10개 중에 8개가 메모리 연산이다. 조금 더 구체적으로 볼까? *dest 값을 얻기 위해 어떤 instruction을 수행했는지 살펴보자. 

movl        12(%ebp), %eax

movl        (%eax), %edx

이 두 명령어가 *dest를 얻는 부분으로 매 loop마다 반복된다. 그리고 data[i]를 얻는 부분은 아래와 같다.

movl        -12(%ebp), %eax

sall         $2, %eax

addl        -20(%ebp), %eax

movl        (%eax), %eax

위의 네 줄이 data[i]를 얻는 과정이다 그렇게 해서 얻어진 *dest 값을 갖는 %edx값과 data[i] 값을 갖는 %eax 값을 imull instruction으로 곱하는 것이다.

imull        %eax, %edx

위와 같이 곱한다. 자 대충 combine3에 대한 어셈블리 코드가 이해가 되는가? 이제는 combine4에 대한 어셈블리 코드를 보자.

마찬가지로 .L9이 for 문 안쪽의 부분이다. 한번 분석해보자. 우선 acc값을 어떻게 얻는가?

movl        -16(%ebp), %edx

아까 combine3에서는 두 개의 메모리 계산을 했던 것에 반해 이번에는 한 개의 메모리 연산으로 acc값을 얻어 올 수 있었다. data[i] 값은 어떻게 얻는지 살펴보자. 사실 이 부분은 별로 다를 것이 없다.

movl        -12(%ebp), %eax

sall         $2, %eax

addl        -24(%ebp), %eax

movl        (%eax), %eax

%ebp에 대한 offset이 조금 바뀌긴 했지만 같다고 보면 된다. 자 이제 대충 왜 효율 개선이 없었는지 알겠지? 어셈블리언어, 컴퓨터가 이해하는 언어 입장에서는 바뀐게 거의 없기 때문이다. 사람이 머리 속으로 이해하기에는 편하겠지. 하지만 명령어를 실행하는 것은 사람이 아니라 컴퓨터라는 점을 명심하자.

지금까지 한 일을 한 마디로 정리해보자. 바로 메모리 연산을 줄이고 함수 호출을 줄임으로서 프로그램 성능의 개선을 보는 것이다. 이러한 방식으로 성능을 개선하는 것은 하드웨어에 독립적으로(hardware independent) 개선하는 것이다. 즉, 어떠한 하드웨어 환경에서도 개선 효과를 볼 수 있는 general 한 개선 방법이다. 다음 포스팅에서는 hardware dependent 한 성능 개선을 찾아보자.