Post

[V8] TurboFan

[V8] TurboFan

Ignition은 JavaScript를 Bytecode로 변환하여 실행한다.

하지만 Bytecode를 하나씩 해석하면서 실행하는 방식은 빠르게 실행을 시작할 수 있다는 장점이 있는 대신 동일한 코드가 반복될 경우 성능이 떨어질 수 있다.

1
2
3
4
5
6
7
function add(a, b) {
  	return a + b;
}

for (let i = 0; i < 10000; i++) {
  	add(i, i + 1);
}

add()는 계속 반복적으로 실행된다.

이런 함수를 매번 같은 방식으로 해석해서 실행하기보다는 해당 함수에 대해 최적화된 기계어를 만들어 직접 실행하는 것이 훨씬 빠를 수 있다.

이러한 최적화를 담당하는 V8의 top tier optimizing compiler가 TurboFan이다.


V8의 실행 구조

현재 V8은 여러 실행 계층을 사용한다.

1
JavaScript -> Parser -> Ignition -> Sparkplug -> Maglev -> TurboFan -> Optimized Machine Code

Ignition은 빠르게 JavaScript를 실행하기 시작하는데 유리하고 TurboFan 쪽으로 갈수록 컴파일에는 더 많은 비용이 들지만 더욱 최적화된 기계어를 만들 수 있다.

그렇다고 모든 함수를 TurboFan으로 최적화하는 것은 아니다.

한두번밖에 실행되지 않는 함수를 복잡하게 분석하고 최적화한다면 오히려 컴파일 비용이 더 커질 수도 있기 때문이다.

따라서 V8은 실행 빈도 등의 정보를 이용하여 자주 실행되는 코드를 상위 티어로 올린다.

이러한 코드를 흔히 Hot Code, 함수를 Hot Function이라고 부른다.


최적화

JavaScript는 동적 타입 언어이기 때문에 a + b를 실행한다고 했을 때 a와 b가 정수인지 문자열인지 실수인지 확정할 수 없다.

V8은 JavaScript를 빠르게 만들기 위해 실제 실행 결과를 관찰한다.


Feedback

전에 공부했던 Feedback Vector와 Inline Cache가 여기서 나온다.

예를 들어 어떤 함수를 계속 같은 자료형을 주면서 실행한다고 했을 때 V8은 함수에 이 자료형이 들어오고 있다는 정보를 Type Feedback으로 활용할 수 있다.

이것이 Speculative Optimization으로 이어진다.


Speculative Optimization

Speculative는 추측을 기반으로 한다는 의미이다.

TurboFan은 실행하면서 수집한 정보를 보고 이 함수에는 이 자료형만 들어왔으니까 앞으로도 이럴 것이다 라고 생각할 수 있다.

그리고 이 가정을 기반으로 더욱 빠른 코드를 생성한다.

쉽게 말해서 TurboFan의 핵심 기능은 실행 중 얻은 정보를 기반으로 가정을 세우고 그 가정에 특화된 빠른 코드를 생성하는 것이다.


Intermediate Representation

TurboFan이 JavaScript 코드를 최적화한다고 해서 JavaScript를 바로 x86-64와 같은 기계어로 바꾸는 것은 아니다.

중간에 IR(Intermediate Representation)이라는 내부 표현을 사용한다.

컴파일러에서 IR은 소스코드와 기계어 사이에서 프로그램을 표현하는 형태이다.

TurboFan은 역사적으로 Sea of Nodes라는 그래프 기반 IR을 사용해왔다.


Sea of Nodes

TurboFan의 IR에서는 연산 Node로 표현된다.

Node 사이의 Edge에는 다음과 같은 의존성이 존재한다.

  • Value Dependency
  • Effect Dependency
  • Control Dependency

Value Dependency

값 자체의 관계이다.

1
let c = a + b;

라면 Add node는 a, b의 값을 필요로 한다.

1
2
3
a
	-> Add
b

Effect Dependency

메모리 접근처럼 실행 순서를 마음대로 바꾸면 안 되는 연산을 표현한다.

1
2
obj.x = 10;
console.log(obj.x);

에서 두 연산의 순서를 바꾸면 프로그램의 의미가 달라진다.

따라서 이러한 Side Effect가 존재하는 연산들은 Effect 관계를 통해 순서가 관리된다.

Control Dependency

조건문이나 분기처럼 프로그램의 실행 흐름과 관련된 관계이다.

1
2
3
if (x > 10) {
	foo();
}

에서 foo()가 실행되려면 먼저 x > 10이라는 조건을 통과해야 한다.

이러한 실행 흐름 역시 그래프에서 표현된다.


TurboFan의 최적화

IR이 만들어졌다면 TurboFan은 그래프를 분석하면서 여러 최적화를 수행할 수 있다.

Constant Folding

1
2
3
function foo() {
  	return 10 + 20;
}

10 + 20은 런타임에 계산할 필요가 없다.

컴파일 시점에 이미 결과를 알 수 있기 때문에 10 + 20을 30으로 바꿀 수 있다.

이를 Constant Folding이라고 한다.


Dead Code Elimination

절대로 사용되지 않는 코드가 있다면 제거할 수도 있다.

1
2
3
4
5
6
function foo() {
  	let x = 10;
  	let y = 20;
  
  	return x;
}

y가 실제 프로그램의 결과에 영향을 주지 않으므로 연산을 제거할 수도 있다.


Inlining

1
2
3
4
5
6
7
function add(a, b) {
  	return a + b;
}

function foo(x) {
  	return add(x, 10);
}

매번 실제로 add()를 호출하는 대신 조건이 적절하다면 함수의 내용을 호출 위치에 직접 넣을 수도 있다.

1
2
3
function foo(x) {
  	return x + 10;
}

와 같은 형태로 만들 수 이다.

이를 Inlining이라고 한다.

함수 호출에 필요한 Overhead를 줄일 수 있고 Inlining 이후 추가적인 최적화가 가능해진다는 장점도 있다.


Type 추론

TurboFan 최적화에서 특히 중요한 것이 Type Information이다.

예를 들어 어떤 값이 분석 결과 Signed32 범위라는 사실을 알 수 있거나 더 구체적으로 Range(0, 100) 처럼 가능한 값의 범위를 추론할 수도 있다.

이러한 정보가 많아질수록 컴파일러는 더 공격적인 최적화를 수행할 수 있다.

예를 들어 값이 항상 특정 범위 안에 있다는 사실이 증명된다면 불필요한 검사 일부를 제거할 수도 있다.


Lowering

JavaScript의 연산은 처음에는 고수준이다.

항상 예를 들지만 만약 a + b라면 JavaScript에서 +는 Number 연산도 될 수 있고 String 연산도 될 수 있기 때문에 초기 IR에서는 비교적 고수준의 JavaScript 의미를 가진 연산으로 표현된다.

그리고 최적화를 진행하면서 더 구체적인 저수준 연산으로 변환된다.

이렇게 고수준의 연산을 점차 저수준의 연산으로 변환하는 과정을 Lowering이라고 한다.


Deoptimization

최적화할 때 세운 가정이 더 이상 맞지 않는다면 V8은 최적화된 코드를 그대로 실행할 수 없다.

이때 발생하는 것이 Deoptimization, 줄여서 Deopt이다.

예를 들어 어떤 함수에 같은 자료형만 들어와서 그에 맞게 최적화 되었다고 가정한다. 그런데 이후 이전과 다른 형태의 값이 들어온다면 기존 최적화 가정이 깨진다.

이 경우 V8은 optimized execution에서 빠져나와 프로그램의 정확한 JavaScript semantics를 보장할 수 있는 lower tier로 실행 상태를 복원한다.

따라서 전체 구조를 보면 다음과 같다.

1
Feedback 수집 -> TurboFan -> Speculative Optimization -> Check -> 가정 실패 -> Deoptimization

TurboFan과 Turboshaft

TurboFan은 역사적으로 Sea of Nodes IR을 중심으로 동작했지만 최근 몇 년 동안 TurboFan의 여러 부분을 새로운 Turboshaft IR로 이전하고 있다.

Turboshaft는 Sea of Nodes와 달리 좀 더 전통적인 CFG 기반 IR을 사용한다


This post is licensed under CC BY 4.0 by the author.