Speeding up the algorithm with List <T> .Sort and IEnumerable

Question

For my project, I first load the image from the file and put each pixel in a 2D pixels[,] array. Then I want to examine each pixel and divide them into “bins” based on how they are colored, and then sort each bit. So I have a Bin object that encapsulates a List<Pixel> , and I have a List<Bin> containing a (relatively small) number of boxes.

My problem is that when I try to fill these bins from very large images (1920x1200 = 2.3 million pixels, for example), the algorithm I use is slower than I would like, and I traced the problem to some of the C language features # which seem to take longer than I expected. I would like some tips on how best to use C # to eliminate these bottlenecks.

After loading the image, I call the function "fillBinsFromSource", which takes an enumerated list of pixels, finds in which box they are located, and puts them there:

 public void fillBinsFromSource(IEnumerable<Pixel> source) { Stopwatch s = new Stopwatch(); foreach (Pixel p in source) { s.Start(); // algorithm removed for brevity // involves a binary search of all Bins and a List.Add call s.Stop(); } } 

For large images, it was expected that my algorithm would take some time, but when I put the stopwatch outside the function call, it turns out that it takes about two times the time typed on s , which means that enumeration using foreach takes half the time of this function ( about 800 ms 1.6 seconds for an image of 1920 × 1200).

The reason I need to list is because sometimes users will add only a small area of ​​the image, not the whole image. A time-consuming call skips several iterators, first from the list of images, then from each image in the list, also (simplified):

 class ImageList : IEnumerable<Pixel> { private List<Image> imageList; public IEnumerator<Pixel> GetEnumerator() { foreach (Image i in imageList) foreach (Pixel p in i) yield return p; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } class Image : IEnumerable<Pixel> { private Pixel[,] pixels; // all pixels in the image private List<Pixel> selectedPixels;// all pixels in the user selection public IEnumerator<Pixel> GetEnumerator() { if (selectedPixels == null) for (int i = 0; i < image.Width; i++) for (int j = 0; j < image.Height; j++) yield return pixels[i, j]; else for (int i = 0; i < selectedPixels.Count; i++) yield return selectedPixels[i]; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } 

Then finally I call it

 ImageList list; // pretend it contains only 1 image, and it large fillBinsFromSource(list); 

Question 1) Due to the need to list both the 2D array of pixels and the selected area, depending on what the user has selected, the enumeration is simply very slow. How can I speed this up?

Then, after filling all these beans with Pixel objects, I sort them. I call List<Pixel>.Sort() and rely on IComparable , for example:

 ImageList list; // pretend it contains only 1 image, and it large fillBinsFromSource(list); foreach(Bin b in allBins) b.Sort(); // calls List<Pixel>.Sort() class Pixel : IComparable { // store both HSV and RGB float h, s, v; byte r, g, b; // we sort by HSV value property public int CompareTo(object obj) { // this is much faster than calling CompareTo on a float Pixel rhs = obj as Pixel; if (v < rhs.v) return -1; else if (v > rhs.v) return 1; return 0; } 

Question 2) Let allBins have 7 elements; sorting of 7 separate lists, for which a total of 2.3 million Pixel in them takes about 2 seconds. Sorting a single list of 2.3 million random int takes less than 200 milliseconds. I can appreciate that there is some level of acceleration using primitive types, but is it really 10% slower to use IComparable ? Are there any accelerations you need to have here?

I apologize for the long question, if anyone has any advice for me, I would appreciate it!

Answer 1

You really need to profile your code and see what happens slowly.

The most obvious:

• Pixel does not implement the generic IComparable<Pixel> , and as a result Compare had to do a lot more work.
• Try to create a pixel value type. Most likely, you will see a decrease in performance, but it may not be.
• Consider passing 2d ranges (a rectangle) and accessing Pixel objects directly by index instead of iterators if you find that performance is below what you think is acceptable. Iterators are good, but not free.

Answer 2

All kinds of indirection, such as a visitor pattern or virtual inheritance, are poison if you want to work with raw metal. Virtual calls, distribution, unpredictable branching causes great damage to the algorithm, where there is a small, dense inner loop in which 99.99% of the time is spent.

Why? Because the CPU likes to execute many (tens) of instructions in parallel. He can only do this if he can look ahead into the flow of commands. The above things interfere with this.

You really need to get the innermost loop. Do not select them, do not call virtual functions (or interface methods or delegates).

Perhaps your inner loop should handle the rectangle of the given image with the hard-coded kernel. Instead of implementing your processing function per pixel, implement it on a rectangle.

On the contrary, it does not matter how you provide the image stream. Use LINQ wherever you want. This is a small-volume operation because there are millions of pixels per image.

Answer 3

Instead of using an iterator or even creating an array / list of pixels for starters, you can use a visitor template. Images, image lists, and other objects representing arbitrary samples can receive a class of visitors using the single VisitPixel method and call this method for each pixel that represents the object. Then the visitor class will be responsible for combining all the pixels as they visit.

This may eliminate the need to extract all your pixels in a separate array. It may also preclude the creation of iterators in favor of simple for loops.

Alexey Levenkov has some good points regarding your second question. It might be even faster to use a Sort overload that accepts an instance of IComparer<T> .