Rivertrail: concurrency in javascript

The use of the possibilities of parallelism has now become a common practice in programming. However, all languages can be divided into two types: those in which parallelism is applied with might and main and actively (for example, C), and those that have not yet tasted the joys of multithreading. These include JavaScript in particular. To fill this annoying gap and fill up the piggy bank of progressive experience, we bring to your attention the translation of a message from the blog of Nick Matsakis , a programmer at the Mozilla Foundation, in which he shares his first personal impressions of using Rivertrail, a parallelization tool in JavaScript created by Intel.

Recently, I started using Rivertrail - a product offered by Intel as a tool for paralleling data in JS. The project so far leaves only positive impressions. The initial version will be tied to Intel's specifications , but I hope that it will then be possible to combine it with other projects created in the framework of PJs.

Rivertrail for Dummies

Here is a small intro for those who have not heard of this product before: Rivertrail is a specification that allows processing an array in parallel. The specification is based on the addition of the ParallelArray class. These arrays have a number of key differences from JS arrays.

they are unchanged
do not have gaps
they can be multidimensional, but multidimensional “correctly” (for example, in a two-dimensional matrix the number of columns will be equal to the number of rows).

Parallel arrays support a fairly large number of high-level operations, such as () map and () reduce , and more. A complete list can be found in the Rivertrail specification . These methods take functions as an argument, and work in much the same way as the corresponding functions in regular JS arrays. In addition to a couple of important differences:

first, the functions that are taken as an argument should always be “pure” (pure), a little lower on this;
secondly, where possible, the JS engine will try to perform these functions in parallel.

Pure functions

These are normal JS functions that do not change the shared state. This does not mean that functions cannot change anything at all - local variables and objects allocated by the function itself can change.
')
For example, the function calculating the Mandelbrot set is pure:

function mandelbrot(x, y) { var Cr = (x - 256) / scale + 0.407476; var Ci = (y - 256) / scale + 0.234204; var I = 0, R = 0, I2 = 0, R2 = 0; var n = 0; while ((R2+I2 < 2.0) && (n < 512)) { I = (R+R)*I+Ci; R = R2-I2+Cr; R2 = R*R; I2 = I*I; n++; } return n; }

mandelbrot () changes only local variables. But sums () is more interesting in this respect - the function calculates partial sums of the input array X and saves them to the output array sums:

 function sums(x) { var sums = [], sum = 0; for (var i = 0; i < x.length; i++) { sum += x[i]; sums[i] = sum; } return sums; }

What you should pay attention to - this function assigns values to the sums array, changing the heap object, and not just local variables. But, since this object is highlighted in the function itself, it is still a pure function. In fact, a specific example will not be executed in parallel due to a number of limitations in the current version of Rivertrail, but I hope this will change soon.

And here is an example of a function that will not be considered pure, since it changes X , and X is not localized.

 x = [1, 2, 3]; function impure() { x[0] += 1; }

Parallel execution

The main magic of ParallelArray is that, to the extent possible, it will perform functions in parallel. In this case, parallelism or execution sequence will depend on the JS implementation itself. The fact that functions intended for parallel execution are pure means that conceptually they can always be performed safely. But this does not mean that the JS engine itself will be able to execute them.

JS engines do a lot of hidden optimization, and not all of these optimizations are thread safe.

So far, the list of operations performed in parallel is rather conservative, but over time it will expand and, ideally, will grow so that any pure functions can be performed in parallel.

You have to do a lot of things to make sure your code is fast. To ensure parallel execution of code, you have to do the same thing. That's why.

Example

 ab = c

If the JIT compiler analyzes the type a and determines, for example, that the property b is always stored with a certain offset, then it will be able to optimize the code in one assembler instruction. But if the compiler fails to analyze the code, in the worst case the interpreter will be called, working on different hash tables, prototyping trees, and so on. Now you need to understand whether ab = c is thread safe. Everything is simple here - the save instruction is safe under the assumption that only one stream has access to the memory to which it is saved. Which is a guarantee of "clean" function. It will be harder to solve this when the interpreter will affect hundreds, if not thousands, of lines of code.

Of course, knowing which code will be compiled efficiently is not a victory. In the following articles I will talk about some things that ensure parallel execution for today, and give a couple of forecasts in this area for the future.

Parallel execution models

The use model of Rivertrail Mozill is a little different from the prototype developed by Intel. This is a plugin compiling JS in OpenCL. The native implementation allows you to execute code in 4 different ways, but at the moment only the first 2 are available.

Consistently . Standby mode Equivalent to writing for loops or using high-level Array methods. This mode works in assemblies Nightly and, possibly, in Aurora. Try typing in the console var x = new ParallelArray ([1, 2, 3]
Multicore mode . In this mode, we work by default. Multicore mode distributes one thread to each core in the system. Each workflow will work with a parallel copy of the function. A more functional version of this mode is expected in the next couple of months.
Vectorized mode. It looks like a multi-core, but there are differences - each worker thread uses SSE instructions to process more than one array element at a time. This is still in the plans after Multicore.
GPU . This is just a variant of the execution of the vectorization mode, but in it the vectorization of the code will work not on the CPU, but on the GPU. There are many technical differences. On the one hand, the vectorization will be processed by the GPU in hardware, and the compiler will not have to use special instructions. On the other hand, on some platforms, there is a lot of work to be done on copying memory between the CPU and the GPU.

Of the described modes, the most common can be considered Serial - it can be applied to any pure function. Multicore is also quite versatile and can be used when working with pure functions that limit themselves to the currently supported operations.

Vectorization and GPU modes will be more limited. It will make sense to use vectorization only for functions in which code can be converted to SSE instructions without packaging and unpacking, the GPU will impose certain restrictions on data movement, and so on.

A few words about performance

There will be some data, since

I have not finished profiling
there are no good detailed tests yet
no optimization optimization

At least, here are the results of work when calculating the Mandelbrot set on my quad-core laptop with Hypertheading.

seq - runtime in sequential mode
par - the execution time of the same number of threads in parallel mode
ratio is the ratio of the time of the sequential mode to the parallel time (seq / par). The bigger, the better.

Threads	Seq (ms)	Par (ms)	Ratio (Seq / Par)
one	2976	2515	1.18
2	2952	1782	1.65
four	2964	1417	2.09
eight	2880	1149	2.50
sixteen	2891	1109	2.60

Obviously, these values can be improved. It would be great if productivity increased linearly. And I do not think that this is difficult to achieve, I am optimistic.

By the way, the data on the sequential mode here is taken using the JS execution on the basis of arrays, and not on the ParallelArray serial mode, and the code worked for some time to make sure that JIT was used. Although instrumental testing of JIT was not done (which is why I say that “no proper profiling was done”).

About PJs

Some of you may have heard of previous ideas for executing JavaScript in parallel, they were called "PJs" (Parallel Java Script). So far this is all in the plans, but perhaps it will be possible to use some Rivertrail mechanisms in the PJs API. And while there are no reasons that could be a hindrance in this matter. The main thing now is to expand the range of functions supported by the multi-core mode.

Summarizing

Combining data (concurrency) comes to JS (at least in Firefox). Implemented APIs can put JS in the avant-garde of programming languages using parallelism. It is all very simple to use and guarantees a translatable execution. PJs also guarantee deterministic execution, but Rivertrail does not do this because of the presence of functions like () reduce . Few languages can boast that.

Thanks to vikky13 for help with translation and editing.

Source: https://habr.com/ru/post/154999/

All Articles