CODEWITHSUNDEEP
javamultithreadingperformance
NightDog
NightDog

Reputation: 145

Is it worth threading a operation that takes 1 second to complete?

I want to improve the performance of my application, and found that it spends about 90% of its running time doing one of my while loops. What I basically do in this while loop is the following.

int i = 0;
while (i < 100)
  1) Search a big arrayList for position of an objects timestamp.
  2) Search the same arrayList for position of another objects timestamp.
  3) I get this subArrayList (or timewindow).
  4) The array that now is returned I iterate through and compute an average.
  5) I push this average into a stack.
  i++
endwhile

One iteration of this loop takes on average 1-10 milliseconds, and this whole part usually takes from 100-1000 milliseconds. From what I can understand, even tho the 99th sublist only takes about 1 ms to complete, it will have waited 99-9999 ms before it got its chance to do that, right, or am I way off here?

What I had in mind was spawning a thread and have it return its value on position i. When all threads where done, continue program.

I don't care if the average of timewindow x returns before average of timewindow y, only that all the threads/values have returned before I continue.

I got the following questions:

Would it be worthwhile to try and make every iteration a thread of some sort and compute it in parallel?

If so, would I need a thread pool, and what is the best way to go about doing that?

Upvotes: 2

Views: 322

Answers (6)

Mike Dunlavey
Mike Dunlavey

Reputation: 40669

There is significant overhead for coordinating threads, and they do not help performance at all unless they allow multiple cores to get cranking, or if you can overlap computation with I/O.

Before considering a design change, why not find out what bottlenecks you have, and fix them? Here's a simple way to do that. Often you can find large speedups that way.

Upvotes: 1

AlexR
AlexR

Reputation: 115328

I like answers gven by @Suesh and @nanda and would like to summarize.

First, optimize your code. I think that at least half of the time of the operation you are spending on copying of the sub array. You have to work in place: find the first and last index of the array and calculate average of the elements. The best solution requires just one run on the array. If it is impossible (I do not know what is your logic to find the indexes) in the worse case you have to iterate the array twice. But do not copy its content.

If this optimization does not help enough think about thread pool or actors model using Akka (as was suggested by nanda)

Upvotes: 0

Kissaki
Kissaki

Reputation: 9217

Depends on your goal. Should it run in less then a second? May the data grow (a lot)?

Threading is only applicable if you can efficiently create sub-tasks. For example, if your list you iterate through would be a linked list, it may not be applicable with cheap computations on each element as, for a sub-task, navigating to subparts of the list is expensive. If you have individual lists you each have to iterate over it may just be good though, as you’ll start to iterate from the beginning of the list anyway.

In your case, sure. Why not. You’ll have to decide on a strategy on what to do with your results though. Should they be placed in order in your stack? Or does it not matter? Do you want to thread and then let the thread wait until those in front finish? Or do you use a different strategy? Waiting threads is not good though, ofc. If you can create 2 or 4 threads and each can continually work, that’s when it becomes very performant.

As you iterate i from 0 to 100 and each iteration does not depend on another iteration you’re good to separate those into sub-tasks. You have 100 tasks. Those can be split amongst threads.

Don’t overkill with threads, you only have a limited amount of CPUs and only 100 tasks, so 2 or 4 threads should be enough. Make the threads and tell them to compute the content of your while for the indices e.g. 25 to 50.

Upvotes: 0

Dunaril
Dunaril

Reputation: 2795

How do you get your sublist from the big array? A simple, already efficient improvement would be to iterate through the array only once, selecting the elements and adding their to an iteratively calculated average.

Something like :

int sum = 0;
int count = 0;
for(MyObject object : myBigArray){
    if (mustBelongToSublist(object){
        count++;
        sum += object.value();
    }
}
int average = (double)sum/count;

Upvotes: 0

Dead Programmer
Dead Programmer

Reputation: 12575

I get sublist i from a big array.

Why cant you use the same array to compute the average.you know the index start and end position .Run another while loop inside the parent while to compute average.

if you go for threading , i have following question.

which part of the block you want to run parallel

what about Synchronization? , multliple thread writing to the stack.

Upvotes: 3

nanda
nanda

Reputation: 24788

The problem with thread is... it is a heavy object to initiate and synchronize. So one second operation might be not worth it.

Take a look at Actor model pattern. For Java you can use Akka. With actor, you can do concurrent operation lightly.

Upvotes: 4

Related Questions