ParallelJS: data parallelism for JavaScript

By -
Updates:



JavaScript is still a very sequential language. That is slowly changing. This blog post describes ParallelJS, an effort to bring data parallelism to JavaScript.



Background



Concurrency versus parallelism




  • Parallelism: more than one task is executed at the same time. That means that the tasks run on different processors or processor cores.

  • Concurrency: more than one task makes progress at the same time. Often, tasks depend on each other. Concurrent tasks may run in parallel, but they can also be run via time slicing (virtual parallelism, if you will).



These terms are not always used precisely, but the context usually makes it clear what is meant.

Kinds of parallelism



Two models of parallelism are:

  • Data parallelism: The same piece of code is executed several times in parallel. The instances operate on different elements of the same dataset. For example: MapReduce is a data-parallel programming model.

  • Task parallelism: Different pieces of code are executed in parallel. Examples: Web Workers and the Unix model of spawning processes.



ParallelJS tackles data parallelism.

ParallelJS (PJS)



ParallelJS started its life as River Trail, a JavaScript language extension for Firefox by Intel. River Trail provides a new constructor, ParallelArray with iteration methods whose callbacks are executed concurrently.


ParallelJS brings the RiverTrail idea to normal arrays and has recently been included in Firefox Nightly. It adds three methods to arrays (binary data will eventually get those methods, too):


  • Array.prototype.mapPar()

  • Array.prototype.filterPar()

  • Array.prototype.reducePar()



These methods work like the traditional array methods map(), filter() and reduce(), but the order in which the elements are processed is undefined (with the non-par versions, you know exactly in which order they are processed). That enables concurrent execution of multiple instances of the callback. However, not all callbacks can be run concurrently. A callback must fulfill certain requirements:

  • It must not mutate shared data. It can freely change data that it has created, but can only read data from the outside world.

  • Many host (or “native”) objects can’t be used. That includes the DOM, which may never be supported and regular expressions for which short- to mid-term support is likely. All vanilla JavaScript objects are fine, though.


PJS code is executed like this: It is first run sequentially and observed. The requirements for parallelism are checked. If they are fulfilled, parallel code is produced and run in parallel. If any of the requirements are not fulfilled anymore, then PJS reverts to sequential execution.


The rules for when PJS code can be run concurrently will probably never be standardized, because a PJS standard needs to accomodate a variety of implementation approaches (see below). There will, however, be guidelines and recommendations for what works for most implementations.


Given how difficult it is to predict whether your code can be run concurrently or not, an important part of PJS will be diagnostic tools. They will let you find out when and why code is not parallelizable.


ParallelJS is currently tentatively scheduled for ECMAScript 8. If you are worried that that’s too far into the future: ECMAScript 7 and ECMAScript 8 will be smaller and developed more quickly than ECMAScript 6.

Modes of execution



There are several conceivable ways of executing PJS code:

  1. Sequentially: a shim can make the PJS array methods available on older engines

  2. Concurrently: run multiple instances of the callback concurrently. The operating system can distribute those instances across cores.

  3. SIMD: use SIMD processor instructions (such as Intel’s SSE) for faster processing.

  4. GPU: run vectorized code, but on the GPU instead of the CPU.


The current PJS implementation supports #2. A shim for older engines is available, too. #3 and #4 are being explored but will probably take a while to be implemented.

Task parallelism



Mozilla is also considering added task parallelism to JavaScript; fork-join style, via functions to whom rules apply that are similar to PJS’s (don’t mutate shared state, etc.). The two approaches are very similar, you could probably implement a simple version of PJS via the task parallelism primitives.
Therefore, the task parallelism exensions will profit greatly from the work done for PJS. This new kind of task parallelism would be more lightweight than Web Workers and be added to the language proper (as opposed to be part of the web platform).

Sources



This post is based on the following blog posts by Mozilla researcher Nicholas D. Matsakis.

Comments

Post a Comment

Popular posts from this blog

Steve Lopez and the Importance of Newspapers

By -
Image
It has been one year since I cancelled my subscriptions to The New York Times and the Los Angeles Times . In that time, I continued to read both publications online. My assessment of this experiment is that reading newspapers and journalism online is vastly inferior to the hard copy thrown on my porch each morning. So I restarted my subscription to the Los Angeles Times and I have made it a point to buy The New York Times as often as I pass one of those coin boxes or my local news stand. The catalyst for this re-evaluation resulted from catching the film, The Soloist on cable last week. I liked the movie, although the scenes I found most interesting were the ones that showed columnist Steve Lopez at work. I realized the book was sitting in my “to-read” stack, so I pulled it and began reading. The book, as I expected, is better than the film. Lopez clearly addresses the revolution occurring in journalism, and worries about his future with the paper even as he researches and writes...
Keep reading

Ideas for fixing unconnected computing

By -
I traveled quite a bit recently and got exposed to a negative aspect of current technology: Things work well if you have a solid internet connection with no traffic limits and are plugged into a power outlet. Otherwise, things do not work well at all. This blog post describes the problems that arise and suggests solutions. Managing data traffic Cell phones are quite good at conserving traffic, laptops much less so. This becomes a problem when your laptop has a mobile connection (e.g., via tethering or in a hotel with data caps). I once accidentally started iTunes in such a situation and immediately used up my daily allowance of traffic. Similarly, mobile email is frugal with traffic (only the current folder is updated, attachments are only downloaded on demand, etc.), desktop email is usually not. How can this be handled better? I’d like to see three traffic modes for all operating systems: “full”, “restricted”, “minimal”: In full traffic mode , all data transfers are allowed and happe...
Keep reading

Omar to kill me

By -
Image
  The sentence “ Omar m’a tuer ” is unintelligible French, as if it had been written by an illiterate person. At first sight, Mme Ghislaine Marchal —the author of those words in blood—seems to be saying that she had been killed by Omar in her villa at Mougins (Alpes-Maritimes). But why would that dying French lady have used such poor grammar? On that flimsy evidence, in 1991, the Moroccan gardener Omar Raddad was condemned and jailed. But he persisted non-stop upon his innocence. In 1998, he was liberated, and now lives in Morocco. A recent analysis of DNA specimens from the scene of the crime provides new facts. Four males, none of whom was Omar Raddad, have left traces of their presence. Will the real murderer be identified at last?
Keep reading