Post

[V8] Feedback Vector & Inline Cache

[V8] Feedback Vector & Inline Cache

JavaScript는 동적 타입 언어이기 때문에 같은 코드라도 실행할 때마다 서로 다른 형태의 객체가 값이 들어온다.

1
2
3
function getX(obj) {
  return obj.x;
}

obj.x에 접근하려면 V8은 일반적으로 다음과 같은 정보를 확인해야 한다.

  • obj는 어떤 객체인가
  • obj의 Map은 무엇인가
  • x 프로퍼티는 어디에 저장되어 있는가

하지만 getX()가 수천 번 호출되고 항상 비슷한 형태의 객체가 들어온다면 매번 처음부터 프로퍼티를 탐색하는 것은 비효율적이다.

V8은 이런 문제를 해결하기 위해 실행 중 관찰한 정보를 저장하고 재사용한다.

이때 중요한 개념이 Feedback Vector와 Inline Cache이다.


Feedback

1
2
3
function add(a, b) {
  return a + b;
}

JavaScript에서 + 연산은 정수 덧셈만이 아니라 문자열도 이어 붙일 수 있기 때문에 같은 코드에 다른 타입이 들어올 수 있다.

V8은 처음 코드를 실행할 때 a와 b가 number라고 확정지을 순 없기 때문에 실제 실행을 관찰하면서 어떤 타입이 들어왔고 프로퍼티 엑세스에서는 어떤 Map이 들어왔고… 등의 정보를 수집하게 된다.

이러한 실행 정보를 Feedback이라고 한다.


Feedback Vector

Feedback Vector는 함수 실행 과정에서 수집된 Feedback을 저장하기 위한 자료구조이다. 각 연산 위치마다 실행 과정에서 관찰한 정보를 저장하고, 다음과 같이 생각할 수 있다.

각 함수의 property access site에서 관찰되는 객체 구조가 다를 수 있기 때문에 property의 정보만을 저장하는 것이 아니라 특정 함수의 특정 연산 위치에서 어떤 값이 관찰되는가를 기록하는 것이 중요하다.

1
2
3
slot 0 - obj.value에 대한 feedback
slot 1 - 연산에 대한 feedback
slot 2 - ...

각각의 슬롯을 Feedback Slot이라고 한다.

Slot

Ignition Bytecode를 보면 다음과 같이 숫자가 붙어 있는 명령을 볼 수 있다.

1
GetNameProperty a0, [0], [1]
  • a0 -> property를 읽을 객체
  • [0] -> property name 관련 constant
  • [1] -> feedback slot

즉 코드가 Ignition에서 실행될 때 해당 실행 위치에 대한 Feedback도 함께 관리한다.


Inline Cache

Inline Cache는 반복되는 연산에서 이전에 얻은 정보를 재사용하여 같은 작업을 더 빠르게 수행하기 위한 최적화 기법이다.

특히 다음과 같은 연산에서 중요하다.

  • Property Load
  • Property Store
  • Method Call
1
2
3
function getX(obj) {
  return obj.x;
}

처음 obj.x를 실행할 때 V8은 obj의 구조를 알지 못한다.

따라서 실제 property lookup을 수행해야 한다.

1
obj -> Map 확인 -> x 탐색 -> property 위치 확인 -> 값 load

그런데 실행 결과를 통해 Map A를 가진 객체에서 x는 특정 위치에 존재한다 라는 사실을 알게 되면 다음에 다시 Map A를 가진 객체가 들어왔을 때 이전 정보를 재사용할 수 있다.

그러면 기존에 알아낸 방식으로 바로 x를 load 하고 이러한 방식이 Inline Cache이다.


IC Miss & IC Hit

IC Miss

처음 보는 객체 구조이거나 기존 Cache를 사용할 수 없는 경우이다.

1
obj -> Map 확인 -> 기존 정보 없음 -> IC Miss -> 일반적인 Property Lookup -> 결과를 feedback에 기록

이 과정은 상대적으로 느리다.

IC Hit

이미 관찰했던 형태의 객체가 다시 들어오는 경우이다.

1
obj -> Map 확인 -> 기존 Map과 일치 -> IC Hit -> Cached Handler 사용 -> 빠르게 값 Load

이 경우 반복적인 lookup 과정 일부를 생략할 수 있다.


Monomorphic

1
2
3
4
5
6
7
8
9
10
11
function getX(obj) {
  return obj.x;
}

let a = {x:1};
let b = {x:2};
let c = {x:3];

getX(a);
getX(b);
getX(c);

a, b, c가 같은 구조를 가지고 같은 Map을 사용한다. 그러면 getX()의 obj.x 위치에서는 계속 같은 Map만 관찰된다.

1
2
3
getX()

obj.x -> Map A -> Map A -> ...

이런 상태를 Monomorphic이라고 한다. 즉 해당 연산 위치에서 사실상 하나의 객체 형태만 관찰되는 것이다.

가장 예측하기 쉬운 상태이며 V8 입장에서도 최적화하기 좋은 상황이다.


Polymorphic

이번에는 서로 다른 구조의 객체가 들어온다.

1
2
3
4
5
6
function getX(obj) {
  return obj.x;
}

getX({x:1});
getX({x:2, y:3});

두 객체는 property 구조가 다르기 때문에 서로 다른 Map을 가질 수 있다. 그러면 해당 property access site에서는 여러 Map을 처리한다.

이러한 상태를 Polymorphic이라고 한다.


Megamorphic

더 많은 종류의 객체가 계속 들어온다면 상황이 달라진다.

1
2
3
4
5
6
7
8
function getX(obj) {
  return obj.x;
}

getX({x:1}); 
getX({a:1, x:2}); 
getX({b:1, c:2, x:3}); 
getX({d:1, x:4});

매번 다른 Map이 관찰된다면 특정 몇 개의 Map만 저장해서 처리하는 것이 점점 비효율적이 된다.

이런 경우 IC는 Megamorphic 상태가 된다.

1
UNINITIALIZED -> MONOMORPHIC -> POLYMORPHIC -> MEGAMORPHIC

다만 실제 V8 내부 상태 전이는 연산 종류나 현재 구현에 따라 세부적으로 달라질 수 있다.


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