CS:APP | Chapter 3 | (1) 프로그램의 기계수준 표현

오버헤드(overhead)

공부하다 보면 함수의 오버헤드가 발생했다, 메모리 오버헤드가 발생했다 등등 overhead 라는 용어가 자주 등장한다. 

여기서 말하는 (컴퓨터과학 관점에서의) overhead는 특정 작업을 수행하기 위해 필요하지만, 실제 유용한 작업에 직접 기여하지는 않는 추가적인 리소스나 시간을 의미한다. 즉 특정 작업을 수행할 때, 그 핵심 동작을 위한 비용은 아니지만 괜히 간접적으로 낭비되는, 따라서 더 최적화할 여지가 있는 비용이라는 거다. 

 

GPT한테 물어보니 다음과 같은 예시를 준다.

1. 함수의 오버헤드: 함수 호출 시 발생하는 추가적인 처리입니다. 함수를 호출하면, 인자를 전달하고, 리턴 주소를 저장하고, 필요한 경우 스택 프레임을 설정하는 등의 작업이 필요합니다. 이러한 작업들은 함수의 실제 '유용한' 로직과는 별개의 처리이지만, 함수 호출 메커니즘을 위해 필수적입니다.
2. 메모리 오버헤드: 메모리 할당 시 시스템이 사용하는 추가적인 메모리입니다. 예를 들어, 동적 메모리 할당에서 메모리 블록의 관리 정보를 저장하기 위해 사용되는 메모리나, 데이터 구조의 패딩을 위해 사용되는 메모리가 이에 해당합니다.
3. 시간 오버헤드: 어떤 알고리즘이나 프로세스를 실행하는 데에 걸리는 추가적인 시간입니다. 예를 들어, 동기화 메커니즘, 오류 검사, 로깅 등이 있습니다.
4. 통신 오버헤드: 네트워크 통신에서 데이터 패킷을 보내는 데 필요한 프로토콜 헤더나 메타데이터 등이 추가되어 실제 유용한 데이터 전송에 비해 더 많은 데이터가 전송되는 것을 말합니다.

 

 

CPU 아키텍처에서 32bit vs 64bit 차이점

CPU 아키텍처가 32-bit에서 64-bit로 이동하면서 다음과 같은 변화가 발생하였다: 

 

1. 기본 워드 크기가 32 bit에서 64 bit로 확장되었다. 기본 워드 크기는 CPU가 한 번에 처리할 수 있는 데이터의 양을 의미한다. 즉, 한번에 더 큰 데이터를 처리할 수 있게 되었다.
2. 이에 따라 한번에 처리할 수 있는 메모리 주소도 더 커졌다. 당연히 32 bit에서 최대 64 bit의 숫자까지 메모리 주소를 지정할 수 있게 되었다. 그 결과 다룰 수 있는 메모리 크기도 커진다. 4GB(2^32byte) -> 18.4 엑사바이트(EB, 2^64byte) 까지 메모리를 다룰 수 있다. (이론적으로는)
3. 레지스터의 경우 64-bit 아키텍처가 더 많은 레지스터를 제공한다. 범용 레지스터의 경우 기존에 비해 64 bit까지 크기가 확장되었고, 그 수도 8개에서 16개로 많아졌다. (%r9 ~ %r15) 이를 통해 프로그램 실행 속도가 향상된다. (이건 워드 크기 확장에 따른 결과는 아니고, 설계한 사람들이 레지스터 파일 구성을 고려하면서 이렇게 정한 거)
4. 운영체제 호환성 측면에서 보면, 64-bit 운영체제는 32-bit와 64-bit 기반 애플리케이션을 모두 실행할 수 있다. 그러나 32-bit 운영체제가 역으로 64-bit 기반 애플리케이션을 실행할 수는 없다. 64-bit 하드웨어에서 32-bit 운영체제를 실행하는 것은 가능하다. 그러나 마찬가지로 64-bit 기반 기능을 사용할 수는 없다. 

즉, 더 큰 워드 크기와 더 큰 메모리 주소 범위 덕분에 더 큰 데이터 세트를 더 빠르게 처리할 수 있게 되었다. 또한 메모리에 저장할 수 있는 크기도 더 커졌다. 이는 컴퓨터 성능의 전반적인 개선으로 이어진다. 

 

RFLAGS 레지스터

x86-64 아키텍처에서의 플래그 레지스터. (32bit 모드에서는 'EFLAGS' 라는 이름이었음)

CF (Carry Flag), ZF (Zero Flag), SF (Sign Flag), OF (Overflow Flag) 등의 플래그들이 해당 레지스터 내에 위치한다. 

이들 외에도 여러 상태 플래그, 시스템 플래그, 그리고 컨트롤 플래그를 포함하며, 이러한 플래그는 프로세서의 상태를 나타내고 명령어 실행을 제어하는 데 사용된다. 

 

각 플래그는 특정 연산의 결과에 따라 설정되거나 클리어된다. 

 

예를 들어:

• CF (Carry Flag)는 산술 연산이 carry out 또는 borrow를 생성할 때 설정된다.
  • carry out은 덧셈 계산할 때 자릿수 올림 저장용
  • borrow는 뺄셈에서 자릿수 빌림 저장용
  • 비부호형(unsigned) 연산에 대한 오버플로우 나타내기
• ZF (Zero Flag)는 연산의 결과가 0일 때 설정된다.
• SF (Sign Flag)는 연산의 결과가 음수일 때 설정된다.
• OF (Overflow Flag)는 부호형(signed) 산술 연산이 오버플로우를 발생시킬 때 설정된다.

이 플래그들은 조건 분기 명령어나 조건 명령어 실행 등에 사용되어, 프로그램의 흐름을 제어하는 데 매우 중요

 

 

제어문 인스트럭션 (cmp, test, set)

cmp, test, 그리고 set 인스트럭션은 조건부 실행과 관련이 있다. 

 

1. cmp (compare) 인스트럭션:
   • cmp는 오퍼랜드로 주어진 두 값을 비교하는 데 사용된다.
   • 예를 들어, 'cmp %eax, %ebx'는 레지스터 %eax와 %ebx의 값을 비교한다. 
   • 이 명령은 두 값이 동일한지, 하나가 다른 것보다 큰지 또는 작은지를 결정하기 위해 플래그 레지스터를 설정한다. 
2. test 인스트럭션:
   • test는 두 값을 비트 단위로 AND 연산한 후 결과를 검사한다. 
   • 예를 들어, 'test %eax, %eax'는 %eax 레지스터의 값을 자신과 AND 연산하고, 그 결과가 0인지 아닌지를 플래그 레지스터에 설정한다.
3. set 인스트럭션:
   • set 명령어는 특정 조건 플래그에 따라 바이트 레지스터에 0 또는 1을 설정한다.
   • 예를 들어, 'sete %al'은 zero 플래그(ZF)가 설정된 경우 %al 레지스터에 1을 설정하고, 그렇지 않으면 0을 설정한다.
     • set 인스트럭션을 사용하여 %al 레지스터에 1 또는 0을 설정하는 것은 특정 조건을 검사한 결과를 저장하고 이를 나중에 사용할 수 있도록 하는 방법. 이렇게 함으로써, 프로그램은 이전에 수행된 비교 또는 테스트의 결과에 따라 다른 작업을 수행할 수 있다. 예를 들어, 두 수가 같은지 확인한 후, 이 정보를 사용하여 나중에 다른 조건부 작업을 수행할 수 있다.
   • 즉, set 명령은 어셈블리 코드에서 조건부 논리를 표현하고 이해하기 위한 간단하고 효율적인 방법을 제공한다.

이 인스트럭션들은 종종 함께 사용되어 조건부 실행을 수행한다.

예를 들어, 두 값이 동일한지 확인하고 결과에 따라 레지스터를 설정하려면 cmp, je (jump if equal), sete 명령을 함께 사용한다. 

 

간단한 예제를 통해 이를 살펴보자. 

 

<C>

int compare(int a, int b) {
    return a == b;
}

 

<ATT 어셈블리 코드>

is_equal:
    cmp %edi, %esi      # 레지스터 %edi와 %esi를 비교
    sete %al            # 만약 두 값이 동일하다면, %al 레지스터에 1을 설정
    movzbl %al, %eax    # %al의 값을 %eax로 확장 (즉, %eax의 나머지 비트를 0으로 설정)
    ret                 # 결과를 반환하고 함수를 종료

이 예에서 sete %al 명령은 두 값이 동일한지 여부에 따라 %al 레지스터에 1 또는 0을 설정한다. 이 값은 나중에 반환될 값으로 사용되며, 이는 두 수가 같은지 여부를 나타낸다.

 

movzbl 명령은 %al의 값을 %eax로 확장(%al 보다 상위에 있는 24 비트를 0으로 채움)하여, 이 함수의 반환 값을 준비한다. 

%al과 %eax는 동일한 레지스터 내에 존재하며, 단지 서로 다른 비트 영역에 접근하는 방식이다. %al은 %eax 레지스터의 하위 8비트에 접근하고, %eax는 전체 32비트에 접근한다. 이러한 방식으로, 레지스터의 서로 다른 부분에 접근할 수 있도록 하는 것은 아키텍처의 유연성을 제공하며, 특정 연산에 필요한 만큼의 데이터만 사용할 수 있게 한다. 

 

 

Q. 왜 %al의 값을 %eax로 확장하는 작업이 필요할까?

함수의 반환 값은 일반적으로 %eax 레지스터에 저장된다. 그러나 set 명령어는 오직 8비트 레지스터인 %al에만 값을 설정한다. 따라서 %al의 값을 %eax로 확장하여 전체 %eax 레지스터에 해당 값을 설정해야 한다. 이렇게 하면 함수가 올바른 반환 값을 가지게 된다.

 

movzbl 명령어는 Move Zero-extended Byte to Long의 약자이다. (from값 to값 크기에 따라 bw, bq, wl, wq 도 가능) 이 명령어는 %al 레지스터의 값을 가져와서 이를 %eax 레지스터에 저장하며, 나머지 상위 비트를 0으로 설정한다. 이렇게 하면, %eax 레지스터는 이제 32비트 값으로 확장된 %al의 값을 가지게 되며, 이 값은 함수의 반환 값으로 사용된다.

 

 

Q. 꼭 movzbl을 통해 확장해야 할까? 간단하게 mov 인스트럭션을 사용해서 값을 복사하면 안될까?

만약 movzbl을 사용하지 않고 단순히 %al을 %eax에 복사하려고 한다면, 데이터 손실 및 올바르지 않은 값이 저장되는 등의 문제가 발생할 수 있다. 

 

%al은 8비트 레지스터이고 %eax는 32비트 레지스터이다. 따라서 %al의 값만을 %eax에 복사하면, %eax의 나머지 비트는 변경되지 않아 기존에 가지고 있던 무언가의 값이 그대로 유지된다. 이로 인해 데이터 손실이 발생하거나, 이상한 값으로 인식될 수 있다. 

movzbl 명령은 이러한 문제를 방지하기 위해 %al의 값을 %eax로 올바르게 확장한다. 이 명령은 %al의 8비트 값을 %eax의 하위 8비트에 복사하고, %eax의 나머지 상위 24비트를 0으로 설정하여 데이터 손실이나 잘못된 값이 발생하지 않도록 한다. 

 

 

Q. 왜 반환 값을 저장할 용도로 %rax가 아닌 %eax를 쓰는 걸까? 

32비트를 초과하는 값이나 64비트 아키텍처만 작동하는 함수가 아닌 경우에는 일반적으로 %eax를 사용한다. 

 

32비트 값을 반환하는 함수의 경우, %eax 레지스터를 사용하여 값이 반환되는 것이 일반적이다. 물론, 64비트 값을 반환하는 함수의 경우 %rax를 사용할 수 있다. 

 

32비트 값이라는 용어는 32비트로 표현할 수 있는 값을 의미한다. 이는 해당 값이 32개의 비트로 구성되며, 이는 2의 32승, 즉 0부터 4,294,967,295까지의 정수를 표현할 수 있다는 것을 뜻한다. 

 

혹은 32비트 아키텍처에서 작동하는 함수나 프로그램을 의미할 수도 있다. 이 경우, 함수의 반환 값, 매개 변수, 내부 변수 등이 모두 32비트로 제한된다. 다음과 같은 이유가 있을 수 있다. 

1. 호환성: 기존의 32비트 코드와의 호환성을 유지하기 위해, 많은 시스템 및 애플리케이션은 32비트 레지스터를 사용하여 값을 반환한다. 이는 특히 시스템 호출이나 라이브러리 함수 호출에 있어 중요할 수 있다. 
   • 32비트와 64비트 아키텍처 모두에서 호환되는 함수의 경우, 반환 값을 %eax 레지스터에 저장하는 것이 일반적(사실상 필수적)이다. 이는 x86 호출 규약의 일부로, 함수의 반환 값은 %eax 레지스터에 저장되어야 한다. 이 규약은 32비트와 64비트 아키텍처 모두에서 적용되며, 이를 통해 다양한 아키텍처에서 코드의 호환성을 유지할 수 있다.
2. 최적화: 32비트 레지스터를 사용하면, 명령어 크기가 줄어들고 때로는 실행 속도도 빨라질 수 있다. 이는 작은 명령어가 캐시에 더 잘 맞고, 메모리 대역폭을 덜 사용하기 때문.

 

jmp 인스트럭션 목적지를 인코딩 하는 방식 (PC-relative 방법, 절대 주소 제공 방법)

PC-relative 방식은 프로그램의 위치 독립성을 유지하면서 메모리 내의 다른 코드 또는 데이터 영역으로 점프를 수행할 수 있게 해준다. 반면, 절대 주소 방식은 보다 단순하지만 프로그램의 위치 독립성을 유지할 수 없다.

 

PC-relative (Program Counter-relative) 방법:

• PC-relative 방식은 jmp 인스트럭션의 목적지 주소를 현재 프로그램 카운터(PC)의 값에 상대적으로 표현한다. 이 방법은 인스트럭션 바이트 다음의 주소에서 특정 오프셋 값을 더하거나 뺌으로써 목적지를 찾는다.
• 예를 들어, 현재 PC 값이 0x1000이고, jmp 인스트럭션 다음에 0x20이라는 오프셋이 있다면, 목적지 주소는 0x1020이 된다.
• 이 방법의 장점은 프로그램이 메모리 내의 다른 위치로 이동해도, 상대적인 오프셋 값이 변하지 않아서 목적지 주소가 유효하게 유지된다는 것이다. 따라서 이 방식은 위치 독립 코드(Position Independent Code, PIC)를 작성할 때 유용하다.
• 예를 들어, 아래의 x86-64 ATT 어셈블리 코드는 PC-relative 방식을 사용하여 label로 점프한다.

.section .text
.global _start

_start:
    jmp label      # PC-relative jump
label:
    # some code

위 코드에서 jmp label 인스트럭션은 현재 프로그램 카운터의 위치에 상대적인 오프셋을 사용하여 label로 점프한다.

jmp label 인스트럭션에서의 오프셋은 jmp 인스트럭션의 위치와 label 위치 사이의 차이(정확히는 label 주소 - jmp 인스트럭션 주소 +1, jmp 다음 바이트 주소를 기준으로 함)를 나타낸다. 이 차이는 바이트 단위로 측정되며, 이 값이 "jmp" 인스트럭션에 인코딩되어, CPU가 "label"로 점프할 정확한 위치를 알 수 있게 한다.

 

 

절대 주소 제공 방법:

• 절대 주소 방식은 jmp 인스트럭션의 목적지 주소를 명시적으로, 절대적인 값으로 제공한다.
• 예를 들어, jmp 인스트럭션에 0x2000이라는 절대 주소가 명시되어 있다면, 목적지 주소는 0x2000이 된다.
• 이 방법의 단점은 프로그램이 메모리 내의 다른 위치로 이동하면 목적지 주소가 무효가 될 수 있다는 것이다. 그렇기 때문에 프로그램이 메모리에서 위치가 변경될 수 없는 환경에서만 이 방법을 사용할 수 있다.
• 주로 고정된 메모리 위치에 접근할 때 사용된다. 예를 들어, 아래의 C 코드와 그에 해당하는 x86-64 ATT 어셈블리 코드는 절대 주소를 사용하여 함수를 호출한다.

void function() {
    // some code
}

int main() {
    function();
    return 0;
}

이 C 코드를 컴파일하면 다음과 같은 x86-64 ATT 어셈블리 코드가 생성될 수 있다.

.section .text
.global _start

# 함수 정의 .. 
function:
    # 코드 ... 
    ret

# main 함수
_start:
    call function      # Absolute address call
    ret

위 코드에서 call function 인스트럭션은 function 라벨의 절대 주소를 사용하여 함수를 호출한다.

 

 

 

 

3주차 퀴즈

1. 스택, 레지스터 각각의 정의, 용도, 장점을 설명하시오 (자료구조의 관점보다는 Local Storage 관점에서)

스택은 프로그램의 Local Storage 영역으로 사용된다.

스택의 주요 용도 중 하나는 프로시저 호출 시 지역변수, 매개변수, 리턴 주소, 이전 프레임의 스택 포인터를 저장하기 위한 메모리 공간이라는 점. 

선언되는 순서와 반대로 메모리가 해제되는 LIFO 구조를 지닌다.

 

용도:

• 함수의 로컬 변수 저장: 각 함수 호출 시 함수의 로컬 변수들이 스택에 저장된다.
• 함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. 

장점:

• 동적으로 메모리를 할당하고 해제할 수 있다.
• 구현이 간단하며, 메모리 관리 overhead가 낮다. 
• Local Storage를 제공함으로써 프로시저의 실행 상태를 유지한다. 

 

레지스터는 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다.

 

용도:

• 중간 연산 결과의 저장: 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용된다.
• 빠른 데이터 접근: 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용된다.

장점:

• 매우 높은 데이터 접근 속도를 제공한다.
• 데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가한다. 

 

+) 함수호출시 스택의 레이아웃(인자, 로컬변수, 리턴값)과 동작에 대한 이해

 

• 인자(Arguments): 함수 호출시, 함께 넘겨준 인자는 보통 스택에 푸시된다. 이를 통해 함수는 인자에 접근할 수 있다. 스택에 푸시되는 순서는 호출 규약(ex: cdecl, stdcall 등)에 따라 다르다. 
• 로컬 변수(Local Variables): 함수 내부에 선언된 로컬 변수는 스택 프레임에 할당된다. 로컬 변수는 함수의 실행 동안에만 유효하며, 함수가 반환되면 스택에서 제거된다. 
• 리턴 값(Return Value): 함수가 값을 반환하는 경우, 리턴된 값은 보통 레지스터에 저장되거나, 호출자에 의해 제공된 메모리 위치에 저장된다.
• 리턴 주소(Return Address): 함수 호출시, 호출자의 다음 명령어의 주소(리턴 주소)는 스택에 푸시된다. 함수가 종료되고 제어가 호출자로 반환될 때, 이 리턴 주소는 스택에서 pop되어 프로그램 카운터에 로드되어 실행이 계속 된다.

 

 

2. 꼬리 재귀 최적화(Tail Recursion Optimization)를 Call Stack 관점에서 설명

3. 단어 "DATABASE"와 "ALPHABET"의 LCS를 구하고, 행렬과 탐색경로를 함께 기록

4. 그리디 알고리즘과 DP의 정의, DP에서 탑다운 바텀업의 차이에 대한 설명

5. 플로이드 워셜 알고리즘을 사용하여 방향 그래프의 이행적 폐쇄를 구하기 (단계별 도식화)

 

---

면접에서 이런것도 물어봅니다. 시간 날때 고민해보시기 바랍니다.

함수호출시 스택의 레이아웃(인자, 로컬변수, 리턴값)과 동작을 이해하는지…
DP에서는 상향,하향식 이외에도, DP가 가능한 조건(최적부분구조, 중복부분해)에 대해서…