Home > Blogs > Parallelizing Algorithms

Parallelizing Algorithms

By  Aug 23, 2008

Topics: Programming, Java

One of the hardest things to do in concurrent programming is making your programs correct and concurrent. Even if you do that, making good use of concurrency is still very hard. Java Concurrency in Practice gives a lot of good information on this topic, and so I had to take some of these techniques for a test drive.

One of my favorite sites is Project Euler. These are all math-ish problems that are fun to solve in various programming languages. They reveal a lot about the language. I used Euler as a good site to learn Ruby. You can write very succinct solutions in Ruby, but they often stink in terms of performance. This describes Ruby in general. I never bothered with too many Java solutions, but I thought that some of these problems might be fertile ground for trying out some parallel algorithms in Java.

The first problem that looked like an easy target was Problem #42. This involves taking a list of words, converting each into a number, and the checking if that number is a triangle number. My solution was to first calculate the first 10,000 triangles numbers and put them into a set. Then convert each word to a number and test. Here is the original Java code:

public class Euler42 {
    private static final int MAX = 10000;
    private static Set triangles = new HashSet(MAX);
    public static void main(String[] args) throws IOException{
        long start = System.nanoTime();
        calcTriangles();
        List words = readFile();
        int count = 0;
        for (final String word : words){
              int val = value(word);
              if (triangles.contains(val)){
                  count++;
              }
        }
        long duration = System.nanoTime() - start;
        System.out.println(count);
        System.out.println("duration="+duration);
    }
    private static List readFile() throws IOException {
        // get words.txt
        InputStream stream =
            Thread.currentThread().getContextClassLoader().getResourceAsStream("words.txt");
        BufferedReader reader = new BufferedReader(new InputStreamReader(stream));
        List words = new ArrayList();
        String line = reader.readLine();
        while(line != null){
            words.addAll(Arrays.asList(line.split(",")));
            line = reader.readLine();
        }
        return words;
    }

    private static void calcTriangles() {
        // create triangles
        for (int i=0;i
            triangles.add(i*(i+1)/2);
        }
    }
   
    public static int value(String str){
        // remove quotes
        if (str == null || str.length() == 0){
            return 0;
        }
        if (str.charAt(0) == '"'){
            str = str.substring(1);
        }
        int len = str.length();
        if (str.charAt(len-1) == '"'){
            str = str.substring(0, len-1);
            --len;
        }
        int val = 0;
        for (int i=0;i
            val += str.charAt(i) - 'A' + 1;
        }
        return val;
    }
}


This ran fast. So fast, that I didn't think I would get much benefit from using multiple threads. I made it a little slower by making the list of words a lot bigger. It still ran pretty fast. My first optimization was to use multi-threading for the initialization, i.e. creating the set of triangles numbers and reading the list of words. Here is the new class (only main method changes, so that is all that is shown):

public class Euler42 {
    private static final int MAX = 10000;
    private static Set triangles = new HashSet(MAX);
    private static CountDownLatch latch =new CountDownLatch(2);
    public static void main(String[] args) throws IOException, InterruptedException, ExecutionException {
        long start = System.nanoTime();
        ExecutorService exec = Executors.newCachedThreadPool();
        Runnable calcTask = new Runnable(){
            @Override
            public void run() {
                calcTriangles();
                latch.countDown();
            }
        };
       
        Callable> readTask = new Callable>(){
            @Override
            public List call() throws Exception {
                List words = readFile();
                latch.countDown();
                return words;
            }
        };
        exec.submit(calcTask);
        Future> result = exec.submit(readTask);
        List words = result.get();
        latch.await();
        int count = 0;
        for (final String word : words){
            int val = value(word);
            if (triangles.contains(val)){
                count++;
            }
        }
        long duration = System.nanoTime() - start;
        System.out.println(count);
        System.out.println("duration="+duration);
    }
}


I created a Runnable for calculating the set of triangle numbers, and a Callable for loading and parsing the list of words from a file. One of these is a CPU bound task, and the other is an IO bound task. This seemed promising. I also created CountDownLatch to make sure that both tasks were complete before testing each word.

This worked just fine, but the performance did not improve. In fact, on average it was about 5% slower than doing everything serially. If I made the list of words a lot bigger, then I would eventually eek out a performance advantage though. This was all on a dual-core machine.

Next I decided to use multiple threads for the conversion of the words to numbers and testing if they were in the triangle set. Here is what that code looked like, again only main method changed:

public class Euler42 {
    private static final int MAX = 10000;
    private static Set triangles = new HashSet(MAX);
    private static AtomicInteger count = new AtomicInteger(0);
    public static void main(String[] args) throws IOException, InterruptedException, ExecutionException {
        long start = System.nanoTime();
        ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        calcTriangles();
        List words = readFile();
        final CountDownLatch latch = new CountDownLatch(words.size());
        for (final String word : words){
            Runnable task = new Runnable(){

                @Override
                public void run() {
                    int val = value(word);
                    if (triangles.contains(val)){
                        count.incrementAndGet();
                    }
                    latch.countDown();
                }
               
            };
            exec.submit(task);

        }
        latch.await();
        long duration = System.nanoTime() - start;
        System.out.println(count);
        System.out.println("duration="+duration);
    }
}


In this case each conversion and comparison is done in a separate Runnable. The Runnable updates an AtomicInteger that keeps track of the total count, and counts down a CountDownLatch. This way the program doesn't exit until all of the Runnables have run. At first, I used a cached pool, just as above. The performance really stunk, it took 11x as long as the serial version. I switched it to used a fixed pool that was the same size as the number of processors on the system. It still took about 2.5x as long as the serial version. The calculation here is so simple that the overhead of the threads is just not worth it.

So it was an informative exercise, as it allowed me to use a lot of the things from Java Concurrency in Practice. It also demonstrated that multi-threaded code doesn't always help, and thus multiple cores is not always all the helpful.

Become an InformIT Member

Take advantage of special member promotions, everyday discounts, quick access to saved content, and more! Join Today.