LexHuang

## 用JavaScript解释JavaScript虚拟机-内联缓存（inline caches）

• 有时候我把我对V8的了解包装成了很难消化的“做这个，别做那个”的教条化意见。这样的问题在于它对于解释起不到任何帮助并且很容易随着关注人的减少而消失。

• 有时候我们用了错误的抽象层次来解释虚拟机的工作机制。我喜欢一个想法：看见满是汇编代码的ppt演示可能会鼓励人们去学习汇编并且学会之后会去读ppt演示的内容。但我也害怕有时候这些ppt只会被人忽视和遗忘而对于实践毫无用处。

### 用JavaScript来实现动态语言

``````function MakePoint(x, y)
local point = {}
point.x = x
point.y = y
return point
end

function MakeArrayOfPoints(N)
local array = {}
local m = -1
for i = 0, N do
m = m * -1
array[i] = MakePoint(m * i, m * -i)
end
array.n = N
return array
end

function SumArrayOfPoints(array)
local sum = MakePoint(0, 0)
for i = 0, array.n do
sum.x = sum.x + array[i].x
sum.y = sum.y + array[i].y
end
return sum
end

function CheckResult(sum)
local x = sum.x
local y = sum.y
if x ~= 50000 or y ~= -50000 then
error("failed: x = " .. x .. ", y = " .. y)
end
end

local N = 100000
local array = MakeArrayOfPoints(N)
local start_ms = os.clock() * 1000;
for i = 0, 5 do
local sum = SumArrayOfPoints(array)
CheckResult(sum)
end
local end_ms = os.clock() * 1000;
print(end_ms - start_ms)

``````

``````∮ lua points.lua
150.2

``````

``````function MakePoint(x, y) {
var point = new Table();
STORE(point, 'x', x);
STORE(point, 'y', y);
return point;
}

function MakeArrayOfPoints(N) {
var array = new Table();
var m = -1;
for (var i = 0; i <= N; i++) {
m = m * -1;
STORE(array, i, MakePoint(m * i, m * -i));
}
STORE(array, 'n', N);
return array;
}

function SumArrayOfPoints(array) {
var sum = MakePoint(0, 0);
for (var i = 0; i <= LOAD(array, 'n'); i++) {
}
return sum;
}

function CheckResult(sum) {
if (x !== 50000 || y !== -50000) {
throw new Error("failed: x = " + x + ", y = " + y);
}
}

var N = 100000;
var array = MakeArrayOfPoints(N);
var start = LOAD(os, 'clock')() * 1000;
for (var i = 0; i <= 5; i++) {
var sum = SumArrayOfPoints(array);
CheckResult(sum);
}
var end = LOAD(os, 'clock')() * 1000;
print(end - start);

``````

``````∮ d8 points.js
points.js:9: ReferenceError: Table is not defined
var array = new Table();
^
ReferenceError: Table is not defined
at MakeArrayOfPoints (points.js:9:19)
at points.js:37:13

``````

``````function Table() {
// Map from ES Harmony is a simple dictionary-style collection.
this.map = new Map;
}

Table.prototype = {
load: function (key) { return this.map.get(key); },
store: function (key, value) { this.map.set(key, value); }
};

function CHECK_TABLE(t) {
if (!(t instanceof Table)) {
throw new Error("table expected");
}
}

CHECK_TABLE(t);
}

function STORE(t, k, v) {
CHECK_TABLE(t);
t.store(k, v);
}

var os = new Table();

STORE(os, 'clock', function () {
return Date.now() / 1000;
});

``````

``````∮ d8 **--harmony** quasi-lua-runtime.js points.js
737

``````

### 探索隐藏结构

1. 对于每个javascript对象，运行时系统都会将其合一个hidden class关联起来。就像Java VM会关联一个`java.lang.Class`的实例给每个对象一样。
2. 如果对象的布局改变了，则运行时就会 找到一个hidden class或者创建一个新的hidden class来匹配这个新对象布局并且连接到该对象上。

``````function Transition(klass) {
this.klass = klass;
}

function Property(index) {
this.index = index;
}

function Klass(kind) {
// Classes are "fast" if they are C-struct like and "slow" is they are Map-like.
this.kind = kind;
this.descriptors = new Map;
this.keys = [];
}

``````

``````Klass.prototype = {
// Create hidden class with a new property that does not exist on
// the current hidden class.
var klass = this.clone();
klass.append(key);
// Connect hidden classes with transition to enable sharing:
//           this == add property key ==> klass
this.descriptors.set(key, new Transition(klass));
return klass;
},

hasProperty: function (key) {
return this.descriptors.has(key);
},

getDescriptor: function (key) {
return this.descriptors.get(key);
},

getIndex: function (key) {
return this.getDescriptor(key).index;
},

// Create clone of this hidden class that has same properties
// at same offsets (but does not have any transitions).
clone: function () {
var klass = new Klass(this.kind);
klass.keys = this.keys.slice(0);
for (var i = 0; i < this.keys.length; i++) {
var key = this.keys[i];
klass.descriptors.set(key, this.descriptors.get(key));
}
return klass;
},

// Add real property to descriptors.
append: function (key) {
this.keys.push(key);
this.descriptors.set(key, new Property(this.keys.length - 1));
}
};

``````

``````var ROOT_KLASS = new Klass("fast");

function Table() {
// All tables start from the fast empty root hidden class and form
// a single tree. In V8 hidden classes actually form a forest -
// there are multiple root classes, e.g. one for each constructor.
// This is partially due to the fact that hidden classes in V8
// encapsulate constructor specific information, e.g. prototype
// poiinter is actually stored in the hidden class and not in the
// object itself so classes with different prototypes must have
// different hidden classes even if they have the same structure.
// However having multiple root classes also allows to evolve these
// trees separately capturing class specific evolution independently.
this.klass = ROOT_KLASS;
this.properties = [];  // Array of named properties: 'x','y',...
this.elements = [];  // Array of indexed properties: 0, 1, ...
// We will actually cheat a little bit and allow any int32 to go here,
// we will also allow V8 to select appropriate representation for
// the array's backing store. There are too many details to cover in
// a single blog post :-)
}

Table.prototype = {
if (this.klass.kind === "slow") {
// Slow class => properties are represented as Map.
return this.properties.get(key);
}

// This is fast table with indexed and named properties only.
if (typeof key === "number" && (key | 0) === key) {  // Indexed property.
return this.elements[key];
} else if (typeof key === "string") {  // Named property.
return (idx >= 0) ? this.properties[idx] : void 0;
}

// There can be only string&number keys on fast table.
return void 0;
},

store: function (key, value) {
if (this.klass.kind === "slow") {
// Slow class => properties are represented as Map.
this.properties.set(key, value);
return;
}

// This is fast table with indexed and named properties only.
if (typeof key === "number" && (key | 0) === key) {  // Indexed property.
this.elements[key] = value;
return;
} else if (typeof key === "string") {  // Named property.
var index = this.findPropertyForWrite(key);
if (index >= 0) {
this.properties[index] = value;
return;
}
}

this.convertToSlow();
this.store(key, value);
},

// Find property or add one if possible, returns property index
// or -1 if we have too many properties and should switch to slow.
findPropertyForWrite: function (key) {
if (!this.klass.hasProperty(key)) {  // Try adding property if it does not exist.
// To many properties! Achtung! Fast case kaput.
if (this.klass.keys.length > 20) return -1;

// Switch class to the one that has this property.
return this.klass.getIndex(key);
}

var desc = this.klass.getDescriptor(key);
if (desc instanceof Transition) {
// Property does not exist yet but we have a transition to the class that has it.
this.klass = desc.klass;
return this.klass.getIndex(key);
}

// Get index of existing property.
return desc.index;
},

// Find property index if property exists, return -1 otherwise.
if (!this.klass.hasProperty(key)) return -1;
var desc = this.klass.getDescriptor(key);
if (!(desc instanceof Property)) return -1;  // Here we are not interested in transitions.
return desc.index;
},

// Copy all properties into the Map and switch to slow class.
convertToSlow: function () {
var map = new Map;
for (var i = 0; i < this.klass.keys.length; i++) {
var key = this.klass.keys[i];
var val = this.properties[i];
map.set(key, val);
}

Object.keys(this.elements).forEach(function (key) {
var val = this.elements[key];
map.set(key | 0, val);  // Funky JS, force key back to int32.
}, this);

this.properties = map;
this.elements = null;
this.klass = new Klass("slow");
}
};

``````

[我不打算一行一行地解释上面的代码，因为它已经是用JavaScript书写的了；而不是C++ 或者 汇编...这正是使用JavaScript的意义所在。然而你可以通过评论或者邮件来询问任何不理解的地方。]

### 打包生成后代码

1. 一个全局变量，每个ic都会使用一个全局变量来模拟可变调用指令;

2. 并使用闭包来代替存根。

``````// Initially all ICs are in uninitialized state.
// They are not hitting the cache and always missing into runtime system.
var STORE\$0 = NAMED_STORE_MISS;
var STORE\$1 = NAMED_STORE_MISS;
var KEYED_STORE\$2 = KEYED_STORE_MISS;
var STORE\$3 = NAMED_STORE_MISS;
var STORE\$5 = NAMED_STORE_MISS;
var STORE\$9 = NAMED_STORE_MISS;

function MakePoint(x, y) {
var point = new Table();
STORE\$0(point, 'x', x, 0);  // The last number is IC's id: STORE\$0 ⇒ id is 0
STORE\$1(point, 'y', y, 1);
return point;
}

function MakeArrayOfPoints(N) {
var array = new Table();
var m = -1;
for (var i = 0; i <= N; i++) {
m = m * -1;
// Now we are also distinguishing between expressions x[p] and x.p.
// The fist one is called keyed load/store and the second one is called
// The main difference is that named load/stores use a fixed known
// constant string key and thus can be specialized for a fixed property
// offset.
KEYED_STORE\$2(array, i, MakePoint(m * i, m * -i), 2);
}
STORE\$3(array, 'n', N, 3);
return array;
}

function SumArrayOfPoints(array) {
var sum = MakePoint(0, 0);
for (var i = 0; i <= LOAD\$4(array, 'n', 4); i++) {
}
return sum;
}

function CheckResults(sum) {
var x = LOAD\$13(sum, 'x', 13);
var y = LOAD\$14(sum, 'y', 14);
if (x !== 50000 || y !== -50000) throw new Error("failed x: " + x + ", y:" + y);
}

``````

``````function NAMED_LOAD_MISS(t, k, ic) {
if (t.klass.kind === "fast") {
// Create a load stub that is specialized for a fixed class and key k and
// loads property from a fixed offset.
}
return v;
}

function NAMED_STORE_MISS(t, k, v, ic) {
var klass_before = t.klass;
STORE(t, k, v);
var klass_after = t.klass;
if (klass_before.kind === "fast" &&
klass_after.kind === "fast") {
// Create a store stub that is specialized for a fixed transition between classes
// and a fixed key k that stores property into a fixed offset and replaces
// object's hidden class if necessary.
var stub = CompileNamedStoreFastProperty(klass_before, klass_after, k);
PatchIC("STORE", ic, stub);
}
}

if (t.klass.kind === "fast" && (typeof k === 'number' && (k | 0) === k)) {
// Create a stub for the fast load from the elements array.
// Does not actually depend on the class but could if we had more complicated
// storage system.
}
return v;
}

function KEYED_STORE_MISS(t, k, v, ic) {
STORE(t, k, v);
if (t.klass.kind === "fast" && (typeof k === 'number' && (k | 0) === k)) {
// Create a stub for the fast store into the elements array.
// Does not actually depend on the class but could if we had more complicated
// storage system.
var stub = CompileKeyedStoreFastElement();
PatchIC("KEYED_STORE", ic, stub);
}
}

function PatchIC(kind, id, stub) {
this[kind + "\$" + id] = stub;  // non-strict JS funkiness: this is global object.
}

// Key is known to be constant (named load). Specialize index.
var index = klass.getIndex(key);

if (t.klass !== klass) {
// Expected klass does not match. Can't use cached index.
// Fall through to the runtime system.
}
return t.properties[index];  // Veni. Vidi. Vici.
}

}

function CompileNamedStoreFastProperty(klass_before, klass_after, key) {
// Key is known to be constant (named load). Specialize index.
var index = klass_after.getIndex(key);

if (klass_before !== klass_after) {
// Transition happens during the store.
// Compile stub that updates hidden class.
return function (t, k, v, ic) {
if (t.klass !== klass_before) {
// Expected klass does not match. Can't use cached index.
// Fall through to the runtime system.
return NAMED_STORE_MISS(t, k, v, ic);
}
t.properties[index] = v;  // Fast store.
t.klass = klass_after;  // T-t-t-transition!
}
} else {
// Write to an existing property. No transition.
return function (t, k, v, ic) {
if (t.klass !== klass_before) {
// Expected klass does not match. Can't use cached index.
// Fall through to the runtime system.
return NAMED_STORE_MISS(t, k, v, ic);
}
t.properties[index] = v;  // Fast store.
}
}
}

if (t.klass.kind !== "fast" || !(typeof k === 'number' && (k | 0) === k)) {
// If table is slow or key is not a number we can't use fast-path.
// Fall through to the runtime system, it can handle everything.
}
return t.elements[k];
}

}

function CompileKeyedStoreFastElement() {
function KeyedStoreFastElement(t, k, v, ic) {
if (t.klass.kind !== "fast" || !(typeof k === 'number' && (k | 0) === k)) {
// If table is slow or key is not a number we can't use fast-path.
// Fall through to the runtime system, it can handle everything.
return KEYED_STORE_MISS(t, k, v, ic);
}
t.elements[k] = v;
}

return KeyedStoreFastElement;
}

``````

``````∮ d8 --harmony quasi-lua-runtime-ic.js points-ic.js
117

``````