V8

Vyacheslav Egorov

[email protected]

V8 is a JS VM

used by Chrome & node.js

being a JavaScript VM
is not an achievement

being a fast VM is

the challenge


// Adding integers.
function add(a, b) {
  return a + b;
}


// Adding doubles.
function add(a, b) {
  return a + b;
}


// Concatenating strings.
function add(a, b) {
  return a + b;
}


// Arrays are just objects with
// properties "0", "1", "2", ...
Array.prototype[1] = "ha!";
var arr = [0, /* hole */ , 2];
arr[1] // => "ha!"


// Making a "class".
function Dog(name, breed) {
  this.name  = name;
  this.breed = breed;
}

Dog.prototype.woof = function () {
  /* ... */
};


// Inheriting from a class.
function Dog(name, breed) {
  Animal.call(this, name);
  this.breed = breed;
}

Dog.prototype =
   Object.create(Animal.prototype);


// Another way to create a dog.
var dog = {
  name: name,
  breed: breed,
  woof: function () { /* ... */ }
};


// Yet another way.
function makeADog(name, breed) {
  // name and breed are now "private"
  return {
    woof: function () { /* ... */ }
  }
}


// Yet another way.
var Dog = {
  woof: function () { /* ... */ }
};

function makeADog() {
  var dog = Object.create(Dog);
  dog.name = name;
  dog.breed = name;
  return dog;
}


// ES6 sugar
class Dog extends Animal {
  constructor(name, breed) {
    super(name)
    this.breed = breed;
  }

  woof() {
    /* ... */
  }
}

representation

resolution

redundancy

① representation

tagging to avoid boxing everything

pointer has "unused" bits
due to alignment

(e.g. if all objects are 8 byte aligned - b₃₁...b₃000)


/* pointer: x...xx1 */
function tag(ptr) { // ptr & 1 === 0
  return ptr | 1;
}

function untag(taggedVal) {
  return taggedVal & ~1;
}

function isPtr(taggedVal) {
  return (taggedVal & 1) === 1;
}


/* small integer: xx...x0 */
function tag(smiVal) {
  return smiVal << 1;
}

function untag(taggedVal) {
  return taggedVal >> 1;
}

function isSmi(taggedVal) {
  return (taggedVal & 1) === 0
}

Double
⇒ still boxing

NaN-tagging
(SM, JSC, LuaJIT2)
ARMv8 tagged pointers
(upper byte)

objects?

hidden classes

≈ maps from Self VM


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);


function Point(x, y) {
  this.x = x;
  this.y = y;
}

var p1 = new Point(1, 2);
var p2 = new Point(3, 4);
p2.z = 5;

static structure approximated dynamically.


var arr = [];
for (var i = 0; i < 101; i++)
  arr[i] = Math.sqrt(i);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);
arr[3] = "xyz";


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);
arr[3] = "xyz";


var arr = [];
arr[0] = Math.sqrt(0);
arr[1] = Math.sqrt(1);
arr[2] = Math.sqrt(2);
arr[3] = "xyz";

tracking denseness and unboxing


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1;
v.y += 1;


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1;
v.y += 1;


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1;
v.y += 1;

mutable boxes

what happens on read?


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1; v.y += 1;
while (true) v.x;


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1; v.y += 1;
while (true) v.x;


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1; v.y += 1;
while (true) v.x;


function Vec2(x, y) {
  this.x = x;
  this.y = y;
}
var v = new Vec2(0.1, 0.2);
v.x += 1; v.y += 1;
while (true) v.x;

only beneficial
if we can read unboxed


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };
// How hidden class of K.prototype looks like?


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };
// How hidden class of K.prototype looks like?


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };
// Want it to be more 'class'-like


// Want *fast* method calls.
// Don't want (pseudo-code)
m = LoadProperty(obj, "f")
CheckIfFunction(m)
Invoke(m, obj)


// Want *fast* method calls.
// Better:
CheckClass(obj, klass0);
Invoke(foo, obj);

promote functions
to hidden class


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };


function K() { }
K.prototype.f = function foo() { };
K.prototype.g = function bar() { };
// Now it's more like vtbl!

whole closure
is promoted!


// What is "perf-unfriendly" here?
function buyDog() {
  return {
    woof: function () {
      /* ... */
    }
  }
}

different `woof`
⇒different classes

not all objects
are structures

② resolution


function Load(receiver, property) {
 var O = ToObject(receiver);
 var P = ToString(property);
 var desc = O.[[GetProperty]](P);
 if (desc === $undefined) return $undefined;
 if (IsDataDescriptor(desc)) return desc.Value;
 assert(IsAccessorDescriptor(desc));
 var getter = desc.Get;
 if (getter === $undefined) return $undefined;
 return getter.[[Call]](receiver);
}

JSObject.prototype.[[GetProperty]] = function (P) {
 var prop = this.[[GetOwnProperty]](P);
 if (prop !== $undefined) return prop;
 var proto = this.[[Proto]];
 if (proto === $null) return $undefined;
 return proto.[[GetPropery]](P);
};

JSObject.prototype.[[GetOwnProperty]] = function (P) {
 return this.properties.get(P);
};


function Load(receiver, property) {
 var O = ToObject(receiver);
 var P = ToString(property);
 var desc = O.[[GetProperty]](P);
 if (desc === $undefined) return $undefined;
 if (IsDataDescriptor(desc)) return desc.Value;
 assert(IsAccessorDescriptor(desc));
 var getter = desc.Get;
 if (getter === $undefined) return $undefined;
 return getter.[[Call]](receiver);
}

JSObject.prototype.[[GetProperty]] = function (P) {
 var prop = this.[[GetOwnProperty]](P);
 if (prop !== $undefined) return prop;
 var proto = this.[[Proto]];
 if (proto === $null) return $undefined;
 return proto.[[GetPropery]](P);
};

JSObject.prototype.[[GetOwnProperty]] = function (P) {
 return this. properties.get(P);
};


function Load(receiver, property) {
 var O = ToObject(receiver);
 var P = ToString(property);
 var desc = O.[[GetProperty]](P);
 if (desc === $undefined) return $undefined;
 if (IsDataDescriptor(desc)) return desc.Value;
 assert(IsAccessorDescriptor(desc));
 var getter = desc.Get;
 if (getter === $undefined) return $undefined;
 return getter.[[Call]](receiver);
}

JSObject.prototype.[[GetProperty]] = function (P) {
 var prop = this.[[GetOwnProperty]](P);
 if (prop !== $undefined) return prop;
 var proto = this.[[Proto]];
 if (proto === $null) return $undefined;
 return proto.[[GetPropery]](P);
};

JSObject.prototype.[[GetOwnProperty]] = function (P) {
return this. properties.get(P);
};

tons of code
⊕
dictionary lookup

can we do better?

must do the first lookup

what about the second?

same hidden class
⇒ same structure

inline caching


;; Compiled code
mov eax, obj
mov ecx, "foo"
call LoadIC_Initialize


// Runtime system.
function LoadIC_Initialize(obj, prop) {
  var lookupResult = obj.lookup(prop);
  patch(lookupResult.compile());
  return lookupResult.value;
}


// Runtime system.
function LoadIC_Initialize(obj, prop) {
  var lookupResult = obj.lookup(prop);
  patch(lookupResult.compile());
  return lookupResult.value;
}


;; Compiled LoadIC Stub
0xabcdef:
cmp [eax - 1], klass0
jnz LoadIC_Miss
mov eax, [eax + 11]
ret
;; Compiled code
mov eax, obj
mov ecx, "foo"
call 0xabcdef ;; patched!


;; Compiled LoadIC Stub
0xabcdef:
cmp [eax - 1], klass0
jnz LoadIC_Miss
mov eax, [eax + 11]
ret

;; Compiled code
mov eax, obj
mov ecx, "foo"
call 0xabcdef ;; patched!


;; Compiled LoadIC Stub
0xabcdef:
cmp [eax - 1], klass0
jnz LoadIC_Miss
mov eax, [eax + 11]
ret

;; Compiled code
mov eax, obj
mov ecx, "foo"
call 0xabcdef ;; patched!


;; Compiled LoadIC Stub
0xabcdef:
cmp [eax - 1], klass0
jnz LoadIC_Miss
mov eax, [eax + 11]
ret

;; Compiled code
mov eax, obj
mov ecx, "foo"
call 0xabcdef ;; patched!


;; Compiled LoadIC Stub
0xabcdef:
cmp [eax - 1], klass0
jnz LoadIC_Miss
mov eax, [eax + 11]
ret

;; Compiled code
mov eax, obj
mov ecx, "foo"
call 0xabcdef ;; patched!

Everything is an IC stub

property accesses
element accesses
method calls
special method calls
global variables lookup
arithmetic operations


Vector.prototype.length = function () {
  return Math.sqrt(this.x * this.x +
                   this.y * this.y);
};


Vector.prototype.length = function () {
  return Math.sqrt(this.x * this.x +
                   this.y * this.y);
};

③ redundancy

Crankshaft (2010)

compile unoptimized code
feed hot functions into optimizer
speculate types based on IC states
apply classic optimizations
emit optimized code

Crankshaft (2010)

compile unoptimized code
feed hot functions into optimizer
speculate types based on IC states
apply classic optimizations
emit optimized code

checks in the code
verify speculations

failed check
⇒ jump to unoptimized code

code can depend on assumptions

[e.g. that some prototype chain
does not change]

violated assumption
⇒ deopt dependant code


Vector.prototype.length = function () {
  return Math.sqrt(this.x * this.x +
                   this.y * this.y);
};


CheckMap v0, klass
v1 = Load v0, @12
CheckMap v0, klass
v2 = Load v0, @12
d3 = TaggedToDouble v1
d4 = TaggedToDouble v2
d5 = Mul d3, d4
CheckMap v0, klass
v6 = Load v0, @16
CheckMap v0, klass
v7 = Load v0, @16
d8 = TaggedToDouble v6
d9 = TaggedToDouble v7
d10 = Mul d8, d9
d11 = Add d5, d10


CheckMap v0, klass     ①
v1 = Load v0, @12      ②
CheckMap v0, klass     ①
v2 = Load v0, @12      ②
d3 = TaggedToDouble v1 ③
d4 = TaggedToDouble v2 ③
d5 = Mul d3, d4
CheckMap v0, klass     ①
v6 = Load v0, @16      ④
CheckMap v0, klass     ①
v7 = Load v0, @16      ④
d8 = TaggedToDouble v6 ⑤
d9 = TaggedToDouble v7 ⑤
d10 = Mul d8, d9
d11 = Add d5, d10


CheckMap v0, klass
v1 = Load v0, @12
d3 = TaggedToDouble v1
d5 = Mul d3, d3
v6 = Load v0, @16
d8 = TaggedToDouble v6
d10 = Mul d8, d8
d11 = Add d5, d10

inlining
GVN
LICM
DCE
representation selection
uint32 optimization
escape analysis
type inference
range inference
bounds check elimination

V8

Vyacheslav Egorov

[email protected]

V8 is a JS VM

used by Chrome & node.js

being a JavaScript VMis not an achievement

being a fast VM is

the challenge

representation resolution redundancy

① representation

tagging to avoid boxing everything

pointer has "unused" bits due to alignment

Double ⇒ still boxing

objects?

hidden classes

≈ maps from Self VM

static structure approximated dynamically.

tracking denseness and unboxing

mutable boxes

what happens on read?

only beneficial if we can read unboxed

promote functions to hidden class

whole closure is promoted!

different woof⇒different classes

not all objects are structures

② resolution

tons of code⊕dictionary lookup

can we do better?

must do the first lookup

what about the second?

same hidden class ⇒ same structure

inline caching

Everything is an IC stub

③ redundancy

Crankshaft (2010)

Crankshaft (2010)

checks in the code verify speculations

failed check ⇒ jump to unoptimized code

code can depend on assumptions

[e.g. that some prototype chain does not change]

violated assumption ⇒ deopt dependant code

TurboFan

new optimizing pipeline

TurboFan

[Sea-of-Nodes IR, real lowering]

[work in progress]

being a JavaScript VM
is not an achievement

representation

resolution

redundancy

pointer has "unused" bits
due to alignment

Double
⇒ still boxing

only beneficial
if we can read unboxed

promote functions
to hidden class

whole closure
is promoted!

different `woof`
⇒different classes

not all objects
are structures

tons of code
⊕
dictionary lookup

same hidden class
⇒ same structure

checks in the code
verify speculations

failed check
⇒ jump to unoptimized code

[e.g. that some prototype chain
does not change]

violated assumption
⇒ deopt dependant code