morzel.net

.net, js, html, arduino, java... no rants or clickbaits.

Why the use of GetPixel and SetPixel is so inefficient!

Bitmap class provides two simple methods: GetPixel and SetPixel used respectively to retrieve a point of image (as the Color structure) and set a point of image. The following code illustrates how to retrieve/set all the pixels in the bitmap:

private void GetSetPixel(Bitmap image) {
   for (int x = 0; x < image.Width; x++) {
      for (int y = 0; y < image.Height; y++) {
         Color pixel = image.GetPixel(x, y);
         image.SetPixel(x, y, Color.Black);
      }
   } 
}

As shown, review and modification of pixels is extremely simple. Unfortunately behind the simplicity of the code lies a serious performance trap. While for a small number of references to image points, the speed at which GetPixel and SetPixel work is good enough, for larger images it is not the case. Graph presented below can serve as a proof of that. It shows results of 10 tests* which consisted of 10-fold invocation of previously shown GetSetPixel method for images 100x100 and 1000x1000 pixels in size.

Wyniki testów prędkości operacji na pikselach obrazu z użyciem metod GetPixel i SetPixel klasy Bitmap.

The average test time for an image measuring 100 by 100 pixels was 543 milliseconds. This speed is acceptable if the image processing is not done frequently. Performance problem is, however, clearly visible when you try to use an image of size 1000 per 1000 pixels. Execution of the test in this case takes an average of more than 41 seconds - more than 4 sec. on a single call to GetSetPixel (seriously!).

Why so slow?

Low efficiency is due to the fact that access to the pixel is not a simple reference to a memory area. Each getting or setting of color is associated with invocation of .NET Framework method, which is a wrapper for native function contained in gdiplus.dll. This call is through the mechanism of P/Invoke (Platform Invocation), which is used to communicate from managed code to unmanaged API (API outside of the .NET Framework). So for a bitmap of 1000x1000 pixels there will be 1 million calls to GetPixel method that besides the validation of parameters uses the native GdipBitmapGetPixel function. Before returning color information, GDI+ function has to perform such operations as calculating the position of bytes responsible for description of desired pixel… Similar situation occurs in the case SetPixel method.

Look at the following code of Bitmap.GetPixel method obtained with the .NET Reflector (System.Drawing.dll, .NET Framework 2.0):

public Color GetPixel(int x, int y) {
   int argb = 0;
   if ((x < 0) || (x >= base.Width)) {
      throw new ArgumentOutOfRangeException(“x”, SR.GetString(“ValidRangeX”));
   }
   if ((y < 0) || (y >= base.Height)) {
      throw new ArgumentOutOfRangeException(“y”, SR.GetString(“ValidRangeY”));
   }
   
   int status = SafeNativeMethods.Gdip.GdipBitmapGetPixel(new HandleRef(this, base.nativeImage), x, y, out argb);
   if (status != 0) {
      throw SafeNativeMethods.Gdip.StatusException(status);
   }
   return Color.FromArgb(argb);
}

Here is import of GDI + function:

[DllImport(“gdiplus.dll”, CharSet=CharSet.Unicode, SetLastError=true, 
ExactSpelling=true)]
internal static extern int GdipBitmapGetPixel(HandleRef bitmap, int x, int y, out int argb);

* I have tested on such laptop: HP Pavilion dv5, AMD Turion X2 Dual-Core Mobile RM-70, 3 GB RAM, Vista Home Premium

Why strings are immutable and what are the implications of it?

String type (System.String) stores text values as a sequence of char (System.Char) elements that represent Unicode characters (encoded in UTF-16). Usually one char element stands for one symbol.

When working with text one has to remember that strings in .NET are immutable! This simply means that once created, strings cannot be modified (without reflection or unsafe code), and the methods that apparently modify a string, really return a new object with the desired value.

Immutability of strings has many advantages (more about it soon), but it can cause problems if programmer forgets that any "change" to the string actually causes creation of a new instance of String class. Although the CLR treats strings in a special way, they are still a reference type, for which the memory is allocated on the managed heap.

Operation of this loop will create 10 000 string variables, all of which except the last are trash that will need to be collected by Garbage Collector:

string s = string.Empty;

for (int i = 0; i < 10000; i++)
{
    s += "x";
}

The following picture shows part of the "Histogram by Size for Allocated Objects" window from CLR Profiler application. You can see how subsequent iterations caused heap allocations for ever larger strings.

To avoid creating many unwanted objects use StringBuilder class, which allows you to modify the text without making new String class instances.

StringBuilder sb = new StringBuilder();

for (int i = 0; i < 10000; i++)
{
    sb.Append("x");
}

string x = sb.ToString();

This simple change has a huge impact on the amount of allocated and freed memory. See the following comparison of fragments of Profiler’s “Summary” window:

Why do designers of .NET (just like the creators of Java) decided to implement immutable text strings?

For optimization reasons (mainly because of comparison speed), texts can be stored in a special table (intern pool) maintained by the CLR. The idea is to avoid creating a number of variables defining the same string. Below is a piece of code proving that variables that have the same string value can point to the same* object:

string a = "xx";
string b = "xx";
string c = "x";
string d = String.Intern(c + c);

Console.WriteLine((object)a == (object)b); // True
Console.WriteLine((object)a == (object)d); // True

If the strings were modifiable, change to the value of variable a, would also change the value of b and d.

Immutability of strings has positive significance in multithreaded applications – any text amendment causes creation of a new variable so there is no need to set up the lock to avoid conflicts while multiple threads simultaneously access text. This is really important because quite often authorization of some operations is based on particular string value (for example, you can block specific functionality of a service based on client’s address).

Another important reason for immutability is the widespread use of strings as keys in hash tables. Would calculation of position of the element in table make any sense if it would be possible to modify the value of a key? The following listing shows that the "change" to variable used as the key does not affect the operation of the hash table:

string key = "abc";
Hashtable ht = new Hashtable();
ht.Add(key, 123);

key = "xbc";

Console.WriteLine(key); // xbc
Console.WriteLine(ht["abc"]); // 123

What would happen in the case of modifiable strings can be seen through a block of code that uses unsafe mode to actually change the string used as key:

unsafe
{
    string key = "abc";
    Hashtable ht = new Hashtable();
    ht.Add(key, 123);

    fixed (char* p = key)
    {
        p[0] = 'x';
    }

    Console.WriteLine(key); // xbc
    Console.WriteLine(ht["abc"]); // Not found!
}

Immutability is also related to the fact that the string is stored internally as an array - the data structure representing a continuous address space (which for performance reasons does not support insert operation).

* Whether a text literal is automatically added to the pool may be dependent on the use of ngen.exe tool or CompilationRelaxations settings...