Extreme Optimization > Resources > Current Page > Techniques of Extreme Optimization

Extreme Optimization Resources

Understand the problem

It is said that asking the right question brings you halfway to the solution. Understanding the essence of what your software is meant to do will provide you with plenty of ideas on how to get the job done effectively. Conversely, a lack of understanding can easily lead to inefficiency and chaos.

In the most general terms, the goal of programming is to transform inputs into certain outputs. The act of programming is to specify this process of transformation in great detail.

Understanding a problem means we have built a model in our mind of how this process of transformation works. The more thorough our understanding is, the more specific our model will be. We can then exploit our knowledge of the components of our model to streamline the process.

Know your tools

Thorough knowledge about the internals of the environment you are working in is essential to extreme optimization. Elegant code can hide complicated operations that slow down your code considerably.

Let's look at an example in the .NET framework.

Strings are unchangeable

Strings in the .NET framework can not change their value. As a result, operations that appear to modify a string in fact create a new string. Look at this piece of code. Its purpose is to reverse the characters in a String.

public String Reverse(String original)
{
String reverse = String.Empty;
for (Int32 index = original.Length-1;
index >= 0; index--)
reverse += original[index];
return reverse;
}

In each iteration, the following steps are performed:

1. A new String object is created, with length equal to s.Length+1.
2. The current value of reverse is copied to the new string.
3. The character at the current index is copied to the new string.
4. The reverse variable is set to reference the new string.

This means that, to reverse a string of 1,000 characters, 1,000 temporary objects will be created and a total of roughly 1,000,000 bytes will be copied in memory. A 10,000 character string requires 10,000 temporary objects and roughly 100 MB to be copied. This is an unreasonable amount of copying. The longer the string, the worse things get.

To remedy this situation, Microsoft provides the StringBuilder class. A StringBuilder object acts like a changeable string. A new object is not created when the contents of the string are changed. When construction of the string is complete, the ToString() method converts it to a normal unchangeable String.

The new implementation, using a StringBuilder object, looks as follows:

public String Reverse(String original)
{
System.Text.StringBuilder sb
= new System.Text.StringBuilder(original.Length);
for (Int32 index = original.Length-1; index > = 0; index--)
sb.Append(original[index]);
return sb.ToString();
}

Because of the way the StringBuilder class works internally, no in-memory copying is done at all.

Use optimized class library functions

The .NET Framework class library is made up of thousands of functions. Most of these have been optimized to a great degree. In many cases, the Microsoft development team was able to use optimizations internal to the framework. If there is a class or function in the library that has the specific functionality you need, there is a good chance it will work at least as fast as any managed code you may write.

As an example, we can take a further look at the Reverse function we developed earlier. Its purpose is to return a String with the characters in reverse order. We came up with a technique using the StringBuilder class that is a dramatic improvement over the naive algorithm.

It may come as somewhat of a surprise that the String class doesn't have a Reverse method. After all, a similar function is part of both the standard C library and the Visual Basic language. However, the Array class does have this method. It is a static (class level) method that reverses the elements of an array in place. Together with optimized methods for converting between arrays of characters and strings, we can use it to reverse strings as well:

public String Reverse(String original)
{
Char[] characters = original.ToCharArray();
Array.Reverse(characters);
return new String(characters);
}

As it turns out, this function is about five times faster than our previous method.

Delegate to the compiler

A resource that is sometimes overlooked in optimization is the developer. The .NET compilers do a pretty good job of optimizing most common programming constructs.

Keep in mind also that compiling in the .NET work is a two-step process. Your source code is first compiled into Intermediate Language (IL). IL is similar to Java byte code: a processor independent machine language. The first time your code is executed the JIT compiler translates the IL stored in the executable into native machine instructions. Optimizations take place on both levels, and some of the techniques are pretty advanced.

• Automatic inlining of function calls with at most 32 bytes of IL code.
• Special treatment for some classes, including: Array classes, String and StringBuilder.
• Range check elimination. Because arrays and strings are unchangeable, the compiler can be certain that the array indices inside a loop will remain within bounds, thereby eliminating the need to verify they are within range.

Copyright 2004-2008, Extreme Optimization. All rights reserved.
Extreme Optimization, Complexity made simple, M#, and M Sharp  are trademarks of ExoAnalytics Inc.
Microsoft, Visual C#, Visual Basic, Visual Studio, Visual Studio.NET, and the Visual Studio Logo are registered trademarks of Microsoft Corporation