Support multiprocessing with Web Workers

[parasyte]

If we can parallelize parts of the update loop, then we could vastly increase performance by doing most of the work in worker threads.

A simple example would be doing all AI updates in one thread, and simultaneously doing collision detection in another thread.

A very complex example would be doing 1/8 of the collision detection in each thread, with a total of 8 threads (optimal configuration for an 8-core machine). The biggest issue here is doing parallel collision detection/response in a deterministic manner.

[agmcleod]

I think it's a really neat idea, but given workers would run separate from the game thread, couldn't it become quite the callback mess?

[parasyte]

Avoiding callback hell is a matter of organization. Workers can only communicate back with the main thread via the PostMessage API, so ideally you have a single listener callback that handles the results of all Workers. As long as the Workers have a single, well-defined task, there's no need to route the results to upstream handlers... Although that is a design decision to make if you have more than one kind of task that gets deferred to Workers.

What I'm suggesting here is to defer only collision detection, or AI to WebWorkers. E.g. the simplest implementation is replacing the update() loop with a worker spawner and waits for their completion, before beginning drawing operations.

[parasyte]

These will be useful for this task:

• http://wiki.whatwg.org/wiki/NavigatorCores
• http://www.whatwg.org/specs/web-apps/current-work/multipage/scripting.html#proxying-canvases-to-workers

[obiot]

I really would like to give it a try for 1.2.0 actually, I was also thinking about it a couple of weeks ago when working on the quadtree (as we could use one worker for each first level branch), but just use it first for the update loop would be already a great addition,

Just having a look at this image manipulation example, makes realize how easy it would be to implement : http://www.sitepoint.com/using-web-workers-to-improve-image-manipulation-performance/

[obiot]

And...... compatibility status is really good ! http://caniuse.com/webworkers

[agmcleod]

Any concerns with android 4.4 only? Given not everyone will be using chrome.

[obiot]

Well for android 4.4 and IE9 (of course), we can just use the regular loop :(

The trick i'd say being to redesign some function in a way that they can be executed partially by several thread or totally by a single one.

I think there is a polyfill somewhere as well, that simulate 1 thread worker.

On 14 août 2014, at 19:28, Aaron McLeod notifications@github.com wrote:

Any concerns with android 4.4 only? Given not everyone will be using chrome.

— Reply to this email directly or view it on GitHub.

[agmcleod]

Ah fair enough. Yeah that sounds great then :)

On Thu, Aug 14, 2014 at 7:36 AM, Olivier Biot notifications@github.com wrote:

Well for android 4.4 and IE9 (of course), we can just use the regular loop :(

The trick i'd say being to redesign some function in a way that they can be executed partially by several thread or totally by a single one.

I think there is a polyfill somewhere as well, that simulate 1 thread worker.

On 14 août 2014, at 19:28, Aaron McLeod notifications@github.com wrote:

Any concerns with android 4.4 only? Given not everyone will be using chrome.

— Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/melonjs/melonJS/issues/459#issuecomment-52172778.

Aaron McLeod http://agmprojects.com

[parasyte]

Both update and draw loops can be performed in parallel by multiple workers. Coming up with a good estimate of workload can be difficult with multiple containers though, because the problem is no longer linear; some branches will be heavier than others, so it's harder to distribute workloads evenly.

On Aug 14, 2014, at 6:14, Aaron McLeod notifications@github.com wrote:

Ah fair enough. Yeah that sounds great then :)

On Thu, Aug 14, 2014 at 7:36 AM, Olivier Biot notifications@github.com wrote:

Well for android 4.4 and IE9 (of course), we can just use the regular loop :(

The trick i'd say being to redesign some function in a way that they can be executed partially by several thread or totally by a single one.

I think there is a polyfill somewhere as well, that simulate 1 thread worker.

On 14 août 2014, at 19:28, Aaron McLeod notifications@github.com wrote:

Any concerns with android 4.4 only? Given not everyone will be using chrome.

— Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/melonjs/melonJS/issues/459#issuecomment-52172778.

Aaron McLeod http://agmprojects.com — Reply to this email directly or view it on GitHub.

[setthase]

We should have in mind that CocoonJS doesn't support WebWorkers for Canvas+ view: http://support.ludei.com/hc/communities/public/questions/200524503-Web-Worker-support

[obiot]

No worries, anyway we have to provide a fallback for IE9 and old android browser anyway :)

On 20 Aug 2014, at 20:21, Tomasz Sobczak notifications@github.com wrote:

We should have in mind that CocoonJS doesn't support WebWorkers for Canvas+ view: http://support.ludei.com/hc/communities/public/questions/200524503-Web-Worker-support

— Reply to this email directly or view it on GitHub.

[parasyte]

Yes, gracefully degradation has been our motto. But if we can get better performance on some platforms with Web Workers (and WebGL, for that matter) then we're going to do it. :)

[Zolmeister]

If you guys ever get to this, just a heads up that you'll need to be using typed arrays for passing data to/from Web Workers. Otherwise it's a data copy operation, which is extremely slow.

I wrote a library a while back that started to solve the problem in a generic way by creating a JSON object backed by static memory:
https://github.com/Zolmeister/zed.js

Good Luck!

[parasyte]

@Zolmeister zed.js looks pretty reasonable!

It reminds me of a stack implementation that I started for WebGL (but did not use). It was a wrapper around a typed array that would grow as necessary (only exponential growth) and never shrink. Which is good for a stack because you're constantly pushing and popping from the array. It didn't make much difference with performance, because V8 is pretty smart about small arrays. Would have been better suited for stacks that grow and shrink rapidly.

I noticed your string encoding uses Uint8, but JS Strings internally use UTF-16; charCodeAt returns a 16-bit number. It should also be possible to replace your read-loop https://github.com/Zolmeister/zed.js/blob/master/index.js#L116-L118 with something like:

return String.fromCharCode.apply(String, Array.apply([], this.uint16View.subarray(index / 2 + 1)));

And similar for the write-loop:

this.uint16View.set(val.split("").map(function (v) { return v.charCodeAt(0); }), index / 2  + 1);

That should make the string encoding a bit more efficient and correct. :)

Also, be careful about special number values, like NaN and Infinity.

[obiot]

http://blog.nparashuram.com/2016/09/rise-of-web-workers-nationjs.html