DEV Community: Henrique Ferreira

Memory management in C# - Part 2: analyzing

Henrique Ferreira — Wed, 04 Oct 2023 21:09:02 +0000

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 :)

Memory management in C# - Part 1: why we should care

Henrique Ferreira — Wed, 20 Sep 2023 15:59:57 +0000

One could argue that as software programmers our main goal is to efficiently manage hardware resources.

There are many of those, like network cards, hard drive disks, SSDs, I/O devices, telemetry devices, and arguably by far most commonly CPUs and RAM modules (notice the different abstraction layers in those examples).

So this time let’s talk about RAM modules. And C#.

Please notice this article greatly simplifies the contents. If you want to expand on the knowledge, please use the references at the end. There are too many great books on the subject by people much more knowledgeable than me :-)

“Wait, but isn’t it all abstracted away from us, as application developers?” Yes, and here’s why we should still care.

Where’s my memory? (a recap)

There are lots of interesting online explanations on Heap vs. Stack memory, especially theoretical and introductory. But how and when should we actually choose to use them?

Naturally, we are constrained to the Stack. When executing a program, the OS uses a stack implementation. Nothing too fancy, it’s literally (with some simplification) a stack of function calls (i.e. the Call Stack), internally implemented as a contiguous array of so-called stack frames.

Every language has a calling convention which specifies what goes into this stack (i.e. what is a stack frame). Generally, data is included regarding

Return addresses, for actually JUMPing between function calls
Parameter data
Some space for return values
Scoped variables

For our purposes, let’s leave other implementation details to the C# language specification, and the lower level stuff for the OS and the likes of Intel and AMD and their Instruction Set Architectures

From another perspective, the Call Stack tracks where the program is in terms of execution. It has to be a stack basically due to the efficiency of pushing and popping functions in it, which is exactly how a program executes in the first place!

And there it is, your parameter and variable memory is in “the Stack”. When the function returns, it finishes execution and gets popped from the stack, meaning the memory is automatically free’d up.

Since C# is a general purpose programming language, we could arguably write any solution with Stack memory only 👀 It’s fast, easy to write, and there’s no need for explicit memory management (the GC will end up managing it as well, but we’ll discuss this in the next sections). Here are some good use cases:

Recursive functions
Procedural programming
Functional programming

Of course, it is limited. The C# (.NET) stack size for 32bit architectures defaults to 1MB per Thread, which is a lot for most applications - we can go tens of thousands of levels deep for simple recursive functions. If you exceed it, be prepared for an infamous StackOverflow exception (that said please don't be afraid of recursive code).

The other problem is scope, meaning we’d have to pass down local variables as parameters all the way through the code execution, which would make complex code less readable and a nightmare to maintain.

Should it be all “new”?

But don’t panic! (and make sure to bring your towel). We still have the Heap. As with the Stack, it also resides within RAM. But it's a different data structure, for a different kind of access.

A heap can be implemented just as well from a simple array. The rules are different though, since it is a tree-like structure that allows for some optimized read access at the cost of more complex writes. So yes, it is slower than the Stack (it can even end up with some fragmentation). So why use it? It's virtually limitless! We can easily throw data at it, and we get the reference to where that data is.

As opposed to a value which holds the value itself (int x = 2), a reference is a pointer which holds an address to where the value is dynamically allocated (var x = new string[10]). The address size can vary, but on an 32-bit machine, they are usually 4 bytes long (pointing to anything in the Heap, including functions!). The difference is commonly abstracted away from the programmer in C#, so it is a good idea to have the C# Value type docs and the C# reference types docs close in case of doubts.

So how do we use the heap in C#? The short, over-simplified and slightly off answer is with the new keyword (or instantiations). The complete answer is:

A reference type is allocated on the heap
A value type is created where the scope is: if it's a field in a class, along in the heap. If it's a local variable in a method, most likely on the stack (notice C# has tons of features and there are more complex scenarios, for lambda expressions there have shared scopes for example)

The above list is short and ambiguous on purpose. The language specification makes no guarantees on what goes where, and the compiler will ultimately and optimally decide.

To another extent, the C# heap is a global Managed Heap. That also means there is a runtime data structure running along with our code: the Garbage Collector.

So my code is produces Garbage?

Jokes apart, the Garbage Collector (GC) doesn't mean to offend us. It is responsible for effectively managing the C# memory (Heap and Stack), and can be our best friend when used correctly.

To reiterate, the GC runs with our code and goes reclaiming dead objects (pieces of memory we're not using). Hence we don’t need to explicitly free memory, which is a great and dangerous power. Most content out there will tell you to leave it all to the GC, since it knows better.

If you’ve gone this far though, you’re like me and is not particularly happy with having some data structure we can’t control taking care of so much of our program. So like Morpheus, I’m hereby admittedly inviting you to take the red pill with me.

Collecting the garbage

Remember the reference type from the previous sections? Let’s assume the OOP nature of C# and start calling it “object” (it has to be an object anyways given how an OOP compiler makes Semantic Analysis).

In a “managed” language like C#, objects have lifetimes: a short-lived object has been allocated recently and is likely closed related to others also just allocated, while a long-lived is older and maybe less related.

For completeness sake, the GC also differentiates between Large Objects (85,000 bytes and larger) and regular ones, with a separate heap for each type

The criteria to define an object lifespan is based on so-called GC generations. There are three of them:

Gen 0: consists of youngest objects, like a recently allocated temporary variable. It’s the cheapest to manage, being the first option to free space for new allocations and also where GC collections are more frequent. All new objects implicitly go to Gen 0, except Large Objects, which go straight to Gen 3. We like Gen 0
Gen 1: literally the mid way of object lifetimes, in between short and long-lived objects. After the Gen 0 collection, the memory is compacted and objects - like collections, for example - are promoted to Gen 1. Gen 1 is not checked every time for collection, only when the Gen 0 collection couldn’t feee up enough space for newer allocations. We have mixed feelings for Gen 1.
Gen 2: long-lives objects, usually alive for the duration of a process (like Singletons, for example). Surviving a Gen 2 collection (i.e. a full collection) means sticking around until the memory is determined unreachable. We’re not fans of Gen 2, but it’s serves its purpose
Gen 3: is just a nickname space for Large Objects only

Objects can survive collections, being promoted from Gen 0 to Gen 1 and Gen 1 to Gen 2. In simples terms, the GC will try to find the sweet spot between not getting too intrusive in collections and not letting the memory become too big.

GC - Ghost Component

What we’ll discuss now may seem like a lot of developer work for a GC that automatically sorts out the memory usage. It isn’t. The thing is the GC makes thread pauses (for ephemeral collections - Gen 0 and Gen 1 - lasting a couple of milliseconds) to actually cleanup the memory. In general, what we want is to make these pauses less frequent and faster. Most of the real challenge goes to understanding how have we implemented the solution - how we have used the memory.

So you may have heard about “problems with the GC” or “memory leaks in C#”. These are usually due to Gen 2 objects that are hanged around or maybe a concentration of Large Objects.

Some objects interact with “out-of-process” resources (i.e. unmanaged resources), like disk I/O, and network connections (and any other general OS resources). When that happens, explicit cleanup becomes necessary (after all we wouldn’t want the GC to step in and shut down a network port, and it wouldn’t know if the port is being used anyways).

With regards to such unmanaged resources, a case-by-case analysis is necessary. For the GC to be able to collect them, we should implement the IDisposable.Dispose method. We should also consider using destructors, or in C# terms, the Object.Finalize method in case there’s a chance of Dispose not being called by a developer.

Finally, if you make too many allocations, you may get a nasty OutOfMemory exception. That ultimately means the OS was not able to provide addressable space for allocations. In such a case, remember: the .NET CLR, .exe and other .dll modules are sharing the memory with your application.

Analyzing and profiling

In the next parts, we’ll actually analyze and profile a C# program in practice. Then, we’ll discuss tools, trade-offs and myths in terms of memory management. See you there!

PS.: Please leave your comments and feedback. This very condensed article should be used as a general discussion and not a static reference. Let me know if I should expand on any of the content :)