Code works but memory usage is erratic

Question

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.Threading;
using System.Threading.Tasks;
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);

        Task readFileTask = new Task(() => readFiles(fi, ct, BigBuffer));

        Task<string> computeHashTask = new Task<string>(() => calcHash(fi, BigBuffer, ct, prg));

        readFileTask.Start();
        computeHashTask.Start();

        return computeHashTask;
    }

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

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

                bytesRead = fileBlock.Length;

                //Infinite timeout
                BigBuffer.TryAdd(fileBlock, -1, ct);

            } while (bytesRead != 0);

            BigBuffer.CompleteAdding();
        }
    }

    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."; ;
    }

}

//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 readonly SynchronizationContext context;

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

Answer 1

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:

• "How do you convert a byte array to a hexadecimal string and vice versa in C#?" on StackOverflow. The issue gets beaten to death here, with the selected answer getting close to 200 votes.

• An open source repository for a project called "Convert Byte Array to Hex String Performance Test", which was inspired by the previously noted StackOverflow question. It tested 9 candidate methods, (the StringBuilder implementation analogous to our previous result being the slowest).

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:

2nd Best, Highly-Readable Version:

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:

• BlockingCollection<T> performance`

• Fast and Best Producer/Consumer Queue Technique - BlockingCollection<T> vs ConcurrentQueue<T>

Answer 2

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.

Answer 3

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;
    using System.Threading;
    using System.Threading.Tasks;

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

        int Length
        {
            get;

            set;
        }
    }

    public sealed class FileBlock : IFileBlock
    {
        private readonly byte[] data;

        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);
            var readFileTask = new Task(() => this.ReadFiles(fi, ct, bigBuffer));
            var computeHashTask = new Task<string>(() => CalcHash(fi, bigBuffer, ct, prg));

            readFileTask.Start();
            computeHashTask.Start();
            return computeHashTask;
        }

        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)
        {
            using (var stream = File.OpenRead(fi.FullName))
            {
                int bytesRead;

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

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

                    // Infinite timeout.
                    bigBuffer.TryAdd(fileBlock, -1, ct);
                }
                while (bytesRead != 0);

                bigBuffer.CompleteAdding();
            }
        }

        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.";

        private readonly int percentDone;

        private readonly string infoText;

        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 readonly SynchronizationContext context;

        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);
        }
    }
}

Answer 4

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.