Dave Herman and I were tossing around ideas the other day for a revision of the typed object specification in which we remove nominal array types. The goal is to address some of the awkwardness that we have encountered in designing the PJS API due to nominal array types. I thought I’d try writing it out. This is to some extent a thought experiment.

Description by example

I’ve had a hard time trying to identify the best way to present the idea, because it is at once so similar and so unlike what we have today. So I think I’ll begin by working through examples and then try to define a more abstract version.

A quick follow-up to my previous post. The approach I suggested (“generate boxing instructions but bypass them when possible”) is in some sense pessimistic: we generate the instructions we need for the worst case and then cleanup. Like many problems in computer science, it has an optimistic dual. We could generate unboxed data and then insert boxes where needed. In fact, we have an existing mechanism for doing that, called the type policies. Basically, there is a phase where each MIR opcode goes through and examines the types of its inputs, attempting to reconcile those types with what it needs, either by boxing or unboxing as needed.

There is currently some ongoing effort to implement the proposed JavaScript SIMD API in Firefox. The basic idea of the API is to introduce explicit vector value types called float32x4 and int32x4. These types fit into the typed objects hierarchy, so you can create arrays of them, embed them in structs, and so forth.

The semantics of these vectors types is designed to make it possible for JIT engines to detect and optimize their use. One crucial bit is that they are values and hence do not have identity. Basically float32x4 values work like numbers and strings do today – they are equal if they have the same value. This is quite different from objects, which may be unequal if their properties are the same (e.g., {} !== {}).

I want to optimize assignments to struct-typed fields in typed objects. This post is an effort to work through my optimization plan.

The goal

Imagine some code like this:

var PointType = new StructType({x: int32, y: int32});
var LineType = new StructType({from: PointType,
                               to: PointType});
var line = new LineType();
line.to = {x: 22, y: 44};

The last line in particular is the one I am interested in. Today we execute this in the most naive way. The code which ion generates looks something like:

I think someone reading this blog would be forgiven for thinking that I must spend most of my energy thinking about Rust. In fact I spend a good part of my working hours hammering on PJS. I thought I’d try to write up a bit of a preview of the things we are working on.

Parallel methods on arrays

Right now, on Nightly Firefox builds, you can use the parallel methods mapPar, filterPar, and reducePar on normal JS arrays. These work basically like their sequential equivalents except that they execute in an undefined order (for reducePar, that can be a more significant difference, since both the left and right operand might be the result of a reduction). That means you can write code like:

Yesterday Dmitry Lomov and I had a discussion about the typed objects API. Much of the discussion revolved around the specific issue of handles. In this post I will summarize the issues we discussed and review the various design options.

I’ll begin with a summary of what handles are and how they are used in current APIs; if this is familiar to you (cough Dave Herman cough) you may want to skip ahead to the section “Subtle points”.

Since I last wrote, we’ve made great progress with the work on the Parallel JS and Typed Objects (nee Binary Data) implementation. In particular, as of this morning, preliminary support for typed objects has landed in Mozilla Nightly, although what’s currently checked in is not fully conformant with the current version of the standard (for this reason, support is limited to Nightly and not available in Aurora or Beta builds).

Since the new version of PJS is going to be based on binary data, we are going to need to have a well-optimized binary data implementation. Nikhil Marathe has prepared an initial implementation, but it is limited to the interpreter. I am looking now at how to integrate binary data into the JIT. The goal is to have accesses get compiled to very efficient generated code. In this blog post, I specifically want to cover the plan for integrating our type inference with binary data.

We’ve been making a lot of conceptual progress with the PJS API that has not been written down anywhere, so I want to cover some of that work. This post focuses on the integration of parallel methods with the binary data API. It shows how the new API approach allows users to avoid allocation for higher efficiency.

Methods, not types

We are moving away from a ParallelArray type and into methods that will be offered on existing array types. Current plan is to name them things like pmap (vs normal sequential map). The defined semantics are similar to the sequential version except that the order of iterations is undefined, because iterations may occur in parallel (I described the subset of JS that we expect to parallelize in a previous post).

I want to look at an interesting topic: what subset of JavaScript do we intend to support for parallel execution, and how long will it take to get that working? As my dear and loyal readers already know, our current engine supports a simple subset of JavaScript but we will want to expand it and make the result more predictable.

From my point of view, the subset below includes basically all the JavaScript syntax that I ever use. There are two primary limitations that I think people will encounter in practice:

In my last post about ParallelJS, I discussed the ForkJoin() intrinsic and showed how it was used to implement the parallel map operation. Today I want to write about the high-level changes to IonMonkey that are needed to support ForkJoin(). IonMonkey, of course, is our JavaScript engine.

Parallel execution mode

To support ParallelJS, we introduce a second mode of compilation called parallel execution mode. JavaScript compiled in this mode produces executable code that is suitable to be run in parallel. To accommodate this new mode, each JSScript* potentially contains pointers to two IonScript* data structures, one for standard sequential mode and one for parallel mode.

One common criticism of the work on ParallelJS is that the API itself does not guarantee parallel execution. Instead, our approach has been to offer methods whose definition makes parallel execution possible, but we have left it up to the engines to define the exact set of JavaScript that will be safe for parallel execution.

Now, I definitely think it is a good idea to clearly define the subset of JavaScript that our engine will be able to execute in parallel. As I wrote in my preivous post, I want to do this both via documentation and via developer tools that provide live feedback. In some cases, I think, the rules will probably depend on type inference or other dynamic analysis techniques that are subtle and hard to explain, but live feedback should be helpful in detecting and resolving those cases.

I am going to write a series of blog posts giving a tour of the current Parallel JS implementation in SpiderMonkey. These posts are intended to serve partly as documentation for the code. The plan is to begin high level and work my way down to the nitty gritty details, so here we go!

I will start my discussion at the level of the intrinsic ForkJoin() function. As an intrinsic function, ForkJoin() is not an API intended for use by end-users. Rather, it is available only to self-hosted code and is intended to serve as a building block for other APIs (ParallelArray among them).

The first version of our work on ParallelJS has just been promoted to mozilla-central and thus will soon be appearing in a Nightly Firefox build near you. I find this pretty exciting. In honor of the occassion, I wanted to take a moment to step back and look both at what has landed now, what we expect to land soon, and the overall trajectory we are aiming for.

What is available now

Once Nightly builds are available, users will be able to run what is essentially a “first draft” of Parallel JS. The code that will be landing first is not really ready for general use yet. It supports a limited set of JavaScript and there is no good feedback mechanism to tell you whether you got parallel execution and, if not, why not. Moreover, it is not heavily optimized, and the performance can be uneven. Sometimes we see linear speedups and zero overhead, but in other cases the overhead can be substantial, meaning that it takes several cores to gain from parallelism. Nonetheless, it is pretty exciting to see multithreaded execution landing in a JavaScript engine. As far as I know, this is the first time that something like this has been available (WebWorkers, with their Share Nothing, Copy Everything architecture, do not count).

Lately, I’ve been thinking about the ParallelJS API that we want to expose. In particular, I’ve been considering offering methods on the normal array type for basic parallel operations. I think this opens up some interesting doors.

Note: To give credit where credit is due, I should note that a lot of the ideas in this post originate with other members of the Parallel JS team (Shu-yu Guo, Dave Herman, Felix Klock). But I don’t want to speak for them, since we seem to each have our own opinions on the best arrangement, so I’m writing the post from the first person singular (“I”) and not a team perspective (“we”). This does not imply “ownership” of the ideas within.

In my last post, I made the case against having a deterministic semantics. I’ve gotten a fair amount of feedback saying that, for a Web API, introducing nondeterminism is a very risky idea. Certainly the arguments are strong. Therefore, I want to take a moment and make the case for determinism.

Why determinism?

All things being equal, it’s clear that deterministic execution semantics are preferable. They’re easier to debug and they avoid the question of browser incompatibilities.

One of the interesting questions with respect to Parallel JS is what the semantics ought to be if you attempt a parallel operation with a kernel function that has side-effects. There are basically three reasonable options:

1. Deterministic results where possible: The function behaves “as if” it executed sequentially, executing the kernel from 0 to n, just like Array.map.
2. Error: An exception is thrown.
3. Non-determinstic results: The function behaves “as if” it executed sequentially, but the items were mapped in an unspecified order.

The branch currently implements option 3: I believe it is the most consistent and will yield the best performance. However, reasonable people can differ on this point, so I want to make my case.

I mentioned in my previous post that we are using a single primitive parallel operation to implement PJs. It turns out that I am not very satisfied with what we currently have and I have been thinking about some alternatives. In this post I’ll describe briefly how things are setup, what problems I see, and then sketch out how I think we could improve it.

How things work now: %ParallelBuildArray()

The current intrinsic is %ParallelBuildArray(length, func, args...). It attempts to construct an array in parallel using a pool of N worker threads. Conceptually, %ParallelBuildArray() allocates an array result of length length and then instructs each worker thread to invoke func(result, id, N, warmup, ...args), where:

The blog has been silent for a while. The reason is that I’ve been hard at work on Parallel JS. It’s come a long way: in fact, the goal is to land an initial version in the next couple weeks!

One of the very exciting developments has been that we switched to a self-hosting implementation. Self-hosting is a very cool new direction for the SpiderMonkey engine being introduced by Till Schneidereit. The idea is to implement large parts of the engine itself in JavaScript, similar to projects like Squeak, Jikes RVM, Maxine, PyPy and numerous others. As an example, imagine the standard JavaScript function Array.map. In SM, this is currently implemented with approximately 80 lines of C++ code. This function must handle all sorts of annoying conditions, such as ensuring that objects are rooted, checking for interrupts, and using an optimized call sequence to make it faster to invoke the JS code. If the implementation were written in JS, however, all of these issues would be handled automatically by the engine itself, just as they are for any other JS function.

I can’t believe I’m saying this, but I’ve started to think that Parallel JS (nee Rivertrail) should not demand pure callbacks to functions like map() and so forth. Rather it should just accept arbitrary functions. Previously, I thought that it was important that ParallelArray methods should only accept functions which, at least in a perfect world, would be safely parallelizable. But I am no longer so sure why that is an important goal. Here is my reasoning.

In this post I propose an extension of Rust’s purity rules. The short version is that pure functions would be allowed to mutate data owned by their &mut parameters. This extends the current Rust purity rules which allow pure functions to invoke impure closures so long as they are an argument to the function. The principle is the same: pure functions are functions whose side-effects can be completely determined by examining their parameters (for the more formally minded among you, this is effectively an effect-parametric system with very lightweight notation). The rest of the post is an elaboration and justification of this idea.

I have started work on implementing Rivertrail, Intel’s proposal for data parallelism in JS. I am excited about this project, it seems like it’s going to be great fun. The initial version that we produce is going to be focused on Intel’s specification, but I hope we can eventually combine it with the more general stuff I’ve been doing as part of PJs. There is an awful lot of overlap between the two, though also a few minor differences that will need to be ironed out.

It’s been a while since I wrote anything on the blog! A lot has been going on in the meantime, both in Rust, parallel JavaScript, and personally…I hate to write a big update post but I gotta’ catch up somehow!

Rust

First, we made our 0.1 release, which is great. We are now planning for 0.2. The goal is to make frequent, relatively regular releases. We’re still in such an early phase that it doesn’t seem to make sense to literally release every few months, but at the same time we don’t plan to wait long.

In one of the comments on yesterday’s post, Tushar Pokle asked why I would champion my model over an Erlang model of strict data separation. There are several answers to this question. The simplest answer is that Web Workers already provide an actors model, though they do not make tasks particularly cheap (it’s possible to work around this by creating a fixed number of workers and sending tasks for them to execute).

Lately the ideas for a parallel, shared memory JavaScript have begun to take shape. I’ve been discussing with various JavaScript luminaries and it seems like a design is starting to emerge. This post serves as a documentation of the basic ideas; I’m sure the details will change as we go along.

User Model

The model is that a JavaScript worker (the “parent”) may spawn a number of child tasks (the “children”). The parent is suspended while the children execute, meaning that it will not process events or take other actions. Once the children have completed the parent will be re-awoken.