mraleph

> Interesting to see them moving away from AST-to-ASM and building an IR, which looks to be a CFG.

V8 actually has been using a compiler with a proper IR since 2010 when Crankshaft[1] was released.

[1] http://blog.chromium.org/2010/12/new-crankshaft-for-v8.html

> Lua also has finalizers, which effect the GC's design.

V8 has a weak callback mechanism, which (while not exposed to JS) allows reentering JS from inside a weak callback - which means you can emulate Lua's __gc on top of this mechanism.

> The Lua/C api also makes it impossible for the GC to move objects, which means pretty much every current JS VM's GC is out.

If we disregard lua_topointer then Lua/C API only leaks internal pointers for strings (lua_tostring), userdata (lua_newuserdata, lua_touserdata) and threads (lua_newthread,lua_tothread) - everything else is manipulated using lua_State's stack.

This means VM only has to take care with regards to these objects. Userdata and threads can be just allocated outside of movable part of the heap and strings can be "externalized" (i.e. they payload relocated into the immovable space) on first access via lua_tostring. Coincidentally last thing is something that V8 supports[1] (though of course externalization is not a cheap operation as it requires copying).

> Lua 5.3 has 64 bit integers, which would effect most JS VM's in a significant way

Yeah, that's certainly a whole ton of work, but most of this work would be pretty technical.

JS engines might actually get int64/uint64 value types in the future (at some point there was an ES7 proposal - but currently it does not seem to be on track for inclusion).

[1] https://github.com/v8/v8-git-mirror/blob/master/include/v8.h...

> Worth noting that IIRC, for a while LuaJIT in interpreted mode was able to beat V8 in optimized mode not all that infrequently

V8 had no optimizing compiler when Mike Pall sent his (in)famous mail about "LuaJIT interpreter beating V8 compiler"[1].

Also usual disclaimers about cross-language benchmarks apply (e.g. nobody looked how those benchmarks differ between JS and Lua implementation).

[1] http://lua-users.org/lists/lua-l/2010-03/msg00305.html

Arguably it's an optimization that compiler could perform instead and a method JIT most likely would. However tracing JIT's optimizations are confined to a linear trace - which I guess exactly the limitation the author wanted to demonstrate.

I would not call it a performance hack, it's just a readable way to write an algorithm - most important part of my original suggestion was actually to use x.charCodeAt(i) instead of x[i]

It's written with continue precisely to avoid additional `if (j === hlen)` check after the loop and having a single increment of `j` in the loop :)

To be honest reasoning about the loop with continue is actually easier than about one without.

> The set of things you are worrying about it actually precisely the set of things CLZ solves :)

I think the set of things I worry about is slightly different, because they operate in a static environment and I operate in a dynamic one. For example, they don't seem to be worried about the transformation from:

  loop {
    if (pred) {
      // o and o.f are loop invariants
      Guard(o is X);
      v = Load(o.f);
      Use(v)
    }
  }

to

  Guard(o is X);
  v = Load(o.f);
  loop {
    if (pred) {
      Use(v)
    }
  }

this tranformation might or might not be "beneficial" depending on relation between predicate and the guard - e.g. it can lead to a code which will just deoptimize on the guard before entering the loop. There is no way of knowing this statically, so you just have to take a bet (unless you have clear indications that guard will fail when hoisted) and then undo your decision later.

> The only case that arr.length could change, and hence the if statement taken, is if the if statement had already been taken - i.e. arr.length had already changed.

Fair point. I misread your original comment. To see this you need a more sophisticated analysis pass than V8 is capable of performing - something similar in spirit to sparse conditional constant propagation, V8's LICM just assumes that all blocks are reachable so it takes the union of all possible side-effects.

> So that's not a good excuse.

I am not making an excuse, I am simply stating a fact: this is a slide deck, it needs JS to operate. As simple as that. If there is an easy fix - please send me a PR[1], I will gladly take it

[1] https://github.com/mraleph/mraleph.github.com/tree/master/ta...

I always pronounce it as /līkm/, but I am not a native speaker so I can't be sure about correct pronunciation.

> Why does this require JS (to the point of giving a blank page!) for something that can be trivially done without?

This is a slide deck (not a blog post or article) hence its dependence on JS.

(though even blog posts I write usually depend on JS to provide proper syntax highlighting and diagrams)

> Can someone explain to me why it has to assume that arr.length could change? It states it does, but I don't see why.

If you don't know where `throwConcurrentModificationError(arr)` goes then you don't know what it does, e.g. it can do something like this:

    H.throwConcurrentModificationError = function (arr) {
      arr.push(10);
    };

(contrary to its name - but JITs don't optimize based on names)

That's why JIT has to assume global side effects from the `throwConcurrentModificationError` call - unless of course it emits an unconditional deoptimization right before it which is what happens in the (0, o.f)() case.

Yes, you are absolutely right - semantics is quite different. But that's not what changes perf here - the difference comes from whether there is an explicit property load or a property load is an implicit part of the method call. This change is also made in the code that never executes during the benchmark run - which adds to a conundrum.

There is a very V8 / Crankshaft specific thing going on here - slides try to explain it.

Thanks, I am glad you like my blog :)

I might write something about TF but right now it's still not used to compile normal code and the team is just starting on stuff like adaptive optimizations, so it's a bit too early.

Also given that I don't work on V8 anymore I always think it's a bit unfair for me to do it --- somebody from V8 team should do it instead, cause my perspective is bound to be slightly different from theirs :)

Indeed there are some relatively well understood negative consequences to LICM and various other redundancy elimination optimizations: e.g. they increase life-time of values which can have negative impact on register allocation. Another thing is getting LICM right in the presence of conditional control flow within the loop is a non-trivial exercise, in dynamically typed languages this becomes a problem because JIT in general wants to hoist type guards aggressively but it has to account for conditional control flow to avoid weird/unnecessary deopts

Oops, sorry for that. Forgot to shrink them before publishing. Will fix as soon as I get to a place with a stable internet connection - traveling right now.

upd. done, scaled down to 1024x768

I obviously craft/collect examples of V8 going off the rails for these talks just to show that VMs are software and all software has bugs --- and those bugs don't necessarily manifest as crashes and incorrect results - they can lead to worse performance and developers must be ready for this: must be ready to diagnose these issues, report them and work around them.

For a single test case where V8 goes off the rails there are millions of lines of code across the globe which V8 optimizes correctly.

On a funny note: I actually do have a version of this talk where I show GCC going slightly of the rails and producing a code that is 3 times slower than it should be because it hits an (infamous) partial register dependency stall --- see StackOverflow question[1] for the gory details.

> How do I ensure that the VM does not execute my 'dumb but readable' code literally?

Well, as I do say in the talk: reasonable code should be reasonably fast. If it is not the case --- file bugs with VM vendors.

Keeping your code relatively static / monomorphic is the best way to achive performance in any language.

In any case I think it's much much much more important to optimize algorithms not their concrete implementations.

[1] http://stackoverflow.com/questions/26585977/64-bit-code-gene...

> LICM is a very simple thing to do.

Yeah, it sometimes surprises me how much value the most simple optimizations have and how much they break people's attempts to measure performance.

There is another side to this medal which is best expressed in a quote I picked up from a relatively old paper:

"A survey of the literature on optimization uncovers many techniques that are hard to understand, harder to implement, more general than necessary and of marginal value. Our approach was to do the most profitable machine independent optimizations in the most profitable way" (A Portable Optimizing Compiler for Modula-2 by Michael L. Powel)

In some sense the more microbenchmarks an optimization breaks the bigger its impact on real world code is :)

It was recorded but I don't know when it will be publicly released.

This talk is a combination of two separate talks I have given before plus two new examples, based on my recent endeavors.

Talks merged here are LXJS 2013 one[1] where I talk about microbenchmarking pitfalls and WebRebels 2014 one[2] where describe how bugs in VMs can affect benchmarking results.

If you have any questions about the slides just ask them here or send me an email --- I will try to answer as soon as I can.

[1] https://www.youtube.com/watch?v=65-RbBwZQdU

[2] https://webrebels.23video.com/crooked-mirrors-of-performance...

Dart VM is an essential part of the Dart ecosystem.

Dart tools: pub's (package manager) client, analyzer, dart2js compiler, etc are all written in Dart.

We have a good story for server side developement and we are not looking to abandon it but rather we are looking to expand it, e.g. we just released a package to facilitate creation of REST APIs[1]. Pub's server side is being rewritten into Dart as we speak[2]

Among cool internal users of Dart VM I could mention Google Fiber - they'll share their experience during the upcoming Dart Summit[3].

[1] http://news.dartlang.org/2015/03/create-your-own-rest-api-wi...

[2] https://github.com/dart-lang/pub-dartlang-dart

[3] https://www.dartlang.org/events/2015/summit/sessions/google-...

Dart VM is not going anywhere.

Sealing prototypes is easy - V8 already "pseudo"seals them: it removes the map checks against prototypes and instead deoptimizes the code depending on hidden classes when somebody changes them.

Similar pseudo-sealing technique can be applied to objects: when optimizing some code you can assume that if some hidden class is a leaf in the transition tree it is no likely to change - then make the code depend on this assumption. This would mean you only need to check this once.

I think the most interesting part that stricter-minus-types mode brings to the table (at least it's informally described part) are hole-less arrays. This is something that is missing from the ES as it is described now: new Array(N) is producing a hole-full array. V8 is capable of tracking whether array is containing holes or not - but the way to efficiently preallocate holeless version is simply missing from the ECMAScript.

Thanks for the update.

I posted this reply on your site, but I will duplicate it here for the sake of HN readers:

> BTW --nouse-osr makes all three tests run faster.

As I tried to explain above: OSR at it is implemented now impacts code quality depending on which loop OSR hits. Which in turn depends on heuristics that V8 uses. These heuristics are slightly different in newer V8. As a result of these changes V8 hits inner loop instead of outer loop. This leads to worse code.

Code that benefits from OSR is the code that contains a loop which a) can be well optimized b) runs long b) is run only few times in total. The Sieve benchmark is opposite of this and as a result it doesn't benefit from OSR - you get bigger penalty from producing worse code and no benefit from optimizing slightly earlier.

Not using OSR for Sieve also hides the other issue with mortality of typed array's hidden classes. I say "hides" not "fixes" because one can easily construct a benchmark where the mortality would still be an observable performance issue even if benchmark itself is run without an OSR: https://gist.github.com/mraleph/2942a14ef2a480e2a7a9

Is it 10% slower even if you keep array alive and apply --nouse-osr (to both node.js and io.js)?

On my machine results are fluctuating within the same ballpark (though I am on Linux and benchmarking 64-bit builds).

Ok reporting back. There are two issues here.

The first major one is related to mortality of TypedArray's maps (aka hidden classes). When typed array stored in the Data variable is GCed and there are no other Uint8Array in the heap then its hidden class is GCed too. This also causes GC to find and discard all optimized code that is specialized for Uint8Array's and clear all type feedback related to Uint8Array's from inline caches. When we later come and reoptimize - optimizing compiler thinks that cleared type feedback means we need to emit a generic access through the IC (there is reasoning behind that) because this is potentially going to be a polymorphic access anyways. I have filed the issue[1] for the root cause (mortality of typed array's hidden class).

Now there is a second much smaller issue (which also explains performance of the Buffer case) - apparently there were some changes in the optimization thresholds and OSR heuristics. After these changes we hit OSR at a different moment: e.g. I can see that we hit inner loop one that loops over `j` instead of hitting outer loop which leads to better code. In V8 OSR is implemented in a way that tries to produce optimized code that is both suitable for OSR and as a normal function code - this is done by adding a special OSR entry block that jumps to the preheader of the selected loop we are targeting with the OSR. This allows V8 to reuse the same optimized code without optimizing it again for the normal entry - but this also leads to code quality issues if OSR does not hit the outer loop because OSR entry block inhibits code motion. This is a know problem and there are plans to fix it. The hit usually is quite small unless you have very tight nested loops (like in this case).

Disabling OSR (--nouse-osr) not only "solves" the second issue but it also partially fixes (hides)the first issue: 1) we no longer optimize with partial type feedback - so we never emit generic keyed access but always specialize it for the typed array 2) we no longer emit OSR entry - hence no code quality issues related to it.

[1] https://code.google.com/p/v8/issues/detail?id=3824

I can explain what happened to Array case. 100000 used to be the threshold at which new Array(N) or arr.length = N started to return a dictionary backed array. Not anymore: this was changed by https://codereview.chromium.org/397593008 - now new Array(100001) returns fast elements array.

I will check out what happened to Buffer/TypedArray. Should not degrade that much unless something really goes south here.

Try running something OOPy instead of a tight loopy code, e.g. DeltaBlue, you will discover that LuaJIT has weaknesses too.

Though I must admit V8 could handle dictionaries a bit better - but at the moment it does not.

I have amended the section, please check it out.

There is certain technical heritage here.

Originally method calls compiled down to a single IC that did load and call within a IC stub. Type feedback from these ICs was interpreted in the same way as from property load ICs. On the other hand function calls cb(...) compiled down to a call through CallFunctionStub which did not record any feedback whatsoever. At some point CallFunctionStub learned to record a bit of type feedback (monomorphic / megamorphic) and we started using it in Crankshaft for speculative inlining.

Only recently method calls were decomposed into Load IC and a separate Call IC (an evolved CallFunctionStub) which invokes loaded function. For property invocation o.m(...) feedback comes from the Load IC now, and Call IC feedback is ignored. For variable invocation cb(...) feedback comes from the Call IC - which is still only able to distinguish only monomorphic and megamorphic state.

> I do think the blog post implies that v8 can't do polymorphic inlining.

It took me a bit to realize where this confusion comes from (especially given the whole discussion of how polymorphic property access is handled). Is it due to "Undiscussed - Not all caches are the same" section?

Indeed V8 can't at the moment do polymorphic inlining at non-method callsites - f(), however it can on method callsites o.m().

The reason for this is lack of type feedback.

I will seek to clarify the wording in that section.

> Aside: That was a very thorough and well written blog post, mraleph :) A very enjoyable read.

Thanks.

V8 can inline at bimorphic (trimorphic and quadmorphic :)) site. That's explicitly stated in the post: see the part about decision tree building. When you inline at polymorphic site in the worst case you have branching flow graph that decides which particular operation to pick. Rewriting example from the post into Java terminology yields:

    if (o.getClass() == A.class) {
      // inlined variant that matches A
    } else if (o.getClass() == B.class) {
      // inlined variant that matches B
    } else if (o.getClass() == C.class) {
      // inlined varint that matches C
    } else {
      $Deoptimize(); // -> exit, this never returns.
    }

[Note: `$GetShape(o)` became `o.getClass()`]

V8 can do this. If inlined variants for A, B and C are all the same V8 can also do

    // Check that we are either A, B, C
    if (o.getClass() != A.class &&
        o.getClass() != B.class &&
        o.getClass() != C.class) {
      $Deoptimize();  // -> exit, this never returns
    }
    /* inlined variant for A, B, C */

However in both cases you pay penalty for the conditional control flow and in the first case V8 is unable to merge subsequent decision trees in any way to eliminate redundancy between them so `o.x + o.y` might end up compiled into something like (assuming polymorphic code that uses objects of shapes {x, y} and {y, x}):

    int o_x;
    if (o.getClass() == A.class) {
      o_x = $LoadByOffset(o, 12);
    } else if (o.getClass() == B.class) {
      o_x = $LoadByOffset(o, 16);
    } else {
      $Deoptimize(); // -> exit, this never returns.
    }
    int o_y;
    if (o.getClass() == A.class) {
      o_y = $LoadByOffset(o, 16);
    } else if (o.getClass() == B.class) {
      o_y = $LoadByOffset(o, 12);
    } else {
      $Deoptimize(); // -> exit, this never returns.
    }
    o_x + o_y

That's a lot of repetitive branching right here. Arguably the code quality can be substantially improved by merging ifs like this:

    int o_x, o_y;
    if (o.getClass() == A.class) {
      o_x = $LoadByOffset(o, 12);
      o_y = $LoadByOffset(o, 16);
    } else if (o.getClass() == B.class) {
      o_x = $LoadByOffset(o, 16);
      o_y = $LoadByOffset(o, 12);
    } else {
      $Deoptimize(); // -> exit, this never returns.
    }
    o_x + o_y

but at the moment V8 does not do this hence the penalty is higher.

I totally agree with you! I would love to have equivalent functionality built right into Dev Tools. Immediacy is a very important aspect of usability - I would like to inspect a running program without any special movements.

> upload files to a web page.

Minor clarification: nothing ever leaves your local computer. There is no server component in IRHydra. It's purely your browser that interprets these files.

Thanks! You are absolutely correct in summarizing two underlying themes for my microbenchmarking related posts: (a) one needs to understand what one is measuring (b) one needs to understand if that actually matters for their project.

> Currently, I find the external tools for doing this hard enough to set up

I have tried making this kind of information easier to grok for JavaScript developers by creating IRHydra[1]. Please reach out and describe your issues - one of the reasons why something like IRHydra is not part of Dev Tools yet is that Dev Tools people are not registering big demand for indepth analysis tools.

[1] http://mrale.ph/irhydra/2