Great Code 독후감 9장 배열 ~ 10장 문자열

9장 배열 자료구조

(1) 데이터 타입별 정렬크기 및 실제 메모리에 할당받는 크기

(예제 코드 출처: http://blog.naver.com/jackcom5/100035258638)

다음과 같이 크기가 다른 데이터형들이 메모리에 할당될때 몇바이트 크기를 차지하며, 어떻게 정렬되는지를 확인한다.

/*******************************************/
!! 32비트 인텔 프로세서에서의 실험 결과임 !!
/*******************************************/

#include

typedef struct {
char a;
double b;
char c;
} st_a;

typedef struct {
char a;
double b;
char c;
} __attribute__((packed)) st_b;

typedef struct {
char a;
double b;
char c;
short d;
} st_c;

typedef struct {
char a;
double b;
char c;
int d;
char e;
} st_d;

st_a AA;
st_b BB;
char arr1[3];
st_c CC;
st_d DD;

short arr2[3];
char pad;
int arr3[2];

int main(void)
{
printf("AA:%p, size=%d\n", &AA, sizeof(AA));
printf("%p %p %p\n\n", &AA.a, &AA.b, &AA.c);

printf("BB:%p, size=%d\n", &BB, sizeof(BB));
printf("%p %p %p\n\n", &BB.a, &BB.b, &BB.c);

printf("CC:%p, size=%d\n", &CC, sizeof(CC));
printf("%p %p %p %p\n\n", &CC.a, &CC.b, &CC.c, &CC.d);

printf("DD:%p, size=%d\n", &DD, sizeof(DD));
printf("%p %p %p %p %p\n\n", &DD.a, &DD.b, &DD.c, &DD.d, &DD.e);

printf("%p %p %p %p\n", arr1, arr2, &pad, arr3);

return 0;
}

gioserver@gurugio:great$
gioserver@gurugio:great$
gioserver@gurugio:great$
gioserver@gurugio:great$ cat 9-1.c

#include

typedef struct {
char a;
double b;
char c;
} st_a;

typedef struct {
char a;
double b;
char c;
} __attribute__((packed)) st_b;

typedef struct {
char a;
double b;
char c;
short d;
} st_c;

typedef struct {
char a;
double b;
char c;
int d;
char e;
} st_d;

st_a AA;
st_b BB;
char arr1[3];
st_c CC;
st_d DD;

short arr2[3];
char pad;
int arr3[2];

int main(void)
{
printf("AA:%p, size=%d\n", &AA, sizeof(AA));
printf("(char)%p (double)%p (char)%p\n\n", &AA.a, &AA.b, &AA.c);

printf("BB:%p, size=%d\n", &BB, sizeof(BB));
printf("(char)%p (double)%p (char)%p\n\n", &BB.a, &BB.b, &BB.c);

printf("CC:%p, size=%d\n", &CC, sizeof(CC));
printf("(char)%p (double)%p (char)%p (short)%p\n\n", &CC.a, &CC.b, &CC.c, &CC.d);

printf("DD:%p, size=%d\n", &DD, sizeof(DD));
printf("(char)%p (double)%p (char)%p (int)%p (char)%p\n\n", &DD.a, &DD.b, &DD.c, &DD.d, &DD.e);

printf("(char[3])%p (short[3])%p (char)%p (int[2])%p\n", arr1, arr2, &pad, arr3);

return 0;
}

gioserver@gurugio:great$ gcc -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.1.3 --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --enable-checking=release i486-linux-gnu
Thread model: posix
gcc version 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

gioserver@gurugio:great$ gcc -Wall -O2 9-1.c
gioserver@gurugio:great$ ./a.out
AA:0x80497e0, size=16
(char)0x80497e0 (double)0x80497e4 (char)0x80497ec

BB:0x80497bb, size=10
(char)0x80497bb (double)0x80497bc (char)0x80497c4

CC:0x804979c, size=16
(char)0x804979c (double)0x80497a0 (char)0x80497a8 (short)0x80497aa

DD:0x80497c8, size=24
(char)0x80497c8 (double)0x80497cc (char)0x80497d4 (int)0x80497d8 (char)0x80497dc

(char[3])0x80497c5 (short[3])0x80497b4 (char)0x80497ba (int[2])0x80497ac

구조체로 묶인 char형 변수들은 packed 선언을 하면 1바이트를 차지하고, 기본적으로는 자신의 다음에 선언된 데이터 형의 정렬값에 맞춰서 크기가 정해진다.

AA.a는 크기가 4바이트인데 AA.b가 double 타입으로 정렬값이 4바이트이기 때문이다. 하지만 CC.c의 크기는 2바이트가 되는데, CC.d는 short 타입이므로 정렬값이 2바이트이기 때문이다.

char형 변수의 주소를 확인하면 자기 자신의 정렬값은 1바이트임을 알 수 있다.

===> char형 데이터 정렬값=1, 데이터 크기=다음 데이터의 정렬을 위해 달라짐

short형 데이터는 char형 데이터와 같은 원리로 자기 자신의 주소를 출력해본 결과 2바이트로 정렬됨을 알 수 있다. 그리고 다음에 나오는 데이터의 크기에 따라 데이터 크기 값이 달라진다.

===> short 형 데이터 정렬값=2, 데이터 크기=다음 데이터의 정렬을 위해 달라짐

int나 double, long 등도 같은 원리임을 확인할 수 있다.

===> int,double,long 정렬값=4, 데이터 크기=int/long은 4, double은 8바이트

구조체의 정렬값을 확인하기 위해 각각의 구조체를 다양하게 변형해보았다. char 변수 하나만 있는 구조체를 여러개 만들어봤지만 모두 4바이트의 정렬값을 가진다. 구조체는 기본적으로 packed로 선언되지 않으면 4바이트의 정렬값을 가진다고 생각된다.

===> 구조체의 정렬값=4

======================================================================================

(2) 동적 배열 생성

보통 1차원 동적 배열은 동적 메모리 할당을 사용해서 사용하는데 원래는 아래 소스와 같이 배열 인덱스를 동적으로 지정해서 스택에 배열을 만들수도 있다.

#include
#include

int main(void)
{

int x,y;

// user input or etc...
x = 3, y = x+2;

// one-dimension dynamic array
int arr2[y];

arr2[0] = 0x1;
arr2[1] = 0x2;
arr2[y-1] = y;

printf("%x %x\n", arr2[0], arr2[y-1]);

int arr3[x][y];
arr3[2][y-1] = 0xa3a3;
printf("%x\n", arr3[2][4]);

// 2-dimension dynamic array
int (*arr)[y] = (int (*)[y])malloc(x*y*sizeof(int));

arr[0][2] = 0x22;
arr[2][4] = 0xff;

printf("%x %x\n", arr[0][2], arr[2][4]);

printf("\n\n%p %p %p %p %p\n", &x, &y, arr2, arr3, &arr);

return 0;
}

실행 결과 값을 보면 다음과 같다.

gioserver@gurugio:great$ gcc -Wall 9-2.c
gioserver@gurugio:great$ ./a.out
1 5
a3a3
22 ff

0xbfaa43d8 0xbfaa43d4 0xbfaa4390 0xbfaa4340 0xbfaa43d0

실행 결과 값을 보면 일차원배열 arr2는 원래 의도했던 20바이트보다 더 큰 56바이트가 할당되었다. -S 옵션으로 어셈블리 코드를 읽어보면 스택에 배열을 만들때 원래 크기보다 더 크게 스택을 사용한다는 것을 알 수 있다. 이렇게 동적인 배열 할당이 가능한 것은 배열을 스택에 만들기 때문에 실행중에 메모리를 할당받을 수 있기 때문이다.

2차원 배열도 마찬가지로 스택에 할당받을 때는 배열의 크기를 동적으로 결정할 수 있다.

보통 이렇게 2차원 배열을 만든다.

arr = (int **)malloc(y * sizeof(int *));

for(i = 0; i < y; i++)
{
arr[i] = (int *)malloc(x * sizeof(int));
}

그리고 보통 2차원 배열을 할당받을 때는 1차원 포인터배열을 동적으로 만들고, 그 다음에 여러개의 배열을 만들어서 처음의 포인터배열에 포인터를 저장하는 방식을 쓰는데 이것을 원칙적으로 2차원 배열을 만드는 방법이 아니다. 배열의 정의에 따르면 메모리에 연속적으로 저장되어야 하는데 이렇게 여러번 메모리를 할당받아서 배열을 만들면 배열이 아닌 메모리 공간 여러개가 되는 것이다.

따라서 위의 예제 소스와 같이 하나의 연속된 메모리 영역을 할당받고 2차원 포인터에 포인터를 저장해서 사용하면 된다.

참고로 2차원 포인터의 데이터 타입은 (*)[열크기] 이다. malloc() 함수의 타입 변환을 (int (*)[열크기]) 로 하면 int의 2차원 배열로 타입을 변환한다.

10장 문자열

(1) 0으로 끝나는 문자열

0으로 끝나는 문자열(ASCIIz 혹은 0-terminated string이라고 부름)은 C/C++/JAVA 등 가장 많은 언어에서 사용하는 문자열 표현 방식이다.

장점
- 언어의 대중성덕분에 많은 라이브러리가 있음
- 구현하기 쉬움. 문자열을 처리하기 위한 언어적 기능이 필요하지 않으므로 단순한 정의가 가능함. (하지만 반대로 생각하면 프로그래머가 신경써야 할 것이 많아짐)
- 0으로 끝나는 문자열은 배열과 같은 특성을 가지므로 포인터를 이용해서 간단하게 접근이 가능하다.

단점
- 문자열을 처리하는 함수가 비효율적인 경우가 많음. 문자열의 길이를 알아내기 위해서는 문자열 전체를 스캔해야 하므로 긴 문자 처리에 불리함
- 문자열 데이터가 얼마까지 길어질 수 있는지에 대한 정보가 없음. 문자열 길이의 병합, 문자열 전달 등에서 문자열의 길이에 대한 확인 절차가 추가로 필요해짐.

0으로 끝나는 문자열을 사용할 때는 다음 사항을 주의한다.

- 직접 문자열 함수를 작성하지 말고 컴파일러가 제공하는 런타임 라이브러리를 최대한 활용한다.
- 문자열의 길이를 자주 확인해야 한다면 매번 글이를 계산하지 말고, 길이 정보를 따로 저장해 둔다.

(2) 표준 문자열 함수 사용

거의 모든 경우에 문자열을 처리할 때는 런타임 라이브러리를 사용한다. 다음 예제와 같이 짧은 문자열을 복사하는 strcpy() 함수는 함수 호출로 처리되는 것이 아니라 인라인함수로 코드가 삽입되는 형태로 컴파일된다.

$ gcc -S 10-1.c

#include

int main(void)
{
char localstr[256];
strcpy(localstr, "hello,world");
printf(localstr);
return 0;
}

.file "10-1.c"
.text
.globl main
.type main, @function
main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $276, %esp
movl %gs:20, %eax
movl %eax, -8(%ebp)
xorl %eax, %eax
leal -264(%ebp), %eax

movl $1819043176, (%eax) -> 스택에 바로 문자를 써버림
movl $1870081135, 4(%eax)
movl $6581362, 8(%eax)

leal -264(%ebp), %eax
movl %eax, (%esp)
call printf
movl $0, %eax
movl -8(%ebp), %edx
xorl %gs:20, %edx
je .L3
call __stack_chk_fail
.L3:
addl $276, %esp
popl %ecx
popl %ebp
leal -4(%ecx), %esp
ret
.size main, .-main
.ident "GCC: (GNU) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)"
.section .note.GNU-stack,"",@progbits

컴파일러는 특정 함수들의 이름을 인식하고 함수를 호출하는 대신에 효율적인 인라인 코드로 변환한다. 따라서 직접 만든 함수를 사용하는 것보다 좋은 성능을 가진다.

물론 문자열을 처리하는 함수들은 대부분 아주 간단한 기능만을 가진다. 최소한의 정해진 기능들을 가진 함수들만을 라이브러리로 만들기 때문에 만약 조금이라도 다른 기능을 가진 함수가 필요하다면 직접 만드는 것이 효율적일 때가 있다.

중요한 것은 문자열 라이브러리가 어떤 기능을 수행하는지 어떤 방식으로 처리하는지 정확이 이해하고 있는 것이다. 그래야 런타임 함수를 이용하거나 새롭게 만들지 판단할 수 있다.

(3) 반복 연산 피하기

문자열 처리에서 대표적인 실수가 다음과 같이 루프안에서 불필요한 연산을 반복하는 것이다.

for (i=0; i if (ch == localstr[i])
break;
}

이 코드에 해당하는 기계 코드는 다음과 같다.

jmp .L2
.L3:
movl -276(%ebp), %eax
movzbl -268(%ebp,%eax), %eax
cmpb -269(%ebp), %al
je .L4
addl $1, -276(%ebp)
.L2:
movl -276(%ebp), %edx --> i 값
leal -268(%ebp), %eax
movl $-1, %ecx
movl %eax, -284(%ebp)
movl $0, %eax
cld
movl -284(%ebp), %edi
repnz
scasb --> 문자열에서 0이 나올때까지 카운트
movl %ecx, %eax
notl %eax
subl $1, %eax
cmpl %eax, %edx
jb .L3
.L4:

strlen() 함수를 최적화해서 인라인함수로 변환한다고 해도 문자열의 길이를 반복해서 계산하므로 낭비가 된다. 이렇게 명시적으로 낭비가 보이는 코드라면 문제가 작지만 다음과 같이 명시적으로 낭비가 보이지 않는 코드는 찾기가 어렵다.

#include

int main(void)
{

char str[] = "TEST STRING";

int len = strlen(str);
char *newstr;

if (len == 0)
newstr = NULL;
else
newstr = strdup(str);

return 0;
}

strdup() 함수의 내부에는 인자로 받은 문자열의 길이를 계산해서 새롭게 메모리를 할당받는 코드가 있으므로 결국 이 코드가 실행되는데는 두번의 strlen이 호출되는 셈이다. 만약 strdup() 함수가 대량으로 호출되는 프로그램이라면 strlen()의 호출을 줄이기 위해 다음과 같이 문자열의 길이를 인자로 전달받는 함수를 만들어 사용하는 것도 좋다.

함수 선언: char *new_strcup(const char *src, size_t length);

이렇게 조금이라도 문자열에 접근하는 것을 막는 이유는 길이가 긴 문자열을 처리할 때 메모리 접근이 필요한 경우가 생기기 때문이다. 환경 변수나 로그데이터, 파일 읽기 등에서 긴 문자열을 처리할 때 한번 읽은 문자열을 계속해서 자주 다루는 상황이 아닌 이상 하드웨어 캐시 히트를 바라기가 힘들어진다. 따라서 최대한 문자열의 복사나 길이 계산 등 문자열을 메모리에서 읽는 경우를 줄이기 위해 노력해야 한다.