V8

Vyacheslav Egorov

me@mrale.ph

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 - b31...b3000)


/* 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)

  1. compile unoptimized code
  2. feed hot functions into optimizer
  3. speculate types based on IC states
  4. apply classic optimizations
  5. emit optimized code

Crankshaft (2010)

  1. compile unoptimized code
  2. feed hot functions into optimizer
  3. speculate types based on IC states
  4. apply classic optimizations
  5. 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

TurboFan

new optimizing pipeline

TurboFan

[Sea-of-Nodes IR, real lowering]

[work in progress]