Thread: Effect of Multi-thread on application running time

  1. #1
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275

    Effect of Multi-thread on application running time

    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

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 12-02-2011 at 11:13 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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

  5. #5
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275
    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...

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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).
    Last edited by Elysia; 12-02-2011 at 01:14 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    A programmer has a problem. The programmer thinks, "I know, I'll use threads." Now the programmer has two problems.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Nov 2011
    Posts
    37
    Quote Originally Posted by brewbuck View Post
    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

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by walla View Post
    It is usually said about regular expressions
    But unlike regular expressions, threads literally split your program in two.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 05-26-2007, 12:37 AM
  2. clock and cycle times' effect on counter time?
    By rexnprogress in forum C++ Programming
    Replies: 0
    Last Post: 11-11-2005, 07:16 PM
  3. Replies: 3
    Last Post: 06-13-2003, 06:47 AM
  4. Running an application
    By Hankyaku in forum C++ Programming
    Replies: 10
    Last Post: 05-06-2003, 01:23 AM
  5. running an application
    By 1976 in forum Windows Programming
    Replies: 1
    Last Post: 11-12-2001, 04:17 AM