This book is primarily concerned with helping you understand the basics of performance from a nuts-and-bolts perspective. It is critical to understand the cost of your building blocks before putting together larger applications. Everything covered so far in this book applies to most .NET application types, including those discussed in this appendix.
This appendix will take a step higher and give you a few brief tips for popular types of applications. I will not cover these topics in nearly as much detail as in the rest of this book, so think of this as a general overview to inspire further research. For the most part, these tips are not related to .NET, per se, but are architecture-, domain-, or library-specific.
<compilation debug="true"/>
).OutputCache
: Caches page output.Cache
: Caches arbitrary objects however you desire.ViewState
to small objects. If you must use it, compress it.Page.DataBind
method.Page.IsPostBack
property to run code that only needs to happen once per page, such as for initialization.Server.Transfer
instead of Response.Redirect
.DataView
objects on top of DataSet
objects rather than re-querying the same information.DataReader
if you can live with a short-lived, forward-only iterator view of the data.StreamGeometry
is faster than PathGeometry
, but supports fewer features.Drawing
objects are faster than Shape
objects, but support fewer features.DependencyProperty
metadata to customize when changing values will cause a re-render.Recompile for Universal Windows Platform, targeting Windows 10 to achieve significant performance improvements for free.
At a layer above direct performance profiling lies algorithmic analysis. This is usually done in terms of abstract operations, relative to the size of the problem. Computer science has a standard way of referring to the cost of algorithms, called “Big O” analysis.
Big O notation, also known as asymptotic notation, is a way of summarizing the performance of algorithms based on problem size. The problem size is usually designated n. The “Big O”-ness of an algorithm is often referred to as its complexity. The term asymptotic is used as it describes the behavior of a function as its input size approaches infinity.
As an example, consider an unsorted array that contains a value we need to search for. Because it is unsorted, we will have to search every element until we find the value we are looking for. If the array is of size n, we will need to search, worst case, n elements. We say, therefore, that this linear search algorithm has a complexity of O(n).
That is the worst case. On average, however, the algorithm will need to look at n/2 elements. We could be more accurate and say the algorithm is, on average, O(n/2), but this is not actually a significant change as far as the growth factor (n) is concerned. Constants are dropped, leaving us with the same O(n) complexity.
Big O notation is expressed in terms of functions of n, where n is the input size, which is determined by the algorithm and the data structure it operates on. For a collection, it could be the number of items in the collection; for a string search algorithm, it is the length of the respective strings.
Big O notation is concerned with how the time required to perform an algorithm grows with ever-larger input sizes. With our array example, we expect that if the array were to double in length, then the time required to search the array would also double. This implies that the algorithm has linear performance characteristics.
An algorithm with complexity of O(n2) would exhibit worse than linear performance. If the input doubles, the time is quadrupled. If problem size increases by a factor of 8, then the time increases by a factor of 64, always squared. This type of algorithm exhibits quadratic complexity. A good example of this is the bubble sort algorithm. (In fact, most naive sorting algorithms have O(n2) complexity.)
private static void BubbleSort(int[] array)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < array.Length; i++)
{
if (array[i - 1] > array[i])
{
int temp = array[i - 1];
array[i - 1] = array[i];
array[i] = temp;
swapped = true;
}
}
} while (swapped);
}
Any time you see nested loops, it is quite likely the algorithm is going to be quadratic or polynomial (if not worse). In bubble sort’s case, the outer loop can run up to n times while the inner loop examines up to n elements on each iteration, therefore the complexity is O(n2).
When analyzing your own algorithms, you may come up with a formula that contains multiple factors, as in O(8n2 + n + C) (a quadratic portion multiplied by 8, a linear portion, and a constant time portion). For the purposes of Big O notation, only the most significant factor is kept and multiplicative constants are ignored. This algorithm would be regarded as O(n2). Remember, too, that Big O notation is concerned with the growth of the time as the problem size approaches infinity. Even though 8n2 is 8 times larger than n2, it is not very relevant compared to the growth of the n2 factor, which far outstrips every other factor for large values of n. Conversely, if n is small, the difference between O(n log n), O(n2), or O(2n) is trivial and uninteresting. Note that, you can have complex significant factors such as O(n22n), and neither component involving n is removed (unless it really is trivial).
Many algorithms have multiple inputs and their complexity can be denoted with multiple variables, e.g., O(mn) or O(m + n). Many graph algorithms, for example, depend on the number of edges and the number of vertices.
The most common types of complexity are:
Algorithmic complexity is usually described in terms of its average and worst-case performance. Best-case performance is not very interesting because, for many algorithms, luck can be involved (e.g., it does not really matter for our analysis that the best-case performance of linear search is O(1) because that means it just happened to get lucky).
The following graph shows how fast time can grow based on problem size. Note that the difference between O(1) and O(log n) is almost indistinguishable even out to relatively large problem sizes. An algorithm with O(n!) complexity is almost unusable with anything but the smallest problem sizes.
Though time is the most common dimension of complexity, space (memory usage) can also be analyzed with the same methodology. For example, most sorting algorithms are O(log n) in time, but are O(n) in space. Few data structures use more space, complexity-wise, than the number of elements in the data structure.
Sorting
Graphs
Searching
Special Case
Often, O(n!) is really just shorthand for “brute force, try every possibility.”