2

Background: I hope my question is not too vague. I will try and explain as much as possible, and cannot post too much code, as the affected method is very complex and lengthy. So my problem is that I am trying to speed up processing with multiple threads. The application is for lighting in my 2D game engine, where I draw black rectangles of different transparency levels on top om my scene (which is currently causing lag).

The first step for me was to batch adjacent rectangles of equal light level together to reduce some rendering work. This worked out fine (perhaps it can be done better, but not the point now), and now I also implemented a crude threading system, which will each batch together lighting for a separate portion of the screen.

Crux of my question: While analyzing the timing of the particular batching method described above (for different number of threads working on separate, disjoint data sets), I noticed some odd spikes. Previously, when working with one thread, the method took about 12ms to execute, with odd jumps to 15ms. I didn't think much of it. When processing with 2 or 3 threads however, I get more or less 4~5ms, with jumps to 10ms, and sometimes even as high as 20ms.

Now I realize that it is not possible for anyone to tell what the cause could be without inspecting my code, so I do not expect that. Rather, I am trying to draw some conclusions and wish to confirm them now. As stated before, each thread does work on portions of my data set, completely disjoint from one another (they do not overlap). However, the entry point to the data array is through the same method of the same instance of a particular class. So the threads all access the same array (yet separate portions of it - and for this reason I also don't use any locks) through the same method. Could this cause unexpected slow downs?

Or is it perhaps normal behavior for threads to act in this way (with execution time varying to more than double of the norm)? As another note, I create all threads at the moment I need them, and let them run to completion.

The accessing method for the data set:

public short GetLightLevelAt(int x, int y)
{
   if (inLightingBounds(x, y))
   {
      return lightData[x, y];
   }
   else
   {
      return GuessLightLevelAt(x,y); //This won't ever happen currently, guaranteed
   }
}
Improve this question
8
  • Your timing measurements suggest either 1. A bit of contention is taking place between threads while blocking occurs, and/or 2. The operating system is doing some background processing. Commented Jun 20, 2012 at 22:04
  • 1
    There are definitely good ways and bad ways to access an array just because of underlying hardware idiosyncrasies. Is there any chance the GC might be causing your spikes? Are there objects being created/destroyed? Commented Jun 20, 2012 at 22:05
  • @RobertHarvey I was suspecting contention, but my knowledge is perhaps a bit limited to pin down why this would be the cause. Could you please elaborate on how the contention occurs? This is more or less what I expect as an answer! Commented Jun 20, 2012 at 22:06
  • 1
    Contention occurs when you lock something, and some other thread tries to access it. The second thread must wait for the first thread to release its lock. Commented Jun 20, 2012 at 22:08
  • @itsme86 Hmm, that may very well be a cause. That didn't even cross my mind. My data set was initially quite small, and I created some arrays to help me with the batching. They used to be small as the lighting resolution used to be horrible (big rectangles). But now I intend to reduce the rectangles to the size of a pixel. So the data structures are much larger. I will look into that right now! Thanks! Commented Jun 20, 2012 at 22:09

4 Answers 4

Reset to default
2

In your case, it probably has to do with Garbage Collection or Context Switching as mentioned above, due to the high spikes.

However, running multi-threading over the same array may still exhibit slowdowns due to false sharing. (even with non-overlapping partitions)

For instance, the following code could have a problem with false sharing:

int[] array = new int[100000];
int a = 1;
int b = 0;

//The following loops run concurrently

//Thread A
for( int i = 0; i < 50000; i++ )
    array[i] = a;

//Thread B
for( int j = 50000; j < 100000; j++ )
    array[j] = b;

The false sharing occurs since int a and b are declared next to each other, and quite likely are on the same cache line as each other.

If run concurrently, this code could exhibit no speed-up at all, and possibly a slow-down.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think this matches closely to what I have. Is there any way to overcome this problem? Perhaps just do it sequentially instead of concurrently? Or could I restructure my data in some way? Maybe split it up or something? How would you fix the problem posed in your example?
If you declare other values between a and b, then you can force them to be on different cache-lines. In this example, I could put the declaration for "int a" before the array, and leave the declaration for "b" afterword. Or just declare an int[] padding = new int[33], between "a" and "b" (try different sizes than 33 too). There are ways to programmatically determine the size of the cache-line, but trial and error is probably easiest.
2

Maybe your dataset(s) is as large as to trash CPU cache and thus perform inconsistently? With multiple levels of cache and no way of controlling it, you'll never be able to tell exactly how much something will take.

For example, if your data is as large as most intimate cache size on the processor, and you move from one thread to three, you'll be effectively letting go of any performance benefits that it could otherwise give you. Sometimes it's really better to do things one-by-one, sequentially.

Improve this answer

7 Comments

This was one of my thoughts too (albeit not a very confident one). Thanks for the insight. I guess this will be a difficult one to test though
Only if you find how to TURN OFF the cache and re-run the whole thing.
oh, clever :) Maybe I should look into that as well.
I tried doing it sequentially right before adding my threads. This was just to help me out with splitting up the data processing and such. Didn't really affect the performance. Perhaps it could if I split it up even more. I only split it up in 2. Maybe if I split it more, it would fit in the cache. Although, my method is quite lengthy and and some long, nested loops. Not too cache friendly in my opinion.
long nested loops operating on say 1MB of data is what the cache is designed for.... What are your data sizes?
|
1

The overhead you are experiencing might be coming from context switching or resource contention. Once you max out the available cores, the OS will start context switching (basically moving from one process/thread to another process/thread).

However it is hard to tell without posting code.

Improve this answer

3 Comments

I realize this. I'm struggling to find a piece of code that is small enough, yet sensible to post. I am only using 3 working threads currently on my quad core. So it shouldn't be context switching, right?
@Denzil : You have to remember that your program isn't the only thing running on the machine.
yeah this is true. I guess I could sorta assume that the effect of the background programs would be negligible.
1

you asked whether switching from few threads to many to run that method could cause the latency. the short answer is no.

you dont have lock on that array so nothing to do with contentions.

GC will show up at random piece of code so you will see spikes here and there and not in particular place.

I bet this is not a spike. this is context switch. you clock resolution is most likely high and your quantum size is high too. so one single context switch will halt your thread for long time.

if this is the reason for your troubles then you need to reduce number of threads. you are making it slower than it could be.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.