Java factorial calculation with thread pool
I managed to compute the factorial with two threads without a pool. I have two factorial classes called Factorial1, Factorial2 and extend the Thread class. Suppose I want to calculate the value! 160000. In the Factorial1 run () method, I multiply in the for loop from i = 2 to i = 80000 and in Factorial2 from i = 80001 to 160000. Then I return both values ββand multiply them in the main method. When I compare the execution time, it is much better (which is 5000 milliseconds) than the computation time without a thread (15000 milliseconds) even with two threads.
Now I want to write cleaner and better code because I have seen the efficiency of threads in factorial computation, but when I use thread pool to compute factorial value, parallel computation always takes longer than computation without thread (almost 16000). My code snippets look like this:
for(int i=2; i<= Calculate; i++)
{
myPool.execute(new Multiplication(result, i));
}
run (), which is in the multiplication class:
public void run()
{
s1.Mltply(s2); // s1 and s2 are instances of my Number class
// their fields holds BigInteger values
}
The Mltply () method, which is in the Number class:
public void Multiply(int number)
{
area.lock(); // result is going wrong without lock
Number temp = new Number(number);
value = value.multiply(temp.value); // value is a BigInteger
area.unlock();
}
In my opinion, this blocking can kill all the benefits of using a stream, because it seems like all those streams are multiplication, but nothing else. But without that, I can't even calculate the true result. Let's say I want to calculate! 10, so thread1 calculates 10 * 9 * 8 * 7 * 6 and thread2 calculates 5 * 4 * 3 * 2 * 1. Is this what I'm looking for? Is this possible with a thread pool? Of course, the execution time should be less than a normal computation ...
I appreciate all your help and suggestion.
EDIT: - My own solution to the problem -
public class MyMultiplication implements Runnable
{
public static BigInteger subResult1;
public static BigInteger subResult2;
int thread1StopsAt;
int thread2StopsAt;
long threadId;
static boolean idIsSet=false;
public MyMultiplication(BigInteger n1, int n2) // First Thread
{
MyMultiplication.subResult1 = n1;
this.thread1StopsAt = n2/2;
thread2StopsAt = n2;
}
public MyMultiplication(int n2,BigInteger n1) // Second Thread
{
MyMultiplication.subResult2 = n1;
this.thread2StopsAt = n2;
thread1StopsAt = n2/2;
}
@Override
public void run()
{
if(idIsSet==false)
{
threadId = Thread.currentThread().getId();
idIsSet=true;
}
if(Thread.currentThread().getId() == threadId)
{
for(int i=2; i<=thread1StopsAt; i++)
{
subResult1 = subResult1.multiply(BigInteger.valueOf(i));
}
}
else
{
for(int i=thread1StopsAt+1; i<= thread2StopsAt; i++)
{
subResult2 = subResult2.multiply(BigInteger.valueOf(i));
}
}
}
}
public class JavaApplication3
{
public static void main(String[] args) throws InterruptedException
{
int calculate=160000;
long start = System.nanoTime();
BigInteger num = BigInteger.valueOf(1);
for (int i = 2; i <= calculate; i++)
{
num = num.multiply(BigInteger.valueOf(i));
}
long end = System.nanoTime();
double time = (end-start)/1000000.0;
System.out.println("Without threads: \t" +
String.format("%.2f",time) + " miliseconds");
System.out.println("without threads Result: " + num);
BigInteger num1 = BigInteger.valueOf(1);
BigInteger num2 = BigInteger.valueOf(1);
ExecutorService myPool = Executors.newFixedThreadPool(2);
start = System.nanoTime();
myPool.execute(new MyMultiplication(num1,calculate));
Thread.sleep(100);
myPool.execute(new MyMultiplication(calculate,num2));
myPool.shutdown();
while(!myPool.isTerminated()) {} // waiting threads to end
end = System.nanoTime();
time = (end-start)/1000000.0;
System.out.println("With threads: \t" +String.format("%.2f",time)
+ " miliseconds");
BigInteger result =
MyMultiplication.subResult1.
multiply(MyMultiplication.subResult2);
System.out.println("With threads Result: " + result);
System.out.println(MyMultiplication.subResult1);
System.out.println(MyMultiplication.subResult2);
}
}
input :! 160000 Runtime without threads: 15000 milliseconds Runtime with 2 threads: 4500 milliseconds
Thanks for the ideas and suggestions.
source to share
Threads must run independently for quick start. Many dependencies, such as locks, synchronized parts of your code, or some system calls, lead to sleeping threads waiting to access some resources.
In your case, you should minimize the time the thread is inside the block. I may be wrong, but it seems that you are creating a thread for each number. So, for 1.000!
you create 1.000 threads. They all try to acquire the lock on area
and cannot calculate anything, because one thread has become a lock, and all other threads must wait until the lock is unlocked. This way, threads only execute sequentially, which is just as fast as your non-threading example, plus additional time for locking and unlocking, threading, and so on. Oh, and because of the processor context switching it gets even worse.
Your first attempt at splitting the factorial in two streams is the best. Each thread can compute its own result, and only when they are executed, the threads need to communicate with each other. Therefore, they are independent most of the time.
Now you need to generalize this solution. To reduce processor context switching only requires as many threads as your processor has cores (maybe slightly fewer due to your OS). Each thread receives a link of numbers and calculates their product. Then he captures the overall result and adds his own result to it.
This should improve the performance of your problem.
Update: you are asking for more tips:
You said that you have two classes Factorial1
and Factorial2
. They probably have their own ranges of hardcodes. You only need one class that takes a range as constructor arguments. This class implements Runnable, so it has a run
-Method that multiplies all values ββin this range.
In you main
-method you can do something like this:
int n = 160_000;
int threads = 2;
ExecutorService executor = Executors.newFixedThreadPool(threads);
for (int i = 0; i < threads; i++) {
int start = i * (n/threads) + 1;
int end = (i + 1) * (n/threads) + 1;
executor.execute(new Factorial(start, end));
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.DAYS);
You have now computed the result of each thread, but not the overall result. This can be solved with BigInteger
class visible Factorial
(e.g. a static BigInteger reuslt;
in the same main class.) And locking. In the method, run
Factorial
you can calculate the total result by blocking the lock and calculating the result:
Main.lock.lock();
Main.result = Main.result.multiply(value);
Main.lock.unlock();
Some additional advice for the future: This is not very clean because it Factorial
needs to have information about your main class, so it has a dependency on it. But it ExecutorService
returns an Future<T>
-Object that can be used to get the result of the stream. By using this Future
-Object you don't need to use locks. But this requires some extra work, so just try it now ;-)
source to share
You can calculate !160000
at the same time without using a lock by dividing 160000
into the scattered junks when you expand them by dividing it by 2..80000 and 80001..160000.
But you can achieve this using Java Stream API:
IntStream.rangeClosed(1, 160000).parallel()
.mapToObj(val -> BigInteger.valueOf(val))
.reduce(BigInteger.ONE, BigInteger::multiply);
It does exactly what you are trying to do. It splits the entire range into junks, sets up a thread pool, and calculates partial results. It then combines the partial results into one result.
So why are you doing this yourself? Just practicing clean coding?
In my real 4-core computation, there are 8 times more machines in a for loop than when using a parallel thread.
source to share
In addition to my Java Stream API solution, there is another solution here that uses a self-starting thread pool as per your requirement:
public static final int CHUNK_SIZE = 10000;
public static BigInteger fac(int max) {
ExecutorService executor = newCachedThreadPool();
try {
return rangeClosed(0, (max - 1) / CHUNK_SIZE)
.mapToObj(val -> executor.submit(() -> prod(leftBound(val), rightBound(val, max))))
.map(future -> valueOf(future))
.reduce(BigInteger.ONE, BigInteger::multiply);
} finally {
executor.shutdown();
}
}
private static int leftBound(int chunkNo) {
return chunkNo * CHUNK_SIZE + 1;
}
private static int rightBound(int chunkNo, int max) {
return Math.min((chunkNo + 1) * CHUNK_SIZE, max);
}
private static BigInteger valueOf(Future<BigInteger> future) {
try {
return future.get();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
private static BigInteger prod(int min, int max) {
BigInteger res = BigInteger.valueOf(min);
for (int val = min + 1; val <= max; val++) {
res = res.multiply(BigInteger.valueOf(val));
}
return res;
}
source to share