Multithreading not faster than single thread (simple loop test)

Question

I'm experimenting with some multithreading constructions, but somehow it seems that multithreading is not faster than a single thread. I narrowed it down to a very simple test with a nested loop (1000x1000) in which the system only counts.
Below I posted the code for both single threading and multithreading and how they are executed.
The result is that the single thread completes the loop in about 110 ms, while the two threads also take about 112 ms.
I don't think the problem is the overhead of multithreading. If I only submit one of both Runnables to the ThreadPoolExecutor, it executes in half the time of the single thread, which makes sense. But adding that second Runnable makes it 10 times slower. Both 3.00Ghz cores are running 100%.
I think it may be pc-specific, as someone else's pc showed double-speed results on the multithreading. But then, what can I do about it? I have a Intel Pentium 4 3.00GHz (2 CPUs) and Java jre6.

Test code:

// Single thread:
long start = System.nanoTime(); // Start timer
final int[] i = new int[1];     // This is to keep the test fair (see below)
int i = 0;
for(int x=0; x<10000; x++)
{
    for(int y=0; y<10000; y++)
    {
        i++; // Just counting...
    }
}
int i0[0] = i;
long end = System.nanoTime();   // Stop timer

This code is executed in about 110 ms.

// Two threads:

start = System.nanoTime(); // Start timer

// Two of the same kind of variables to count with as in the single thread.
final int[] i1 = new int [1];
final int[] i2 = new int [1];

// First partial task (0-5000)
Thread t1 = new Thread() {
    @Override
    public void run() 
    {
        int i = 0;
        for(int x=0; x<5000; x++)
            for(int y=0; y<10000; y++)
                i++;
        i1[0] = i;
    }
};

// Second partial task (5000-10000)  
Thread t2 = new Thread() {
    @Override
    public void run() 
    {
        int i = 0;
        for(int x=5000; x<10000; x++)
            for(int y=0; y<10000; y++)
                i++;
        int i2[0] = i;
    }
};

// Start threads
t1.start();
t2.start();

// Wait for completion
try{
    t1.join();
    t2.join();
}catch(Exception e){
    e.printStackTrace();
}

end = System.nanoTime(); // Stop timer

This code is executed in about 112 ms.

Edit: I changed the Runnables to Threads and got rid of the ExecutorService (for simplicity of the problem).

Edit: tried some suggestions

Answer 1

You definitely don't want to keep polling Thread.isAlive() - this burns a lot of CPU cycles for no good reason. Use Thread.join() instead.

Also, it's probably not a good idea having the threads increment the result arrays directly, cache lines and all. Update local variables, and do a single store when the computations are done.

EDIT:

Totally overlooked that you're using a Pentium 4. As far as I know, there's no multi-core versions of the P4 - to give the illusion of multicore, it has Hyper-Threading: two logical cores share the execution units of one physical core. If your threads depend on the same execution units, your performance will be the same as (or worse than!) single-threaded performance. You'd need, for instance, floating-point calculations in one thread and integer calcs in another to gain performance improvements.

The P4 HT implementation has been criticized a lot, newer implementations (recent core2) should be better.

Answer 2

Try increasing the size of the array somewhat. No, really.

Small objects allocated sequentially in the same thread will tend to be initially allocated sequentially. That's probably in the same cache line. If you have two cores access the same cache line (and then micro-benhcmark is essentially just doing a sequence of writes to the same address) then they will have to fight for access.

There's a class in java.util.concurrent that has a bunch of unused long fields. Their purpose is to separate objects that may be frequently used by different threads into different cache lines.