JavaScript tree becoming concurrent?

Started 29Oct2015, update 4Nov2016
This page is in group Technology. I hope it to be a note showing whether it’s possible to code the animated tree in concurrent JavaScript code. Or rather, which solution to choose – or which that suits best.

If you get inspired by this blog note and code some concurrent version of the tree, please tell. I will be delighted to learn it and also link it up here.

Intro

“JavaScript is the most commonly used programming language on earth. Even Back-End developers are more likely to use it than any other language”  – stackoverflow Developer Survey Results 2016. In other words: most of the world’s programmers are deprived of concurrency support in their programming language. Asides:  {Kotlin programmers won’t have such support; Swift programmers won’t have such support; etc;} Or are all these free to do concurrency their way? Oh no, Swifters are given GCD, and the others (huge list purposely left out). You have to choose anyhow, like you have chosen a language. And if all languages did have their way of concurrency built into the languages as a primary citizen, then that could just have been one of the selection criteria?

JavaScript is not a concurrent language in the traditional sense [1]. JavaScript runs on the UI thread. Still I’d like to see how the branches could grow and sway by concurrently running code. I’d like to see spring and autumn. By any possible concurrency paradigm. I will invite specialists to suggest, since so far I only have written a few line JavaScript lines myself.  But I want to learn.

This note could not have been without the inspiration I got from an invited talk by Seb Lee-Delisle at Trondheim Developer Conference 2015 (TDC 2015).

Seb Lee-Delisle at TDC 2015 showing JavaScript tree

Fig.1 Seb Lee-Delisle at TDC 2015 showing JavaScript tree

Press picture for higher resolution. See a small (.mov) movie of the swaying tree here. (Permitted by Seb Lee-Delisle). In the next chapter you can run the code directly:

JavaScript non-concurrent original

The code is presented on GitHub as sebleedelisle / live-coding-presentations / 2015 / TrondheimDC at this location. Seb Lee-Delisle wrote to me in a mail that “this tree code was inspired by other people’s code so please feel free to take it and progress it however you like!”

You can run the code by copy-paste it into a text editor and save it as an html file and then double-click on it. Your browser will then run it. Or just press here to run it now. Tip: start them in several new windows side by side and watch the beauty of each one of them. (On OS X 10.11.1 El Capitan both Safari and Firefox run it over and over again, but Chrome only runs it once (so I have to restart Chrome. Reported to Google)).

An interesting matter is how long this code might have been running. I am fortunate enough to have a Lamp iMac G4 that I bought in 2002, last updated in 2010 with OS X Tiger 10.4.11. I’ll never throw it away; it’s a pleasure to use. Just like an old car that sits in the garage and takes everything relaxed. I tested the tree. There is a black screen on both Safari 4.1.3 and Firefox 3.6.8. Maybe the applause by the quite eligible audience was rather sound. This may be as fresh as the swaying. If you can find out, I think it rather interesting.

Specification

The non-concurrent original tree, as Seb Lee-Delilse showed it, perhaps doesn’t need concurrency. In a system, if we can’t tell which events in two processes that happen first, (so no causality between the processes) then those processes are said to be concurrent (Lamport, 1978). The tree grows slowly and sways slowly, depending on a few parameters and a random function. Being concurrent means that components basically run in sequence on one core anyhow. It’s parallel that takes us to cores. So, why this fuzz?

In the code the stem branches off into two branches and then each of them grow and branch off into two. This continues for ten generations. Lengths (size) and angle (rotation) are random values.

But each branch doesn’t live once drawn. It grows only once. (But they sway all the time, where in the code is their “life”?) I’d like new branches or leaves to grow out after some time, after the tree itself has grown out. Even this won’t require a concurrent application (Turing is always right in this sense, isn’t he: everything can be mimicked by anything), but since that’s what this blog note is about, that’s what’s pursued here.

In other words: make it possible with spring and autumn, growth and falling off, make a deciduous tree possible. Think that each(?) part of the tree lives its own life. However: I’m not out after a more lively tree, I am quite satisfied with the original. I really just want to learn about JavaScript and concurrency. By the way, this is all client side. Plus, I really wish it would grow and sway at the same speed on all platforms.

On the shoulders of..

Before you go on here I recommend James Long’s excellent text with interactive code examples. The js-csp project (below), and general usage of concurrency in JavaScript, plus his github fork of js-csp is discussed in Taming the Asynchronous Beast with CSP Channels in JavaScript. (Even if I already had a chapter on js-csp I hadn’t discovered this text; thanks to Gerald Hilderink.)

JavaScript events and callbacks

In Wikipedia’s JavaScript page it states that

Miscellaneous. Run-time environment
JavaScript processes messages from a queue one at a time. Upon loading a new message, JavaScript calls a function associated with that message, which creates a call stack frame (the function’s arguments and local variables). The call stack shrinks and grows based on the function’s needs. Upon function completion, when the stack is empty, JavaScript proceeds to the next message in the queue. This is called the event loop, described as “run to completion” because each message is fully processed before the next message is considered. However, the language’s concurrency model describes the event loop as non-blocking: program input/output is performed using events and callback functions. This means, for instance, that JavaScript can process a mouse click while waiting for a database query to return information [1] (Wikipedia, Oct2015)

Aside 1: A critical view of this model taking us to an alternative is done by Rich Hickey, telling about Clojure core.async, see lecture (45 mins) at (084 ) CSP on Node.js and ClojureScript by JavaScript, ref.[12]. He also designed Clojure. The callbacks of JavaScript correctly need to be non-blocking because JavaScript after all isn’t (by design) a language with built-in active object, thread or process with internal state. So, blocking may be quite sound, see (092) Not so blocking after all – not “evil” at all. It depends. The language Go (which has perfectly reasonable blocking communication channels) also needs to remove the effect on the main thread of execution caused by blocking (operating) system calls. It does this by spawning a new goroutine when a blocking has been going on for some time. But semantically the blocking call is still blocking as seen from the caller. This way, even sitting on top of an operating system makes for all the progress needed.

Aside 2: Back in 2013 (two years ago) I tried to trigger a thread on comp.lang.javascript called History of JavaScript concurrency model. They basically told me it’s not concurrent but Web Workers (later) enable some form of multi-threading. I will try that group again, with this blog note.

At the moment I am unsure if this is how the original program is coded. I think not. Not at the “application level”. Chrome’s “Inspect Element” does not list any “Event Listeners” when I run the code. Chrome Timeline analysis shows that it’s Scripting about 75%, Rendering about 22 % and Painting  about 0.4% plus Other and Idle.

Below application level I think there is callback / event loop based “concurrency”:

  • window.requestAnimationFrame(draw) the draw function is indeed a callback function that is called whenever there is a new frame to paint or animate
  • ctx.translate(..) has no callbacks since it’s inside a callback function(?) As are ctx.save, ctx.clearRect, ctx.translate, tree.render and ctx.restore.

How do I see that there are events and callbacks underneath my code; does JavaScript have “WYSIWYG semantics” with regards to this? I’ll ask somebody.

How about some of the other functions? I think that

  1. canvas.getContext(‘2d’) has no callbacks since it’s part of init
  2. this.children.push(..) I am uncertain about since children implements the nsIAccesible interface and who knows what’s in there. The ref states that “the accessible tree is a subset of nodes in the DOM tree”. I have discussed some of this in (078) HTML and concurrency “HTML5 and concurrency”. I would be surprised if there is no callbacks here
  3. this.children[i].render(); might also contain callbacks. The rendering engine is per browser, per platform and who knows the details of those. However, being object oriented with inheritance I have failed to see which class that has .render. It’s not CanvasRenderingContext2D, it’s not some others I have looked at. Hmm..

But with all this hidden pseudo-concurrency (done by so many programmers who state that they “program only single-threaded”), I am after application level, visible callbacks. But then, callbacks don’t usually contain persistent storage, do they? They are called and that’s it. Help!

JavaScript concurrency by library

I do this chapter despite the statement by Hans-J. Boehm at HP Laboratories that Threads Cannot be Implemented as a Library.

task.js by mozilla (Firefox only?)

See taskjs.org, where I read that “generators + promises = tasks” and that

  • task.js is an experimental library for ES6 that makes sequential, blocking I/O simple and beautiful, using the power of JavaScript’s new yield operator
  • Tasks are interleaved like threads, but they are cooperative rather than pre-emptive: they block on promises with yield
  • task.js works with any framework or library that uses the Promises/A spec.
  • The power of task.js comes from ES6 generators, which are currently only available in Firefox (30Oct2015) (8.2016: not any more)
<script type="application/javascript" src="task.js"></script>

<!-- 'yield' and 'let' keywords require version opt-in -->
<script type="application/javascript;version=1.8">
function hello() {
    let { spawn, sleep } = task;
    spawn(function() { 
        // Firefox does not yet use the function* syntax
        alert("Hello...");
        yield sleep(1000);
        alert("...world!");
    });
}
</script>
  • The spawn function takes a generator function and starts running it as a concurrently-executed task. Every time the task yields a promise, the scheduler blocks the task until the promise is fulfilled

The promise needs a registered callback that’s later called by the promise: onResolve, onError or onResult. So, there’s still the traditional event loop and callback functionality, but with the important addition of the active tasks/threads/processes that’s called promises. This makes a rather large difference to simple single-threading plus event loops and callbacks.

I have tried to search for ES6 compatibility tables to see if more than Firefox supports this. I think it hangs on support for generators.

Any library that uses a concurrency paradigm that runs on all browsers? Let’s see:

Web workers

From Wkipedia I quote:

A web worker, as defined by the World Wide Web Consortium (W3C) and the Web Hypertext Application Technology Working Group (WHATWG), is a JavaScript script executed from an HTML page that runs in the background, independently of other user-interface scripts that may also have been executed from the same HTML page. Web workers are able to utilize multi-core CPUs more effectively.

These programs run in the background. This may perhaps mean parallelization, but there is not a word about “parallel” in the Wikipedia text. There is this in the text: “Web workers are able to utilize multi-core CPUs more effectively.[citation needed]”. However, I did find this about parallel on the W3C HTML Living Standard page (as referenced from the W3C Web workers page):

Some algorithms run in parallel; this means that the algorithm’s subsequent steps are to be run, one after another, at the same time as other logic in the specification (e.g. at the same time as the event loop). This specification does not define the precise mechanism by which this is achieved, be it time-sharing cooperative multitasking, fibers, threads, processes, using different hyperthreads, cores, CPUs, machines, etc. By contrast, an operation that is to run immediately must interrupt the currently running task, run itself, and then resume the previously running task.

However, this is rather clear in the Wikipedia page:

Web Workers allow for concurrent execution of the browser threads and one or more JavaScript threads running in the background. The browser which follows a single thread of execution will have to wait on JavaScript programs to finish executing before proceeding and this may take significant time which the programmer may like to hide from the user. It allows for the browser to continue with normal operation while running in the background.The web worker specification is a separate specification from the HTML5 specification and can be used with HTML5.
There are two types of web workers: dedicated and shared workers.
When web workers run in the background, they do not have direct access to the DOM but communicate with the document by message passing. This allows for multi-threaded execution of JavaScript programs.

In  About thread safety the “process model” of a web worker is described:

The Worker interface spawns real OS-level threads, and mindful programmers may be concerned that concurrency can cause “interesting” effects in your code if you aren’t careful.

However, since web workers have carefully controlled communication points with other threads, it’s actually very hard to cause concurrency problems. There’s no access to non-threadsafe components, or the DOM. And you have to pass specific data in and out of a thread through serialized objects. So you have to work really hard to cause problems in your code.

I like the above. Careful communication points! But it’s not surprising to read this on Wikipedia:

As envisioned by WHATWG, web workers are relatively heavy-weight. They are expected to be long-lived, have a high start-up performance cost, and a high per-instance memory cost.

There are examples that you can also run at html.spec.whatwg.org/multipage/workers.html (it seems like much of the Wikipedia text is cut and paste from it). If you read one the examples, like A background number-crunching worker and run the client-side script …/page.html then the referenced script is on the server here: …/worker.js. If nothing else is said it’s loaded from the default (=same) url as the html page that contains the client-side script.

In TypedArray.org Thibault Imbert blogs about Web workers. Here are several quotes:

Just like with Flash, JavaScript code runs by default on the UI thread, and any expensive computation will usually affect the UI responsiveness. As you may know, at 60 fps, you have around 16ms (1000ms/60) per frame to do what you have to do (computations, rendering and other misc logic). If you exceed that budget, you will alter the frame rate and potentially make your content feel sluggish or worse, unresponsive. (Thibault Imbert)

I must admit, I pasted part of this into the intro at the beginning of this note. They continue:

Web Workers are now broadly available in most browsers even on mobile (caniuse.com stats for Web Workers) and give you the power of concurrency from within JavaScript. (Thibault Imbert)

The process model of a Web worker is a unique JavaScript engine or virtual machine (VM), with all that gives and takes. It grabs a rather large memory footprint and start-up time and it’s not an abstraction that’s worked with directly. Messages are sent between them by message cloning or transfer of ownership. Primitive datatypes (or arrays of them) or any JSON object may be sent. But a Web Worker can’t display anything because there is no DOM (Document Object Model) available. Here a Worker is initiated:

var worker = new Worker("background.js"); // New VM started from main JS
var subworker = new Worker ('Task.js'); // Started from a Worker

A sub Worker is a task.js type of task (above), which should imply that it only runs on Firefox(?)

As we said earlier, Web Workers are commonly used today to perform expensive/synchronous tasks in the background. This allows you as a developer to perform expensive computations in the background, without causing the UI to lock so that your application stays always responsive. (Thibault Imbert)

Reactive Extensions for JavaScript (RxJS)

This is a solution that has left the traditional callback and event loop. (They still call it event-based, probably not to lose the believers). This is a “data flow”, “stream processing” or “reactive programming with spreadsheet” architecture. It handles stream-like architectures as glued onto the single-threaded JavaScript language. I think they have somewhat hijacked the “reactive” term, which used to be closer to what to do to meet some hard real-time requirement (?) I have mentioned Rx Extensions for Swift somewhat in (077) A reactive manifest. Is there a trend these days to make languages basically non-concurrent with no threading (or the like) in the language (with C11 and C++11 as notable exceptions)? This is an extension, probably a good afterthought for several single-threaded languages.

In Rx (Reactive Extensions) by Microsoft Open Technologies I read that:

The Reactive Extensions (Rx) is a library for composing asynchronous and event-based programs using observable sequences and LINQ-style query operators. Using Rx, developers represent asynchronous data streams with Observables, query asynchronous data streams using LINQ operators, and parameterize the concurrency in the asynchronous data streams using Schedulers. Simply put, Rx = Observables + LINQ + Schedulers.

In the formula above they have forgotten Non-concurrent-language, since Rx can’t exist alone. I’d go for this formula instead:

Some-concurrency = Non-concurrent-language + Rx

Further down in the reference page they continue:

Rx complements and interoperates smoothly with both synchronous data streams (IEnumerable<T>) and single-value asynchronous computations (Task<T>) as the following diagram shows:

Single return value Multiple return values
Pull/Synchronous/Interactive T IEnumerable<T>
Push/Asynchronous/Reactive Task<T> IObservable<T>

It’s very interesting that they even mention synchronous data streams. In any proper toolbox both synchronous and asynchronous need to be readily available. There are several flavors of Rx, like Rx.NET, RxCpp (C++, also after C++11 and thread), Rx.rb (Ruby), RxPy (Python). Plus the JavaScript version:

RxJS: The Reactive Extensions for JavaScript (RxJS) is a library for composing asynchronous and event-based programs using observable sequences and LINQ-style query operators in JavaScript which can target both the browser and Node.js.

So, it’s RxJS that goes for this case. In the referenced page they write:

What is RxJS?

RxJS or Reactive Extensions for JavaScript is a library for transforming, composing, and querying streams of data. We mean all kinds of data too, from simple arrays of values, to series of events (unfortunate or otherwise), to complex flows of data.

RxJS makes it easy to:

  • transform data using methods like aggregation and projection.
  • compose data using methods like zip and selectMany.
  • query data using methods like where and any.

Why use it? Here’s a few reasons for choosing RxJS:

  • Our emphasis is on queryability and composibility. Consolidating disparate streams into a meaningful whole is a first class story.
  • We take a general approach to data. We’re not tied to any specific domain. This gives you a common vocabulary for dealing with streams of arbitrary data.
  • The dust has settled on our API. RxJS has a history and our API has gone through some hardening.

The observer pattern, as well as threads in general are criticised in Edward A. Lee’s “The Problem with Threads” – that I have discussed in (021)  The problem with threads .

In a comment in the comp.lang.javascript chapter (below) RxJS is stated to be written using Web workers.

Communicating Generators in JavaScript

Kurt Micallef and Kevin Vella have developed a CSP (Communicating Sequential Processes) library based on generators. These guys are from the Department of Computer Science, University of Malta, Msida, Malta. See [2], where the paper also will come in due course. This is very interesting work.

Provided they get it finished the way they want to and then also get a permission from the university then the code might appear on github or similar. I’ll ask Kurt to tell me when, so that I can update here.

I just wonder if they would present me with a concurrent tree?

JavaScript server side concurrency

This will not make me the concurrent tree in JavaScript that I want, which is client side. I started this note by not being very aware of this, but now I am. I could have deleted this chapter, but it’s nice information that might as well sit her. However,..

the Browserify (at browserify.org/, Wikipedia) tool I have been told, if I understand it correctly, will convert server side code to run client side, in a browser. At places where JavsScript uses require this is resolved(?) And Martin at work also told me that CommonJS is a system that will make client side and server side more equal(?). From the Browserify page:

Browsers don’t have the require method defined, but Node.js does. With Browserify you can write code that uses require in the same way that you would use it in Node.

The default Packet manager is a tool called npm that comes with Node.js (below). “By default, npm modules are retrieved over the Internet from the public package registry maintained on http://npmjs.org” (npm at Wikipedia).

James Long (search for his name here) writes that “You will need to cross-compile generators to run it in all browsers; I recommend the ridiculously awesome regenerator project.” Ok, an alternative?

Node.js

Node.js (Wikipedia) is mainly meant to build server-side web applications. I don’t think it may help me make a concurrent tree!

The older 084 note discusses some ECMAScript 6 (ES6) etc., but it’s not enough.

Node.js handles concurrency, not by spawning OS threads, but presents the event loop as a language construct instead of as a library (here on nodejs.org).

Very expensive but rather nice syntax-wise sub-processes exist. They are spawned as new instances Google’s open source JavaScript engine V8. Nodejs.org writes that “Assume at least 30 ms startup and 10 Mb memory for each new Node.js. That is, you cannot create many thousands of them.” They are created by child_process.fork. They even have what they call channels, used like [child.send(message, [sendHandle])][] (here).

node-csp channels library on Node.js

I have written some about node-csp before (again in 084).  The CSP library is built on server-side Node.js (above), but I need to read myself up again.

It’s installed from https://www.npmjs.com/package/csp by npm:

var csp = require("csp");

node-csp has to be installed and run (so it’s server side). A named CSP process is started and channels created like this:

var in  = new csp.Chan(2);
var out = new csp.Chan(2);
var filterProc = function* (inchan, outchan) {for(;;){..}};
yield csp.spawn (filterProc, in, out) { ... });

CSP (Communicating Sequential Processes) is a different paradigm, first in real use in occam, now also in Go and Clojure’s core.asynch (Clojure runs on the JVM, CLR or JavaScript virtual machines (also 084). But the source is Clojure, not in scope here).

Observe that a CSP implementation never has to busy polling at any level of the code, to make channels and processes run. That’s why I have called one of my CSP schedulers for ChanSched since it’s the channels that drive what happens (channels “schedule”). Application level regular polling of something is different.

PurpleJS by Enonic

(4Nov2016 Just mentioning it for now) See http://purplejs.io/ (and this article in digi.no Norwegian). The docs is at github where I read (colourd by me):

PurpleJS is a Javascript application framework running on the Java Virtual Machine. It’s an alternative to Node.js for Java projects.
..
PurpleJS makes it easy to build performant and lightweight Javascript server applications without the complexity of Node.js asynchronous programming model.
..
Use PurpleJS when you want to:
..
* build fast and lightweight multithreaded applications with Javascript
..
* deliver isomorphic applications – running the same code on both client (i.e. browser) and server

This looks very interesting! I’ll mail them!

MeteorJS framework

(17July2016) I’m investigating Meteor at the moment. See Concurrency as a programming paradigm at the Meteor forum.

In the examples I see this text that triggers my interest (here): “To start working with React as our view library, let’s add some NPM packages which will allow us to get started with React.” This seems like a good starting point, since to me, “react” triggers my interest. Even if the term suffers from terminology-bloating, and I have blogged about it in A reactive manifest, I’m interested to see what’s put into it this time.

A thought-provoking comment (by Ben, here) where he polemizes about architectural level: “our current programming model doesn’t work anymore because everything is hard (because all the easy stuff has been figured out already), so let’s throw it all away and start over”. In my opinion, making everything easy(/hard?) by not relating to or hiding concurrency, or even refuse that concurrency is needed at the conceptual level (“all we need is callbacks and an event loop”), is throwing the baby out with the bathwater. I have commented to Ben’s post there.

js-csp

Here’s another CSP solution (thanks to Michael Haufe for pointing me to this). The original implementation is written by Nguyễn Tuấn Anh (ubolonton) (here). James Long (jlongster) has a fork (here). I have already mentioned Long’s excellent description of concurrency as seen from his desk (above).

It is “Communicating sequential processes for Javascript (like Clojurescript core.async , or Go)”.

It’s installed from https://www.npmjs.com/package/js-csp by npm:

var csp = require("js-csp"); // When do I know whether it's trunc or fork?

Also, from the description: “This is a very close port of Clojurescript’s core.async. The most significant difference is that the IOC logic is encapsulated using generators (yield) instead of macros. Therefore resources on core.async or Go channels are also helpful.”

An excerpt from the description: a channel and two processes are started:

csp.go(function* () {
  var table = csp.chan();

  csp.go(player, ["ping", table]);
  csp.go(player, ["pong", table]);

  yield csp.put(table, {hits: 0});
  yield csp.timeout(1000);
  table.close();
});

This also needs to be installed. There also is a recipe to Browserify it, so it may run on server side. Alternatively regenerator it.

Other CSP variants(?)

See https://www.npmjs.com/search?q=csp. Also see Communicating Generators in JavaScript (above).

Doing it(?)

Model tree building at a fair

Fig.4 Model tree building at a fair

I need to choose. What do I like best? (I think I know..) What would I be able to do? I’ll come back to this, since first I’ll find a discussion group to present this blog note. (When I was younger I also made 3D trees for my railway (from “old man’s beard” of pine trees) – but the above I shot on a visit to a fair today.)

At the moment I feel like js-csp and Browserify. And find a way to transform the recursive algorithm to non-recursive and then make it concurrent.

I wonder about the rationale for JavaScript to be single-threaded. Brendan Eich in 1995 must have known. At that time I had programmed occam on transputer with sub-µs context switch time on a 20 MHz transputer processor for several years. Was it too far across the Atlantic, or was JavaScript designed like that was because it solved his problem there and then? Which it sure did. And at least some 20 years ahead.

comp.lang.javascript

I posted a new thread there: Concurrency folded out? Taking the temperature from that thread then JavsScript concurrency is not what the world think is most interesting. Now isn’t that strange. However..

..answer by Michael Haufe

If this tree was described by an L-System[1], it could utilize Web Workers in a rather straightforward manner.
[1] https://en.wikipedia.org/wiki/L-system

I pasted this reply in here just to get the L-System visible. The Wiki-ref states that “An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. ” This is in fact half of the problem; finding out what to parallelise. I am not after doing a parallel JavaScript tree, but a concurrent. However, finding what might be parallelized and what may be concurrent threads are related ways to think: divide and conquer. So the L-System may be ok to make concurrent(?)

References

Wiki-refs: JavaScript

  1. Concurrency model and Event Loop by Mozilla Foundation, on Mozilla Developer Network, see https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop
  2. Communicating Generators in JavaScript by Kurt Micallef and Kevin Vella, Department of Computer Science, University of Malta, Msida, Malta. Presented at CPA 2016 at the University of Copenhagen. See http://wotug.org/cpa2016/programme.shtml
Email this to someoneShare on FacebookTweet about this on TwitterShare on LinkedIn

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

12,546 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>