Memory management in C# - Part 2: analyzing

In Part 1: why we should care, we've revisited some concepts, discussing the theory with a more practical point of view. In this Part 2, we'll focus on getting our hands dirty (with some theory to back us up, I'm afraid) to actually profile and understand the C# memory usage in practice.

The tooling

There are many free and paid tools to statically analyze a code base, profile it's memory, CPU usage, code coverage, assembly generation, and many more Software Engineering metrics. They'll maybe generate graphs and charts, and overall many numbers as results.

Quantitative and qualitative analysis is a complex subject that goes beyond Software Engineering. In summary, none of the numbers should matter, not more than the meaning behind them. Also, although paid tools may be more complete, there's already a lot of value to be gained with the free tools, which is what we'll use, of course (as I'm poor).

The basis of our discussion is that lot of the memory a program uses is due to the applied solution. Being a popular OOP language, C# commercial programs will usually consist of the use of a framework (such as .NET's CLR - like the open sourced .NET Core or the at least very well referenced .NET Framework), third party libraries (at the moment, there are over 370k of them in Nuget.org only) and our own code, with its .dlls. From any of these places, we should know that human beings - smart, but prone to failures - made decisions on how algorithms and data structures should behave in OOP to solve particular issues.

The real (but theoretical) analysis

Therefore the first tool we should use is our ability to understand the said human decisions by looking at the code. And a very big part of it is with algorithms and data structures analysis. It follows that the most comprehensive strategy (obviously it can be used for any programming language) relies on asymptotic computational complexity. Although the terminology is fancy, we can easily bring it to some triviality - the question one wants to answer in terms of engineering by looking at code is: what does this cost (in the worst case scenario)?

The cost is usually measured in CPU time and memory consumption. Luckily for us, we don’t need to know every CPU clock rate out there (not even the compiled instructions 😀) and it’s also dispensable to know the RAM memory chip’s hardware speed. We use a slightly different RAM, the Random Access Model.

The rules are quite straightforward: any simple operation (+, -, =, /, *, if) takes one “step”. That’s how much it costs. It takes some constant time to execute each step. Yes, it sounds a little arbitrary but will be useful in the next paragraphs.

Any loops and subroutines are made of simple operations. So if we have something like

int x = 5; // 1 step
int a = x + 3; // 1 step

This costs 2 steps. And if we have

// aList is a List<int>() previously allocated
int sum = 0; // 1 step
int n = aList.Count; // 1 step
for (int i = 0 ; i < n; i++) // n steps
{
  sum += aList[i]; // 1 step
}

This costs

$$2 + n * 1$$

Not very exciting so far. Last example:

// n, m, and o are integers representing lengths of arrays
// a3dmatrix is, well, a 3d matrix
int x = 0; // 1 step
int y = 0; // 1 step
int z = 0; // 1 step
int sum = 0; // 1 step

for (int i = 0 ; i < n; i++) // n steps
{
  for (int j = 0 ; j < m; j++) // m steps
  {
    for (int k = 0 ; k < o; k++) // o steps
    {
      sum += a3dmatrix[i][j][k]; // 1 step
    }
  }
}

In this case, the cost is

$$4 + n * m * o * 1$$

Notice the algebraic nature of our analysis. We essentially have functions on the number of steps (i.e. the size of the input). The practical discussion on complexity then boils down to what’s the worst case scenario for an algorithmic implementation. In other words, given two (or more) options, we want to choose the one whose worst case is the lesser.

There also exists best case and average case scenarios, though they are usually not practically as important.

This type of analysis also has its own mathematical notation, known popularly as Big-O notation, where O means “an order of magnitude”. So the previous complexity is of O(n * m * o). Notice we’ve left out the constants and kept only the variables. The intuition is that variable input sizes are the relevant components in complexity analysis, because what is made of only constant steps can all be considered to run in a constant time.

Sounds philosophical? It is! Mathematically speaking, the reasoning is of finding a function

$$f(x)$$

which, given some constant

$$C$$

, is always smaller than or equal to another function

$$g(x) * C$$

for any

$$x ≥ x_0$$

Where this gets interesting is with recursive algorithms and intelligent data structures, in which the time taken can be manipulated by clever use of the stack and heap memories.

Again, that’s not specific to C#. One might also argue that their code does not extensively use recursive functions or clever algorithms and data structures. Myth busted! 😝

• The .NET CLR uses these complex data structures and algorithms (it even calls some OS libraries, which also use them, not to mention disk I/O in some cases)
• 3rd party libraries are definitely often solving complex issues with these strategies
• External resources, like drivers, databases and cloud services are all using the same theoretical premises
• The real value of a software solution is arguably how clever the underlying algorithm or heuristic is

So, effectively, are we

• Using databases? Ever wondered why that query on Entity Framework takes so long? The JOIN SQL clause is likely an O(

  $$n^2$$
  ) algorithm! But that index is a B-tree implementation with logarithmic complexity!

• Using cloud services? Distributed algorithms will run everywhere, with loads of different heuristics, like leader election in replication or distance vector in between networking calls!

• The GC has many implementations on heap collection strategy, like table based compaction, which runs in O(n * log(n)) time, where n is the number of live objects.

These implementation details often get masked behind OOP, as that’s how it’s supposed to be. However, we should still not forget that procedural programming is where the solution eventually is. And that’s basically why asymptotic complexity analysis is so useful.

Finally, notice there is a direct relationship between the memory consumed by an algorithm and the time it takes to compute. Wether we look at stack (like general recursiveness) or heap memory (like C# Arrays, Lists, Strings, Sets, Dictionaries, Collections, Concurrent data structures, or Objects in general), it should all optimize the solution complexity, minimizing its time cost. In other words, the memory cost should be justified by reductions in the time cost. A non-extensive list of examples:

• Multiple searches in collections could benefit from applying some ordering to them (we can implement the IComparable interface and sort the collection)
• Loops should avoid allocating unnecessary objects, like

for (int i = 0; i < n; i++)
{
  var x = new TextExtractor(); // is it necessary to instantiate this object every iteration?
  var y = SomeMethod(); // is SomeMethod re-allocating memory?
}

• Disposable objects should be disposed with using statements or explicitly calling the Dispose method.
• Exceptions should be treated as scenarios in which the program would crash, but should likely continue normal execution (not as part of regular processing)
• Both regular and unsafe memory (HttpClients, API packages - like AWS clients, DbConnections, FileStreams) should be carefully used considering their lifecycle (one object per request, per application, per scope…)
• Rendering frameworks (UI) also should be used as per their lifecycle (WPF, React, Vue, WinForms, and the other hundreds). One useful analysis is with remembering there will commonly be a virtual visual element tree, which will eventually be traversed with an mounting algorithm (usually a variation of DFS or BFS)

All of those examples are justified by the memory-time efficiency trade-off. In those cases and infinitely more, asymptotic computational complexity will explain what are the hot paths, the internal algorithm’s decision and how to better utilize it.

If it seems like too many cases, don’t panic (towel!) Practice makes perfect and cases like the above will become nearly trivial with some time. The idea here is just that we must remember that algorithmic decisions have been made throughout our code base, and the memory we use is heavily affected by them.

Thank you for reading so far! In the next (and I think, final) part we'll get hands-on on profiling memory in a dotnet app :)