Sign in to follow this  
phrebh

Persistence needed during render loops

Recommended Posts

I am trying to write an effect that will average the colors of every pixel in the image/selection and fill the image/selection with that color. I've gotten amazingly close considering I've never done any C# programming before last week, but I've run into problem of the regions used for multi-threading the rendering. Right now I get a series of stripes representing the average color for each rendering region and I cannot figure out how to get the entire image/selection to work.

As you can see in the code, I tried to use a "dreaded" global class, but this doesn't do anything for me, whether I use CodeLab or compile it in VSE. The other thought I had was that if I could work on an invisible canvas, I could do the first pass, turn it 90 degrees and run a second pass to get the final value (which is basically the workaround I have used to get what I needed).

Any help (or original sarcasm) will be greatly appreciated.

[EDIT]

Hidden Content:
This is the CodeLab code:

static class GlobalClass
{
   private static ColorBgra m_globalVar;
   public static ColorBgra AverageColor
   {
       get { return m_globalVar; }
       set { m_globalVar = value; }
   }
}

// Based on Rik Hemsley's code posted on the org.kde.kde-core-devel list.
ColorBgra average(ColorBgra fg, ColorBgra bg)
{
 const double d0 = (double)256;
 const double d1 = 0.2979;
 const double d2 = 0.5866;
 const double d3 = 0.1145;
 const double d4 = -0.1687;
 const double d5 = 0.3312;
 const double d6 = 0.5000;
 const double d7 = 0.4183;
 const double d8 = 0.0816;
 const double d9 = 1.4022;
 const double d10 = 0.3456;
 const double d11 = 0.7145;
 const double d12 = 1.7710;
 const double mix = 0.5;

 double y, cb, cr, y0, cb0, cr0, y1, cb1, cr1;
 double r0, g0, b0, r1, g1, b1;

 ColorBgra ret = fg;

 r0 = (double)fg.R / d0;
 g0 = (double)fg.G / d0;
 b0 = (double)fg.B / d0;

 r1 = (double)bg.R / d0;
 g1 = (double)bg.G / d0;
 b1 = (double)bg.B / d0;

 y0 = d1 * r0 + d2 * g0 + d3 * b0;
 cb0 = d4 * r0 - d5 * g0 + d6 * b0;
 cr0 = d6 * r0 - d7 * g0 - d8 * b0;

 y1 = d1 * r1 + d2 * g1 + d3 * b1;
 cb1 = d4 * r1 - d5 * g1 + d6 * b1;
 cr1 = d6 * r1 - d7 * g1 - d8 * b1;

 y = y0 + mix * (y1 - y0 );
 cb = cb0 + mix * (cb1 - cb0);
 cr = cr0 + mix * (cr1 - cr0);

 ret.R = (byte)(d0 * (y + d9 * cr));
 ret.G = (byte)(d0 * (y - d10 * cb - d11 * cr));
 ret.B = (byte)(d0 * (y + d12 * cb));
 ret.A = (byte)255; // always set to no transparency to make the result visible

 return ret;
}

void Render(Surface dst, Surface src, Rectangle rect)
{
 // The first time render is run we set the AverageColor so we have our first
 // parameter for the first time we call the averager function
 if (GlobalClass.AverageColor == null)
 {
   GlobalClass.AverageColor = src[0, 0];
 }

 PdnRegion selectionRegion = EnvironmentParameters.GetSelection(src.Bounds);

 ColorBgra CurrentPixel;
 for (int y = rect.Top; y < rect.Bottom; y++)
 {
   for (int x = rect.Left; x < rect.Right; x++)
   {
     if (selectionRegion.IsVisible(x, y))
     {
       CurrentPixel = src[x,y];
       GlobalClass.AverageColor = average(GlobalClass.AverageColor, CurrentPixel);
       dst[x,y] = CurrentPixel;
     }
   }
 }

 // fill out selection with average color
 for (int y = rect.Top; y < rect.Bottom; y++)
 {
   for (int x = rect.Left; x < rect.Right; x++)
   {
     if (selectionRegion.IsVisible(x, y))
     {
       dst[x,y] = GlobalClass.AverageColor;
     }
   }
 }
}

p.s. I wouldn't have even understood anything I wrote above even a week ago without the great help of people on the forums and the openness of effects writers. Thanks, all!

Share this post


Link to post
Share on other sites
I am trying to write an effect that will average the colors of every pixel in the image/selection and fill the image/selection with that color.

         dst[x,y] = CurrentPixel;
     }
   }
 }

 // fill out selection with average color
 for (int y = rect.Top; y   {
   for (int x = rect.Left; x     {
     if (selectionRegion.IsVisible(x, y))
     {
       dst[x,y] = GlobalClass.AverageColor;

I've had a quick look at your code and cannot escape the conclusion that you're writing twice to the destination canvas. In the code quote above see the first and last lines? Both seem to dump a value into dst[x,y]. Is this required, or what you desire? The second "write" will always overwrite the first.

p.s. I wouldn't have even understood anything I wrote above even a week ago without the great help of people on the forums and the openness of effects writers. Thanks, all!

Welcome aboard! Despite having released a few meagre plugins, I'm just a beginner myself :wink: I'm sure the wise heads here will be able to point you in the right direction.

Share this post


Link to post
Share on other sites
I am trying to write an effect that will average the colors of every pixel in the image/selection and fill the image/selection with that color. I've gotten amazingly close considering I've never done any C# programming before last week, but I've run into problem of the regions used for multi-threading the rendering. Right now I get a series of stripes representing the average color for each rendering region and I cannot figure out how to get the entire image/selection to work.
The reason you are getting the stripes is because in your averaging code you are only taking the average of the colours in each of the rendering rectangles as opposed to the image as a whole. To take the average of every pixel your average code should look more like this

for(int y = 0; y < src.Height; y++)
{
   for (int x = 0; x < src.Width; x++)
   {
       //TODO: your averaging code
   }
}

notice how I replaced the lines "int y = rect.Top" with "int y = 0" and likewise for the rest of the bounds, this will make sure you look at every pixel in your image.

However you will only want to do this once as its very time consuming so at the start of the rendering method you can check if you need to do the averaging and then do it if you need to. On the other hand, if you are building it in VS, you should calculate the average in the OnSetRenderInfo

Another small tip, when setting the average colour to each pixel, get rid of the call if(selection.IsVisible(x, y)) because it is slow and not really necessary.

Here is a sample of something I just put together which does pretty much what you want it to do, although it doesn't use the blur algorithm from your original code and it takes the average of the whole picture regardless of the selection but you get the idea.

private bool set = false;
private ColorBgra avg;

private unsafe void Render(Surface dst, Surface src, Rectangle rect)
{
   if(!set)
   {
       set = true;     
       ColorBgra[] cols = new ColorBgra[src.Height];        
       for(int y = 0; y < src.Height; y++)
       {
           ColorBgra* ptr = src.GetRowAddress(y);
           cols[y] = ColorBgra.Blend(ptr, src.Width);            
       }  
       avg = ColorBgra.Blend(cols);             
   }                    

   for(int y = rect.Top; y < rect.Bottom; y++)
   {
       for (int x = rect.Left; x < rect.Right; x++)
       {
           dst[x,y] = avg;
       }
   }
}

But like I said, if you build it in VS, you can put the:

ColorBgra[] cols = new ColorBgra[src.Height];        
for(int y = 0; y < src.Height; y++)
{
   ColorBgra* ptr = src.GetRowAddress(y);
   cols[y] = ColorBgra.Blend(ptr, src.Width);            
}  
avg = ColorBgra.Blend(cols); 

in your OnSetRenderInfo() method and remove it from the render function completely.

Have a play with that and see how it goes, if you have any more questions feel free to ask.

Share this post


Link to post
Share on other sites

Okay, over a year has passed and I've finally gotten around to revisiting this plugin. Thanks to help from both Curtis and EER, I've almost got this finished. Maybe it's just because I've been doing a lot of programming (in various non-C# languages) this year, but replacing the global class with a global variable was a fairly thing to do.

For the most part it works, but occasionally it produces transparent, horizontal lines instead of a completely solid color. It seems to happen mostly with elliptical selections, although I have seen it with rectangular ones, too. I have not seen them when averaging the entire image. Strangely enough, if I force CodeLab to re-render it, sometimes the transparent lines go away.

I should point out that it happens whether or not a put the IsVisible check as part of the rendering in the final for loop.

Any thoughts or advice? Thanks!

EDIT: I removed both instances of the isVisible line and adjusted the rest of the code accordingly. It now seems to work for most selections, but with some selections, or if nothing is selected, it seems to either show a dark gray or just the top left pixel color. I've updated the code below with the changes.

CodeLab code:

private bool set = false;
private ColorBgra AverageColor;

// Based on Rik Hemsley's code posted on the org.kde.kde-core-devel list.
ColorBgra average(ColorBgra fg, ColorBgra bg)
{
 const double d0 = (double)256;
 const double d1 = 0.2979;
 const double d2 = 0.5866;
 const double d3 = 0.1145;
 const double d4 = -0.1687;
 const double d5 = 0.3312;
 const double d6 = 0.5000;
 const double d7 = 0.4183;
 const double d8 = 0.0816;
 const double d9 = 1.4022;
 const double d10 = 0.3456;
 const double d11 = 0.7145;
 const double d12 = 1.7710;
 const double mix = 0.5;

 double y, cb, cr, y0, cb0, cr0, y1, cb1, cr1;
 double r0, g0, b0, r1, g1, b1;

 ColorBgra ret = fg;

 r0 = (double)fg.R / d0;
 g0 = (double)fg.G / d0;
 b0 = (double)fg.B / d0;

 r1 = (double)bg.R / d0;
 g1 = (double)bg.G / d0;
 b1 = (double)bg.B / d0;

 y0 = d1 * r0 + d2 * g0 + d3 * b0;
 cb0 = d4 * r0 - d5 * g0 + d6 * b0;
 cr0 = d6 * r0 - d7 * g0 - d8 * b0;

 y1 = d1 * r1 + d2 * g1 + d3 * b1;
 cb1 = d4 * r1 - d5 * g1 + d6 * b1;
 cr1 = d6 * r1 - d7 * g1 - d8 * b1;

 y = y0 + mix * (y1 - y0 );
 cb = cb0 + mix * (cb1 - cb0);
 cr = cr0 + mix * (cr1 - cr0);

 ret.R = (byte)(d0 * (y + d9 * cr));
 ret.G = (byte)(d0 * (y - d10 * cb - d11 * cr));
 ret.B = (byte)(d0 * (y + d12 * cb));
 ret.A = (byte)255; // always set to no transparency to make the result visible

 return ret;
}

void Render(Surface dst, Surface src, Rectangle rect)
{
 PdnRegion selectionRegion = EnvironmentParameters.GetSelection(src.Bounds);
 ColorBgra CurrentPixel;

 if (AverageColor == null)
 {
   AverageColor = src[rect.Top,rect.Left];
 }

 if (!set)
 {
   set = true;
   for (int y = rect.Top; y < rect.Bottom; y++)
   {
     for (int x = rect.Left; x < rect.Right; x++)
     {
       CurrentPixel = src[x,y];
       AverageColor = average(AverageColor, CurrentPixel);
     }
   }
 }

 // fill out selection with average color
 for (int y = rect.Top; y < rect.Bottom; y++)
 {
   for (int x = rect.Left; x < rect.Right; x++)
   {
     dst[x,y] = AverageColor;
   }
 }
}

Share this post


Link to post
Share on other sites

Not to discourage you from writing this plugin, which is a good way to learn, but I already wrote a plugin to average the color over a selection. The post is in the plugin publication section and is called "Plugin to Average Color of Selection." The last comment was added on Sept. 4, 2009. My initial comment includes the CodeLab code. Like your code, it uses a global flag to make the average occur only in the first step.

It isn't obvious to me why you do the funky matrix multiply in the color averaging code, but I assume you have a reason do it that way instead of just adding up the the individual r, g, and b components.

Unless I'm missing something (and I may be), you averaging code won't work. To do a running average, you need to include the current value of N in the calculation. In any case, I don't think it's a good idea to do a running average; it's better to just sum up the components and divide by the total N as the final step, since it's simpler, and the intermediate averages are never needed.

I think you're averaging over the wrong region. "rect.Top," etc. is the extent of the current slice you're working on, so you end up with the average of the first assigned slice. You need to use "selection.Top," etc.

Also, I believe the idea that the IsVisible test isn't needed is mistaken. The test isn't needed to decide whether to write a pixel, since Paint.NET will only write a pixel if it's selected. However, it is necessary to decide whether to include the pixel in the average. Otherwise, you end of with the average of the selection's bounding box. The reason it wasn't needed in Curtis's example is that he was applying it to the entire window, not just a selection.

Share this post


Link to post
Share on other sites

There are two reasons for me to continue. The first one is that I started my plugin months before yours was posted. But most importantly, you are doing it wrong. Averaging the RGB values will not give you the proper color. You have to average the HSV values, which is why my averaging code is so complicated.

I removed the IsVisible check because there are many instances in the forums where the really experienced people say not to use it. Ever.

Through testing, I know that using rect.top, etc., is working because I get different results for different parts of the same region. I won't pretend to understand why.

You do have an excellent point about the running average, though, and I agree that I need to readdress it, but I don't see how that will fix my underlying problem of the missing lines.

Thanks!

Share this post


Link to post
Share on other sites

I think those saying that IsVisible is never needed are wrong. It isn't needed in most cases, and in particular it's never needed for deciding whether to write a pixel. It is needed in this case.

From a theoretical point of view, if you want to include only the selected pixels in the average, there's got to be some test to reject pixels that aren't in the selection. The "selection.Top," etc. limits obviously aren't sufficient, since they always define a rectangular region. Without the IsVisible test, how are non-selected pixels in a non-rectangular selection rejected?

For anyone who doubts that argument, please try the following test. Take my CodeLab code and remove the IsVisible test. Then run Paint.Net and make an image with a red background. Add a circle filled with white. Now select the filled circle. Run my original plugin, and note that the averaged color is, as it should be, white. Undo the change, and do the same thing using the plugin with the IsVisible test removed. Is the averaged color white or is it pink?

You claim I'm doing it wrong, and that it needs to be done in HSV. I don't think so. What your code does -- or attempts to do -- is convert to HSV using a matrix multiplication, average the HSV components, then convert back to RGB by multiplying by the inverse matrix. But the average is a linear combination of the input values, so the result of applying a linear transformation to the values, averaging them, then applying the inverse linear transformation is the same as averaging the original values.

I.e., if c1,...,cN are RGB color vectors, M is the matrix, and I is its inverse:

[1/N (c1 M + c2 M + ... + cN M)] I =

1/N (c1 M I + c2 M I + ... + cN M I) =

1/N (c1 + c2 + ... + cN)

I don't know why you get the results you get using "rect.Top," etc. as the region over which you compute the average, nor am I going to spend any time thinking about it. I do know it's wrong.

[Let me add, by way of an edit, that you aren't really converting to HSV space. It looks like you're actually converting to something called YCbCr space. The HSV conversion involves a nonlinear transformation, so the average in HSV space would be different than the average in RGB space. I'm not sure you could even compute a meaningful average for the H value, since it wraps around from 0 to 360. That implies the results would be order-dependent, which doesn't really make sense for an average. Also, H is undefined for shades of gray.]

Share this post


Link to post
Share on other sites

The IsVisible code is never needed if you stay within the ROI passed into the Render function.

Using Selection.Top, for example, could return pixels to you that are outside of the ROI including pixels that are not even selected. This happens when the selection is not a rectangle.

Consider the following image:

ROI.png

The white pixels that are outside of the selection would be returned if you loop through Selection.Top to Selection.Bottom etc.

BTW, the best way to write the plugin that you are working on is to NOT make it a CodeLab script. Then, you can do your averaging code inside of the OnRender function. (For an example of a full effect, see the source code for my fire effect here: viewtopic.php?f=16&t=26579 )

Hope this helps.

Share this post


Link to post
Share on other sites

Hey phrebh, I know what you mean about persistence, I'd like some too.

I think you've got a good idea here with this HSV average thing, I want to see how it turns out. Maybe I can help you with your code?

First up, two synchronization issues...

1. Other threads may set destination pixels to AverageColor while the first thread is still in the process of updating AverageColor. There's nothing to stop them!

2. Unless the C# compiler magically infers that you want an atomic test-and-set, it's possible for two or more threads to get into the "if (AverageColor == null)" block (or the "if (!set)" block) before you assign AverageColor (or change set to true). You can keep other threads out of a block by using the "lock" statement, it's a nice little bit of syntactic sugar for entering and exiting a Monitor.

Code segment removed, because it's wrong.

If you can sort out the synchronization issues, we can talk about problems with the algorithm you're using to compute the average, and about getting a result for the hue channel that makes sense. I've got some ideas for you. Hope I could help!

Share this post


Link to post
Share on other sites

The synchronization issue is something I didn't take into account when writing my version of the plugin. I have a somewhat ancient single-processor system, so I didn't think about the problem as I probably should have.

I'm not sure if the lock mechanism works with multiple processors (or multiple cores) rather than just for multiple threads on the same processor. I'm also not sure if Paint.NET starts multiple simultaneous rendering threads on single-processor systems. If it does, I would have expected to sometimes see incorrectly colored stripes using my version of the color-averaging plugin. So far, I haven't.

Unless I'm not thinking about the synchronization problem correctly, it seems to me it can be avoided by not setting the flag (called "set" in phrebh's code) until after the average color of the selection has been computed and written into the global variable. In multiprocessor systems, it may happen that more than one processor will compute the average color. That may be somewhat inefficient, but since the average color will be the same each time it's computed, it shouldn't affect the result.

Share this post


Link to post
Share on other sites
I'm also not sure if Paint.NET starts multiple simultaneous rendering threads on single-processor systems.

Paint.NET always uses a minimum of 2 threads, precisely to ensure a more homogenous execution environment between single- and multi-threaded processors.

Share this post


Link to post
Share on other sites

Thanks for writing, MJW!

Multiple processors might affect the order of serialization, but I'm quite sure the lock statement still behaves as expected with multiple cores. Rick just answered your question about the number of rendering threads.

In your code for "Plugin to Average Color of Selection", if thread X enters "if (firstTime)" but doesn't manage to change "firstTime" before transfer of control occurs, then thread Y will still be free to enter the block. The difference is probably only a couple of lines of IL, so it's very unlikely to happen, and if it does occur, it just results in some unnecessary computation. This is because you're correctly using local variables to compute your result. phrebh is using an instance variable (AverageColor), and when multiple threads get into that block, they'll all be taking turns modifying it recursively, in an unpredictable order.

Also, important to note that phrebh's code would still be writing AverageColor out to destination pixels before it's actually done computing it, which is probably the most serious issue. Note that this is done by-value.

If you explicitly serialize the computations by using a lock, then you can use a flag to ensure that only one computation ever occurs. My code uses whether AverageColor is null or not as a flag. Most importantly, the flag and locks keep any thread from writing anything to the output until the computation is finished. But as an added bonus, the flag prevents unnecessary computation. The extra if statement is to prevent any thread from trying to acquire the lock if the average has already been computed. This allows subsequent calls to Render to run in parallel.

My experience with parallel programming is limited, but I feel like this would be pretty common... maybe there's a better way to express it in C#?

Share this post


Link to post
Share on other sites

Thanks to Neil Cassidy and Rick Brewster for their comments.

Here's something that somewhat confuses me. The way my current plugin works, I clear the firstTime flag as soon as I enter the "if (firstTime)" section, then calculate the average color and write it to the global variable. If more than one thread is running, it seems that it would be reasonably likely that between the time the flag is cleared and the time the average is computed (which is a fairly significant amount of computation), the second thread would start to run, see that the flag is clear, and use the uninitialized version of the average color. Yet I've never seen evidence of that happening.

In any case, I'll probably change the code to clear the flag after the average color has been calculated.

I'm glad the lock works for multiprocessors and multi-cores. I don't really understand understand how multiprocessors and multi-cores work. It seems like the instruction pipelines and the memory caches would result in huge headaches in implementing synchronization between processors that are modifying the same memory. I'm glad someone else has to worry about that, and not me.

Share this post


Link to post
Share on other sites

Hi MJW, good question. I thought of a few possibilities that might explain why you don't see errors, and decided to test them by modifying your plug-in. I tried to give other threads a chance to interrupt the first thread after it had entered the critical section and cleared the flag, by adding Thread.Sleep and Thread.SpinWait statements. Results:

2ih2ovk.png

I conclude that it's normally OK because the average calculation in the first call is fast enough to finish before other calls start writing stuff out. The underlying race condition might be an issue for plug-ins with longer-running calculations. In particular, the calculation in phrebh's code will probably take longer, so the artifacts he's seeing may very well be attributable to this.

(edit: long discussion of bug in test)

Share this post


Link to post
Share on other sites

Thanks Neil. I hate to ask you to do more, but I'd very much appreciate it if you'd move the line that clears the firstTime flag so it's after the loop that computes the average color, and then try your "sleep" test again. I think that's a simple fix for the problem, but since even with the sleep the problem doesn't occur on my single-processor system, I can't test it myself.

----

As a note to phrebh on color averaging, if you want to use a different method to compute the average, you should think of some simple situations and what result you want for the average. For example, if you have a selection that's one third (fully saturated) red, one third green, and one third blue, what do you want the average color to be? If you try an average based on HSV, then the average S and V will both be 1, which presents a problem in choosing a sensible average H. I tend to think whatever average is used should be based on some physical model. I'll again point out that in any space that results from a linear transformation of RGB, the result will be the same as simply averaging the RGB values. Also, if you have a transformation like C = 1 - R, M = 1 - G, Y = 1 - B then even though it isn't a linear transformation of RGB, the average computed in this space then transformed back into RGB space will still be the same as the average of the RGB values. That's because you can consider it a linear transformation of (a, r, g, B) space into (a, c, m, y) space with a = 1. I mention this because it corresponds to the idea of each pixel as a mixture of C, M, and Y colored paint, and the average being the result of mixing the paint in the selection together. (In case anyone is wondering, if you define CMYK space by C = max(RBG) - R, M = max(RGB) - G, Y = max(RGB) - B, K = 1 - max(RGB), then the average computed in this space and transformed back to RGB is also just the average RGB value.)

Share this post


Link to post
Share on other sites

No problem MJW! I can tell you what will happen if it's moved to the end: the race will always finish in the correct order, with the first call to Render computing the average before any other calls reach the output step, and the artifacts will never appear. But multiple threads will always enter the critical section, resulting in unnecessary computation.

By "always", I really mean "almost always". Even when the flag-clearing line is the first or last line in the critical section, there's technically still some tiny chance of another thread becoming active at the wrong time, which can lead to unnecessary computation or a race (respectively). I mean it's not like anyone's writing Paint.NET plug-ins that fly airplanes or anything. But making sure that everything is thread-safe is a good habit.

I hope all this is useful to you phrebh... it's definitely related to the problems you're having!

Share this post


Link to post
Share on other sites

Thank you very much, Neil. While I agree that it seems like moving the flag setting would almost always result in extra computation for multiple threads, I'm not sure it actually would. As I understand it, even on multiple processors the problem currently occurs only when an artificial delay is introduced into the average-computation section. If that's true, then the average color is normally computed and saved by the first thread before the other threads reach the firstTime test. The cases where it would do redundant computations if setting the flag is moved would, I believe, be almost the same as the cases where it currently produces incorrect results.

In any case, I intend to modify the plugin, since a few wasted CPU cycles (especially if done in parallel) is a small price to pay for producing the correct result.

Share this post


Link to post
Share on other sites

I wrote a test earlier, and did observe multiple entries to the critical section with certain selections (specifically short and wide ones). You could just modify the plug-in to lock the critical section and thereby avoid both problems. I can update this post with the modifications if you want, it was a four-line change. Might be helpful to phrebh too, because your code is perfect if we assume there's only one thread.

Share this post


Link to post
Share on other sites

I'll have to think about the best way to solve the problem. Normally I tend to use the most straight-forward approach unless there's a compelling reason to do something more complicated. Even though in the current case I'm not convinced that just changing where the firstTime flag is cleared isn't an entirely adequate solution, I'll probably use the more proper locking approach anyway. I assume the code is:

if (firstTime)
{
  lock (myLock)
  {
      if (firstTime)
      {
          // Compute average color
          ...

          firstTime = false;
      }
  }
}

(I intend to eventually follow BoltBait's suggestion and write plugins outside of CodeLab. I can then take advantage of the OnRender function to compute the average.)

Share this post


Link to post
Share on other sites

The following ... (which is isomorphic to what you just posted)

if (flag)
{
   lock (sync)
   {
       if (flag)
       {
           // computation ... store/cache result
           flag = false;
       }
   }
}

use computation;

... is a standard pattern. Another variation that is subtly different is,

lock (sync)
{
   if (flag)
   {
       // computation ... store/cache result
       flag = false;
   }
}

use computation;

The second one ensures that the computation is only ever performed once, and is required if the computation has any side effects (e.g., file accesses, etc.), or if reference identity is important (e.g. you are constructing a cache or dictionary or something). The first one allows most work items to complete without having to take a lock (assuming the # of work items is "larger enough" than the # of threads). However, when the work items first start out it's possible that the computation will be performed up to N times, where N is the # of threads being used. This results in higher CPU usage, but probably not an increase in "proper time" to complete execution (your stopwatch won't know any difference). Lower battery life is thus the real penalty there, but for this application it probably won't be an issue.

The first pattern will probably give better performance in Paint.NET, since the first rendering slice is run -- by itself -- before the remaining slices*. Therefore only that first work item has to take a lock (a simple "lock(object){}" in .NET is cheap, although not free). However, I doubt you'll see any difference between the two since the total # of work items doesn't really get large until you have at least 8 threads.

* This is not guaranteed to be true in the next version of Paint.NET. It is a performance optimization hint, not a correctness axiom.

Share this post


Link to post
Share on other sites

Hi, Rick. Thanks for writing. Just wanted to clear up a misconception regarding code segment 1: "However, when the work items first start out it's possible that the computation will be performed up to N times, where N is the # of threads being used."

If the flag is not set, as many as N threads may queue up to enter the monitor. They will enter in turn. The first thread to enter the monitor will always compute the result and clear the flag before leaving *. After this, any threads that enter the monitor will immediately exit without performing the computation, because the flag has already been cleared *. So the inner if-statement prevents the second computation, and the outer one is just an optimization to avoid unnecessary acquisition of the lock.

* Obviously these statements are not true if one admits break, goto, return, computations that don't terminate, tampering with the lock or flag, probably many other things.

Thanks for mentioning that the first slice is run by itself! It's quite helpful to know. In some cases I observe two threads entering MJW's critical section on my dual-core machine, which I can't seem to explain. This only occurs for wide, short regions.

Share this post


Link to post
Share on other sites

Knowing that the first slice is run separately certainly helps answer the question I had about why I never saw evidence of the problem, even when I thought I should have.

Share this post


Link to post
Share on other sites

Strange discovery: There's a subtle synchronization problem with the code that I recommended above! This particular pattern is apparently quite unpredictable across different platforms, some call it double-checked locking, there's quite a bit of reading material out there.

Synopsis: The problem is not that the computation can occur more than once - rather, it's that it might not finish on time. An out-of-order processor may reorder the writes in the inner if-block in a way that does not violate causal consistency, but which allows the flag to be cleared before the results of the computation are visible to other processors. Another concurrent thread may see the cleared flag and skip the critical section. That thread may then make use of the incomplete results.

There are a few ways to solve this. One is to use Rick's recommendation, which is thread-safe, but not as fast. The solution that I like best uses a memory barrier. All writes which occur above the memory barrier instruction in the program must be committed to memory before any subsequent writes can proceed. This guarantees that the flag will never be cleared before the result has been computed and written out.

Edit: Code segment removed, because it's probably incorrect. The CLR guarantees that these writes won't be reordered anyways, and the code is potentially susceptible to other problems.

Share this post


Link to post
Share on other sites

Or you can use the volatile keyword.

volatile bool flag = true;

However, this may also have performance implications. Worth trying out though.

I recommend thoroughly reading Joe Duffy's blog, http://www.bluebytesoftware.com/ (weirdly enough it's giving me an error at the moment ... hopefully fixed soon?)[/i]. He's the dev in charge of the .NET parallelism stuff here at Microsoft, and has even written a good book on all this stuff, http://www.amazon.com/Concurrent-Programming-Windows-Joe-Duffy/dp/032143482X/ref=sr_1_1?ie=UTF8&s=books&qid=1256755500&sr=8-1]http://www.amazon.com/Concurrent-Progra' ... 500&sr=8-1 .

A frequent subject that he writes about is the memory model of the system, and reordering with respect to correctness (or not!), and the things you do and do not have to worry about with .NET.

Share this post


Link to post
Share on other sites

Thanks for pointing Joe's blog out, Rick! I read it shortly after you first mentioned it, good stuff. I ran a couple of benchmarks a while ago, as I recall, it seemed that using the volatile keyword was slightly (~5%) faster than using an explicit memory barrier. Both solutions were dramatically faster than single-checked locking (by roughly a factor of six).

There was some discussion a while ago about averaging hue values. The average of 1° and 359° should intuitively be 0°, or equivalently 360°, but a naive average calculation (summing the hues and dividing by n) returns 180°... an entirely different color altogether. I came across a nice solution while working on my own effect, and thought that I'd put together some code to share with everyone. I didn't test it much, so use at your own risk.

Hidden Content:
[reason]Code[/reason]
using System;

namespace meanOfAngles
{
   class Program
   {
       // @pre: angles are inside the interval [0, 360) and are in units of degrees
       static double meanOfAngles(double[] angles)
       {
           // Number of angles included in the average.
           int n = angles.Length;

           double sumOfCosines = 0.0;
           double sumOfSines = 0.0;

           for (int i = 0; i < n; i++)
           {
               // Convert the current angle into radians.
               double currentAngleInRadians = Deg2Rad(angles[i]);

               sumOfCosines += Math.Cos(currentAngleInRadians);
               sumOfSines += Math.Sin(currentAngleInRadians);
           }

           // Find the coordinates of the centroid (basically, a 2-dimensional mean).
           double meanOfCosines = sumOfCosines / n;
           double meanOfSines = sumOfSines / n;

           // Use the atan2 function to find the corresponding angle.
           double meanAngleInRadians = Math.Atan2(meanOfSines, meanOfCosines);

           // Atan2 returns results in (-π, π], so move {x:x<0} to reshape into [0, 2π).
           if (meanAngleInRadians < 0.0)
               meanAngleInRadians = 2 * Math.PI + meanAngleInRadians;

           // Convert angle back to degrees and return.
           return Rad2Deg(meanAngleInRadians);
       }

       static double Deg2Rad(double valueInDegrees)
       {
           return valueInDegrees * Math.PI / 180;
       }

       static double Rad2Deg(double valueInRadians)
       {
           return valueInRadians * 180 / Math.PI;
       }

       static void Main(string[] args)
       {
           double[] angles = { 127.0, 231.0, 281.0, 281.0, 281.0, 308.0, 0.0 };

           Console.WriteLine("Average hue is: " + meanOfAngles(angles));
           Console.ReadLine();
       }
   }
}

It's not exactly the same thing as the normal arithmetic mean, in that it minimizes a slightly different measure of dispersion. But it does the trick!

phrebh, if you're interested in finishing this effect I'd be glad to leave it up to you, but I essentially have working code that averages the HSL color of a selection as a byproduct of an effect I'm working on, so I'll publish it in a couple of days if I don't hear anything since you haven't been online for a month, I've published it (see link in sig). With credit to you for the great idea, of course!

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this