Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Concurrency folded out?

96 views
Skip to first unread message

Øyvind Teig

unread,
Nov 18, 2015, 3:48:21 AM11/18/15
to
During a conference I was on I saw a presentation by Seb Lee-Delisle where he presented a beautiful tree growing up and swaying slowly in the wind [1]. It was all coded in JavaScript.

It doesn't need concurrency at all.

However, not in order to making matters complex (even if I realize it might), but to try to learn from it, I decided to blog about how one could still make that code concurrent.

I thought about using either JavaScript events and callbacks, task.js by mozilla (Firefox only?), Web worker, Reactive Extensions for JavaScript (RxJS) or node-csp channels library Node.js.

There may be more alternatives? Or less?

I guess there are two main problems: by which paradigm, and what parts of the tree to make concurrent. Since it's a basically non-parallizable algorithm (?) I assume the latter is rather difficult.

If any of you feel like making a concurrent version, please do. If any of you want to "hold my hand" while I do, you're very welcome.

My blog note is at [2]. Disclaimer: No ads, no money and no gifts in any of my blog notes. I don't write for anybody but myself and the accidental reader.

[1] http://www.teigfam.net/oyvind/code/114/001_tree_by_seb_lee_delisle.html
[2] http://www.teigfam.net/oyvind/home/technology/114-javascript-tree-becoming-concurrent/

Michael Haufe (TNO)

unread,
Nov 19, 2015, 8:14:07 PM11/19/15
to
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>

Øyvind Teig

unread,
Nov 20, 2015, 7:47:24 AM11/20/15
to
Very interesting. It might just be a Pythagoras tree? When you say Web Workers, do you state that since it's parallelisable then you _know_ that Web Workers would do it. But could I ask; this probably does not imply that some of the other methodologies won't work (and in case, for which reason?)

Michael Haufe (TNO)

unread,
Nov 21, 2015, 1:42:07 PM11/21/15
to
On Friday, November 20, 2015 at 6:47:24 AM UTC-6, Øyvind Teig wrote:
>
> Very interesting. It might just be a Pythagoras tree?

It doesn't look like it to me, but what difference does it make? With an L-System grammar you could describe any number of Plant-Like forms such as:

<https://en.wikipedia.org/wiki/L-system#Example_7:_Fractal_plant>


> When you say Web Workers, do you state that since it's parallelisable then you _know_ that Web Workers would do it.

Yes

> But could I ask; this probably does not imply that some of the other methodologies won't work (and in case, for which reason?)

Concurrency != Parallelization

ECMAScript is not defined with parallel semantics and does not have any primitives to support it (nor does any draft version).

Web Workers is specified separately as an API [1]

The other listed solutions are an abstraction over existing functionality:

Events/Callback = Concurrency
task.js = Concurrency
Web Worker = Parallelization
node-csp = Concurrency
RxJS = Concurrency + Parallelization (Using Web Workers)


[1] <https://html.spec.whatwg.org/multipage/workers.html>

Øyvind Teig

unread,
Nov 22, 2015, 4:48:04 PM11/22/15
to
lørdag 21. november 2015 19.42.07 UTC+1 skrev Michael Haufe (TNO) følgende:
> On Friday, November 20, 2015 at 6:47:24 AM UTC-6, Øyvind Teig wrote:
> >
> > Very interesting. It might just be a Pythagoras tree?
>
> It doesn't look like it to me, but what difference does it make? With an L-System grammar you could describe any number of Plant-Like forms such as:
>
> <https://en.wikipedia.org/wiki/L-system#Example_7:_Fractal_plant>

I wasn't studying the algorithm, just watching the looks of the trees. Ok, so with the L-System grammar it's always possible to do parallel rewriting. For any form.
>
>
> > When you say Web Workers, do you state that since it's parallelisable then you _know_ that Web Workers would do it.
>
> Yes
>
> > But could I ask; this probably does not imply that some of the other methodologies won't work (and in case, for which reason?)
>
> Concurrency != Parallelization
I did make a point of that in the blog that I was after concurrency not parallelism (as reflected in the heading). I was after a concurrent version of the tree. Not to make it faster or more elegant, just to learn JavScript and how JavaScripters think. I work with concurrency all day at work, it's 20+ years since I did true parallelism on a set of transputers in occam. By the way, the occam PAR did not differentiate between concurrent and parallel, as did the PLACE statement that placed CSP processes on the same machine or different machines (with a dynamic channel router available). We actually used this in some products as well.
>
> ECMAScript is not defined with parallel semantics and does not have any primitives to support it (nor does any draft version).
Ok
>
> Web Workers is specified separately as an API [1]
Thanks
>
> The other listed solutions are an abstraction over existing functionality:
>
> Events/Callback = Concurrency
> task.js = Concurrency
> Web Worker = Parallelization
> node-csp = Concurrency
> RxJS = Concurrency + Parallelization (Using Web Workers)

Great table. I'll take it into my blog note. I was aware of the contents, but it made it clearer. What functionality of JavaScript would you say that these are abstractions are on top of? A run-time system or operating system (making threads (with different kind of process model) available) written in C, I won't consider an abstraction over existing functionality. I'd like to know what you mean.
>
>
> [1] <https://html.spec.whatwg.org/multipage/workers.html>

If I may ask, provided I do want a concurrent tree, which methodology would you have chosen? I then assume that Web Worker is out.

Thanks for keeping up with me, Michael.

Øyvind Teig

unread,
Nov 24, 2015, 4:15:42 PM11/24/15
to
An update on my own comment.

The part about Web workers being explicitly parallel I have found no reference to. However, they talk about "background" processing in the context of not blocking the main JavaScript thread.

How this may be implemented I think is covered here:

"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." [1]

I then assume that they talk about Web workers' "backgroundness" and not something else.

[1] From https://html.spec.whatwg.org/multipage/infrastructure.html#in-parallel, referenced from https://html.spec.whatwg.org/multipage/workers.html#handler-worker-onmessage

Michael Haufe (TNO)

unread,
Dec 1, 2015, 9:19:04 PM12/1/15
to
Øyvind Teig wrote:
> [...] Not to make it faster or more elegant, just to learn JavScript and how JavaScripters think.

Given the size of the community, I'm afraid it's more like a Bazaar and a Tragedy Of The Commons. "JavaScripters" are better described by their chosen subgroups (What libraries and frameworks do they choose). I guess you could think of it as somewhat analogous to the C++ community debate over being reliant on Boost or not. Depending on which framework/library community you follow you can identify a certain skill level and a certain mindset around what development in JavaScript is.


Michael Haufe (TNO) wrote:
> > The other listed solutions are an abstraction over existing functionality:
> >
> > Events/Callback = Concurrency
> > task.js = Concurrency
> > Web Worker = Parallelization
> > node-csp = Concurrency
> > RxJS = Concurrency + Parallelization (Using Web Workers)


Øyvind Teig wrote:
> Great table. I'll take it into my blog note. I was aware of the contents, but it made it clearer. What functionality of JavaScript would you say that these are abstractions are on top of?

You can look at the respective web pages for details:
[1] <https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame>
[2] <http://taskjs.org/>
[3] <https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers>
[4] <https://web.archive.org/web/20140915015947/http://jlongster.com/Taming-the-Asynchronous-Beast-with-CSP-in-JavaScript?>
[5] <https://github.com/Reactive-Extensions/RxJS>

Øyvind Teig wrote:
> A run-time system or operating system (making threads (with different kind of process model) available) written in C, I won't consider an abstraction over existing functionality. I'd like to know what you mean.

I'm using "abstraction" in the informal sense (Not writing code irrelevant to the problem you are solving). For example: a given library could provide an API such as the following for managing mouse clicks:

mouseClicks.map(function(clickEvent){ ... Do Something ... })

What you're not seeing is the moderate amount of code required to give you this, as it requires converting the provided standard Subject/Observer event model into a Reactive event model.


Øyvind Teig wrote:
> If I may ask, provided I do want a concurrent tree, which methodology would you have chosen? I then assume that Web Worker is out.

Personally I'd probably still try to recreate the effect with an L-System description and use that to drive what I write to canvas pixel data, but that's mostly because I'm a fan of formalisms.

You can use Web Workers still, but the approach would be to have each worker (however many you want to use) draw a generation on a canvas pixel array. When the worker is done it can post the data back to your main thread (which happens asynchronously) which will then update the main canvas when the animation frame calls your render code.

Øyvind Teig

unread,
Dec 4, 2015, 2:36:42 PM12/4/15
to
Michael Haufe wrote on 2Dec2015:
[4] <https://web.archive.org/web/20140915015947/http://jlongster.com/Taming-the-Asynchronous-Beast-with-CSP-in-JavaScript?>

Since this is in web.archive.org, does that imply that it's not available? It's interesting, but is it just some public testing done by the coder? If it's available, where? Where's the directory of available JavaScript libraries? Could they be available and then gone? I feel more and more like a newbie (even now I'm not certain where this comment goes..)

Michael Haufe (TNO)

unread,
Dec 5, 2015, 1:25:29 PM12/5/15
to
On Friday, December 4, 2015 at 1:36:42 PM UTC-6, Øyvind Teig wrote:
> Michael Haufe wrote on 2Dec2015:
> [4] <https://web.archive.org/web/20140915015947/http://jlongster.com/Taming-the-Asynchronous-Beast-with-CSP-in-JavaScript?>
>
> Since this is in web.archive.org, does that imply that it's not available?

Not at the time I wrote my response. It is currently online again.

> It's interesting, but is it just some public testing done by the coder? If it's available, where?

From the above site:

<https://github.com/jlongster/js-csp>

It claims a version of 0.3.2 though, so I assume the author isn't fully confident of its implementation yet.

> Where's the directory of available JavaScript libraries?

Like CPAN? It doesn't exist for JavaScript. There are and have been a number of competing directories over the years. Right now the most popular one might be the one that has sprung up around the current incarnation of Server Side JavaScript community node.js.

<https://www.npmjs.com/>

But as I've said before, it's a bazaar and not a cathedral.

> I feel more and more like a newbie (even now I'm not certain where this comment goes..)

I'd suggest continuing to play with things on your own and ignore libraries and frameworks. As you learn more, build up your own abstractions until you end up with your own library. At that point I think you'll be in a much better position to judge and understand the things you come across in this over-saturated market of ideas.

Øyvind Teig

unread,
Dec 8, 2015, 3:04:55 AM12/8/15
to
Thanks, Michael!

Now I feel most like js-csp and browserify to run it on the client side(?). And find a way to transform the recursive algorithm to non-recursive and then make that concurrent.

Playing with CSP for JavaScript I certainly would want to, but time forbid! Form doing that in C a couple of times I know it's complex to get right. (But then I could have implemented my deadlock-free XCHAN..) I also try to learn XC and the xTIMEcomposer tool, needed for a privat aquarium project! That's why I wanted to piggyback on somebody else's sore shoulders in the JavaScript world!

Now, who can remove the recursive implementation of the tree for me?(http://www.teigfam.net/oyvind/code/114/001_tree_by_seb_lee_delisle.html)

Am I right to say that this would make a concurrent version easier to reach?

Michael Haufe (TNO)

unread,
Dec 8, 2015, 7:06:11 PM12/8/15
to
On Tuesday, December 8, 2015 at 2:04:55 AM UTC-6, Øyvind Teig wrote:
> Thanks, Michael!
>
> Now I feel most like js-csp and browserify to run it on the client side(?).

I've seen no evidence that suggests this.

> And find a way to transform the recursive algorithm to non-recursive and then make that concurrent.

I don't see what the gain would be in doing that.

> Playing with CSP for JavaScript I certainly would want to, but time forbid! Form doing that in C a couple of times I know it's complex to get right. (But then I could have implemented my deadlock-free XCHAN..) I also try to learn XC and the xTIMEcomposer tool, needed for a privat aquarium project! That's why I wanted to piggyback on somebody else's sore shoulders in the JavaScript world!

So did you change your mind on learning it for yourself? You just want a library that will do this for you?

> Now, who can remove the recursive implementation of the tree for me?(http://www.teigfam.net/oyvind/code/114/001_tree_by_seb_lee_delisle.html)

A handful in this group at least.

> Am I right to say that this would make a concurrent version easier to reach?

No, I would say keep it as a recursive algorithm as it is easier to reason about.

Honestly I believe you should play around with graphics programming in JavaScript+HTML separately from playing with concurrency/parallelism. After you can do each confidently, then put them together again.
0 new messages