[concurrency-interest] Implicit parallelism

Aaron Grunthal aaron.grunthal at infinite-source.de
Mon Aug 12 14:43:00 EDT 2013


Why? I see that it would be convenient in some situations. But that is - 
for my tastes - too much magic going on if the application would 
suddenly start spawning threads, potentially competing for resources 
with other tasks in the global thread pool just to execute something 
that appears to be a simple loop.

It would be pure madness if the compiler would suddenly turn a simple 
busy-wait loop with an accumulator (might be used in some locking 
abstractions to spin-wait before yielding) into multiple threads burning 
CPU time.

I could see this happening automatically in some high-throughput data 
processing library (you mentioned OpenMP) because you expect it to 
utilize available resources. But not something low-level as simple loops.

What java *should* do is perform loop-vectorization like GCC or LLVM do. 
I.e. unroll loops and parallelize - say - 4 iterations with SSE/AVX 
instructions where they're data-independent.

System.arraycopy, string cloning and array initialization have 
hand-coded AVX-intrinsics in the most recent hotspot builds I think. 
Instead of manually specializing a few methods this could be generalized.


thread-parallelism:
* consumes additional system resources
* can be done by the programmer or library
* there is decent support for it with parallel streams

vectorization:
* almost free
* can't be done by the programmer (no inline assembly)
* not supported at all unless you want to use JNI or GPGPU-bindings

On 11.08.2013 10:44, Gustav Åkesson wrote:
> Hi,
>
> My point is that the programmer should (in some circumstances) not care
> if it runs in parallel or not - the execution determines this for you as
> long as the program semantics are not broken. That's why I don't want to
> see .parallel or similar - that is somewhat explicit parallelism. As you
> say, the example I gave was read-only so then it should (theoretically)
> be possible to determine that this is safe to run in parallel. The list
> can't change, nor the elements.
>
> But let's take another example. Let's say we have a Scala (immutable)
> list containing Int type. If we then add all integers from 0 to x...
>
> for (i <- 0 to x) {
>   immutableIntegerList = i :: immutableIntegerList
> }
>
> Or in Java, a locally declared array which we fill with values:
>
> int[] arr = new int[x]
>
> for (int i=0; i<x; ++i)
>   arr[i] = i
> }
>
> In my mind it should be possible to split the loop constructs into y
> parts and then concatenate the result in order. Similar to OpenMP but
> without the explicit parallelism annotation. I know this question is of
> rather academic type, but I'm wondering whether there has been any ideas
> or work to bring this type of functionality to the JVM (and the compilers).
>
>
> Best Regards,
> Gustav Åkesson
>
>
> On Sat, Aug 10, 2013 at 11:18 PM, Aaron Grunthal
> <aaron.grunthal at infinite-source.de
> <mailto:aaron.grunthal at infinite-source.de>> wrote:
>
>     Thread-safety in the context of data structure usually (but not
>     always) refers to consistent behavior when it is concurrently
>     *modified*.
>
>     In your example you mention summing over a list. That's a read-only
>     action and doesn't require immutable lists or special concurrency
>     support. Most data structures are well-behaved under concurrent
>     read-only access, barring exceptions such as access-ordered
>     LinkedHashMaps.
>
>     Java 8's parallel streams also are smart enough to not parallelize
>     on small data sets where the overhead would kill any performance
>     advantage. At least for data structures that allow size-estimates or
>     actual sizes to be obtained.
>
>     I think there shouldn't be anything keeping you from adding a
>     .parallel if you anticipate the possibility of your data
>     transformations handling non-trivial amounts of data.
>
>     - Aaron
>
>
>
>     On 10.08.2013 20:45, Gustav Åkesson wrote:
>
>         Hi guys,
>
>         My discussion here concerns implicit parallelism. Let's say we
>         have the
>         following setup:
>
>         @Immutable
>         public class Integer
>         {
>             ...
>         }
>
>         @Immutable
>         public class ImmutableArrayList
>         {
>              ...
>         }
>
>         I'm looking for a way so that the parallelism would be introduced
>         without hard-coding anything related to parallelism (i.e. not
>         stating
>         anything like .parallel or .par on the collection). Only thing
>         needed
>         would be something annotation-ish which tells the execution
>         environment
>         that this datastructure with elements is inherently thread-safe.
>         Then
>         the execution could determine if it would be beneficial to do
>         so. For
>         instance, for a structure with e.g. five elements, then it would
>         not,
>         but for millions of elements, it would most likely be. Perhaps
>         it could
>         even find some kind of sweet-spot of number of elements in which the
>         parallel overhead exceeds the benefits.
>
>         Let's say we wish to sum all the integers in an ImmutableArrayList
>         (setup below), would it be possible for the compiler (javac,
>         scalac or
>         what have you) and JVM to conspire and decide "hey, let's run
>         this in
>         parallel since it doesn't violate application semantics and it
>         can/will
>         be faster"? Is there any research in this area in regards to the
>         JVM?
>
>
>         Best Regards,
>
>         Gustav Åkesson
>
>
>         _________________________________________________
>         Concurrency-interest mailing list
>         Concurrency-interest at cs.__oswego.edu
>         <mailto:Concurrency-interest at cs.oswego.edu>
>         http://cs.oswego.edu/mailman/__listinfo/concurrency-interest
>         <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>
>     _________________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.__oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/__listinfo/concurrency-interest
>     <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>



More information about the Concurrency-interest mailing list