V8 & DartVM

Вячеслав Егоров

@mraleph, [email protected]

Tech Talks NSU, March 2014

V8 - JS VM
внутри Chrome и node.js

Dart - новый язык для вебпрограммирования

VM - это просто

Быстрая VM - сложнее

В чем проблема?

// 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;
}
          

Dart is simpler

• Real frozen classes
• Real arrays (fixed length and growable)
• int vs. double separation
• still dynamically typed

• Representation
• Resolution
• Redundancy

Representation

Use tagging to avoid boxing everything

Pointer has last bit unused
due to alignment

pointer: xx...x1

function tag(ptr) { // ptr & 1 === 0
  return ptr | 1;
}

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

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

small integer: xx...x0

function tag(val) {
  return val << 1;
}

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

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

Double arithmetic
⇒ boxing

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;
          

Approximates static structure dynamically.

Essential in V8,
not needed in DartVM.

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

Track denseness and (un)box!

Same for properties

// Want "real" fast method calls
C.prototype.methodFoo = function () {
  /* ... */
};
C.prototype.methodBar = function () {
  /* ... */
};

obj.methodFoo();
          

// Don't want (pseudo-code)
m = LoadProperty(obj, "methodFoo")
CheckIfFunction(m)
Invoke(m, obj)
          

// Want (pseudo-code)
CheckClass(obj, klass0);
Invoke(methodFoo, obj);
          

Promote functions to hidden class

Catch: The whole closure is promoted!

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

different woof⇒
different classes

Track field types.

(Dart VM does this too)

allows to reuse boxes

store directly

copy on load

objects are not always structures

• too many properties
• delete obj.prop

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?

we have to do first lookup

do we have to do 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

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
d3 = TaggedToDouble v1
d5 = Mul d3, d3
v6 = Load v0, @16
d8 = TaggedToDouble v6
d10 = Mul d8, d8
d11 = Add d5, d10
          

Adaptive compilation

Insert guards to verify speculations

Failed check ⇒
jump to unoptimized code

Guards can be inserted

• at use
• at def

• inlining
• GVN
• LICM
• DCE
• representation selection
• load forwarding
• escape analysis
• type inference
• range inference
• bounds check elimination

Спасибо за внимание!