[concurrency-interest] help show speed-up on a trivial but manual array-map operation?
dl at cs.oswego.edu
Sat Mar 10 09:09:52 EST 2012
On 03/09/12 21:40, Dan Grossman wrote:
> When I have time in a couple weeks, I hope to extend my materials to
> include some of the excellent points and example made here: gotchas
> with respect to timing, the need for large enough problem sizes, and
> -- most important in my mind -- the need for beefy enough arithmetic
> operations to overcome memory-bandwidth issues.
Mostly as a digression: These issues come to the forefront
when developing upcoming parallel aggregate operations on
collections using opaque (to us) functions. As a minimal
goal, a parallel version of, say, c.map(f).reduce(r, b)) should
never be slower than sequential version; and of course should
nicely scale up from there under more favorable conditions.
This is hard to pull off, but I've been working on almost always
hitting this goal for at least the most commonly used underlying
data structures -- array-based (possibly as an enhanced version
of ArrayList) and hash-based (further improving the implementation
of ConcurrentHashMapV8). I'm doubtful that we can come very
close to meeting this for arbitrary data structures. And even
given cleverer FJ-based parallel algorithms for aggregate operations,
improvements are still modulo a long list of underlying issues:
initial thread and memory allocation, megamorphic virtual call
overhead, compilation plans (ensuring that JITs compile the code
that actually matters), method handle performance,
GC cardmark contention, anti-locality consequences of boxing,
and so on. The gap between what you'd naively think ought to be faster
by exploiting parallelism and what we can actually do will surely
shrink over time, but it will take a lot of hard work on a lot of fronts.
In the mean time, when applying time-consuming operations on many
elements of arrays etc in parallel, people routinely get good
parallel performance. But winning in other cases remains an art form.
More information about the Concurrency-interest