V8 Engine : Ignition + TurboFan Pipe Line
V8 Engine Overview
V8 엔진은 Google이 개발한 오픈소스로 가장 대중적인 자바스크립트 엔진이다. C++, 어셈블리어로 개발하였고 Node JS와 Chrome 브라우저의 엔진으로 구동된다.
그런데 엔진이란 말은 무슨 말인가? 자동차 엔진을 생각해보면, 엔진이 없으면 자동차가 구동될 수 없다. 그러므로 Node.js와 Chrome browser 또한 V8 Engine이 없으면, JS 코드가 실행(구동) 될 수 없는 것이다. JS 코드를 실행시키기 위해서는 컴퓨터의 두뇌이자 실행자인 CPU가 이해할 수 있는 0과 1로 이루어진 바이너리 형태의 machine code로 변환이 필요하다. 따라서 V8 Engine의 핵심적인 역할이 JS 코드를 machine code로 변환 해주는 것이다. 또한 V8 엔진은 object에 대한 memory를 allocate하고 garbage collection을 통하여 더 이상 사용하지 않는 메모리를 회수한다.
V8 Engine Work Flow
V8 Engine에서 JS source code가 실행되는 flow는 아래의 그림과 같다. 해당 flow는 크게 paser가 수행하는 parsing, ignition과 turbofan이 수행하는 ignition + turbofan pipeline 두 과정으로 나눌수 있다. 아래의 내용 부터는 V8 엔진의 동작 원리의 흐름대로 내용이 진행된다. 그중에서 Ignition + TurboFan Pipeline 위주로 설명할 것이다.
Parsing
Parsing 과정이 끝나면, 프로그래밍 언어의 문법에 따라 소스 코드 구조를 계층과 종류 별로 표시한다. 그렇다면 이렇게 문법에 따라 계층과 종류별으로 표시하는 이유는 무엇인가?
다음은 대한법룰구조공단의 조직도이다. 아래 처럼 직급에 따라 계층을 나누고, 부서에 따라 조직을 나누면 한눈에 조직을 파악할 수 있다. 이처럼 계층과 종류 별로 구조화한 형식은 빠르게 정보를 파악할 수 있는 아주 좋은 형태이다.
이제 본격적으로 parsing 과정을 살펴보자. V8 Engine의 parsing 과정은 크게 lexical analysis와 syntax analysis 과정으로 진행된다. Parsing을 하는 주체인 parser는 lexical analyzer와 syntax analyzer가 존재한다.
lexical analysis
첫번째로 Lexical analyzer는 소스 코드를 문자 단위로 하나하나 스캔하며 공백 단위로 분할하여 이를 token으로 분할한다.
function a(n) {
if (a > 0) {
return a + 1;
} else {
return a - 2;
}
}위의 소스코드는 아래와 같이 token으로 나눠진다.
// token
'function' 'a' '(' 'n' ')' '{' 'if'...syntax analysis
두번째로 syntax analyzer는 parsing을 하여, 분해한 token들을 분석하고 syntax 규칙에 따라 token들이 계층화와 그룹화하여 AST(Abstract Syntax Tree)으로 만든다. 아래의 사진과 같이 AST의 구조를 볼 수 있다.
Ignition + TurboFan Pipeline 과정
아래서 부터는 Innition과 TurboFan의 파이프라인 과정이다. 동작원리 위주로 자세히 설명하였다. 차근 차근 읽어보시기 바랍니다.
Ignition : Generate Bytecode
직전의 사진과 같이 AST으로 구문을 구조화한 후에, V8의 Ignition의 bytecode compiler가 AST를 byte code로 컴파일한다. 그런 다음 Ignition의 Interpreter가 bytecode를 한줄씩 읽으며 실행시킨다. Ignition은 이렇게 byte code compiler와 Interpreter 두 역할을 수행한다.
그렇다면 Ignition이 컴파일하여 생성한 bytecode는 무엇일까? 간단하게 말하면, Byte code는 machine code를 추상화 한것이다. Machine code를 추상화하였으므로 컴파일시 machine code로 변환이 매우 빠르다.
CPU에 독립적으로 machine code와 맵핑되는 어셈블리어라고 생각하면 된다.
function add10(n) {
const x = 10;
return x + n;
}
console.log(add10(5)); // V8's compiler is lazy, if you don't run a function, it won't interpret it.위의 js 파일을 아래의 명령어를 통해 바이트 코드로 변환하여 바로 확인해보자. 그러면 아래와 같이 바이트 코드가 생성된 것을 볼 수 있다.
$ node --print-bytecode --print-bytecode-filter=add10 index.js
1570 S> 0x25e2b84e32b8 @ 0 : 0d 0a LdaSmi [10]
0x25e2b84e32ba @ 2 : c4 Star0
1578 S> 0x25e2b84e32bb @ 3 : 0b 03 Ldar a0
1587 E> 0x25e2b84e32bd @ 5 : 39 fa 00 Add r0, [0]
1591 S> 0x25e2b84e32c0 @ 8 : a9 ReturnLdaSmi [10], Star0 바이트 코드이며, 0d, 0a 과 매핑되어있다.LdaSmi [10], Star0는 마치 어셈블리와 비슷하게 생겼다. 또한 바이트 코드는 0d, 0a 16진수로 표현되며, 내부적으론 2진수로도 표현될 것이다.
위의 바이트 코드에서 LdaSmi, Add는 opcode 해당하는 명령어를 볼 수 있다. 연산에 해당하는 opcode에 대한 처리는 결국 CPU가 하는 것이다. 그러므로 CPU가 연산처리를 하기 위해서는 CPU 아키텍쳐에 맞는 native machine code가 필요하다.
CPU 제조사의 설계한 아키텍쳐마다 명령어가 다르며, 명령어 종류 또한 다르다. x86과 같은 CISC(Complex Instruction Set Computer) 아키텍쳐는 비교적 복잡하고 긴 명령어와 명령어의 개수가 많은 편이다. 그에 반해, ARM와 같은 RISC(Reduced Instruction Set Computer) 아키테쳐는 비교적 간단하고 짧은 명령어와 개수가 적은편이다.
따라서 바이트 코드는 아키텍쳐가 다른 CPU의 명령어(기걔어)와 1:1로 맵핑되는 어셈블리어와 다르다. 또한 OS도 CPU와 호환이 되어야한다. OS는 CPU가 제공하는 명령어 세트와 기능을 활용하여 컴퓨터 자원 관리(프로세스 스케줄링, 메모리 관리, 입출력 제어 등)를 수행을 하기 때문이다.
하지만 바이트 코드는 CPU 아키텍쳐와 독립적이 코드이며, Interpreter인 ignition은 한줄씩 읽으며 바로 실행이 가능하다고 한다. 어떻게 그게 가능한 것일까?
TurboFan: Macro Assembly Instruction of bytecode for Ignition
이전 설명에는 byte code는 machine code를 추상화 한것이라고 했지만 정확하게 원리를 알아보자.
바이트 코드에서 LdaSmi, Add는 CPU 아키텍쳐에 따라 이해할 수 있는 어셈블리어의 opcode로 변환이 필요하다. TurboFan는 컴파일러로서 여러 CPU 아키텍쳐와 호환되어 1:1로 맵핑되는 어셈블리어가 내재되어있다. 따라서 Ignition 인터프리터는 opcode에 대한 Byte code handler를 생성하기 위해, TurboFan을 통하여 CPU의 아키텍처 독립적인 매크로 어셈블리 명령어를 제공받을수 있다. Byte code handler를 통해 byte code의 opcode를 macro assembly instruction 매핑시키고 Ignitioin Interpreter에게 전달한다.
다시 한번 정리하자면, TurboFan은 명령어를 대상 아키텍처로 컴파일하여 low-level 명령어 선택한다. 그 결과, 코드베이스에 최소한의 새로운 machine code만 추가되면서 바이트코드 명령어를 실행하고 낮은 오버헤드 방식으로 나머지 V8 가상 머신과 상호작용할 수 있는 고도로 최적화된 인터프리터 코드가 생성된다.
Ignition: Machine Register
Ignition Interpreter의 동작 과정을 보기 이전에 알아둬야할게 있다. Ignition는 register-based interpreter이다. Ignition은 register machine을 사용한다. Register machine이란, hardware에 존재하는 register를 추상화시켜 virtual register를 구현한 것이다. 여러 virtual register가 존재하며, 그 중 accumulator와 일부 레지스터는 CPU의 physical register에 매핑되고 다른 일부는 native machine stack memory 안의 특정 슬롯에 매핑된다. Accumulator는 연산과정에서 임시적인 저장 바구니 역할으로서, 연산작업에서 I/O로 사용한다.
아래 그림 처럼 physical register를 가리키는 Interpreter local state를 유지하며, 나머지 virtual register는 Machine stack memory에 저장된다.
왜 ignition은 하드웨어 구성 요소인 register를 소프트웨어적으로 구현하였을까? 인터프리터는 바이트코드를 한줄씩 읽으면서 실행시키기 때문에, 컴파일 보다 속도가 느릴수 밖에 없다. 읽고 실행하는 과정에서 스왑에 대한 오버헤드가 있기 때문이다.
최대한 실행 속도를 빠르게 하기 위해서, 하드웨어의 아키텍처를 소프트웨어에서 구현한 것이다. 그리하면 인터프리터는 하드웨어와 실행 프로세스가 유사하여 더 빠른 속도로 바이트 코드를 실행할 수 있다.
또한 레지스터에 다이렉트로 접근하여, 메모리 접근도 최소화되기 때문에 속도도 빠르다.
TurboFan는 레지스터와 관련해서도 역할을 하는데, 추상화된 register machine 할당을 수행한다. Register machine 할당이란, 가상 레지스터를 실제 하드웨어의 물리적인 레지스터에 할당시키는 것이다.
Ingition: Interpretation Procedure
이제 Ingition의 Interpretation 과정을 살펴보자. 다시 위의 js 소스 코드와 그에 대한 바이트 코드를 다시 가져왔다.
function add10(n) {
const x = 10;
return x + n;
}
console.log(add10(5));$ node --print-bytecode --print-bytecode-filter=add10 index.js
[generated bytecode for function: add10 (0x1867f4fe2179 <SharedFunctionInfo add10>)]
Bytecode length: 9
Parameter count 2
Register count 1
Frame size 8
OSR urgency: 0
Bytecode age: 0
1578 S> 0x1867f4fe3450 @ 0 : 0d 0a LdaSmi [10]
0x1867f4fe3452 @ 2 : c4 Star0
1586 S> 0x1867f4fe3453 @ 3 : 0b 03 Ldar a0
1595 E> 0x1867f4fe3455 @ 5 : 39 fa 00 Add r0, [0]
1599 S> 0x1867f4fe3458 @ 8 : a9 Return
Constant pool (size = 0)
Handler Table (size = 0)
Source Position Table (size = 11)
0x1867f4fe3461 <ByteArray[11]>아래는 바이트 코드의 실행 절차이다. 인지하고 있어야 할 점은 accumulator(register)에서 I/O 작업이 수행된다는 것이다.
LdaSmi [10]
Ld는 Load의 약자이고, a는 accumulator이다. 그리고 Smi는 Small integer이다. accumulator에 상수 값 10을 로드하는 것이다.
2. Star0
현재 accumulator에 있는 값 10을 레지스터 r0 에 저장하는 것이다. St는 Store의 약자,a는 accumulator 이고 ri는 i번째 register이다.
3. Ldar a0
Ldar a0에서 ai는 add10(n) 의 i번째 argument를 가리킨다. 따라서 첫번째 argument에 있는 값을 accumulator에 로드하는 것이다.
4. Add r0 [0]
Accumulator에 0번째 register에 있는 값을 더하란 뜻이다. 여기서 [0]은 피드백 벡터(feedback vector)의 인덱스이다. 피드백 벡터는 TurboFan이 수행하는Inline Caching과 같은 성능 최적화에 사용되는 정보들이 저장되어 있는 데이터 구조이다. 여기서는 바이트 코드의 실행 절차를 살펴보고 있기 때문에 생각하지 않아도 된다. 뒤에 나올 인라인 캐싱 섹터에서 설명할 것이다.
5. return
Accumulator에 있는 값을 return 하는 것이다.
TurboFan Optimze
V8의 Ignition은 바이트 코드를 실행하면서 Profiler를 통해, 반복되는 함수나 객체가 사용되는지 정보를 수집한다. 이렇게 수집한 profiling data와 byte code를 TurboFan에 넘긴다. 만일, 바이트 코드가 반복 실행이 많이 되서 Ignition이 뜨거워졌다면, TurboFan이 optimzed machine code를 생성 및 실행시켜서 Igntion의 쿨링팬과 같은 역할을 한다.
이처럼 V8 Engine은 소스코드를 한줄씩 변환하는 Interpreter(Ignition) 방식과 소스코드를 런타임에 기계어로 변환하는 Compile(TurboFam) 방식이 혼합된 JIT(Just In Time Compilation)을 사용한다.
컴파일시, TurboFan의 최적화 기법에는 대표적으로 Hidden Class나 Inline Caching 등을 사용한다. Hidden Class는 말그대로 숨겨진 클래스라고 생각하면된다. 템플릿처럼 비슷한 형태의 객체끼리 분류 해놓고 가져다 쓰는 것이다. Inline Caching 는 반복적인 코드를 machine code로 최적화 시키고 캐싱하여, 다음 코드 실행 부터는 매우 빠르게 실행될 수 있게 하는 기법이다.
Hidden Class
Hidden Class를 설명하기전에 JavaScript의 객체에 대해 먼저 살펴보자. JavaScript Pack을 살펴보면, JS 객체는 문자열의 key와 value가 있는 dictionary이다. 그리고 Value는 Property attribute이란 프로퍼티의 스펙과 맵핑되어 있다. 이것이 자바스크립트가 객체를 보는 방식이다.
위 그림의 객체의 문자열 x와 y는 dictionary의 key이다. 그리고 5와 6와 같은 Value는 Property attriubutes에 포함되어 있다. 즉, JS엔진에서 JS 객체의 Value에 접근하기 위해서는 다음과 같은 과정이 필요하다. JS엔진은 객체에 접근하고 내부의 key를 찾고 Property attributes에 접근하여 Value를 로드해야한다.
Property attributes는 프로퍼티의 고유의 속성이다. Value를 포함하여 Writeable, Enumerable, Configurable은 ECMAScript의 스펙이다. 아래 처럼 코드를 프로퍼티의 스펙을 확인해 볼 수 있다.
const obj = {
x: 1,
y: 1,
};
for (let prop in obj) {
const propDescriptor = Object.getOwnPropertyDescriptor(obj, prop);
console.log(`Property: ${prop}, Attributes: ${JSON.stringify(propDescriptor)}`);
}
// Property: x, Attributes: {"value":1,"writable":true,"enumerable":true,"configurable":true}
// Property: y, Attributes: {"value":1,"writable":true,"enumerable":true,"configurable":true}두 개의 객체가 비슷한 형태를 가질 경우에는 어떤 결과가 발생할까?
아래의 JS 코드를 보면, a와 b객체가 동일한 프로퍼티 Key를 가지고 있다. 두 객체 모두 형태(Shape)가 같은 것이다. 같은 shape을 가졌지만 a와 b 대한 객체 각각 따로 메모리에 할당을 해줘야한다. 이렇게 되면 메모리 낭비가 발생한다.
const a = {
x: 1,
y: 1,
};
const b = {
x: 3,
y: 4,
};따라서 아래와 같이 shape 인스턴스를 하나 생성한 후에, JS 객체는 shape 인스턴스를 거쳐 Property infomation에 접근하고 offset으로 프로퍼티의 Value을 찾을 수 있다. 여기서 눈을 부릅뜨고 봐야할것은 Shape가 없었으면, property attributes가 4개가 생성되었다. property attributes는 프로퍼티의 고유의 속성이다. Shape 개념을 도입하여 위의 사진에 property attributes가 property infomation으로 바꼈다. property infomation는 프로퍼티에 대한 정보를 저장하고 offset으로 각 객체의 프로퍼티 값을 찾을 수 있다.
이제까지 부르던 shape는 Hidden Class라고 한다. 숨겨진 클래스 개념이 도입되어 shape는 인스턴스로서 역할을 하는 것이다. 이로인해 불필요한 메모리 낭비를 줄였다.
그런데 JavaScript은 동적 타입 언어이다. 아래와 같이 객체 안의 프로퍼티의 개수나 크기가 정해지지 않았다. 동적으로 프로퍼티와 메소드의 추가/삭제가 발생할 수 있다. 그러므로 객체는 메모리 공간에서 크기를 고정할 수 없다. 그렇다면 객체가 변경될때 마다, 여러 shape 인스턴스를 만드는 것은 메모리 낭비로 이어진다. 아래 그림과 같이 위의 o객체 동적으로 프로퍼티를 추가했을때, 나타는 shape 인스턴스들이다.
// empty
let o = {};
// shape (x)
o.x = 5;
// shape (x, y)
o.y = 6;JS 객체는 마지막으로 변경된 shape를 가리키고, 이전의 객체에 추가되었던 프로퍼티의 key를 찾아 링크를 타고 참조할 수 있다. 이것을 'Transition Chain' 이라고 부른다.
또한 현재의 프로퍼티의 Key는 다르지만, 이전에 동일한 shape를 가졌던 객체도 아래와 같은 구조로 나타난다. 이전에는a, b모두 빈 객체였기 때문이다. 이것을 'Transition Tree' 라고 부른다.
마지막으로 정리하자면, Hidden Class는 객체의 메모리를 줄이는 핵심적인 최적화 기법이다.
Inline Caching (ICs)
위의 shape개념은 Inline Caching에서 효과가 극대화 된다. JS 엔진은 Inline Caching을 사용하여 객체의 프로퍼티를 찾을 수 있는 정보를 기록해둔다. 따라서 프로퍼티를 조회할때, 반복적인 프로퍼티에 대한 메모리 참조 시간을 줄여준다. 그리고 Inline Caching은 이렇게 반복적인 프로퍼티를 컴파일도하여 저장해놓는다.
Inline Caching은, 주로 반복적인 코드나 용량이 큰 함수가 최적화 우선순위이다.
Inline Caching의 전체적인 맥락을 아래와 같다. f(a) 함수의 호출을 하면, 해당 함수를 찾기위해 Call Stack을 참조한 후에 , function f(a) { ... } 함수 안의 코드에 대한 객체 등을 찾기위해 또 Heap 영역을 참조를 하게된다. 이런 접근에 대한 시간을 줄이기 위해 함수 호출부에 함수 구현부를 삽입하는 방식이다. 따라서 Inline Caching 실행 속도를 최적화 하는데 핵심적인 기법이다.
아래의 코드로 예제를 들어보겠다.
function getX(o) {
return o.x;
}
getX({x : 'a'});위의 함수를 호출하면 JSC(JavaScriptCore)에서 아래의 그림과 같이 byte code를 생성한다. 참고로 JSC는 safari에서 쓰는 JS Engine이다.
아래의 그림을 보면, 첫 번째 명령문 get_by_id는 arg1(1번째 argument)에서 property x를 로드하여 결과를 loc0에 저장하라는 명령어이다. 첫번째 명령문에 초기화되지 않은 두 개의 슬롯에 메모리 공간을 할당한다. 두 번째 명령문은 loc0에 저장한 것을 반환하라는 명령어이다.
아래의 그림을 보면,getX({ x: 'a' }) 함수가 호출되고 실행하면, 객체에서 객체의 shape에 접근하고 내부에서 x를 검색한다. 이후 Property information을 로드하고 offset을 결정한 다음에, 다시 객체로 돌아가 offset에 value를 로드해야한다. 이런 작업에는 많이 비싼 cost loop가 발생하는 것을 알 수 있다.
아래의 그림을 보다시피 JS엔진은 이미 이작업을 수행하여, 다음 호출시 재사용을 할수 있다. 그것이 바로 Inline Caching이다. 아래의 그림에서 처럼 바이트 코드에 포함된 두개의 슬롯에 shape와 offset을 저장한다. 그리하면 다음번 같은 shape를 가진 객체에 접근할때는 IC가 적용되어 매우 빠르게 접근이 가능하다.
이전의 getX({ x: 'a') 호출 이후에, 동일한 shape인 getX({ x: 'b')가 호출되어도 IC가 적용되었다. getX({ x: 'b' }) 함수가 호출되고 실행하면, 객체에서 객체의 shape에 접근하고 바로 다시 객체로 돌아가 offset에 value를 로드한다. 프로퍼티의 value를 읽는 과정이 많이 단순화 되었고 훨씬 속도도 빨라질 수 있는 것이다.
이제까지 JSC 엔진의 Inline Caching의 동작원리에 대해서 설명하였는데, V8 엔진도 동일하다. 다음은 이전의 Interpretation 과정을 살펴볼때, Add r0 [0] 바이트 코드에서 [0]에 대해 피드백 벡터feedback vector라고 언급했었다. Add r0 [0]은 r0에 있던 값을 accumulator에 더하란 명령어이다. 그[0] 은 명령어를 수행하는데 불필요한 것일까?
TurboFan는 Inline Cache에 있는 데이터를 Feedback이란 데이터 구조에 저장한다.
아래의 그림 처럼, 바이트 코드에서 [0]은 위의 Feedback의 vector의 index이다. 바이트 코드가 처음 실행하여 인라인 캐싱을 수행할지 말지 결정하는 알고리즘을 충족하면, Feedback에 해당 바이트 코드에 대한 정보를 저장한다. 그 이후 해당 바이트 코드에서 feedback vector의 index가 있다면, [i]을 통해 Feedback로 참조하여 인라인 캐싱된 machine code를 실행한다.
TurboFan Deoptimize
그렇다면 deoptimze는 언제 발생하나?
Optimized machine code가 준비중인데, 타입 변환이 일어났을 경우이다. 컴파일된 코드가 동적 변환이 발생한다면, 다시 바이트코드로 전환해야하기 때문에 deoptimize 발생한다. Ignitioin(interpreter)가 바이트 코드로 다시 전환하기 때문에, deoptimize가 발생된다면 꾀나 비용이 들어간다. 그럼므로 타입 변환을 줄이고 런타임에 프로퍼티를 추가하는 것은 지양해야 한다. 결국 최대한 동적 행위를 없을 수록 최적화에서 이점을 얻을 수 있다.
References
