[CA] 코드 최적화하기

프로젝트 목표 및 내용

• 임의의 프로그램을 코드 최적화를 통해 실행 시간을 단축시키는 등 효율을 증가시킨다.
• 선정한 프로그램을 대상으로 profiling 과정을 통해 다단계 program optimization을 수행하고 결과를 분석한다.
• 결과 분석(profiling)은 linux 환경에서 gprof툴을 사용하여 진행한다.
• 직접 최적화를 단계별로 진행하며 각 최적화에 따른 수치 변화의 정도를 직접 확인한다.

 

최적화 선정 프로그램

이전에 리눅스 수업에서 과제로 작성했던 Monte-Carlo 시뮬레이터를 활용하였다. 멀티 쓰레드를 이용한 프로그램으로, 쓰레드 개수와 반복 횟수를 인자값으로 받아 실행된다. 복잡도를 늘리기 위해 여기에 몇 가지 기초 정렬 알고리즘을 추가하여 프로그램을 구성하였다.

코드는 아래 저장소에 올려두었다.

GitHub - BEpaul/code-optimization

 

실행 환경 및 프로그램 실행방법

실행 환경

• Linux (Ubuntu 20.04)
• gcc 7.5.0

실행 방법

$ gcc -Wall -pg code.c -o code -lpthread
$ ./code argv[1] argv[2]
$ gprof code gmon.out > result.txt

• '-lpthread' 옵션: 멀티 쓰레드 구동을 알리기 위한 옵션
• exe 파일 실행 시 인자 값은 각각 argv[1]: 활용 쓰레드 개수, argv[2]: 반복 횟수다.
• 본 프로젝트의 결과값을 도출하는 데에는 모두 인자값을 argv[1]: 15, argv[2]: 1000000으로 하였다.

 

최적화 (Optimization)

초기 결과 확인 및 분석

bubble_sort, selection_sort, insert_sort, monte 함수 순으로 실행시간이 오래 걸린다는 것을 알 수 있고, 이 4개의 함수가 전체 함수의 약 92퍼센트의 실행시간을 차지했다. 실행 시간 비중이 큰 순서대로 최적화를 진행하는 것을 목표로 했다.

 

최적화 1단계: bubble_sort 함수 개선

코드 개선

수정 전

수정 후

버블 정렬 함수 실행 중, 만약에 배열이 이미 정방향으로 이루어져 있어 swap이 발생할 필요가 없을 경우 함수 실행을 하지 않게 하기 위해 flag 변수를 생성하여 for loop문으로 들어가는 것을 최소화 하였다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

함수 실행시간 비율에서는 큰 차이가 없었지만, self seconds 시간이 8.23에서 7.44로 내려갔으므로 상당한 개선이 이루어졌다는 것을 파악할 수 있었다.

 

최적화 2단계: selection_sort 함수 개선

코드 개선

수정 전

수정 후

정렬 함수 쪽으로는 크게 최적화할 부분을 찾지 못하여 int 타입 변수 n을 for loop문이 실행될 때마다 함수의 인자에서 받아오는 것이 아니라, 새로운 int 타입 변수 N에 저장하여 활용하였다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

selection_sort 함수에 대해 기존의 30.43%의 시간 비율에서 23.81%로 약 24% 감소하였고, 함수의 실행 시간 self seconds는 4.09에서 2.91로 약 29% 감소하는 결과를 얻을 수 있었다.

 

최적화 3단계: insert_sort 함수 개선

코드 개선

수정 전

수정 후

기존의 배열의 요소를 이동시키는 방식에서 swap을 이용한 방식을 활용하면 요소의 변경 횟수를 줄여 최적화에 도움이 될 것이라고 판단했고, 위와 같이 수정하였다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

오히려 insert_sort 함수의 로직을 배열의 요소를 이동시키는 것에서 swap으로 바꾸니 실행시간 self seconds가 1.79에서 3.67로 약 2배 증가했다. swap보다는 배열의 요소를 순차적으로 바꾸는 방법이 효율적이라는 것을 알 수 있었고, 수정 내용을 원복했다.

 

최적화 4단계: calc_square, rand_double 함수 개선

코드 개선

수정 전

수정 후

기존의 함수에서는 계산한 값을 return하기 전 새로운 변수를 정의하여 값을 저장 및 계산 후 return 해주었는데, 곧바로 계산 후 return하도록 수정하여 메모리와 레지스터를 아낄 수 있게 수정하였다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

calc_square, rand_double 함수 각각 실행시간이 0.05, 0.01에서 0.01, 0.04로 변경되었다. rand_double 함수의 경우에는 실행시간이 증가하였지만, calc_square 함수의 감소폭이 더 크고, 함수 호출횟수의 경우 9444783과 9444782에서 5790264와 5790273으로 약 40% 감소하여 최적화에 성공하였다.

 

최적화 5단계: quick_sort 함수 개선

코드 개선

수정 전

수정 후

기존의 quick_sort 함수 내부에서 while loop문의 조건식으로 arr[(L+R) / 2] 값을 pivot이라는 새로운 변수에 저장하여 이용하여 배열에 접근하는 횟수를 줄이는 방식으로 최적화를 시도해보았다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

최적화 시도 후 quick_sort 함수의 실행시간은 0.01에서 0.01로 소수점 둘째자리까지는 구분되지 않아 최적화 여부를 확인하기 어려웠으나, for loop문을 돌 때마다 값을 계산하던 방식에서 정적인 값이 주어지는 방식으로 변경하였으므로 성능이 개선되었다고 추측할 수 있다.

 

최적화 6단계: monte 함수 개선

코드 개선

수정 전

수정 후

기존의 for loop문을 돌며 포인터 변수 arg에 접근하여 *((int *)arg)의 값을 계산하던 방식에서 값을 새로운 정적 변수에 저장한 후 for loop 문에 넣어주므로 성능을 개선하고자 하였다.

 

결과 분석

코드 수정 전 profiling 결과

코드 수정 후 profiling 결과

기존의 실행시간 self seconds 0.02에서 0.01로 감소되어 성능이 개선되었다는 것을 확인할 수 있었다.

 

최적화 7단계: atoint 함수 개선

코드 개선

수정 전

수정 후

기존의 atoint 함수에서는 while문 내에 if 조건문을 배치시킴으로써 branch prediction에 대한 문제점이 야기될 수 있고, conditional 연산으로 인해 성능이 저하될 우려가 있었기에 논리연산자를 이용해 while의 조건절에서 한번에 처리될 수 있도록 하여 성능 개선을 기대하였다.

 

결과 분석

코드 수정 전 profiling 결과

코드 수정 후 profiling 결과

기존의 실행시간이 0.00으로 표기되었기에 최적화 여부는 확인할 수 없었지만, 앞서 말한 기대효과를 근거로 성능 개선을 기대하였다.

 

최적화 8단계: main 함수 개선

코드 개선

수정 전

수정 후

기존의 코드에서는 배열의 크기에 대해 상수값으로 설정해놓았고, 배열을 이용한 함수를 사용하거나 반복문에서 sizeof 함수를 이용하여 크기를 계산했기 때문에 상수 변수를 정의하고 이를 이용해 통일한다면 성능이 개선될 것이라고 예상하여 위와 같이 수정하였다.

 

결과 분석

수정 전 profiling 결과

수정 후 profiling 결과

Profiling의 결과에는 main함수가 포함되어있지 않아 성능 개선 여부를 확인하기 어렵지만, 중복하여 사용하는 값을 하나의 상수 변수로 통일함으로써 메모리 성능 향상을 기대하였다.

 

또한 모든 함수에 대해 최적화를 진행하여 최적화가 적절히 진행되었다고 판단하여 최적화 과정을 종료하였다.

 

최종 결론 및 느낀점

총 8단계의 최적화를 진행하였다. 그 결과들을 요약하자면 다음과 같다.

 

1단계: bubble_sort 함수 개선: 성공

함수를 실행하기 전, 적절한 대상인지 판별 과정을 넣으면 효율을 증대시켜 최적화할 수 있다.

 

2단계: selection_sort 함수 개선: 성공

함수의 인자값을 새로운 변수에 저장하여 활용하는 것으로 최적화를 기대할 수 있다.

 

3단계: insert_sort 함수 개선: 실패

Swap 보다는 배열 요소를 선언을 통해 이동시켜주는 것이 소모값이 작다.

 

4단계: calc_square, rand_double 함수 개선: 성공

함수 내에서 변수 사용과 계산을 효율적으로 관리하면 최적화에 기여할 수 있다.

 

5단계: quick_sort 함수 개선: 성공(예상)

반복문 내에서의 계산 프로세스 감소를 통해 최적화를 시도하였다.

 

6단계: monte 함수 개선: 성공

포인터 변수에 접근하는 횟수를 감소시킴으로써 최적화에 성공하였다.

 

7단계: atoint 함수 개선: 성공(예상)

조건문의 최소화를 통해 branch prediction 및 conditional move를 방지하여 최적화를 시도하였다.

 

8단계: main 함수 개선 (상수값 통일 이용): 성공(예상)

중복되는 값의 사용을 줄여 최적화를 시도하였다.

 

느낀점

이전에는 '코드를 이런 식으로 작성하면 효율적이다.' 라는 내용을 보고 그저 따라하는 데에 그쳤다면, 직접 최적화를 진행하고 결과도 분석해보며 실제로 작성한 코드 몇 글자의 차이, 순서의 작은 차이가 큰 결과의 차이를 만들 수 있다는 것을 겪으며 더더욱 코드를 잘 작성해야 할 필요성을 몸소 느낄 수 있었다.