Lecture 01: Course Overview
Great Reality #1
Ints are not Integers, Floats are not Reals
Example 1
\[x^2 \geq 0\]대수학에서 위 부등식은 실수에 대하여 항상 참이다.
그러나 컴퓨터의 관점에서 보면
부동 소수점 수(
float)에 대해서 참정수(
int)의 경우 반례 존재- 오버플로 발생 시, 제곱 연산의 결괏값이 음수가 될 수 있음
1 2 3 4 5
$ lldb (lldb) print 40000 * 40000 (int) $0 = 1600000000 (lldb) print 50000 * 50000 (int) $1 = -1794967296
Example 2
\[(x + y) + z = x + (y + z)\]대수학에서는 실수 집합에서 덧셈에 대한 결합 법칙이 성립한다.
마찬가지로 이를 컴퓨터의 관점에서 보면
정수(
unsigned&signed int)에 대해서 참부동 소수점 수(
float)의 경우 반례 존재- 상대적 차이가 충분히 큰 두 수의 덧셈 연산 시, 정밀도의 한계로 인해 작은 수가 무시될 수 있음
1 2 3 4 5
$ lldb (lldb) print (1e20 + -1e20) + 3.14 (double) $0 = 3.1400000000000001 (lldb) print 1e20 + (-1e20 + 3.14) (double) $1 = 0
Computer Arithmetic
컴퓨터는 수를 한정된 크기의 표현으로 나타내기 때문에, 위의 두 예시처럼 오버플로 또는 정밀도 문제가 발생할 수 있다.
Great Reality #2
You’ve Got to Know Assembly
컴퓨터에서 실행되는 명령어는 어셈블리(Assembly) 언어로 구성된다.
이 클래스에서는 어셈블리 코드를 직접 작성하기보다는, 컴파일러가 생성한 어셈블리 코드를 보고 이해하는 데 중점을 둔다.
Great Reality #3
Memory Matters
Random Access Memory is an Unphysical Abstraction
현대의 컴퓨터는 높은 용량 및 성능을 제공하기 위해 매우 복잡한 메모리 계층 구조를 갖추고 있으며, 이러한 메모리 체계를 이해하고 활용하는 정도에 따라 작성한 프로그램의 속도가 크게 달라질 수 있다.
특히 C로 작성된 프로그램에서 메모리 참조와 관련된 버그가 많이 발생하므로, 이러한 종류의 에러가 무엇인지 이해하고 사전에 방지할 수 있어야 한다.
Memory Referencing Bug Example
1
2
3
4
5
6
7
8
9
10
11
typedef struct {
int a[2];
double d;
} struct_t;
double fun(int i) {
volatile struct_t s;
s.d = 3.14;
s.a[i] = 1073741824; /* Possibly out of bounds */
return s.d;
}
함수 fun()의 인수 i는 크기가 2인 배열 a의 인덱스로 사용되고 있으므로, 유효한 인덱스를 나타내려면 0 또는 1의 값을 가져야 한다. 이 경우 fun(i)의 반환값을 출력해 보면 당연하게도 3.14가 나온다.
1
2
fun(0): 3.14
fun(1): 3.14
그런데 i의 값이 2 이상으로 증가하자 이상한 수가 나타나더니, 6에 도달하는 순간 crash가 발생한다. (구체적인 출력 결과는 시스템에 따라 다를 수 있다.)
1
2
3
4
5
6
fun(2): 3.1399998664856
fun(3): 2.00000061035156
fun(4): 3.14
fun(5): 3.14
*** stack smashing detected ***: terminated
Aborted
fun(i)에서 접근한 메모리를 4바이트 단위의 블록으로 나타내 보자.
fun(i) | i |
|---|---|
| Critical State | 6 |
| ? | 5 |
| ? | 4 |
d7 ... d4 | 3 |
d3 ... d0 | 2 |
a[1] | 1 |
a[0] | 0 |
C/C++은 기본적으로 경계 검사를 수행하지 않기에, 배열의 경계를 벗어나는 인덱스에 접근할 수 있다. 여기서 fun(2)와 fun(3)이 실제로 한 일은 숫자 d를 구성하는 바이트의 값을 변경한 것이고, 그로 인해 이상한 숫자가 나타난 것이다.
Memory Referencing Errors
작성한 프로그램이 잘 실행되는 것처럼 보여도, 엉뚱한 데이터에 접근하여 값을 바꿔 버리는 버그가 발생하면 디버깅하기가 굉장히 어렵다. C/C++은 메모리 보호 장치를 전혀 제공하지 않기 때문에, 자료 구조가 기계 수준에서 어떻게 표현되고 작동하는지 이해하는 것이 이러한 종류의 에러를 다루는 능력에 큰 차이를 만든다.
Great Reality #4
There’s more to performance than asymptotic complexity
상황에 따라 적절한 자료 구조와 알고리즘을 선택하고 활용하는 것도 물론 중요하지만, 시스템이 어떻게 작동하는지 이해한 뒤 일종의 저수준 최적화를 해주는 것이 더욱 중요하다.
Memory System Performance Example
1
2
3
4
5
void copyij(int src[2048][2048], int dst[2048][2048]) {
for (int i = 0; i < 2048; i++)
for (int j = 0; j < 2048; j++)
dst[i][j] = src[i][j];
}
1
2
3
4
5
void copyji(int src[2048][2048], int dst[2048][2048]) {
for (int j = 0; j < 2048; j++)
for (int i = 0; i < 2048; i++)
dst[i][j] = src[i][j];
}
두 함수의 유일한 차이점은 반복문의 중첩 순서가 다르다는 것인데, 일반적으로 위 함수의 실행 속도가 아래보다 훨씬 빠르다.
1
2
copyij(): 7.21 ms
copyji(): 61.17 ms
이렇듯 겉보기에는 별 차이가 없지만 성능 면에서는 엄청난 차이가 날 수 있는데, 이를 이해하려면 메모리 계층 구조와 캐시 메모리에 대해 알아야 한다.
Great Reality #5
Computers do more than execute programs
오늘날의 컴퓨터는 그저 격리된 환경에서 프로그램을 실행할 뿐인 기계에 그치지 않고, 네트워크를 통해 서로 통신하고 물리적 세계와 상호 작용하는 임베디드 컨트롤러이다.