Default operators, Math functions, Conditional statement - Performance comparison

• Environment
• CPU: i7-7700HQ
• Memory: 16GB

• Result

• Source code

Pointer Operation

Valid pointer operations are assignment of pointers of the same type.

• Possible Pointer Operation

1. adding or subtracting a pointer and an integer

2. subtracting or comparing two pointers to members of the same array

3. assigning or comparing to zero

All other pointer arithmetic is illegal except for 1~3.

• Impossible Pointer Operation

1. add two pointers,

2. to multiply or divide or shift or mask

3. to add float or double

4. to assign a pointer of one type to a pointer of another type without a cast

※ except for void *

• Pointer Operation Result Example

x86 system is 4byte pointer

x64 system is 8byte pointer

The example is x86 system. (but acutal system is x64 system)

integer 1 = 0x4

p2 = p1 + 4;

integer 4 is address 16(0xf) by pointer operation

p3 = p2 - p1

p3 is 4 by pointer operation but not 16(0xf)

Flexibly convert string input to integer array

• EOF(End Of File input method)

Windows : ^Z (Ctrl + Z)
Unix/Linux : ^D (Ctrl +D)



reference) K&R2 Book

Performance Optimization (성능 최적화)

• Performance Optimization 

 성능 최적화를 하기 위해서는 이전 프로그램보다 적은 메모리를 사용하고 실행 속도가 빨라져야한다. 즉, 해당 프로그램이 이전의 프로그램보다 성능을 최적화한 것이다.

• Example Source ( before Optimization )

http://kys910524.blogspot.kr/2016/05/radix-sort-vs-qsort-function-limited.html






















이전의 RadixSort는 제한적인 입력에 대해서 qsort보다 약 4배 빠른 것을 알 수 있다.

• Optimization Contents

1) 비교 숫자를 기계어 해석에 맞게 10진수가 아닌 16진수로

 위 소스는 기수 정렬(Radix Sort)와 qsort 함수의 성능 비교의 소스코드와 그 결과이다. 여기서 기수 정렬은 제한적인 자리수와 10진수 정수를 통한 일반적인 방법으로 구현되었다. qsort함수보다 성능이 3~4배 가량 빨라진 것을 알 수 있다. 여기서 이 소스를 여러가지 방법으로 성능 최적화를 시킨다면, 이보다 얼마나 더 개선될 수 있는지 알아 보겠다. 10진수를 기준으로 비교하였지만, 실제 컴퓨터 CPU는 2진수의 기계어를 해석하기 때문에, radix를 2진수, 8진수 16진수 같이 2진수로 묶이는 숫자로 비교 할 것이다. 여기서는 우리가 프로그래밍할 때, 보통 16진수 단위로 보기 떄문에 16진수를 radix로 사용하겠다. 이로 인하여 성능 최적화를 위한 비트연산(bitwsie operation)을 사용할 수 있게 되었다.

사용된 비트 연산 : |(OR), &(AND), <<(LEFT-SHIFT), >>(RIGHT-SHIFT), ^(XOR)

2) getMaxValue() function

 이 함수는 기수 정렬을 위해 최대 자리수를 구하기 위한 최댓값을 얻는 함수이다.

- before

  

- after

 이전 함수는 정렬할 배열 arr에서 최댓값을 찾는 함수였다. 각각의 하나의 값을 비교하기 위해 조건문과 대입문이 필요하다. 하지만 개선된 함수는 모든 arr배열의 값들은 | 비트연산을 하였다. 조건문도 필요 없으며 새로운 값을 대입하는 것이 아닌 | 비트연산 후 대입이기에 이전 함수보다 효율적이다. 

예를 들면

10011

10110

11011

을 모두 | 연산을 한다면 11111이 된다. 가장 큰 11011이 모두 1로 꽉찬 11111보다 절대 커질 수 없으므로, 모든 arr배열의 값들을 | 연산하면 가장 큰 숫자를 얻을 수 있다.

3) countSort() function

 이 함수는 매개변수로 전달된 자리수를 통해 해당 자리수의 정렬이 수행되는 함수이다.

- before

- after

 16진수로 되어 있기 때문에 몫을 구하는 과정이 / exp에서 >> exp의 RIGHT-SHIFT 비트연산으로 바뀌었다. 나누는 연산는 +,-보다 많은 시간이 필요한 작업이기 때문에, 이 과정을 비트연산으로 처리함으로써 효율적인 연산 처리가 가능하다. 비트연산 << 4는 / 16과 같고 비트연산 << 8은 / 256과 같다.

 또한 나머지를 구하는 과정을 %R(10)진수 대신에 비트연산 & 0xF를 사용하였다. 0xF는 15이기 때문에 0xF와 원래 숫자를 &연산 할 경우, 0~15까지의 숫자만 나올 수 있으므로 두 과정은 같은 연산이다. 나머지(%) 연산도 나누기(/) 연산 못지 않게 연산 과정이 많이 필요한 처리이므로, 이 과정을 비트 연산으로 처리하면 효율적인 연산 처리가 가능하다.

int tmp[N];

for (i = 0; i < n; i++)

 arr[i] = tmp[i];

또한 위의 소스코드 두 구문이 사라졌다. 이 이유는 radixSort 함수를 설명하면서 설명하겠다.

4) radixSort() function

 이 함수는 arr배열의 최댓값을 getMaxValue함수를 통해서 얻고 그 최댓값을 통해 1자리부터 최댓값의 자리수까지 countSort함수를 호출하는 함수이다. 

- before

- after

 countSort함수에서 지역변수 tmp[N]가 없어진 이유는 이전 함수에 만약 int형 데이터 100만개의 데이터를 정렬하려고 한다면, tmp배열이 지역변수로 선언되려고 하면 스택 오버플로우가 발생할 것이다. Windows의 스택 기본 할당은 1MB이며 VisualStudio의 스택 기본 할당도 1MB이다. 따라서 int형(4byte)기준으로 최대 25만개의 데이터만 스택에 배열로 선언할 수 있다. 따라서 radixSort함수에서 스택 공간 대신 힙공간을 이용한다. tmp배열을 동적으로 선언하여 countSort함수에 해당 힙공간을 가리키는 tmp를 전달해주면 된다.  이러한 방법을 통해 해당 소스는 확장성(scalability)가 생기게 되며 불필요한 지역변수 선언이 사라짐으로써 함수 호출과정에서 이전보다 더 적은 메모리를 사용하게 된다.

for (i = 0; i < n; i++)

 arr[i] = tmp[i];

 countSort함수의 위 문장은 각 자리수마다 radix기준으로 정렬된 결과가 tmp배열에 저장된다. 따라서 다시 원래의 arr배열에 대입해줘야 하기 떄문에 위의 문장이 필요하였다. tmp배열을 arr의 배열에 다시 대입하는 과정은 배열의 크기가 커질수록 그 시간 또한 증가한다. 따라서 arr, tmp, arr, tmp 순서로 자리수 정렬 결과를 번갈아 넣어주면 위의 복사 과정을 하지 않아도 된다. 복사하는 과정이 없어졌기 이 전의 함수보다 효율적이다.

int* pages[] = { arr, tmp };

 위의 소스 코드를 통해 arr, tmp 순서로 번갈아 호출 될 수 있게, 두 배열의 주소값을 배열로 저장하였다.

for (int exp = 0; (m >> exp) > 0; exp += 4, page_index ^= 1)

countSort(pages[page_index], pages[page_index ^ 1], n, exp);

 exp는 16진수이기에 x16씩 자리수를 계산해야하기 때문에 RIGHT SHIFT 연산을 위해서 4씩 증가하게 바꾼다.

 page_index는 0으로 초기화 되어있다. 해당 for문을 한번 돌 때 마다, ^비트연산을 통해 page_index ^= 1 가 사용되기 때문에 0, 1, 0, 1과 같은 값을 토글 효과를 얻을 수 있다.

1 XOR 0 = 1

0 XOR 0 = 0

0 XOR 0 = 1

...

따라서 countSort함수는 

countSort(pages[0], pages[1])

countSort(pages[1], pages[0])을 번갈아 가면서 호출하기 때문에 countSort의 정렬결과가 tmp에 저장된다면 해당 tmp는 다음 countSort함수의 arr이 되고 arr은 tmp가 된다. 

if (page_index & 1) {

int *_tmp = tmp;

tmp = arr;

arr = tmp;

}

위의 if문은 정렬된 결과를 출력할 때, arr배열을 사용하기 때문에 마지막 countSort함수의 결과가 tmp에 저장되어있다면, tmp와 arr를 서로 swap한다.

4) main() function

- before

- after

main문도 확장성을 위해 arr과 arr2를 힙공간에 동적 할당 해준다.

• Example ( after Optimization )

 이전의 RadixSort보다 3배 정도 빨라졌으며, qsort보다 10~20배 정도 더 빨라졌다. 또한 이전 소스보다 확장성도 좋아졌으며, 스택에 할당해야하는 불필요한 배열들이 없어져서 메모리 사용도 효율적이게 되었다. 이 결과를 통해 성능 최적화의 중요성을 알 수 있었다. 한정된 자원에 빠른 처리를 요하는 프로그램을 만든다면, 위와 같은 최적화는 필수적일 것이다.

• CF

 여담으로, 컴파일러를 통해 최적화를 한다면 지금보다 더 빨라진다. release모드의 결과를 보게되면, 다음과 같다.
(여기서 release모드를 사용한다면 최적화하는 과정이 RadixSort뿐만 아니라 qsort도 빨라진다.)

※ std::sort가 qsort보다 빠른 이유

1>

 qsort는 콜백함수 compare가 매개변수로 필요하기 때문에 compare 함수 호출에 따른 오버헤드 발생한다.

 std::sort는 template으로 구성되어 함수 객체를 사용함으로써 inline이 가능하다.

2>

qsort는 return타입이 int이고 조건에 따른 3가지의 반환 값 1, 0, -1

std::sort는 return타입이 bool이고 조건에 따른 2가지의 반환 값 true, false

std::sort가 qsort 보다 빠른 이유 : Reference Link

Debug Mode vs Release Mode (디버그 모드 vs 릴리즈 모드)

Debug Mode와 Release Mode는 실행파일에서 차이가 있습니다.

Debug Mode는 컴파일시에 Debug정보를 실행파일에 같이 삽입합니다.
Release Mode에서는 Debug 관련 정보를 삽입하지 않습니다.

따라서 Release Mode로 만든 파일이 속도도 빠르며 실행파일 크기도 작습니다.

또한 Debug Mode의 실행파일은 컴파일러가 최적화를 해주지 않지만, Realase Mode의 실행 파일은 최적화를 해줍니다.




다음과 같이 소스 파일이 있을 때, 반복문을 1000번 돌 때마다 a에 10을 대입해줍니다.
우리가 눈으로만 봐도 알 수 있듯이, a에 10만 대입하고 끝내면 될 걸, 의미 없는 반복문이 돌고 있습니다. 컴파일러 또한 이것을 인지합니다.

• Debug Mode DisAssembly Screen

• Release Mode DisAssembly Screen

변수 a와 i, 반복문 과정을 모두 생략했으며 printf함수에 10(0Ah)을 출력한 명령어만 들어간 것을 확인할 수 있습니다.

• Debug Mode File Size

•  Release Mode File Size

실행 파일 크기가 Debug 모드에 비해 작은 것을 확인할 수 있습니다.



 ※ 우리는 실제 프로그램을 만들 때, 개발과정에서는 Debug Mode로 컴파일 하지만, 실제 제품으로 출시하기 위해서는 최종적으로 Release Mode로 컴파일이 되야 합니다. 또한 두 Mode 결과가 일치해야 합니다.

Build and Compile Difference (빌드와 컴파일 차이점)

비쥬얼 스튜디오에서 우리는 보통 F7을 눌러 에러 상황을 확인한다. 바로 F7이 Build이며, Ctrl+F7이 Compile이다. 이 둘의 차이점은 다음과 같습니다.

Compile ⊂ Build 이며,
간단하게 말하자면
Build = Compile + Link 인 것입니다.

Compile만 하게 되면 .obj 파일인 목적파일만 생성되며 링킹 과정을 하지 않습니다.
Build를 하게 되면 목적파일이 생성되고 링킹과정 뿐만 아니라 실행파일도 생성됩니다.


다음과 같이 두 개의 파일이 있을 때,








Test.c 파일의 변수 a를 주석처리하고 빌드(F7)을 하게 되면, 다음과 같은 에러가 납니다.





외부 변수 a를 찾을 수 없다는 에러입니다. 즉 링킹 과정에서 Test.c와 TestMain.c를 링킹 하였지만, 선언 된 변수 a가 주석처리되어 찾을 수 없다는 의미입니다.



하지만 컴파일(Ctrl+F7)을 하게 되면 에러가 나타나지 않습니다.



왜냐하면, 각각의 두 소스파일에 대해 .obj 목적파일만 생성되었기 때문입니다.

Multidimensional Array Fuction Parameter Delivery & Return

포인터 배열 : 배열에 메모리 주소 값을 저장하는 배열
int* a[3] = {0xf02f1022, 0xaddf1022, 0xf4221124 }

배열 포인터 : 배열을 가리키는 포인터
int (*a)[4] : 한 행마다 열을 4만큼씩 표현하는 2차원 배열

1차원 배열 변수의 값은 해당 배열공간을 가리키는 주소 이므로
int a[10];
int *b = a;
가 가능하다.

파란색 = 옳은 것
빨간색 = 틀린 것

• 매개변수 (Parameter)

다차원 배열을 함수의 인자로 전달할 때 다음과 같이 전달할 수 있다.
void Ex(int a[2][2]) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++)
cout << a[i][j] << " ";
cout << endl;

}
}
void main() {
int ary[2][2]{ 1,2,3,4 };
Ex(ary);
}
하지만 이와 같은 방법은 범용적이지 못하고 한정적이다. 2행 2열 크기의 배열만 전달할 수 있기 때문이다.
---------------------------------------------------------------------------------------------------

void Ex(int a[][]) {
 // ditto
}
그렇다면 이렇게 함수를 만드는 경우를 생각할 수 있을 것이다. 하지만 이 경우도 옳지 않다. 왜냐하면 힘수로 배열을 전달할 때, 배열의 첫번째 주소를 전달한다. 매개변수로 받을 변수는 이 주소가 몇 행 몇 열인지 모르기 때문에 컴파일 오류가 발생할 것이다. 따라서 배열에 명시적으로 명시해줘야한다.
---------------------------------------------------------------------------------------------------

void Ex(int a[2][]) {
 // ditto
}
다음과 같이 행만 명시한다면, 이 부분도 잘못 됬다. 만약에 2행 2열의 배열이 함수의 인자로 전달되면 매개변수 a는 1행부터 데이터를 몇 번째 열까지 데이터를 받아야 할지 모르기 때문이다.
---------------------------------------------------------------------------------------------------

void Ex(int a[][2]) {
 // ditto
}
이와 같은 방법으로 사용하면 된다.
1 2 3 4 5 6 7 8 9 10 인 배열이 Ex함수의 매개변수로 전달된다면
a배열에 저장된 데이터는 {{1,2}, {3,4}, {5,6}, {7,8}, {9,10}}과 같이 표현 할 수 있다.
열에 명시적으로 숫자를 주었기 때문에, 컴파일러가 위와 같이 해석할 수 있다.

void Ex(int (*a)[2]) {
 // ditto
}
또는 배열 포인터를 이용한다.
int형 포인터를 저장할수 있는 배열이라는 의미이다.
쉽게 풀어서 말하자면, 2개의 데이터를 가진 배열의 주소를 가리키는 포인터이다.
---------------------------------------------------------------------------------------------------

• 반환 (Return)

다차원 배열을 반환한다고 할 때, C에 익숙치 못한 사람은 다음과 같이 생각할 것이다.

int** Ex2() {
static int a[3][3] = { 1,0,0,0,1,0,0,0,1 };
return a;
}
void main() {
int** dm;
dm = Ex2();
}
 위 방법은 잘못 됬다. Ex2함수에서 int a[3][3] 자체는 3행 3열의 배열을 가리키는 주소이기 때문에 더블 포인터로 반환 할 수 없다. 다차원 배열들을 표현하기 위해 int a[3][3]와 같이 사용한 것이지, 실제로는 한 메모리 공간에 있는 것이다. (동적으로 다차원 할당하는 경우는 힙안에서 여러 공간에 있을 수 있다.)
---------------------------------------------------------------------------------------------------

int* Ex2() {
static int a[3][3] = { 1,0,0,0,1,0,0,0,1 };
return (int*)a;
}
void main() {
int (*dm)[3];

dm = (int(*)[3])Ex2();

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cout << dm[i][j] << " ";
cout << endl;
}
}
 네트워크 프로그래밍을 해본 사람은 다음과 같이 형변환을 이용하여 반환할 수도 있다.
 2차원 배열도 실제로는 1차원 배열이 쭉 나열 되있는 것이므로, int형 포인터로 캐스팅후 반환하면 된다. main문에서도 int*형으로 받아야 한다. 2차원 배열로 받을려면 명시적으로 (int(*)[3])와 같이 캐스팅 해줘야한다.
 함수 안에 static으로 선언한 이유는 지역 변수는 함수가 끝나면 소멸되기 때문이다. 만약에 static을 사용하지 않고 반환하게 되면 배열의 주소 값이 반환되게 되는데, main문으로 돌아와 이 주소값을 다른 변수에 저장하여도, 이미 이 배열 공간은 함수가 반환되면서 스택에서 소멸되었기 때문이다.
 위 방법은 어찌보면 편법에 가깝다. 캐스팅 변환 없이 반환하려면 반환형을 명시적으로 표현 해줘야한다.
---------------------------------------------------------------------------------------------------

int(*Ex2(void))[3]{
static int a[3][3] = { 1,0,0,0,1,0,0,0,1 };
return a;
}
void main()
{
int (*dm)[3];
dm = Ex2();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cout << dm[i][j] << " ";
cout << endl;
}
}
위와 같이 사용하면 다차원 배열을 반환할 수 있다.
---------------------------------------------------------------------------------------------------

팁으로 (int(*)[3])와 같은 표현은 가독성이 떨어진다. 따라서 다음과 같이 typedef 해주는 것이 좋다.
typedef int(*Dimension)[3];
Dimension Ex2(void){
static int a[3][3] = { 1,0,0,0,1,0,0,0,1 };
return a;
}
void main()
{
Dimension dm;
dm = Ex2();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cout << dm[i][j] << " ";
cout << endl;
}
}
---------------------------------------------------------------------------------------------------

3차원 이상 배열도 다음과 같은 방법으로 코딩 하면 된다.
int (*Ex2(void))[2][2]{
static int a[][2][2] = { { {1,2} ,{1,2} },{ {1,2} ,{1,2} } };
return a;
}
void main() {
int (*dm)[2][2] = Ex2();

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++)
cout << dm[i][j][k] << " ";
cout << endl;
}
cout << endl;
}
}
---------------------------------------------------------------------------------------------------

가독성을 생각한다면 다음과 같이 코딩한다.
typedef int(*Dimension)[2][2];
Dimension Ex2(void){
static int a[2][2][2] = { { {1,2} ,{1,2} },{ {1,2} ,{1,2} } };
return a;
}
void main() {
Dimension dm = Ex2();

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++)
cout << dm[i][j][k] << " ";
cout << endl;
}
cout << endl;
}
}
---------------------------------------------------------------------------------------------------

3차원 배열은 문자열에 많이 사용 된다.
typedef char(*Dimension)[2][10];
Dimension Ex2(void){
static char a[2][2][10] = { { "abcd" , "qqqq" },{ "adzoo" , "vvvv" } };
return a;
}
void main() {
Dimension dm = Ex2();

for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
cout << dm[i][j] << endl;
}
cout << endl;
}
}
---------------------------------------------------------------------------------------------------

 이와 같은 형식들은 외우는 것이 아니다. 포인터에 대한 메모리 관점에서 생각해보면 전혀 외울 필요가 없을 것이다.  

Return Value of 'scanf' Function

scanf 반환 값은 입력 받을 서식문자 중 성공한 서식문자의 개수를 반환합니다. 예를 들면, int a,b,c;  scanf("%d %d %d", &a, &b, &c) 가 있을 때, 정수 3개 입력이 아닌 5 3 c를 입력하면 2가 반환 됩니다. 예외가 발생하면 EOF로 반환 된다고 알고 있는 사람들이 많습니다. 하지만 무조건 EOF를 반환하지 않습니다. ( #define EOF (-1) ) 문자열 충돌이나 제어 문자열의 내용이 맞지 않는 경우 등등이 예외가 발생하는데, 예외가 발생해도 성공한 입력인자의 개수들은 반환해줍니다. EOF를 반환하는 경우는 인자를 통해서 값을 하나도 전달 받지 못한 상태에서 입력 내용과 제어 문자열의 충돌도 일어나지 않고 파일의 끝을 만난 경우 함수는  EOF를 반환합니다. ex) 이 소스는 무슨 의미 일까요? for(; ~scanf("%d", &a) ; ) cf) !는 logical operator not ~는 bitwise operator not 입니다. ~(0) 하면 8비트 기준 11111111 이 되기 때문에 ~(-1) 해야 00000000이 됩니다. anwser) 인자를 통해서 값을 하나도 전달 받지 못한 상태에서 파일의 끝(입력 서식문자의 끝)을 만난 경우 EOF를 리턴하여  for문의 조건이 ~(EOF) 즉 false(0)이 되기에 for문을 빠져 나옵니다. 그러지 않으면 for문을 계속 돌게 됩니다. reference : 'C: A Reference Manual' Book