Threads slowing down application and not working properly

Question

I'm making a software renderer which does per-polygon rasterization using a floating point digital differential analyzer algorithm. My idea was to create two threads for rasterization and have them work like so: one thread draws each even scanline in a polygon and the other thread draws each odd scanline, and they both start working at the same time, but the main application waits for both of them to finish and then pauses them before continuing with other computations.

As this is the first time I'm making a threaded application, I'm not sure if the following method for thread synchronization is correct:

First of all, I use two global variables to control the two threads, if a global variable is set to 1, that means the thread can start working, otherwise it must not work. This is checked by the thread running an infinite loop and if it detects that the global variable has changed its value, it does its job and then sets the variable back to 0 again. The main program also uses an empty while to check when both variables become 0 after setting them to 1.

Second, each thread is assigned a global structure which contains information about the triangle that is about to be rasterized. The structures are filled in by the main program before setting the global variables to 1.

My dilemma is that, while this process works under some conditions, it slows down the program considerably, and also it fails to run properly when compiled for Release in Visual Studio, or when compiled with any sort of -O optimization with gcc (i.e. nothing on screen, even SEGFAULTs). The program isn't much faster by default without threads, which you can see for yourself by commenting out the #define THREADS directive, but if I apply optimizations, it becomes much faster (especially with gcc -Ofast -march=native).

N.B. It might not compile with gcc because of fscanf_s calls, but you can replace those with the usual fscanf, if you wish to use gcc.

Because there is a lot of code, too much for here or pastebin, I created a git repository where you can view it.

My questions are:

1. Why does adding these two threads slow down my application?
2. Why doesn't it work when compiling for Release or with optimizations?
3. Can I speed up the application with threads?
4. If so, how?

Thanks in advance.

Answer 1

An infinite loop that makes no attempt to sleep or yield is going to relentlessly eat up your CPU. In other words:

while(t1a || t2a);

When both t1a and t2a are false, this will do a lot of work to achieve nothing. It will use as much CPU time as it can to check these two variables over and over again. Instead, you should do something more like:

while ( active ) {
    if ( ! t1a && ! t2a ) {
        // do work here
    }
    // sleep for a small amount of time
}

As for your other problems, I'm not really sure, but I bet if you make this change you'll be in a much better position to understand what's going wrong.

Also, I didn't look through your code a whole lot, but it sounds like you're also missing some locking mechanisms. Whenever two threads need to access to the same memory, they should use a locking mechanism such as a mutex to ensure that they do not do so at the same time.

Answer 2

I'll try to answer your questions but i didn't go extensively through your code so it's possible i may have missed something.

1) Adding threads has a cost. You must be sure that the cost of adding the threads is a good investment. In your case, I think you may be getting sucked into too much busy waiting from the main thread (and thus, getting cycles away from the threads) and maybe a bad parallelization scheme (tasks too small).

2) I'm really not sure abut this but based in my experience, when threaded things fail after you add optimizations is because there's some base you are not covering, like a race condition, some unitialized variable or any kind of code that is shaky and changes because of the optimizations. In your case, i think it's possible that the code "while(t1a || t2a);" is simply ommited causing all kinds of crazy things.

3) Without really understanding your code, my gut feeling is YES. (see below for some extra comments on this), but obviously you will have to do the math and the actual code to get the real answer.

4) Some ideas here:

• Busy waiting is generally BAD. Run away from it unless you have a really good reason.
• Try to split the work in such a way that the comunication between threads is minimal. If you can do n/2 sub-tasks in each thread, try to "submit" the work just once with the complete list of sub-tasks, instead of asking each thread once per each sub-task. The mechanism to talk between threads takes time (which is the overhead you have to overcome to make threads useful) and each time a thread has to wait for something you are simply wasting precious cpu cycles.
• This is not really for performance per se, simply good practice. Get in the habit of using the tools you should use to signal threads. Use condition variables if you need to signal a thread "something" happened (like the event of having work to do) and use mutexes where they should be used. These objects are heavier than simply setting a variable, but ENSURE CORRECTNESS which is no small feat. On the good side, the condition variables should allow you to use the machine's resources more effectively because you will only do work when it is needed, as opposed to hog resources and possibly slowing other processes :P.
• Finally, measure how much time your code is taking and do some excercises with higher amounts of data. It's possible that your code is working fine and you do have a noticeable improvement when the amount of data processed is bigger.

Hope this helps

Answer 3

Like others have mentioned, using threads adds cost. This is often more insidious than you'd expect, as you have to know a lot about the underlaying hardware to know what's actually going on.

This is especially true when several threads access a lot of the same data. Threads work the best when they have little or no overlapping data.

Cache lines make the "overlapping" harder to see - I'll trivialize, but let's say you have a cache that always reads 1kB of data. If your program accesses one byte, and it's not in the cache, the CPU actually has to fetch 1kB of data to the cache for you to get the one byte.

Now, let's say that you have two threads that are plotting pixels in, what looks to you, in different places in memory. Let's, for the sake of this example, say the pixels take one byte each.

If the pixels hit the same cache line, you're invalidating the cache all the time, and what in a single-threaded application took 1kB of data transfer per 1k of pixels plotted may end up taking 1kB per pixel plotted - ending up with 1MB of data transferred!