# Code works but memory usage is erratic

I have the following class which is a tool for retrieving MD5 hashes of files that are input into it. They can potentially be very large files and I require cancellation and progress report, hence why i rolled my own solution rather than just passing in a filestream to HashAlgorithm.

I have a producer - consumer set up so that I can be reading in file blocks at the same time as calculating the MD5 hasher. I find the best performance is using 16mb blocks, which I allow a max pre-read of 3 blocks. Considering I have up to 5 of these running in parallel (5 drives) then memory usage can max out at 240mb assuming that the GC collects immediately. Obviously this doesn't happen so i see memory usage jump to approx 700mb or more in some instances.

How can I reduce this erratic memory behaviour?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.IO;
using System.Collections.Concurrent;

namespace MD5Library
{

public class FileBlock
{
public byte[] Data;

public int Length;

public FileBlock(int inBufferSize)
{
Data = new byte[inBufferSize];
}
}

public class MD5Hasher
{
protected int bufferSize = 1024 * 1024 * 16; //16mb at a time

public void MD5Hasher()
{
}

public void MD5Hasher(int _bufferSize)
{
bufferSize = _bufferSize;
}

public Task<string> Go(string inFile, CancellationToken ct, IProgress<ProgressReport> prg)
{
FileInfo fi = new FileInfo(inFile);
// Queue with capacity 3x the buffer
BlockingCollection<FileBlock> BigBuffer = new BlockingCollection<FileBlock>(3);

}

private async void readFiles(FileInfo fi, CancellationToken ct, BlockingCollection<FileBlock> BigBuffer)
{

using (FileStream stream = new FileStream(fi.FullName, FileMode.Open))
{
do
{
FileBlock fileBlock = new FileBlock(bufferSize);

fileBlock.Length = await stream.ReadAsync(fileBlock.Data, 0, bufferSize, ct);

//Infinite timeout

}
}

private string calcHash(FileInfo fi, BlockingCollection<FileBlock> BigBuffer, CancellationToken ct, IProgress<ProgressReport> prg)
{
long _fileSize = fi.Length;
long _bytesProcessed = 0;

using (HashAlgorithm hashAlgorithm = MD5.Create())
{
foreach (var b in BigBuffer.GetConsumingEnumerable(ct))
{
hashAlgorithm.TransformBlock(b.Data, 0, b.Length, b.Data, 0);

_bytesProcessed += b.Length;

// Report progress
ProgressReport p = new ProgressReport();
p.setProgress(_bytesProcessed, _fileSize);
prg.Report(p);
}

hashAlgorithm.TransformFinalBlock(new byte[0], 0, 0);

return HashToString(hashAlgorithm.Hash);
}
}

public int BufferSize
{
get
{
return bufferSize;
}
}

public string HashToString(byte[] inHash)
{
string hex = "";
foreach (byte b in inHash)
{
hex += b.ToString("x2");
}

return hex;
}
}

public class ProgressReport
{
public int PercentDone
{
get;
set;
}

public string InfoText
{
get;
set;
}

public void setProgress(long _progress, long _total)
{
PercentDone = Convert.ToInt32((_progress * 100) / _total);
InfoText = PercentDone + "% complete."; ;
}

}

public class PropertyProgress<T> : IProgress<T>, INotifyPropertyChanged
{

private T progress;

public PropertyProgress(T initialProgress = default(T))
{
this.context = SynchronizationContext.Current ?? new SynchronizationContext();
this.progress = initialProgress;
}

public T Progress
{
get
{
return this.progress;
}

private set
{
this.progress = value;
if (this.PropertyChanged != null)
{
this.PropertyChanged(this, new PropertyChangedEventArgs("Progress"));
}
}
}

void IProgress<T>.Report(T value)
{
this.context.Post(_ => { this.Progress = value; }, null);
}

public event PropertyChangedEventHandler PropertyChanged;
}

}


Usage:

    string source = @"c:\largefile.dat";

MD5Hasher md5async = new MD5Hasher();
PropertyProgress<ProgressReport> p = new PropertyProgress<ProgressReport>();
CancellationTokenSource cts = new CancellationTokenSource();

Console.Writeline(await md5async.Go(source, cts.Token, p));

-

1. Before I address your specific issue directly, I'd like to suggest that you review MSDN's guidelines for C# naming conventions, specifically with respect to capitalization. The erratic name formatting makes your code unnecessarily difficult to follow. You will undoubtedly increase the consistency of your code when it becomes more readable, and you will be able to gain much more when interacting with other programmers (such as on CodeReview).

2. I am not 100% certain about the culprit here, but I have a suspicion that your performance issue is being caused by the way you are creating the string in your HashToString method. Your code is concatenating the strings together using the + operator. There are known performance issues with this approach, and the performance degradation increases proportionally to the number of strings. As a general rule, you should use a StringBuilder if you are concatenating more than four strings. An informative article about this guideline is available at: dotnetperls - C# string.Concat. If you are concatenating strings in a loop, you should always use a StringBuilder. You can also read an article with benchmarks and explanation of the relative performance between concatenation and StringBuilder at dotnetperls - C# StringBuilder Performance. After reading these articles, it should be clear that converting any large array to a string using your approach will result in terrible performance. I found another article, which cites performance tests that indicate using a StringBuilder is 550% faster than using a plus sign.

Now, let's start with your code and see if we can find a better way to handle that issue...

## Original string.Concat* Version:

*The + operator calls String.Concat under the hood.

public string HashToString(byte[] inHash)
{
string hex = "";
foreach (byte b in inHash)
{
hex += b.ToString("x2");
}
return hex;
}


Now, since the concatenation is happening in a loop, we know it's better to use the StringBuilder than the + operator. This is what the code looks like if we make this change:

## Better StringBuilder Version:

public string HashToString2(byte[] inHash)
{
StringBuilder hexBuilder = new StringBuilder();
foreach (byte b in inHash)
{
hexBuilder.AppendFormat("{0:x2}", b);
}
return hexBuilder.ToString();
}


Now, if you read the dotnerperls articles, you'd realize we can do a minor tweak to get this to give use even better performance. The performance tweak involves explicitly assigning the StringBuilder's capacity when you create the instance. Since we have an array and we know each element in the array will result in 2 characters, we can determine the capacity of the StringBuilder and eliminate the cost of constant resizing.

## Even Better StringBuilder Version:

public string HashToString3(byte[] inHash)
{
StringBuilder hexBuilder = new StringBuilder( inHash.Length * 2 );
foreach (byte b in inHash)
{
hexBuilder.AppendFormat("{0:x2}", b);
}
return hexBuilder.ToString();
}


At this point, you should be able to run tests and notice better performance. Since we know that at least one of your issues was caused by the HashToString method, it's worth stepping back and see if we are converting a hash to a string in the most optimal way. Now, the hash is just a byte array in a specific context, so we really just need to know how to get the best performance when converting a byte array to a hexadecimal string in C#. I googled this, and found out that this issue has been discussed and tested exhaustively. The resources I found include:

The fastest result from the performance test used byte manipulation and looks like:

## Ridiculously Optimized Byte Manipulation Version:

public string HashToString4(byte[] bytes) {
char[] c = new char[bytes.Length * 2];
byte b;
for (int i = 0; i < bytes.Length; i++)
{
b = ((byte)(bytes[i] >> 4));
c[i * 2] = (char)(b > 9 ? b + 0x37 : b + 0x30);
b = ((byte)(bytes[i] & 0xF));
c[i * 2 + 1] = (char)(b > 9 ? b + 0x37 : b + 0x30);
}
return new string(c);
}


My only criticism of this is that the byte manipulation technique is very difficult for human beings to read. The second best option was about half as fast as the byte manipulation, but is very readable and leverages a built in .NET function for converting byte arrays to hexadecimal strings. It looks like:

public string HashToString5(byte[] bytes) {
return BitConverter.ToString(bytes).Replace("-", "");
}


Now, I said at the beginning that I wasn't certain this is your only culprit. However, I know for a fact that making this change will increase your performance in general. Try the suggested refactoring, and let us know how your situation changes.

## Update re: BlockingCollection

It looks like BlockingCollection is also worth exploring for performance issues. I'm personally not very familiar with this class, but Reed Copsey indicates that certain versions of it have scaling issues. Here are a couple StackOverflow posts that are probably worth reading if the HashToString overhaul doesn't completely solve your issue:

-
I'm pretty sure string concatenation is not the problem here. The MD5 hash has only 16 bytes. And doing one string concatenation of 16 two-character strings per each file of several hundred megabytes will be completely insignificant, even if done very inefficiently. Your advice might be good in general, but it's not relevant in this case. –  svick Oct 9 '12 at 14:03
@svick, (1) I asked the user to test for validation. (2) It has been demonstrated that string concatenation performance decreases drastically after four strings (this would be 16). (3) I also pointed out some possibilities w/ the BlockingCollection. I do not know what interactions this could result in. –  smartcaveman Oct 9 '12 at 14:09
Yes, concatenating many strings this way has bad performance (because it's O(n^2)). But are you seriously suggesting that concatenating 16 very short strings once in a while will waste hundreds of megabytes of memory? And of the two articles you linked to, the first one talks about a very specific version of BlockingCollection, which isn't used here. And the second one doesn't mention any performance problems at all. –  svick Oct 9 '12 at 14:22
I'd use LINQ in HashToString: return inHash.Aggregate(string.Empty, (current, b) => current + b.ToString("x2")); –  Jesse C. Slicer Oct 9 '12 at 15:12
@JesseC.Slicer, that was one of the ones that got tested. Check out the project, it's got results if you wanna compare them –  smartcaveman Oct 9 '12 at 17:06

First, make sure that this is actually a problem for you. Large number in the “used memory” column might look scary, but it's not a problem if the memory wouldn't be used for anything anyway.

The reason why your program seems to be using too much memory is most likely because the garbage collector doesn't run often enough. .Net tries to not run GC too often, so it doesn't affect performance too much. But, as a side effect, this means your application will consume more memory than what you might expect.

The quick and dirty solution to this is to make sure the GC runs more often, by calling GC.Collect(). An appropriate place to do that would be right before you allocate your big array in the constructor of FileBlock. But, depending on how many objects are there in your application, this could significantly affect performance.

A better solution might be to create a pool of blocks. When you need a new block, you would first look in the pool and take it from there is there was one. When you're done with a block, you wouldn't just rely on the GC, but you would put it back into the pool. This way, blocks wouldn't be GCed and then reallocated again and again, which should lead to less wasted memory.

One question is how to decide that the pool is too big, so you can remove unused blocks from it and let it be GCed. You'll have to try that by yourself, but one possibility is to base this decision on time: if a block is in the pool for, say, one minute, you can discard it.

Another option would be to have a fixed total number of blocks. In this case, if a block is requested when the pool is empty, you would block until some block is returned to the pool. This would ensure that your memory usage doesn't go over some limit, but it could also affect performance, because a thread that could be reading from the disk can't do that, because there are no blocks available.

-

Here's how I would go about it (mostly from a readability standpoint rather than a performance one - though the use of immutable data may help contribute to well-measurable performance and memory usage metrics):

namespace MD5Library
{
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Linq;
using System.Security.Cryptography;

public interface IFileBlock
{
byte[] Data
{
get;
}

int Length
{
get;

set;
}
}

public sealed class FileBlock : IFileBlock
{

public FileBlock(int inBufferSize)
{
this.data = new byte[inBufferSize];
}

public byte[] Data
{
get
{
return this.data;
}
}

public int Length
{
get;

set;
}
}

public class MD5Hasher
{
private readonly int bufferSize = 1024 * 1024 * 16; // 16mb at a time.

public MD5Hasher()
{
}

public MD5Hasher(int bufferSize)
{
this.bufferSize = bufferSize;
}

protected int BufferSize
{
get
{
return this.bufferSize;
}
}

public Task<string> Go(string inFile, CancellationToken ct, IProgress<IProgressReport> prg)
{
// Queue with capacity 3x the buffer.
var fi = new FileInfo(inFile);
var bigBuffer = new BlockingCollection<IFileBlock>(3);

}

private static string HashToString(IEnumerable<byte> inHash)
{
return inHash.Aggregate(string.Empty, (current, b) => current + b.ToString("x2"));
}

private async void ReadFiles(FileInfo fi, CancellationToken ct, BlockingCollection<IFileBlock> bigBuffer)
{
{

do
{
var fileBlock = new FileBlock(this.bufferSize);

fileBlock.Length = await stream.ReadAsync(fileBlock.Data, 0, this.bufferSize);

// Infinite timeout.
}

}
}

private static string CalcHash(FileInfo fi, BlockingCollection<IFileBlock> bigBuffer, CancellationToken ct, IProgress<IProgressReport> prg)
{
var fileSize = fi.Length;
var bytesProcessed = 0L;

using (HashAlgorithm hashAlgorithm = MD5.Create())
{
foreach (var b in bigBuffer.GetConsumingEnumerable(ct))
{
hashAlgorithm.TransformBlock(b.Data, 0, b.Length, b.Data, 0);
bytesProcessed += b.Length;

// Report progress.
prg.Report(new ProgressReport(bytesProcessed, fileSize));
}

hashAlgorithm.TransformFinalBlock(new byte[0], 0, 0);
return HashToString(hashAlgorithm.Hash);
}
}
}

public interface IProgressReport
{
int PercentDone
{
get;
}

string InfoText
{
get;
}
}

public sealed class ProgressReport : IProgressReport
{
private const string PercentComplete = "% complete.";

public ProgressReport(long progress, long total)
{
this.percentDone = Convert.ToInt32((100 * progress) / total);
this.infoText = this.PercentDone + PercentComplete;
}

public int PercentDone
{
get
{
return this.percentDone;
}
}

public string InfoText
{
get
{
return this.infoText;
}
}
}

// Borrowed from Stephen Cleary: http://nitoprograms.blogspot.co.uk/2012/02/reporting-progress-from-async-tasks.html
public class PropertyProgress<T> : IProgress<T>, INotifyPropertyChanged
{

private T progress;

public PropertyProgress(T initialProgress = default(T))
{
this.context = SynchronizationContext.Current ?? new SynchronizationContext();
this.progress = initialProgress;
}

public event PropertyChangedEventHandler PropertyChanged;

public T Progress
{
get
{
return this.progress;
}

private set
{
this.progress = value;
if (this.PropertyChanged != null)
{
this.PropertyChanged(this, new PropertyChangedEventArgs("Progress"));
}
}
}

void IProgress<T>.Report(T value)
{
this.context.Post(_ => { this.Progress = value; }, null);
}
}
}

-

You are seeing memory climb because the garbage collector is not running at the same rate that data is allocated. It is important to note that FileBlock.Data is allocating in the large object heap. Conceptually, large object heap objects belong the generation 2 because they are collected at the same time generation 2 is collected. http://msdn.microsoft.com/en-us/magazine/cc534993.aspx#id0070017 has some good pointers on the LOH.

You could consider pre-allocating a pool of 16MB blocks. There would also be an extra speed advantage since the memory manager wouldn't need to keep zeroing 16MB arrays for each allocation.

-