In this article, we will focus on memory allocation optimization using BenchmarkDotNet. We will also learn how to effectively do that using the MemoryDiagnoser attribute while comparing two of the most popular sorting algorithms – QuickSort and MergeSort.
Let’s dive in!
Why Do We Need to Check Memory Allocation?
Memory management is a critical aspect of software development that can significantly impact our applications’ performance, stability, and scalability. One aspect of memory management that requires careful attention is memory allocation. By assessing the frequency and size of memory allocations, we can optimize .NET applications. Memory allocation optimizations can minimize redundant or unnecessary memory usage and allow the application to use available resources more efficiently.
Sometimes, when dealing with large amounts of data we have to sort that data by some criteria. There are multiple options for sorting algorithms, and all have pros and cons. Some can be fast but use a lot of memory, while others might be the opposite. This makes the choice of a proper sorting algorithm crucial.
In this article, we’re going to compare the QuickSort and MergeSort algorithms that we have already covered in previous articles.
Installing and Setting up the BenchmarkDotNet Package
Let’s start by installing the BenchmarkDotnet package:
dotnet add package BenchmarkDotnet
Then, let’s set things up:
public class SortingBenchmark
{
private const int ARRAY_SIZE = 10_000;
private int[] _quickSortArray;
private int[] _mergeSortArray;
[GlobalSetup]
public void Setup()
{
Random random = new Random();
_quickSortArray = new int[ARRAY_SIZE];
_mergeSortArray = new int[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++)
{
int randomNumber = random.Next();
_quickSortArray[i] = randomNumber;
_mergeSortArray[i] = randomNumber;
}
}
[Benchmark]
public void QuickSort()
{
Sort.QuickSort(_quickSortArray, 0, _quickSortArray.Length - 1);
}
[Benchmark]
public void MergeSort()
{
Sort.MergeSort(_mergeSortArray, 0, _mergeSortArray.Length - 1);
}
}
We create the SortingBenchmark class and we will use it to run our benchmarks. Then we declare two arrays – _quickSortArray and _mergeSortArray. We also declare a constant that indicates their size and set it to 10 000. The Setup method initializes the arrays with random integer values using the Random class. It’s important to decorate the method with the GlobalSetup attribute so the program knows to run it before every test.
The class includes two benchmark methods, QuickSort and MergeSort, decorated with the Benchmark attribute. These methods invoke the respective sorting algorithms, passing in the pre-initialized arrays as parameters.
The last thing to do before we can run our benchmarks is to set the program to Release mode and add one line in our Main method:
BenchmarkRunner.Run<SortingBenchmark>();
For a detailed look at how BenchmarkDotNet works, you can check our dedicated article.
Checking Memory Allocation With MemoryDiagnoser Attribute
Let’s run our benchmark as set in the previous section in Release mode:
| Method | Mean | Error | StdDev | |---------- |------------:|---------:|---------:| | QuickSort | 38,072.2 us | 52.77 us | 41.20 us | | MergeSort | 316.1 us | 5.67 us | 5.30 us |
From the result, we can surmise that, despite its name, the QuickSort algorithm is a little over 100 times slower than MergeSort.
Now, if we want to check memory allocation using BenchmarkDotNet, we need to update our code:
[MemoryDiagnoser(false)]
public class SortingBenchmark
{
}
We decorate our SortingBenchmark class with the MemoryDiagnoser attribute, passing false as an argument.
Let’s re-run our benchmark:
| Method | Mean | Error | StdDev | Allocated | |---------- |------------:|----------:|----------:|----------:| | QuickSort | 38,260.2 us | 159.05 us | 140.99 us | 32 B | | MergeSort | 325.1 us | 6.47 us | 10.63 us | 792040 B |
We can now see the Allocated column. It displays the allocated memory per single operation in bytes. The results show that QuickSort is the more memory-efficient option. It allocates only 32 bytes of memory during the sorting process. This minimal memory footprint makes it particularly advantageous when dealing with smaller datasets or situations where memory usage is a critical consideration.
On the other hand, MergeSort utilizes a significantly larger memory allocation – 792 040 bytes. This is because we are recursively creating new arrays in the Merge method. While this may not be a problem for systems with abundant memory resources, it can be a notable factor when memory is limited or needs to be used carefully.
More Detailed Memory Allocation With MemoryDiagnoser Attribute
We can go one step further and pass true to the MemoryDiagnoser attribute:
[MemoryDiagnoser(true)]
public class SortingBenchmark
{
}
This will display a more detailed memory allocation report:
| Method | Mean | Error | StdDev | Gen0 | Allocated | |---------- |------------:|----------:|----------:|---------:|----------:| | QuickSort | 38,241.9 us | 183.16 us | 162.37 us | - | 32 B | | MergeSort | 328.1 us | 6.47 us | 12.16 us | 125.9766 | 792040 B |
This is additional information about garbage collections per 1000 operations. When it comes to QuickSort, no specific data on garbage collection is provided. This suggests that the algorithm has no need for garbage collection during its sorting process. In contrast, MergeSort, triggered garbage collection, with a reported value of 125.9766. This indicates that it generates garbage during its execution, which requires periodic collection to reclaim memory. While this level of garbage collection may not be a big issue in systems with ample memory, it could impact performance in resource-constrained environments.
Conclusion
In this article, we explored the importance of checking allocated memory using the MemoryDiagnoser attribute. By analyzing the results of memory allocation using BenchmarkDotNet, developers can identify potential memory leaks, excessive allocations, or inefficient memory usage that could hamper application performance and scalability. In the quest for optimal memory management, benchmarking memory allocation becomes a key point for software developers.
The attribute proves invaluable in evaluating memory allocation efficiency across different algorithms, functions, or code snippets. By careful benchmarking, we can gain insights into memory consumption patterns and make informed decisions to optimize our applications.
