Getting familiar with Threads in Java: Why does this program's runtime increase with increasing number of threads

Question

Situation

I am trying to get familiar with threads in Java. For that reason I modified a program listing I found in a book. What is does is pretty simple:

1. It creates a boolean[]-array with 100.000.000 elements.
2. It randomly fills that array's elements with true or false using NUMBER_OF_SERVERS threads.
3. Finally it scans that array with NUMBER_OF_SERVERS threads and counts how many entries are set to true

For further details, please see the code below on the bottom of this post.

Problem

When I run the code with different number of threads and measure the runtime, I get a very strange result; or at least a behaviour that I do not understand: The BuildService-Thread consumes MORE runtime when I use MORE threads. When building the entire array (based on random truedistribution) in just one thread that takes about 10 seconds. Next, when I use four threads I would expect the runtime to decrease. However, I get a time consumption of about 17 seconds.

My ScanService works as expected: Time consumption decreases with more threads.

Please see the following chart for details:

However, if change one line in my code and replace the if ((int) ((Math.random() * 2d)) == 0)-statement (for random true-distribution) with if (i % 2 == 0) (thus, every second item will be true) I get a behaviour I would expect:

Questions

So, my questions are:

1. Why do MORE threads lead to a LONGER runtime when using Math.random() function?
2. Vice versa, why does the runtime DECREASE when using only ONE thread using the exact same function?
3. What "general rules" can be derived from this behaviour when it comes down to dealing with threads?

Background info

The code was run on an Intel core i3.

Code

public class AsynchService
{
    private static final int ARRAY_SIZE = 100000000; //100.000.000
    private static final int NUMBER_OF_SERVERS = 16;
    private static final int HOW_MANY = ARRAY_SIZE / NUMBER_OF_SERVERS;

    //build array asynch
    public static boolean[] buildArrayAsynch()
    {
        //build array with NUMBER_OF_SERVERS-Threads
        boolean[] array = new boolean[ARRAY_SIZE];
        Thread[] buildServerThread = new Thread[NUMBER_OF_SERVERS];

        long startTime = System.currentTimeMillis();

        for (int i = 0; i < NUMBER_OF_SERVERS; i++)
        {
            int start = i * HOW_MANY;
            int end = (i != NUMBER_OF_SERVERS - 1) ? (i + 1) * HOW_MANY - 1 : ARRAY_SIZE - 1;

            buildServerThread[i] = new BuildService(array, i, start, end);
        }

        //synchronize and wait for result
        int expectedResult = 0;

        for (int i = 0; i < NUMBER_OF_SERVERS; i++)
        {
            try
            {
                buildServerThread[i].join();
            }
            catch (InterruptedException ex) {}

            expectedResult += ((BuildService) buildServerThread[i]).getExpectedResult();
        }

        System.out.println("\nNumber of \"true\"s ==> Expected result: " + expectedResult);
        System.out.println("Build duration: " + (System.currentTimeMillis() - startTime) + " ms\n");

        return array;
    }

    //scan array asynch
    public static int scanArrayAsynch(boolean[] array)
    {
        //create services and server-threads
        Thread[] serverThread = new Thread[NUMBER_OF_SERVERS];

        long startTime = System.currentTimeMillis();

        for (int i = 0; i < NUMBER_OF_SERVERS; i++)
        {
            int start = i * HOW_MANY;
            int end = (i != NUMBER_OF_SERVERS - 1) ? (i + 1) * HOW_MANY - 1 : ARRAY_SIZE - 1;

            serverThread[i] = new ScanService(array, i, start, end);
        }

        //synchronize with servers, wait for server end
        int result = 0;

        for (int i = 0; i < NUMBER_OF_SERVERS; i++)
        {
            try
            {
                serverThread[i].join();
            }
            catch (InterruptedException ex) {}

            result += ((ScanService) serverThread[i]).getResult();
        }

        System.out.println("Search duration: " + (System.currentTimeMillis() - startTime) + " ms");
        return result;
    }

    public static void main(String[] args)
    {
        //build array
        boolean[] array = buildArrayAsynch();

        //scan array
        int result = scanArrayAsynch(array);

        //display result
        System.out.println("\nResult: " + result);

    }
}

class BuildService extends Thread
{
    private boolean[] array;
    private int start;
    private int end;
    private int expectedResult = 0;

    public BuildService(boolean[] array, int serviceId, int start, int end)
    {
        this.array = array;
        this.start = start;
        this.end = end;

        this.setName("BuildService " + serviceId);

        this.start();
    }

    public int getExpectedResult()
    {
        return expectedResult;
    }

    public void run()
    {
        if (start < 0 || end >= array.length) throw new IndexOutOfBoundsException();

        System.out.println(getName() + ": StartIndex = " + start + "; EndIndex = " + end);

        long startTime = System.currentTimeMillis();

        for (int i = start; i <= end; i++)
        {
            //if (i % 2 == 0)
            if ((int) ((Math.random() * 2d)) == 0)
            {
                array[i] = true;
                expectedResult++;
            }
            else
            {
                array[i] = false;
            }
        }

        System.out.println(getName() + " finished! \"true\" elements: " + expectedResult + "; duration = " + (System.currentTimeMillis() - startTime) + "ms");
    }
}

class ScanService extends Thread
{
    private boolean[] array;
    private int serviceId;
    private int start;
    private int end;
    private int result = 0;

    public ScanService(boolean[] array, int serviceId, int start, int end)
    {
        this.array = array;
        this.serviceId = serviceId;
        this.start = start;
        this.end = end;

        this.start();
    }

    public int getResult()
    {
        return result;
    }

    public void run()
    {
        if (start < 0 || end >= array.length) throw new IndexOutOfBoundsException();

        System.out.println("Server " + serviceId + ": StartIndex = " + start + "; EndIndex = " + end);

        for (int i = start; i <= end; i++)
        {
            if (array[i]) result++;
        }
    }
}

Answer 1

The devil is in the details. The documentation of Math.random() has the answer:

This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.

To get around this issue, try creating an instance of java.util.Random for each instance of your BuildService class, and use that instead of Math.random(). A benefit of using java.util.Random is also that you don't have to do unnecessary double-int-arithmetic, but can simply use the nextBoolean() method.

Answer 2

You are probably seeing the effect of thread contention in Math.random(). Java 7 has the ThreadLocalRandom feature to avoid just this problem.

Answer 3

Your Code seems to be using 16 number of threads and each thread is using the Join method as in here

serverThread[i].join();

which seems to not use the full potential of threads.

when using the join you are actually saying the thread to wait till the other thread completes not running the threads in parallel.

you might want to use start method instead of join method.

Try running the changed code and post your analysis on time line.

Good luck learning

Answer 4

Taking Andreas Troelsen's answer into account I came up with the code shown below leading to the following runtimes.

Compared to what happened before, this solution now meets my expectations much better!

import java.util.Random;

class BuildService extends Thread
{
    private boolean[] array;
    private int start;
    private int end;
    private int expectedResult = 0;
    private Random random = new Random();

    public BuildService(boolean[] array, int serviceId, int start, int end)
    {
        this.array = array;
        this.start = start;
        this.end = end;

        this.setName("BuildService " + serviceId);

        this.start();
    }

    public int getExpectedResult()
    {
        return expectedResult;
    }

    public void run()
    {
        if (start < 0 || end >= array.length) throw new IndexOutOfBoundsException();

        System.out.println(getName() + ": StartIndex = " + start + "; EndIndex = " + end);

        long startTime = System.currentTimeMillis();

        for (int i = start; i <= end; i++)
        {
            array[i] = random.nextBoolean();
            if (array[i]) expectedResult++;
        }

        System.out.println(getName() + " finished! \"true\" elements: " + expectedResult + "; duration = " + (System.currentTimeMillis() - startTime) + "ms");
    }
}