593706 - Answering the question "can this .forEach call be parallelized ?"

Status: RESOLVED WONTFIX

(Mozilla Labs :: Doctor JS, defect)

Description

[David Bruant]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; fr; rv:1.9.2.8) Gecko/20100723 Ubuntu/10.04 (lucid) Firefox/3.6.8
Build Identifier: 

In a blog article (http://longtermlaziness.wordpress.com/2010/09/05/array-foreach-a-better-abstraction-may-lead-to-better-performances/), I describe how static analysis could be used to dramatically improve performance of Array.prototype.forEach (this could certainly apply to .map, .some and .every).

The basic idea is that if you can prove that the order in which elements of an array are visited doesn't matter, you can parallelize the calls of forEach by opening threads to do the calls.

This bug is a response to the invitation I have found here (http://brendaneich.com/2010/08/static-analysis-ftw/) to tell what we would to see in DoctorJS.

Depending on how interested this bug is to DoctorJS maintainer, I may open on bug on JaegerMonkey to integrate this work to it.

Reproducible: Always

Comment 1

[Brendan Eich [:brendan]]

Good topic, one we discussed the other week with some folks who work on SIMD programming language support. Cc'ing usual suspects.

/be

Comment 2

[Dimitris Vardoulakis]

Hi David. I haven't worked on dependency analysis and automatic parallelization, but from what I understand they are very hard problems and there hasn't been much progress on them except for toy programs. 

In general, it is easier to use a parallel construct whenever possible instead of trying to discover parallelism opportunities. In your example, one would use map when they know that the order of processing the elements doesn't matter and foreach when it matters.

Comment 3

[Dave Herman [:dherman]]

CC'ing bhackett (for obvious reasons!)

> In your example, one would use
> map when they know that the order of processing the elements doesn't matter and
> foreach when it matters.

To make this a little more concrete: people usually use forEach when they want the action to have a side effect (like modifying the DOM or mutating a shared variable), and generally the order is going to matter for those side effects. That said, there might theoretically be cases where we can prove that the only side effects are, say, registering callbacks with DOM libraries, and we could log the registrations and then perform them in a transaction.

But map and array comprehensions are more often used without side effects; if it computes each element without referring to mutable state, it could be parallelized. Figuring this out is still tricky, though.

All that said... trying to figure this out via static analysis is a pretty blunt approach. If people want parallelization, they're gonna want *predictable* parallelization. We ought to explore explicitly parallelized constructs in the language. That in and of itself is tricky, since it requires linguistic enforcement that the specified code is safe to parallelize. As Brendan said, we've been discussing this topic recently with some good people.

Dave