Java 8 Collections concurrent processing

Question

I am planning to do an internal presentation in my company on new features and concepts in Java 8.

What I would like to focus is on the parallel processing capabilities of new collection libraries.

Wherever I read about Java 8 and the need for more functional style iterators of the collection library, it is mentioned that this will help to leverage the multi-core servers that are normal nowadays. But very rarely it is mentioned how this is made possible and whether this is a universal truth, let alone any benchmarks on performance.

As even experienced developers in my company who claims to know about threads have no clue how actual threading works at the lower level, I am trying to collect some knowledge in this area. I have made a set of following assertions based on reading several blogs etc.

I would be thankful for some feedback for the following points (true/false)..

1. A thread is the lowest unit of scheduling in an OS (yeah basic stuff, but not all application programmers know this ;-))

2. A single threaded program can run only on one core at a time. So in a quad core CPU, 75% of the CPU is not utilized for example.

3. The problem with present Java collection iterator is that it is an external iterator and it is not possible (atleast out of the box) to distribute a bulky collection iteration to multiple threads. The new collection library operations makes it possible to have concurrency without having the need to deal with low level concurrency issues

4. Java 8 makes it possible using an enhanced collection library to parallellize iteration using an internal iterator

   Instead of Java 7

   for (Shape s : shapes) {if (s.getColor() == RED)s.setColor(BLUE); }

   we have in Java 8

   shapes.forEach(s -> { if (s.getColor() == RED) s.setColor(BLUE); })

5. But inorder to parallellize the above iteration, one must explicitly use parallel() method of Stream API

   private static void printUsingCoolLambda (final List<String> names) { names.parallelStream().forEach(s -> System.out.println(s)); System.out.println("Printed using printUsingCoolLambda"); }

   But even then there is no guarantee that the operation will be done in parallel as the Javadoc of parallelStream() says the following "Returns a possibly parallel {@code Stream} with this collection as its source. It is allowable for this method to return a sequential stream"

6. Ultimately, there is no guarantee that all the cores will be utilized as thread scheduling is NOT a JVM responsibility, rather dictated by OS.

edit

I have most difficulty in getting points 5 and 6 right. As various Java 8 blogs says just that "use this new parallelStream() and you will get parallel processing out of the box(for free and you as an application programmer are freed from having to worry about that)", my question in one sentence would have been is that really correct all the time?

Answer 1

I would be thankful for some feedback for the following points (true/false)..

Unfortunately none of the answers are either true or false. They are all "it depends" or "it's complicated". :-)

1: A thread is the lowest unit of scheduling in an OS.

This is basically true. OSes schedule threads, and for the most part a Java thread corresponds to an OS thread.

However, there's more to the story. I'd encourage you not to think too much about threads. They are a very low-level construct to use to structure a parallel application.

Of course it's possible to write applications using threads, but it's often preferable to use a higher level construct. One such construct is a task, which is an application-specific chunk of work. If you can divide your workload into separate tasks, you can submit these tasks to an Executor, which will manage the scheduling of tasks onto threads and the creation and destruction of threads. This is the java.util.concurrent stuff that went into Java SE 5.

Another way to structure a parallel applications is using data parallelism. Java SE 7 introduced the Fork-Join framework. This refers to forking and joining not of threads but of tasks, specifically, tasks representing recursively-splittable portions of data. The FJ framework is quite effective for some workloads, but the splitting and joining of tasks is the responsibility of the programmer, and this can be burdensome.

New in Java SE 8 is the streams API, which supports data parallelism in a much more convenient fashion.

I've extrapolated quite a bit from your question about threads, but your questions seemed focused on threads, and there is much more to parallelism than threads. (One of my colleagues recently said, "Threads are a false God.")

2: A single threaded program can run only on one core at a time. So in a quad core CPU, 75% of the CPU is not utilized for example.

Mostly true. If you consider just the application thread, a single thread can never use more than 25% of a quad core CPU. However, if you consider a Java thread running in a JVM, even a single-threaded Java application will likely run faster on a multi-core system than on a single-core system. The reason is that JVM service threads like the garbage collector can run in parallel with the application thread on a multi-core system, whereas they have to pre-empt the application thread on a single-core system.

3: The problem with present Java collection iterator is that it is an external iterator and it is not possible (at least out of the box) to distribute a bulky collection iteration to multiple threads. The new collection library operations makes it possible to have concurrency without having the need to deal with low level concurrency issues.

Mostly yes. External iteration and internal iteration are concepts. External iteration is embodied by the actual Iterator interface. Internal iteration might use an Iterator, a simple for-loop, a set of fork-join tasks, or something else.

It's not so much the new collection library, but the new Streams API in Java 8 will provide a much more convenient way to distribute work across threads.

4: Java 8 makes it possible using an enhanced collection library to parallellize iteration using an internal iterator (... shapes.forEach example ...)

Close. Again, it's the new Streams library, not collections, that provides convenient parallelism. There's nothing like Collection.parallelForEach. To process elements of a collection in parallel, you have to pull a parallel stream from it. There are also a variety of parallel operations for arrays in the java.util.Arrays class.

5: But in order to parallelize the above iteration, one must explicitly use the parallel method of the Stream API .... But even then there is no guarantee that the operation will be done in parallel.

Right, you need to request parallelism with the parallel or parallelStream method, depending on whether you're starting with a stream or a collection.

Regarding no guarantees, sure, there are never any guarantees in life. :-) After all, if you're running on a single-core system, nothing can run in parallel. Another scenario is, in an applet, the security manager might prohibit the application from using more than a single thread. In practice, in most environments, requesting a parallel stream will indeed split up the workload and run the tasks in parallel. By default, these tasks run in the common fork-join pool, which by default has as many threads as there are cores in the system. But somebody might have set the number of threads to a different number, or even to 1, which is one reason the API itself cannot provide any guarantees.

6: Ultimately, there is no guarantee that all the cores will be utilized as thread scheduling is NOT a JVM responsibility, rather dictated by OS. ... As various Java 8 blogs says just that "use this new parallelStream() and you will get parallel processing out of the box (for free and you as an application programmer are freed from having to worry about that)", my question in one sentence would have been is that really correct all the time?

As above, no guarantees. There are many layers in the system where things can take a left turn. Even if your common FJ pool has as many threads as there are cores, there are no guarantees that each Java thread has its own OS thread. (In the Hotspot JVM I think this is always true though. It depends on the JVM.) There could be other processes -- even other JVMs -- on the same system competing for cores, so your application might not get as many cores as you'd like. In that sense the JVM is at the mercy of the OS to schedule threads for it.

I'm not sure where that blog entry came from, but the bit about parallel processing "for free" and the "you don't have to worry" sentiment is overblown. In fact, it's basically wrong.

It's true that it's possible to write a parallel stream much more conveniently than using earlier APIs. But it's also possible to get it very, very wrong. If you put side effects into your stream pipeline, you'll have race conditions, and you might get a different wrong answer every time. Or, even if you take care to synchronize around side effects, you might create enough contention so that a parallel stream might run even slower than a sequential one.

Even if you've managed to avoid these pitfalls, it's not the case that running a parallel stream on an N-core system will give you an N times speedup. It just doesn't work that way. For small workloads the overhead of splitting and joining parallel tasks dominates, which can cause the computation to be slower than a sequential one. For larger workloads, the overhead is offset by the parallel speedup, but the overhead is still there. The amount of speedup also depends on the nature of the workload, the splitting characteristics, lumpiness of the data, etc. Tuning a parallel application is something of a black art.

For easily-parallelizable workloads, in my experience, it's pretty easy to max out a two-core system. A four-core system usually can get at least 3x speedup. With more cores, it's not too difficult to get a 5x-6x speedup, but getting speedup beyond that requires actual work.

For not-so-easily parallelizable workloads, you might have to do a lot of thinking and restructuring of the application before you can even try running it in parallel.

I would not say that Java 8 gives you parallelism "for free" or "without worry" or anything like that. I would say that Java 8 gives you the opportunity to write parallel programs much more conveniently than before. But you still have to work to get it correct, and you will probably still have to work to achieve the speedup that you want.

Answer 2

is that really correct all the time?

It is correct all the time you want it to be. The special allowance that a sequential stream is also OK was absolutely necessary to have this a useful feature at all: there will be many situations (perhaps testing, debugging etc.) where you will want a simple, sequential stream involved. Most concurrent issues begin their way to solution by trying to reproduce the issue in a non-concurrent setting. Concurrent debugging being much harder, the first thing to make sure is that it is really needed.

You should never worry about CPU core utilization: this is old and stable technology, and they do get utilized in all my experience with Java. If you are missing some percentage on your CPU utilization dashboard, you can be almost certain that the issues is solvable within Java, by streamlining locks and other thread coordination, rather than the fully correct Java program falling victim to the quirks of the runtime.