New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support multiprocessing with Web Workers #459

Open
parasyte opened this Issue Mar 16, 2014 · 15 comments

Comments

5 participants
@parasyte
Member

parasyte commented Mar 16, 2014

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.

@parasyte parasyte added this to the 1.1.0 milestone Mar 16, 2014

@agmcleod

This comment has been minimized.

Show comment
Hide comment
@agmcleod

agmcleod Mar 17, 2014

Member

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?

Member

agmcleod commented Mar 17, 2014

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

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Mar 17, 2014

Member

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.

Member

parasyte commented Mar 17, 2014

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.

@obiot obiot modified the milestones: Future, 1.1.0 Jul 23, 2014

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 14, 2014

Member

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/

Member

obiot commented Aug 14, 2014

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

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 14, 2014

Member

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

Member

obiot commented Aug 14, 2014

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

@agmcleod

This comment has been minimized.

Show comment
Hide comment
@agmcleod

agmcleod Aug 14, 2014

Member

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

Member

agmcleod commented Aug 14, 2014

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

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 14, 2014

Member

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.

Member

obiot commented Aug 14, 2014

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

This comment has been minimized.

Show comment
Hide comment
@agmcleod

agmcleod Aug 14, 2014

Member

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
#459 (comment).

Aaron McLeod
http://agmprojects.com

Member

agmcleod commented Aug 14, 2014

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
#459 (comment).

Aaron McLeod
http://agmprojects.com

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Aug 14, 2014

Member

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
#459 (comment).

Aaron McLeod
http://agmprojects.com

Reply to this email directly or view it on GitHub.

Member

parasyte commented Aug 14, 2014

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
#459 (comment).

Aaron McLeod
http://agmprojects.com

Reply to this email directly or view it on GitHub.

@codename-

This comment has been minimized.

Show comment
Hide comment
@codename-

codename- Aug 20, 2014

Contributor

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

Contributor

codename- commented Aug 20, 2014

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

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 20, 2014

Member

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.

Member

obiot commented Aug 20, 2014

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

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Aug 20, 2014

Member

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. :)

Member

parasyte commented Aug 20, 2014

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

This comment has been minimized.

Show comment
Hide comment
@Zolmeister

Zolmeister Jan 8, 2015

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!

Zolmeister commented Jan 8, 2015

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

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Jan 8, 2015

Member

@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.

Member

parasyte commented Jan 8, 2015

@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

This comment has been minimized.

Show comment
Hide comment

@obiot obiot added this to To Do (Core) in Roadmap Dec 4, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment