mraleph

[mraleph-blog-blog]

[I am no longer using Tumblr to write posts directly, I moved blog to github pages]

[mraleph-blog-blog]

V8's --trace-* flags and Chrome on Windows

Various V8 optimization guidelines recommend passing --js-flags="--trace-opt --trace-deopt" and similar flags to Chrome to investigate performance problems with your JavaScript. However people trying this on Windows can't see any output and are unable to redirect stdout via conventional >. Here is a small hacky Python script I use to battle this problem:

import mmap import ctypes GUI = 2 CUI = 3 # Take chrome.exe from the current directory with open("chrome.exe", "r+b") as f: map = mmap.mmap(f.fileno(), 1024, None, mmap.ACCESS_WRITE) # DWORD field of IMAGE_DOS_HEADER e_lfanew = (ctypes.c_ulong.from_buffer(map, 30 * 2).value) # Signature (4 bytes), IMAGE_FILE_HEADER (20 bytes), offset to Subsystem field in IMAGE_OPTIONAL_HEADER subsystem = ctypes.c_ushort.from_buffer(map, e_lfanew + 4 + 20 + (17 * 4)) if subsystem.value == GUI: subsystem.value = CUI print "patched: gui -> cui" elif subsystem.value == CUI: subsystem.value = GUI print "patched: cui -> gui" else: print "unknown subsystem: %x" % (subsystem.value)

Run it in a directory containing chrome.exe and script will patch the executable: flipping Subsystem field in IMAGE_OPTIONAL_HEADER from IMAGE_SUBSYSTEM_WINDOWS_GUI to IMAGE_SUBSYSTEM_WINDOWS_CUI (and back if you run it again). When you run patched chrome.exe Windows will attach console to it so that you can see (and redirect) what Chrome writes to stdout/stderr. For example to see a trace of optimized functions, failed optimization attempts and deoptimizations run Chrome like this:

chrome.exe --no-sandbox --js-flags="--trace-opt --trace-bailout --trace-deopt"

[--no-sandbox is apparently required to allow renderers to write to a shared console. But don't browse around with this flag :-)]

[mraleph-blog-blog]

Explaining JavaScript VMs in JavaScript

I have a thing for virtual machines that are implemented in the language (or a subset of the language) they are built to execute. If I were in the academia or just had a little bit more free time I would definitely start working on a JavaScript VM written in JavaScript. Actually this would not be a unique project for JavaScript because people from Université de Montréal kinda got there first with Tachyon, but I have some ideas I would like to pursue myself.

I however have another dream closely connected to (meta)circular virtual machines. I want to help JavaScript developers understand how JS engines work. I think understanding the tools you are wielding is of uttermost importance in our trade. The more people would stop seeing JS VM as a mysterious black box that converts JavaScript source into some zeros-and-ones the better. 

I should say that I am not alone in my desire to explain how things work internally and help people write a more performant code. A lot of people from all over the world are trying to do the same. But there is I think a problem that prevents this knowledge from being absorbed efficiently by developers. We are trying to convey our knowledge in the wrong form. I am guilty of this myself:

sometimes I wrap things I know about V8 into hard to digest lists of "do this, not that" recommendations. The problem with such serving is that it really does not explain anything. Most probably it will be followed like a sacred ritual and might easily become outdated without anybody noticing it. 

sometimes trying to explain how VMs works internally we choose wrong level of abstraction. I love a thought that seeing a slide full of assembly code might encourage people to learn assembly and reread this slide later, but I am afraid that sometimes these slides just fall trough and get forgotten by people as something not useful in practice. 

I have been thinking about these problems for quite some time and I decided that it might be worth to try explaining JavaScript VM in JavaScript. The talk "V8 Inside Out" that I've given at WebRebels 2012 pursues exactly this idea [video] [slides] and in this post I would like to revisit things I've been talking about in Oslo but now without any audible obstructions (I like to believe that my way of writing is much less funky than my way of speaking ☺).

Implementing dynamic language in JavaScript

Imagine that you want to implement in JavaScript a VM for a language that is very similar to JavaScript in terms semantics but has a much simpler object model: instead of JS objects it has tables mapping keys of any type to values. For simplicity lets just think about Lua, which is actually both very similar to JavaScript and very different as a language. My favorite "make array of points and then compute vector sum" example would look approximately like this:

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)

Note that I have a habit of checking at least some final results computed by my μbenchmark. This saves me from embarrassment when somebody discovers that my revolutionary jsperf test-cases are nothing but my own bugs.

If you take the code above and put it into Lua interpreter you will get something like this:

∮ lua points.lua 150.2

Good, but does not help to understand how VMs work. So lets think how it could look like if we had quasi-Lua VM written in JavaScript. "Quasi" because I don't want to implement full Lua semantics, I prefer to focus only on the objects are tables aspect of it. Naïve compiler could translate our code down to JavaScript like this:

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++) { STORE(sum, 'x', LOAD(sum, 'x') + LOAD(LOAD(array, i), 'x')); STORE(sum, 'y', LOAD(sum, 'y') + LOAD(LOAD(array, i), 'y')); } return sum; } function CheckResult(sum) { var x = LOAD(sum, 'x'); var y = LOAD(sum, 'y'); 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);

However if you just try to run translated code with d8 (V8's standalone shell) it will politely refuse:

∮ 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

The reason for this refusal is simple: we are still missing runtime system code which is actually responsible for implementing object model and semantics of loads and stores. It might seem obvious, but I want to highlight this: VM, that looks like a single black box from the outside, on the inside is actually an orchestra of boxes playing together to deliver best possible performance. There are compilers, runtime routines, object model, garbage collector, etc. Fortunately our language and example are very simple so our runtime system is only couple dozen lines large:

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"); } } function LOAD(t, k) { CHECK_TABLE(t); return t.load(k); } function STORE(t, k, v) { CHECK_TABLE(t); t.store(k, v); } var os = new Table(); STORE(os, 'clock', function () { return Date.now() / 1000; });

Notice that I have to use Harmony Map instead of normal JavaScript Object because potentially table can contain any key, not just string ones.

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

Now our translated code works but is disappointingly slow because of all those levels of abstraction every load and store have to cross before they get to the value. Lets try to reduce this overhead by applying the very same fundamental optimization that most JavaScript VMs apply these days: inline caching. Even JS VMs written in Java will eventually use it because invokedynamic is essentially a structural inline cache exposed at bytecode level. Inline caching (usually abbreviated as IC in V8 sources) is actually a very old technique developed roughly 30 years ago for Smalltalk VMs.

Good duck always quacks the same way

The idea behind inline caching is very simple: we want to create a bypass or fast path that would allow us to quickly, without entering runtime system, load object's property if our assumptions about object and it's properties are correct. It's quite hard to formulate any meaningful assumptions about object layout in a program written in language full of dynamic typing, late binding and other quirks like eval so instead we want to let our loads/stores observe&learn: once they see some object they can adapt themselves in a way that makes subsequent loads from similarly structured objects faster.  In a sense we are going to cache knowledge about the layout of the previously seen object inside the load/store itself hence the name inline caching. ICs can be actually applied to virtually any operation with a dynamic behavior as long as you can figure out a meaningful fast path: arithmetical operators, calls to free functions, calls to methods, etc. Some ICs can also cache more than a single fast path that is become polymorphic.

If we start thinking how to apply ICs to the translated code above it soon becomes obvious that we need to change our object model. There is no way we can do a fast load from a Map, we always have to go through get method. [If we could peak into raw hashtable behind Map we could make IC work for us even without new object layout by caching bucket index.]

Discovering hidden structure

For efficiency tables that are used like structured data should become more like C structs: a sequence of named fields at fixed offsets. The same about tables that are used as arrays: we want numeric properties to be stored in array like fashion. But it's obvious that not every table fits such representation: some are actually used as tables, either contain non-string non-number keys or contain too many string named properties that come and disappear as table is mutated. Unfortunately we can't perform any kind of expensive type inference, instead we have to discover a structure behind each and every table while the program runs creating and mutating them. Fortunately there is a well known technique that allows to do precisely that ☺. This technique is known as hidden classes. 

The idea behind hidden classes boils down to two simple things:

runtime system associates a hidden class with each an every object, just like Java VM would associate an instance of java.lang.Class with every object;

if layout of the object changes then runtime system will create or find a new hidden class that matches this new layout and attach it to the object;

Hidden classes have a very important feature: they allow VM to quickly check assumptions about object layout by doing a simple comparison against a cached hidden class. This is exactly what we need for our inline caches. Lets implement some simple hidden classes system for our quasi-Lua runtime. Every hidden class is essentially a collection of property descriptors, where each descriptor is either a real property or a transition that points from a class that does not have some property to a class that has this property:

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 = []; }

Transitions exist to enable sharing of hidden classes between objects that are created in the same way: if you have two objects that share hidden class and you add the same property to both of them you don't want to get different hidden classes.

Klass.prototype = { // Create hidden class with a new property that does not exist on // the current hidden class. addProperty: function (key) { 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)); } };

Now we can make our tables flexible and allow them to adapt to the way they are constructed

var ROOT_KLASS = new Klass("fast"); function Table() { // All tables start from the fast empty root hidden class. 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 = { load: function (key) { 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. var idx = this.findPropertyForRead(key); 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. this.klass = this.klass.addProperty(key); 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. findPropertyForRead: function (key) { 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"); } };

[I am not going to explain every line of the code because it's commented JavaScript; not C++ or assembly... This is the whole point of using JavaScript. However you can ask anything unclear in comments or by dropping me a mail]

Now that we have hidden classes in our runtime system that would allow us to perform quick checks of object layout and quick loads of properties by their index we just have to implement inline caches themselves. This requires some additional functionality both in compiler and runtime system (remember how I was talking about cooperation between different parts of VM?).

Patchwork quilts of generated code

One of many ways to implement an inline cache is to split it into two pieces: modifiable call site in the generated code and a set of stubs (small pieces of generated native code) that can be called from that call site. It is essential that stubs themselves (or runtime system) could find callsite from which they were called: stubs contain only fast paths compiled under certain assumptions, if those assumptions do not apply for an object that stub sees then it can initiate modification (patching) of the call site that invoked this stub to adapt that site for new circumstances. Our pure JavaScript ICs will also consist of two parts:

a global variable per IC will be used to emulate modifiable call instruction;

and closures will be used instead of stubs.

In the native code V8 finds IC sites to patch by inspecting return address sitting on the stack. We can't do anything like that in the pure JavaScript (arguments.caller is not fine-grained enough) so we'll just pass IC's id into IC stub explicitly. Here is how IC-ified code will look like: 

// 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 LOAD$4 = NAMED_LOAD_MISS; var STORE$5 = NAMED_STORE_MISS; var LOAD$6 = NAMED_LOAD_MISS; var LOAD$7 = NAMED_LOAD_MISS; var KEYED_LOAD$8 = KEYED_LOAD_MISS; var STORE$9 = NAMED_STORE_MISS; var LOAD$10 = NAMED_LOAD_MISS; var LOAD$11 = NAMED_LOAD_MISS; var KEYED_LOAD$12 = KEYED_LOAD_MISS; var LOAD$13 = NAMED_LOAD_MISS; var LOAD$14 = NAMED_LOAD_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 // named load/store. // 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++) { STORE$5(sum, 'x', LOAD$6(sum, 'x', 6) + LOAD$7(KEYED_LOAD$8(array, i, 8), 'x', 7), 5); STORE$9(sum, 'y', LOAD$10(sum, 'y', 10) + LOAD$11(KEYED_LOAD$12(array, i, 12), 'y', 11), 9); } 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); }

Changes above are again self-explanatory: every property load/store site got it's own IC with an id. One small last step left: to implement MISS stubs and stub "compiler" that would produce specialized stubs:

function NAMED_LOAD_MISS(t, k, ic) { var v = LOAD(t, k); 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. var stub = CompileNamedLoadFastProperty(t.klass, k); PatchIC("LOAD", ic, stub); } 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); } } function KEYED_LOAD_MISS(t, k, ic) { var v = LOAD(t, k); 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. var stub = CompileKeyedLoadFastElement(); PatchIC("KEYED_LOAD", ic, stub); } 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. } function CompileNamedLoadFastProperty(klass, key) { // Key is known to be constant (named load). Specialize index. var index = klass.getIndex(key); function KeyedLoadFastProperty(t, k, ic) { if (t.klass !== klass) { // Expected klass does not match. Can't use cached index. // Fall through to the runtime system. return NAMED_LOAD_MISS(t, k, ic); } return t.properties[index]; // Veni. Vidi. Vici. } return KeyedLoadFastProperty; } 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. } } } function CompileKeyedLoadFastElement() { function KeyedLoadFastElement(t, k, 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_LOAD_MISS(t, k, ic); } return t.elements[k]; } return KeyedLoadFastElement; } 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; }

It's a lot of code (and comments) but it should be simple to understand given all explanations above: ICs observe and stub compiler/factory produces adapted-specialized stubs [attentive reader can even notice that I could have initialized all keyed store ICs with fast loads from the very start or that it gets stuck in fast state once it enters it].

If we throw all the code we got together and rerun our "benchmark" we'll get very pleasing results:

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

This is a factor of 6 speedup compared to our first naïve attempt! 

There is never a conclusion to JavaScript VMs optimizations

Hopefully you are reading this part because you have read everything above... I tried to look from a different perspective, that of a JavaScript developer, onto some ideas powering JavaScript engines these days. The more code I was writing the more it felt like a story about blind men and an elephant. Just to give you a feeling of looking into the abyss: V8 has 10 descriptors kinds, 5 elements kinds (+ 9 external elements kinds), ic.cc that contains most of IC state selection logic is more that 2500 LOC and ICs in V8 have more than 2 states (there are uninitialized, premonomorphic, monomorphic, polymorphic, generic states not mentioning special states for keyed load/stores ICs or completely different hierarchy of states for arithmetic ICs), ia32-specific hand written IC stubs take more than 5000 LOC, etc. These numbers only grow as time passes and V8 learns to distinguish&adapt to more and more object layouts. And I am not even touching object model itself (objects.cc 13kLOC), or garbage collector, or optimizing compiler.

Nevertheless I am sure that fundamentals will not change in the foreseeable future and when they do it will be a breakthrough with a loud bang! sound, so you'll notice. Thus I think that this exercise of trying to understand fundamentals by (re)writing them in JavaScript is very-very-very important.

I hope tomorrow or maybe the week after you will stop and shout Eureka! and tell your coworkers why conditionally adding properties to an object in one place of the code can affect performance of some other distant hot loop touching these objects. Because hidden classes, you know, they change!

[mraleph-blog-blog]

My JSConf 2012 talk

Last week I travelled to US for the first time in my life to give a talk about V8 at JSConf 2012. The conference absolutely fantastic and allowed me to meet a lot of different people. If you know any other conference that would allow me to chat with Richard Hudson about transactional memory applications for concurrent GCs, listen to Dan Ingalls talk, discuss compiler design with people from Mozilla and Microsoft and make s'mores with Rickard Falkvinge - give me a call and I'll buy some tickets :-)

But there is another reason why JSConf was an invaluable experience for me: I like talking and sharing knowledge but both preparing and speaking is hard for me. Partially because I am not exactly very good in speaking English - my thoughts and jokes-cortex are accustomed to immense flexibility of Russian grammar. It's also always hard to fit both useful information and some entertainment into 30 minutes talk.

Yes, I do think that any talk should be both useful and entertaining. Some talks are entertaining but not useful. Some are highly useful but not entertaining. The balance is crucial.

When I was preparing my talk for JSConf 2012 I decided that I don't want to speak about V8 basics again: hidden classes, number representations, optimizing vs. non-optimizing compiler, flags to trace optimizations, profiler, generic performance advices. There are numerous presentations on this: from V8 developers mine, Daniel Clifford's, from Chrome DevRel team Lilly Thomson's and from Mozilla SpiderMonkey team David Mandelin's. There are also numerous posts (some on this blog, some in Andy Wingo's) plus +Florian Loitsch started turning notes he took while working on Dart to JavaScript compiler into blog posts. I highly recommend reading them. 

Thus I considered foundations well covered and decided to choose a different goal for my talk: I wanted to encourage people to look under V8's hood. Following this decision I called my talk "Can V8 do that?!" and tried to demonstrate that V8 assembly and HIR can be quite readable with some practice and that they hide a lot of wonders. I don't yet know if I succeeded or failed, only future will tell, but I will monitor v8-dev & v8-users mailing lists for questions about V8 internals and incoming patches :-)

I also have a suspicion that there are still might be some misunderstandings (e.g. if you think that V8 can always hoist expression like a.length from the loop please raise your hand in comments!). Nevertheless... I will continue to work on my ability to convey knowledge in an entertaining way and I am looking forward to my next talk: 1h with V8 internals in the beautiful Oslo at Web Rebels

MY JSCONF 2012 SLIDES

[mraleph-blog-blog]

"I want to optimize my JS application on V8" checklist

Samurais had something called bushido, way of the warrior, code of conduct they had to follow. In similar manner you have to follow certain opt-dō if you want to optimize your application. I have tried to sketch such a path in my nodecamp.eu talk "Understanding V8" and +Daniel Clifford tried to do the same in "V8 Performance Tuning Tricks" talk on GDD11 in Berlin. But not everybody has seen those talks and the question keeps coming back again. So I decided to write down a quick check list for developers who want to optimize their apps. tl;dr version of my checklist is: "Understand before you act". 

Understanding V8 and beyond [talks and posts]

UPDATE June 27 2012 More and more talks are being given about optimizing for V8 and understanding it's internals so I decided to maintain a list of them here. If I missed some interesting/useful blog post or talk about any JavaScript VM please send me a link and I will add it.

Practical recommendations and optimization walk-throughs for V8

Understanding V8 (me, nodecamp.eu 2011) [slides]

V8 Performance Tuning Tricks (+Daniel Clifford, GDD2011 Berlin) [slides]

Console to Chrome (+Lilli Thompson, GDC 2012) [slides] [video]

Breaking the JavaScript Speed Barrier with V8 (+Daniel Clifford, Google I/O 2012) [slides] [video]

Optimizing for V8 (series of blog posts from +Florian Loitsch, based on his experience writing dart2js compiler)

V8 talks (old ones might contain outdated information)

V8: High Performance JavaScript Engine in Google Chrome (+Kevin Millikin, GDD 2008 London) [video]  

V8 Internals (+Mads Ager, Google I/O 2009) [video]

Erik Meijer and +Lars Bak on Channel 9: Inside V8 - A Javascript Virtual Machine (2009)

Crankshaft: Turbocharging the Next Generation of Web (+Kasper Lund, YOW 2011) [video] [slides]

Fundamentals of V8 and other JS VMs

Andy Wingo blogs about his adventures in V8's and JavaScriptCore's compilation pipelines

David Mandelin's (SpiderMonkey TL) talk Know Your Engines (Velocity Conf 2011) [slides] [video].

I am trying to explain inline-caching used by JavaScript VMs by writing IC in JavaScript, also see my talk "V8 Inside Out" from WebRebels 2012 [slides] [video]

Miscellaneous

Can V8 do that?! (me, JSConf 2012) [slides] [vides]

Do you understand what the application is trying to do and how?

The more you understand about your app the better you can optimize it. Sometimes a tricky algorithm or a cache placed in right place will yield more improvements than any local tweaking. Understanding your application in large is a very difficult problem which requires special tooling and discipline. I highly recommend to read @coda's Metrics Metrics Everywhere talk if you want to get a glimpse of that world. Sometimes it is possible to split big application into pieces and optimize them separately but there is no guarantee that overall gain will not be lost when those pieces are connected back together.

Did you profile your application with built in statistical profiler?

Profiling helps to discover obvious hot spots. Don't waste time rewriting places that occupy 0.0001% of running time. Concentrate your efforts on those that are high on the profile. If you are using V8's tick processors keep in mind that LazyCompile: prefix does not mean that this time was spent in compiler, it just means that the function itself was compiled lazily. Statistical profiler is not the most accurate tool in the world and might miss overheads that are finely spread across execution (as sampling interval is 2ms). Tools like dtrace, perf, Instruments, VTune might provide a more fine grained picture but they do not necessarily have support for JITed code (see below).

JavaScript function is high on the profile

Ensure that this function is optimized and Crankshaft friendly. V8's tick processing scripts mark optimized functions with * (asterisk) and non-optimized with ~ (tilda). You can also use --trace-opt --trace-deopt --trace-bailout flags to see what Crankshaft does with your program. Deoptimizations happen when assumptions made by the compiler does not match program's runtime behavior, bailouts happens when compiler can't compile the function with optimizations for some reason. If you want to understand ideas behind V8 optimization pipeline I recommend to start by reading Andy Wingo's A Tale of Two Compilers post.

In general it's a good idea to know more about modern JavaScript VMs, especially their strengths and weaknesses. I recommend going through David Mandelin's talk Know Your Engines. This talk stresses a very important aspect of modern JS performance: fastest application is the one that is essentially statically typed in it's nature.

Modern JavaScript VMs try to grasp "static" structure hidden inside dynamic JS code by utilizing hidden classes and inline caches. Take a look at my slide deck to get a basic understanding of how those hidden classes are built and used.  

For V8 it is also important to check how you store floating point numbers (and integers that exceed 31-bit range in case of ia32 version of v8) and use WebGL typed arrays if appropriate. These days V8 tries to adapt generic arrays' storage to the data you store in them, but understanding whether those optimizations kicked in or not might be difficult; thus I just recommend using typed arrays.

GC is high on the profile

Try to understand what your are allocating and (more important) what survives several GCs. The worst kind of object is the one that survives a couple of partial (aka scavenge) collections and then gets thrown away. This kind of workload is the most stressful for GC because it has to copy young objects around constantly. Objects that live long are less stressful (but you have to keep in mind that GC cost is proportional to the number of live objects). The best kind of object is the one that dies shortly after it's allocation. You can use --trace-gc to see GC pauses and you can use built in heap snapshots to figure out what takes space in your heap. [it might be hard or impossible to capture "middle-aged" garbage with heap snapshots because V8 does full garbage collection before taking snapshot thus effectively killing all such garbage].

JS natives are high on the profile

When I say _natives_ I mean built in methods of String/Number/Boolean/RegExp/JSON and global functions like parseInt etc. Here you can't optimize anything directly but you can try to figure out two things:

Try calling them less by changing your algorithms and/or fusing them into it. Some of those methods are very generic (e.g. forEach). Some can be fused with your functions (e.g. you have to parse integer contained in some stream: you can either build a temporary string character by character and pass it to parseInt or you can fuse parsing and reading from a stream; later is better)

Is there some obvious performance problem with them? V8's implementation of the native method can be suboptimal. If you see a bug (or you suspect that it can be improved) please file a bug or write a question to v8-users mailing list.

Some strange V8 internals are high on the profile

In this case you can either read V8's source or send a question to v8-users list.

A lot of time is spent in your C++ code

Sorry this is out of scope. Consult C++ optimization guides :-)

Do you feel that V8's statistical profiler misses hotspot?

Your best bet then is either hardware counters based tool like Linux perf for which V8 has support (see v8/tools/ll_prof.py --help for more details) or trying to spot anomalies by some sort of software counters based profiling. V8 has it's own simple software counters subsystem (try passing --native-code-counters --dump-counters to d8 shell).

Do you want to go deeper?

If you feel that generated code is slow and you can improve it you should definitely check it out using flags --print-code --code-comments. You can also dump IR used by optimizing compiler with --trace-hydrogen. IR will be written into hydrogen.cfg file that can be viewed by C1 Visualizer.

Are you still lost?

Drop a line to me or better to v8-users mailing list. Try your best to provide as much context as possible (a standalone JS benchmark is the best way). It's nearly impossible to diagnose performance problems based on vague descriptions of what you are trying to achieve and how slow it runs.

There is something to be learned from a rainstorm. When meeting with a sudden shower, you try not to get wet and run quickly along the road. But doing such things as passing under the eaves of houses, you still get wet. When you are resolved from the beginning, you will not be perplexed, though you still get the same soaking — Hagakure by Yamamoto Tsunetomo.

Similarly you have to be resolved from the beginning when you want to optimize your app. Randomly tweaking things in panic here and there does not help.

Understand before you act.

[mraleph-blog-blog]

The trap of the performance sweet spot

Disclaimer: This is my personal blog. The views expressed on this page are mine alone and not those of my employer.

This post is about JavaScript performance but I would like to start it by telling a story that might seem unrelated to JS. Please bear with me if you don't like C.

A story of a C programmer writing JavaScript

Mr. C. is a C programmer as you can probably guess from his name. Today he was asked by his boss to write a very simple function: given an array of numbered 2d points calculate vector sum of all even numbered points... He opens his favorite text editor and quickly types something like (I'll be intentionally skipping some #include boilerplate):

typedef struct { int32_t n; double x; double y; } Point; Point arrayofpoints_sum(Point* points, size_t n) { Point sum = { 0, 0, 0 }; for (size_t i = 0; i < n; i++) { if ((points[i].n & 1) == 0) { sum.x += points[i].x; sum.y += points[i].y; } } return sum; }

Oh, that was pretty easy... There are still some time left, so mr. C. throws in some array creation and benchmarking code:

Point* arrayofpoints_create(size_t n) { Point* points = (Point*) malloc(n * sizeof(Point)); for (size_t i = 0; i < n; i++) { points[i].n = i; points[i].x = i * 0.1 + 0.1; points[i].y = i * 0.9 - 0.1; } return points; } void arrayofpoints_free(Point* array) { free(array); } static uint64_t now() { struct timeval t; gettimeofday(&t, NULL); return ((uint64_t) t.tv_sec) * 1000000 + (uint64_t) t.tv_usec; } void test_arrayofpoints() { static const size_t kArraySize = 10000; static const size_t kIterations = 10000; uint64_t create_total = 0; uint64_t sum_total = 0; for (size_t i = 0; i < kIterations; i++) { uint64_t t1 = now(); Point* array = arrayofpoints_create(kArraySize); uint64_t t2 = now(); Point sum = arrayofpoints_sum(array, kArraySize); uint64_t t3 = now(); assert((int)sum.x == 2500000); assert((int)sum.y == 22495000); assert(sum.n == 0); arrayofpoints_free(array); create_total += (t2 - t1); sum_total += (t3 - t2); } printf("create: %lld [%.2f per iteration] usec, sum: %lld [%.2f per iteration] usec\n", create_total, (double)create_total / kIterations, sum_total, (double)sum_total / kIterations); } int main(int argc, char* argv[]) { test_arrayofpoints(); return 0; }

His code seems to compile and run just fine:

% gcc --std=c99 -O3 -o point point.c % ./point create: 508075 [50.81 per iteration] usec, sum: 214779 [21.48 per iteration] usec

Suddenly mr. C gets a call from his boss. "We've decided to rewrite our apps in JavaScript. It is pretty fast nowdays, ya know." says the boss and hangs up. Mr. C. does not like JavaScript as much as he likes C but he is one of those programmers who can write programs in any language:

function Point(n, x, y) { this.n = n; this.x = x; this.y = y; } function sumArrayOfPoints(points) { var sum = new Point(0, 0, 0); for (var i = 0; i < points.length; i++) { if ((points[i].n & 1) === 0) { sum.x += points[i].x; sum.y += points[i].y; } } return sum; } function createArrayOfPoints(n) { var points = new Array(n); for (var i = 0; i < n; i++) { points[i] = new Point(/* n */ i, /* x */ i * 0.1 + 0.1, /* y */ i * 0.9 - 0.1); } return points; } function now() { return Date.now() * 1000; } function assertStrictlyEqual(expected, value) { if (expected !== value) { throw new Error("Assertion failed: expected " + expected + " got " + value); } } function testArrayOfPoints() { var kArraySize = 10000; var kIterations = 10000; var createTotal = 0; var sumTotal = 0; for (var i = 0; i < kIterations; i++) { var t1 = now(); var array = createArrayOfPoints(kArraySize); var t2 = now(); var sum = sumArrayOfPoints(array); var t3 = now(); assertStrictlyEqual(2500000, sum.x | 0); assertStrictlyEqual(22495000, sum.y | 0); assertStrictlyEqual(0, sum.n); createTotal += (t2 - t1); sumTotal += (t3 - t2); } console.log("create: " + createTotal + " [" + (createTotal / kIterations) + " per iteration] usec," + " sum: " + sumTotal + " [" + (sumTotal / kIterations) + " per iteration] usec\n"); } testArrayOfPoints();

That was very easy, but the numbers don't look as impressive as mr. C. or his boss expected:

% ~/src/v8/d8 point1.js create: 4629000 [462.9 per iteration] usec, sum: 2056000 [205.6 per iteration] usec

JavaScript program is approximately 10 times slower than original C program. Hmm thinks mr. C. and starts digging.

If C is a stone then JavaScript is a fog

C is a low-level programming language. People call it a portable assembly sometimes. You just take a piece of memory and say: hey, this smallish sequence of 24 bytes is actually a Point which has one uint32_t field followed by two double fields.

Small chunk of unused memory between n and x appears to make x and y fields nicely aligned. CPUs ♥ aligned doubles. On some architectures you can't even read an unaligned one directly from memory into a floating point register (you'll get punished if you try).

Arrays in C are also nice and tight: you just take a bigger region of memory and assume that it contains a sequence of Points one after another.

But in JavaScript things are destined to get hairy. You can't take a flat piece of memory and call it Point with this and that as fields. Instead you have an extremely flexible thing called Object. Object can have properties which can come and go as they wish (almost). You can write constructor:

function Point(n, x, y) { /* ... */ }

but nothing actually prevents you from modifying Point instances after they were created. VM that runs JavaScript has to be always ready for virtually anything that can happen with your object (new properties added, old properties deleted, property descriptor modified). Because of this flexibility it can't pack Point objects into 24 bytes and has to go with something like this (example layout used by V8):

V8 actually tries to make the object more struct like. It attempts to figure out how much space should be preallocated directly inside the object for properties by looking at the constructor and/or doing allocation profiling. Some VMs just use a fixed constant or even store all properties outside of an object in a separate array. Another thing to notice is that V8 always boxes numbers that are not 31-bit integers (32-bit on x64). Some VMs (e.g. SpiderMonkey and JSC) don't box doubles but instead use NaN-tagging instead. 

Nevertheless Point object will be 3.3 times as big on x64 version of V8 than it was in C program and it will not be continuously allocated in memory (doubles are accessed via indirection). There are three additional fields: pointer to hidden class (known as Map in V8, Shape in SpiderMonkey, Structure in JavaScriptCore) which captures and describes layout of the object, pointer to out of object properties backing store and pointer to elements backing store. All these fields are required because object can be mutated in an unpredictable ways after it's creation. 

Array of points object looks basically the same:

Array is a JavaScript object and thus it also has hidden class, pointer to the properties backing store and pointer to the elements backing store. Backing stores can have different representations. For example VMs usually try to represent sparse arrays as dictionaries and non-sparse arrays should have flat backing stores. In our program array of points is always non-sparse and it gets a flat backing store. 

The mathematics of performance is simple: each point of flexibility and each indirection (arrow on the picture) adds additional runtime cost. Evaluating simply looking expression points[i].x in JavaScript requires answering to an expensive questions: "What is points? How do I get property called i from it? How then I get x?". Fully statical analysis of the program is too expensive to be used to answer these questions. Instead modern JITs reduce these costs by adapting generated code to the program while it runs via techniques like inline caching and adaptive compilation pipelines. Simply speaking: because in JavaScript an application can't tell compiler "points is an array of Point objects" via types declarations JIT has to eavesdrop to notice that. 

If you want to get good performance you need to speak loud enough for JIT compiler to hear you and adapt to your application. This means: your objects should have stable layouts, property access and call sites better be monomorphic, no funny language features (e.g. with or eval) in sight, using typed arrays where appropriate instead of pure JS arrays etc. In a sense you'll be writing statically typed code in a language that does not support static typing. 

"Wait a second!"  somebody might say here "Mr. C's code above is pretty damn type stable and yada-yada. But it's still 10x times slower! Can he make it faster?"

Yes, he can but he will have to

Write JavaScript as if it's assembly generated by C compiler

To get as close as possible to raw memory from JavaScript we have to use WebGL typed arrays. It's easy for a JIT to befriend those guys and optimize the hell out of reads and writes, because they have a nice semantics for their backing stores: no nasty holes leading to prototype lookups, all elements have known primitive type and no boxing is required.

var blocks = []; function Block(size) { this.size = size; this.buf = new ArrayBuffer(this.size); this.i32 = new Int32Array(this.buf); this.f64 = new Float64Array(this.buf); } function malloc(N) { if (blocks[N] && blocks[N].length) return blocks[N].pop(); return new Block(N); } function free(addr) { (blocks[addr.size] || (blocks[addr.size] = [])).push(addr); }

This is a very naïve implementation (I would even say parody) of the famous malloc&free duo. It does not try to optimize memory usage at all but it is perfect for our demonstration.

var $stack = malloc(8 * 1024); var $sp = 0;

Original C program returns sum on the stack so will have our toy stack to mimic that.

function createArrayOfPoints(n) { var points = malloc(24 * n); var points_i32 = points.i32; var points_f64 = points.f64; for (var i1 = 0, i2 = 1, i = 0; i < n; i++, i1 += 6, i2 += 3) { points_i32[i1] = /* n */ i; points_f64[i2] = /* x */ i * 0.1 + 0.1; points_f64[i2 + 1] = /* y */ i * 0.9 - 0.1; } return points; }

Creating array of points is simple: you malloc an array and fill it. It might be hard to read this code and see how it relates to the first JavaScript version or even to the original C function but that's because it actually tries to mimic one of the optimizations every good C compiler tries to do: strength reduction. Calculating points[i] as (byte*)points + sizeof(Point) * i might be wasteful because multiplication is expensive compared to addition so good C compiler will try to replace points[i] with a new artificial induction variable p' that starts as p' = points[i] and is advanced as p += sizeof(Point).

function sumArrayOfPoints(points, n) { var x = 0; var y = 0; var points_i32 = points.i32; var points_f64 = points.f64; for (var i1 = 0, i2 = 1, k = 6 * n; i1 < k; i1 = i1 + 6, i2 = i2 + 3) { if ((points_i32[i1] & 1) === 0) { x += points_f64[i2]; y += points_f64[i2 + 1]; } } // Caller should have reserved space for the return value. var retval_addr = $sp - 24; $stack.i32[retval_addr >> 2] = 0; $stack.f64[(retval_addr + 8) >> 3] = x; $stack.f64[(retval_addr + 16) >> 3] = y; return retval_addr; }

Summing loop was translated from C in the same way as initialization loop in createArrayOfPoints but there is another important classical optimization demonstrated here: scalar replacement. Smart compiler sees (via escape analysis usually) that Point sum does not have to exist as a continuos entity on the stack. Instead it can be exploded and its fields becomes separate variables (register allocator later puts them into registers). Result of the sumArrayOfPoints is returned on the "stack" just like in the original C version.

The rest of code is unchanged but minor changes are required in the testArrayOfPoints function:

var t1 = now(); var array = createArrayOfPoints(kArraySize); var t2 = now(); $sp += 24; // Reserve space for return value on the "stack". sumArrayOfPoints(array, kArraySize); $sp -= 24; var sum_n = $stack.i32[$sp >> 2]; var sum_x = $stack.f64[($sp + 8) >> 3]; var sum_y = $stack.f64[($sp + 16) >> 3]; var t3 = now(); assertStrictlyEqual(2500000, sum_x | 0); assertStrictlyEqual(22495000, sum_y | 0); assertStrictlyEqual(0, sum_n); free(array);

We have to take care of managing stack space for stack allocated sum object and we should remember to free allocated array of points. We are using JavaScript as assembly after all...

% ~/src/v8/d8 point.c.js create: 532000 [53.2 per iteration] usec, sum: 988000 [98.8 per iteration] usec

As you can see in exchange for completely unreadable JavaScript code we got a nice 9x speedup on creation and 2x speedup on sum calculation. 

If you are curious enough to look at the code V8 generates for the sum loop and compare it with code generated from C by GCC you will notice that while it is pretty tight V8 does not understand that i32 and f64 are actually the same array and treats them separately. There are also bounds checks that are not there for C code.

Don't be charmed by the sweet spot

Roughly a week ago a friend of mine sent me a link to Broadway.js accompanied by numerous expletives to better convey his excitement with this project and emscripten in general: "Look how mighty fast JavaScript became, old chap!". 

My friend has fallen into the logical trap without even noticing it. Good performance demonstrated by some inhumanly written piece of code (e.g. translated from C via optimizing compiler) does not prove that "JavaScript is already fast enough" unless you are planning on writing your webapps in C for the rest of your life or you are capable of writing such inhuman code yourself just like mr. C. Instead it proves that "Certain features of JavaScript when used in certain way lead to good enough performance." Efficiency on a tight computational kernel does not necessarily translate into efficiency on different workloads. I call this the trap of the sweet spot.

It's not JavaScript that becomes faster and faster. It's JavaScript's sweet spot. 

You can hit the sweet spot, no doubt about that. But you have to follow rules to hit it. And those rules are strict (application runs best when it's actually pretty static in it's behavior) and sometimes unknown (different VMs rely on different heuristics). And hitting the sweetest part requires some strange engineering decisions as demonstrated by the mr. C.'s example above.

Obviously JavaScript VMs are nowhere near the end of the performance improvements road and the language itself is going to get features like binary data that would make hitting sweet-sweet spot much easier. But I doubt that the language as whole is going to become performance sweet.

Real world performance is not as shallow as some micro-benchmark score. It has at least three very important facets: speed, memory, VM's complexity.

If you look at existing JavaScript VMs you will notice that they have to pay a lot in terms of complexity to overcome ineffective execution or memory utilization. And implementation complexity is the worst kind of complexity in the world: it leads to subtle bugs that occur on 0.000001% of programs, it leads to unpredictable and hard to analyze performance, it leads to volumes of rulebooks that specify how to appease the compiler.

JavaScript is a complex and expensive language in it's very core. Keep that in mind and don't be charmed by the sweet spot. 

But I must admit: working on a JavaScript VM and making sweet spot larger and easier to hit is an interesting challenge that make one burst with excitement and stresses the brain. :-)

[mraleph-blog-blog]

Dangers of cross language benchmark games

Disclaimer: This is my personal blog. The views expressed on this page are mine alone and not those of my employer.

Every time I stumble upon yet another cross language benchmark comparison I remember Fight Club. No, seriously! What can be more enjoyable than watching your favorite language pummel not-so-favorite languages? Developers love cross language benchmark games. There is no doubt about that. But they tend to forget the first rule of benchmark club:

The first rule of benchmark club is you do not talk about benchmark club jump to conclusions.

A couple of weeks ago one of my friends sent me a link to Programming Language Benchmarks by Attractive Chaos, a younger brother of The Computer Language Benchmarks Game maintained by Isaac Gouy, and asked for some insight into V8's performance on matmul_v1.js benchmark. 

So I cloned official PLB repo, slightly patched matmul_v1.js to make it work with V8's shell instead of d8 (which I do not use) and started digging. 

% svn info $V8 | grep Revision Revision: 7810 % time $V8/shell matmul_v1.js -95.58358333329998 $V8/shell matmul_v1.js 11.16s user 0.15s system 100% cpu 11.264 total

(measurements for this post were done on V8 r7810 so results are slightly different from the ones for r7677 shown in PLB table)

Yikes. 11s are not very exciting especially when PyPy and LuaJIT2 show 8.5s and 2.7s respectively. 

Foes of number representation

The only number type JavaScript and Lua provide is double precision floating point and requires 64 bits of memory. Thus VM implementers have a choice either to make every slot (local variables, objects properties, array elements) wide enough to contain a 64-bit double or to store 64-doubles as boxed values.

V8 goes with the latter approach and boxes† every number that does not fit into 31-bit integer range. Here is for example a backing store of an array [3.14, 1, 2.71, 2] on 32-bit architecture:

LuaJIT2 (as well as JSC and SpiderMonkey) on the other side uses a technique called NaN-tagging, which allows to store both pointers (or other 32-bit values) and doubles in 64-bit wide slots. Here is how the same array will look like in these VMs:

V8's approach allows to save heap space when numbers mostly fit into 31-bit integer range but it also incurs overhead of double indirection and extra allocation when application starts working with dense arrays of floating point numbers. Fortunately there is a solution: WebGL typed arrays. 

† - It should be noted here that V8's optimizing backend is able to keep local double values and temporaries on the stack and in xmm registers. Boxing only occurs when the value escapes optimized code (e.g. is stored to a property, passed as an arguments or returned from a function). Non-optimized code always works with boxed numbers. ↑

Float64Array

Typed array constructed with new Float64Array(N) behaves just like a normal JS object almost in every aspect:

% $V8/shell V8 version 3.3.5 (candidate) > arr = new Float64Array(10) [object Object] > arr.prop = "this is prop"; this is prop > Object.keys(arr) 0,1,2,3,4,5,6,7,8,9,length,BYTES_PER_ELEMENT,prop > arr.prop this is prop

The only observable difference is in semantics of indexed properties. This specialized semantics allows V8 to use unboxed backing stores for such typed arrays.

Will it be cheating to use such specialized data type? I do not think so. We are trying to get some real world data and educate programmers about strength and weaknesses of a particular VM. Nobody uses std::list<std::list<double> > to represent dense matrices in C++. The same applies to all participating languages. For example PyPy's version of matmul benchmark matmul_v2.py uses module array, which provides Python's equivalent of typed arrays. Mike Pall contributed matmul_v2.lua that relies on a low-level FFI type which is not even safe unlike it's Python and JavaScript counterparts:

% ./luajit-2.0/src/luajit LuaJIT 2.0.0-beta6 -- Copyright (C) 2005-2011 Mike Pall. http://luajit.org/ JIT: ON CMOV SSE2 SSE3 SSE4.1 fold cse dce fwd dse narrow loop abc fuse > ffi = require 'ffi' > arr = ffi.new 'double[10]' > for i = 0, 10000 do arr[i] = 0 end zsh: bus error ./luajit-2.0/src/luajit

So here is matmul_v2.js a slightly altered version of matmul_v1.js that uses Float64Arrays to store matrix rows. Some would probably notice that I did not even bother to manually hoist row's loads like somebody did for matmul_v1.js, because V8's optimizing backend is able to perform loop invariant code motion in this case.

% time $V8/shell matmul_v2.js -95.58358333329998 $V8/shell matmul_v2.js 2.61s user 0.07s system 101% cpu 2.650 total

Using the right representation, as you can see, gives a nice 4.2x speedup which puts V8 pretty close to LuaJIT2 and low-level statically typed languages like C.

But LuaJIT2 is still faster! Why?

Indeed. LuaJIT2 is still faster.

% time $LUAJIT/luajit matmul_v1.lua 1000 -95.5835833333 $LUAJIT/luajit matmul_v1.lua 1000 2.26s user 0.05s system 99% cpu 2.325 total

There are two main reasons:

V8 is missing array bounds check elimination. LuaJIT2 is able to hoist bounds checks out of the hot loop, V8 does not try to do that.

V8 has termination and debugging API while LuaJIT2 does not. For example any script on the webpage can be interrupted from Chrome DevTools by the pause button. To support these APIs V8 has to insert an interruption check on the backedge of every loop.

When did you have to multiply two matrices last time?

Most of programmers don't have to deal with matrix multiplication, signal processing and DNA sequencing every day, but it's easy to forget about that when interpreting results of cross language benchmark games, especially if your favorite language implementation is da winner.

But it's really dangerous to base your language choice on such comparisons as they are pretty much one sided (tight numeric loops) and do not cover all important facets of a language implementation.  

Out of curiosity I've rewritten DeltaBlue, constraint solver written in a classical object-oriented style, included into V8 Benchmark Suite from JavaScript into Lua.

When porting benchmark's code from JavaScript to Lua I've used metatables to implement object hierarchy. This approach is widespread in Lua community and is described in the book written by language authors. DeltaBlue does not use any weird JavaScript features so rewrite was very smooth and mostly done by Emacs's "Replace Regexp" :-) I've used Lua for 5 years so I am also pretty sure that result is as close to idiomatic Lua as possible. Original benchmark uses global namespace, which is considered bad taste in Lua, so I created two Lua versions: one directly converted from JavaScript (global variables became global variables) and one with all global variables turned into local variables.

Surprisingly LuaJIT2 does not perform very well on this benchmark:

% time $LUAJIT/luajit deltablue-10000iterations.lua globals $LUAJIT/luajit deltablue-10000iterations.lua globals 55.03s user 0.09s system 99% cpu 55.630 total

% time $LUAJIT/luajit deltablue-10000iterations.lua locals $LUAJIT/luajit deltablue-10000iterations.lua locals 26.72s user 0.04s system 99% cpu 26.824 total

% time $V8/shell deltablue-10000iterations.js $V8/shell deltablue-10000iterations.js 4.64s user 0.04s system 89% cpu 5.213 total

As you can see V8 is roughly 5-12x times faster. Does it mean that LuaJIT2 is a worse compiler? Definitely not. It's probably just not tuned for this kind of workload. (There is also a slight possibility that I screwed somewhere when doing search&replace operations).

Conclusion

Everything has it's own strength and weaknesses. VMs, compilers and even benchmark suites. There is no simple answer when the question is "which language is better?". Even more: to compare two languages you need to be adept in both. 

In the beginning of this post I've mentioned the first rule of benchmark club and I think it's appropriate to conclude by reminding you about the second rule.

The second rule of benchmark club is you DO NOT jump to conclusions.

[mraleph-blog-blog]

Improved V8 external arrays support and nodejs Buffer type

Recently V8's optimizing pipeline (Crankshaft) got full support for external arrays (aka WebGL typed arrays). One of core NodeJS types - Buffer - is exposed to JavaScript code as an external unsigned byte array so I decided to do a small unscientific benchmark to see the improvement with my own eyes:

var LONG_STRING = "qwertyuiop"; for (var i = 0; i < 13; i++) LONG_STRING += LONG_STRING; // force cons-string flattening outside of timed loop. LONG_STRING.charCodeAt(); console.log("LONG_STRING is %s chars long", LONG_STRING.length); function Str2BufferJS(s) { var length = s.length; var b = new Buffer(length); for (var i = 0; i < length; i++) b[i] = s.charCodeAt(i); return b; } function Str2BufferNative(s) { var length = s.length; var b = new Buffer(length); b.asciiWrite(s, 0); return b; } var N = 1000; function LoopAndTime(name, f) { var start = Date.now(); for (var i = 0; i < N; i++) f(); var end = Date.now(); console.log("%s took %s ms per %s calls", name, end - start, N); } LoopAndTime("Str2BufferNative", function() { Str2BufferNative(LONG_STRING); }); LoopAndTime("Str2BufferJS", function() { Str2BufferJS(LONG_STRING); });

Results were fascinating:

# node 0.4.4 with V8 3.1.8.5 LONG_STRING is 81920 chars long Str2BufferNative took 224 ms per 1000 calls Str2BufferJS took 1180 ms per 1000 calls # node 0.4.4. with V8 3.2.7 (current bleeding_edge) LONG_STRING is 81920 chars long Str2BufferNative took 254 ms per 1000 calls Str2BufferJS took 231 ms per 1000 calls

As you can see JS function optimized by Crankshaft is now on par with native implementation of Buffer.writeAscii.