Multi-Threaded program runs slower than single threaded

Question

I was trying to solve Euler Project. Gist here. Yes, I get it, there is no algorithm used - I am not trying to. The question is, the 2nd file is using an ExecutorService to find the values - I understand that the result will not be correct but it is crawling compared to single threaded one. I thought creating threads itself might have overhead reduced the pool size to 4 (I have an eight core processor) but that did nothing.

Earlier I had also used similar approach to significantly speed up thumbnail generation using multiple threads. But I am not able to understand what might be causing the slowness of this particular case. I am not trying to get the correct solution - I understand that I should do that first and then attempt anything else. What is that I doing it wrong. I am not coming here with intention to find a solution to the problem but I want to understand why is it slow. I have used static variables that are accessed by Threads. Could that be an issue ?

How long are the threads running? If they are short lived then it may not be worth it. Are they blocked on IO? You only see speed improvements if you are CPU bound. — Gray
It might be the overhead of creating an almost infinite number of Runnables (including ones for negative numbers) — user253751
@Gray I am using ExecutorService, so hopefully all threads should live until a number is found - I kill the program after 5-6 minutes of execution since it is running very slowly. Should I run it longer ? But calls in a thread lasts only a few milliseconds around 1-2. Blocked on IO - Now I only have one line of System.out.println - will that still matter that tell the count I have reached in checking factor ? It still runs much slower compared to single-threaded. — ykesh
@immibis Even after running for a few minutes I see the count - not of thread, but how many times thread have executed a particular method - I have reached is in few hundred thousands. Number of threads - I am printing the Thread ID, the maximum Thread ID I see is 15. Also I think I am using thread pool, so will it still create infinite threads. Am I missing something? — ykesh

Gray Gray · Accepted Answer · 2014-03-25T19:42:00

I understand that the result will not be correct but it is crawling compared to single threaded one

I kill the program after 5-6 minutes of execution since it is running very slowly

First off, I assume you are using a Executors.newFixedThreadPool() which allocates a fixed number of threads and not a cached thread pool.

It seems to me that you may be creating some huge number of jobs and you program is running out of memory. As you fill up memory the JVM works harder and harder on GC which shows up as your process getting slower and slower. You could connect to the application using jconsole to verify the number of threads and the memory. You could also do a thread-dump on it (kill -QUIT pid) and see how many jobs you have forked.

If you are creating some huge number of jobs and your ExecutorService just can't keep up, then you will need to throttle the job production. There are a couple different ways to do that. Here's what I use:

Process Large File for HTTP Calls in Java

Couple other solutions linked from there.

I thought creating threads itself might have overhead reduced the pool size to 4 (I have an eight core processor) but that did nothing.

Yeah this doesn't seem like a processor issue. I would move it back to 8. If this really makes the box unusable then try 7 or 6 threads in your ExecutorService.

Edit:

After looking at the code more, you are doing a bunch of unsynchronized data updating that is going to cause strange results. Anytime you modify shared memory (in your case shared static fields) then you are going to have to have some synchronization both in terms of mutex (++) and memory sharing.

I'd consider using AtomicLong and others if you can but you should read some threading tutorials on shared memory and synchronization: http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html

Multi-Threaded program runs slower than single threaded

1 Answers