Effect of Multi-thread on application running time

[fnoyan]

Hi

I have an app using Qt as GUI tookit that is simple program that reads TXT files and creates string vectors from lines read from the files.

I perform some kind of vlookup (from MS Excel) operation on two vectors

for (int j=0;j<VectorA.size();j++)
for (int k=0; k<VectorB.size();k++)
if (MyFunction(VectorA.at(j),VectorB.at(k)))
do_some_stuff();

so, it takes time to complete the process. I have two questions regarding to code above;

i ) any other way to perform similar operation
ii ) is there going to be a significant diffrence between process complition time if I use different threads to perform the check (fro example one thread will start from middle of vector, and the other run until middle of vector)

thanks

[MK27]

Here's some general principles:

- if you have a task that involves waiting on IO, etc, and another task that does not require this to be completed first, threading will allow you to get a head start on the second task.
- if you have a task (such as yours) that can be split up and done concurrently, runtime will improve using a number of threads less than or equal to the number of cores. Using more than this will likely decrease performance, because you will have multiple threads competing for a single core. Ie, do not simply launch threads based on how there is to do.

[Elysia]

Don't take these principles for granted. A lot of things can affect performance. These general principles can be used as a guide for giving you a hint if it's possible to parallelize it or not.
Make sure to always test. When you implement a concurrent strategy, measure its performance compared to a single-threaded solution. Some things are not suited for parallelism.

[Codeplug]

The first step in achieving speedup is analysis: Where is time being spent? File reading, vector construction, MyFunction(), do_some_stuff(), etc... A profiler can provide this information. There may be plenty of opportunity for speedup without introducing additional threads.

When considering code for parallelization, each stage of the process should be analyzed to determine if it's "I/O bound" or "CPU bound" work. For example, file reading is I/O bound work. Once the file data is in memory, breaking it up into lines in vectors is CPU bound work. In general, there is more potential for speedup when parallelizing CPU bound work - and parallelizing I/O bound work typically isn't worth it.

Another thing to analyse when looking at parallelizing CPU bound work are all the data dependencies - or in other words, data that requires shared access by multiple threads. Ideally there will be no data dependencies at all. When considering how to break up a task into multiple threads, try to minimize the data dependencies.

Asynchronous (or "overlapped") I/O is another method that can provide speedup when you have lots of data to read from disk, and the data can be (CPU bound) processed as soon as it's available. This allows I/O bound work and CPU bound work to occur at the same time, but without introducing additional threads.

But before considering threads or asynchronous I/O, analyse and profile what you have now. This will give you clues as to what direction to go in.

gg

[fnoyan]

Hi

Thanks for replies.

Actually, I create vectors and then perform the vector search operation (which is the main part that causes the applicaion run longer), so we can say that the part I am trying to speed up is CPU related part.

MK27 made a good point on number-of-cpu and threads to avoid competing threads to be scheduled. Since I am writing the code for windows, I will get number of cores and create threads according to this information.

#include <windows.h>

SYSTEM_INFO sysinfo;
GetSystemInfo(&sysinfo);
x = sysinfo.dwNumberOfProcessors;

thanks...

[Elysia]

The rule that the number of threads must match the number of CPUs is not always true.
Experiment with setting up a number of threads to split the work and time them.
I'd suggest the use of std::thread (or, if you don't have access to C++11, boost::thread).

[brewbuck]

A programmer has a problem. The programmer thinks, "I know, I'll use threads." Now the programmer has two problems.

[walla]

A programmer has a problem. The programmer thinks, "I know, I'll use threads." Now the programmer has two problems.

It is usually said about regular expressions

[King Mir]

It is usually said about regular expressions

But unlike regular expressions, threads literally split your program in two.