Java Concurrency using Limited Threads

1. You should always consider using thread pool, but not unlimited numer of threads.

2. The class library provides a flexible thread pool implementation along with some useful predefined configurations. You can create a thread pool by calling one of the static factory methods in Executors. I think for your case the following method should be used:

   newFixedThreadPool - creates a fixed-size thread pool creates threads as tasks are submitted, up to the maximum pool size, and then attempts to keep the pool size constant (adding new threads if a thread dies due to an unexpected Exception).

   During thread pool creation you set pool size, but you may add as many threads as you wish to the executor (thread per your node for example). Threads that will not be executed, will be queued.

3. If you have a batch of computations to submit to an Executor and you want to retrieve their results as they become available, you may use a completion service. CompletionService combines the functionality of an Executor and a BlockingQueue. You can submit Callable tasks to it for execution and use the queue like methods take and poll to retrieve completed results, packaged as Futures, as they become available. ExecutorCompletionService implements CompletionService, delegating the computation to an Executor.

   Here is an example of using CompletionService from Java in Concurrency book:

   public class Renderer {
       private final ExecutorService executor;
   
   
   Renderer(ExecutorService executor) { this.executor = executor; }
   
   
   void renderPage(CharSequence source) {
       final List<ImageInfo> info = scanForImageInfo(source);
       CompletionService<ImageData> completionService =
           new ExecutorCompletionService<ImageData>(executor);
       for (final ImageInfo imageInfo : info)
           completionService.submit(new Callable<ImageData>() {
                public ImageData call() {
                    return imageInfo.downloadImage();
                }
           });
   
   
       renderText(source);
   
   
       try {
           for (int t = 0, n =  info.size(); t < n;  t++) {
               Future<ImageData> f = completionService.take();
               ImageData imageData = f.get();
               renderImage(imageData);
           }
       } catch (InterruptedException e) {
           Thread.currentThread().interrupt();
       } catch (ExecutionException e) {
           throw launderThrowable(e.getCause());
       }
   }
   
   
   }
   

For CPU intensive tasks, the optimal number of threads is likely to be the number of cores or logical threads you have. This could be 4, 6 or 8 on your machine. A simple way to create a thread pool which matches the number of physical threads available is.

ExecutorService pool = Executors.newFixedThreadPool(
                       Runtime.getRuntime().availableProcessors());

If you have more threads than cores, your threads will have to context switch adding overhead and making them slower.

This looks like a good fit for the Fork/Join framework being developed for Java 7; it's also available for Java 6 at http://gee.cs.oswego.edu/dl/concurrency-interest/ (under jsr166y). You can use the RecursiveTask class to represent your computation and fork additional tasks for child nodes in your data structure. There's a short tutorial at http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html.