Jins' Dev Inside

면접에서 단골처럼 등장하는 질문이자, 컴퓨터 공학과 시험에서 한번쯤은 보았을 법한 CS 기본 지식을 정리하고자 한다.

컴퓨터는 데이터를 저장할 수 있는 몇가지 종류의 공간들을 갖고 있고, 해당 공간들은 쓰임새가 다르고 만들어진 이유가 다르기 때문에 각각 I/O 작업에 있어서 다른 퍼포먼스를 낸다.

그 중에서도 Access 에 대한 다음 Computing Operation 의 속도 비교는 알아두어야 한다.

 - CPU Register

 - Context Switch

 - Memory Access (RAM)

 - Disk Seek (HDD)

위의 Operation 들에 대한 속도 비교 결과는 빠른 순서대로 다음과 같다.

1. CPU Register Access

2. Memory Access

3. Context Switching

4. Disk Seek

(1) CPU 레지스터에 대한 접근은 단 한번의 CPU 사이클만으로 이루어지기 때문에 즉각적으로 이루어진다.

한 사이클이라는 것은 말그대로 번개와 같은 속도로 이루어진다는 뜻이다.

(2) Memory Access 는 일반적으로 RAM 에서 데이터를 읽어내는 것을 말하며, 당연히 RAM 의 목적에 맞게 HDD 로부터 읽어오는 것보다 빠르다.

일반적인 상태에서의 작업은 레지스트리에 접근하는 것에 비견될만큼 빠를 수 있지만 논리 구조 위에서 동작하기 때문에 Virtual Memory Swapping 과 같은 작업에서 자유로울 수 없으며 이런 경우에는 Disk Access 만큼 느려질 수도 있다. 

(3) Context Switching 는 대체적으로 빠른 접근이 보장이 된다. 하지만 여러개의 프로세스가 동시에 실행되며 스위칭이 빈번하게 이뤄질 경우 굉장히 느려질 수도 있다.

(4) Disk Seek. HDD 에 대한 Disk Seek 은 위에 언급한 Operation 들에 비해 빠를 수가 없는 작업이지만 캐싱을 통해 비약적인 성능 향상이 가능하다.

BUS 에서의 병목을 피할 수 있으며 캐싱을 통해 Main Memory 에 Access 하는 것 만큼의 퍼포먼스를 기대할 수도 있다.

면접에서 갑작스레 질문받은 내용이라 당황했던 적이 있었다.

알고있었던 내용이라 답변은 잘 했으나... 끝나고나서 다시 점검해볼만큼 기본기가 아직 충분치 못한 것 같아 정리해둔다.

컴파일 과정은 사람이 이해할 수 있는 High Level Programming Language 로 구성된 소스코드를 기계가 이해할 수 있는 Lower Level Language 로 바꾸는 과정이다.

컴파일러는 다음과 같은 과정을 통해 컴파일을 수행한다.

[출처 : https://www.programcreek.com/2011/02/how-compiler-works/]

위의 그림은 컴파일의 단계를 간략하게 설명한다. 다음은 그림에 대한 설명이다.

(1) Lexical Analysis 

소스코드를 Token 으로 분할한다. 모든 키워드와 Parenthesis, 변수들 및 괄호들을 분리해낸다.

(2) Syntax Analysis

앞선 단계에서의 스캔으로 만들어진 토큰들(Token Stream)의 문법을 분석하기 위한 자료구조료 변형한다.

이렇게 만들어지는 자료구조를 Parse Tree 라고 한다.

이 단계에서는 Token 이 Valid 한지 검출하지 못하며, Token 이 사용되기 이전에 정의 또는 초기화되어있는 지 등 정적분석은 불가능하다.

또한 이단계에서 파싱이 일어난다. Parsing 작업은 Top-Down, Bottom-Up 두가지 방식으로 나뉜다.

Top-Down Parsing 은 Parse Tree 의 윗쪽부터 파싱을 수행하며, Bottom-Up Parsing 은 트리의 아래쪽부터 파싱이 수행된다.

유명한 파서의 종류로 Top-Down 방식의 Non-Backtracking Predictive Parser 인 LL Parser와 Bottom-Up 방식의 LR Parser 가 존재한다.

(3) Semantic Analysis

각 기호들 및 구문들을 의미있는 값들로 변경한다. 가령 기호 < 는 bool 을 Return 하는 Operand 함수로,

While 과 같은 키워드는 반복 구조를 이루는 void 함수로, 각 변수는 메모리로 치환한다.

이 단계에서 Type 의 Mismatch 나, 변수의 미정의, 파리미터 미정의 등 문법적 요소들이 검증된다.

(4) IR Generation

구문 분석으로 이루어진 자료를 중간 언어로 변경하는 작업을 수행한다.

IR 은 Intermediate Representation 의 약어로 소스코드에 근접한 기계어인 High Level IR, 타겟 머신에 종속적으로 디자인된 Low Level IR 이 존재한다.

컴파일러는 소스코드를 High Level IR -> Low Level IR 로 변경한 뒤 Target Machine Code 로 해석한다.

(5) IR Optimization

중간 언어를 최적화한다. 불필요한 루프를 없애거나, 사용하지 않는 변수의 정리 등이 수행된다.

(6) Code Generation

Syntax Analyzer 및 Semantic Analyzing 된 출력값을 Low level Code 로 해석한다.

이 단계를 거쳐서 Assembly Code 등의 Object Code 로 번역된다.

이 단계에서 수행되는 작업들은 다음과 같다.

 - Instruction Selection : 어떤 명령어를 사용할 것인지

 - Instruction Scheduling : 어떤 명령어를 먼저 실행할지 (최적화)

 - Register Allocation : 변수들을 프로세서 레지스터에 할당

 - Debug data generation : 디버그 모드인 경우 디버그를 위한 코드를 생성

(7) Optimization

위의 과정에서 생성된 코드를 한단계 더 최적화한다.

이 단계의 최적화는 두단계로, Machine 에 종속되지 않은 일반적인 형태의 최적화와 Machine 에 종속된 최적화가 이루어진다.

이 과정을 거치면서 중복 제거, 메모리 확보, 코드 정리, 루프 최적화, Control Flow 개선이 일어난다.

위의 단계들을 거치면 High Level Source Code 는 Machine Code 로 변환된다.

Generating 되는 코드는 대게 머신별로 다르게 되며, 세부로직 및 최적화의 과정 역시 컴파일러에 따라 차이가 존재하게 된다.

본 포스팅은 컴파일러에 대한 간략한 소개를 다루고 있으며 더 자세한 내용은 다음 링크들을 참조한다.

(이해해야할 분량이 많다.)

참조

https://www.tutorialspoint.com/compiler_design/index.htm

https://www.programcreek.com/2011/02/how-compiler-works/