Optimizing Memory Allocations in .NET Applications

• Download source - 2.1 MB

Introduction

Not so long ago, I WAS accidentally faced with a code snippet in a web which validates ISBN-10 number (if you are not familiar with what ISBN is, please refer to wiki page). This code works great. I wrote several unit tests to verify the algorithm's correctness and all of them passed. But when I started to delve deeper into details, I found out a broad room for improvements regarding performance optimization. I used Visual Studio profiler and WinDbg to catch the root cause of a bottleneck. I also used BenchmarkDotNet library (https://github.com/PerfDotNet/BenchmarkDotNet) to perform benchmarking. Below, I describe all the steps I took to significantly boost algorithm's performance.

The Algorithm

The problem that an algorithm is trying to solve is given a string input (for example 0-201-53082-1), answer the question if it is a valid ISBN-10 number or not.

According to wiki ISBN-10, validation algorithm can be expressed as follows:

Quote:

The final character of a ten digit International Standard Book Number is a check digit computed so that multiplying each digit by its position in the number (counting from the right) and taking the sum of these products modulo 11 is 0. The digit the farthest to the right (which is multiplied by 1) is the check digit, chosen to make the sum correct. It may need to have the value 10, which is represented as the letter X. For example, take the ISBN 0-201-53082-1: The sum of products is 0×10 + 2×9 + 0×8 + 1×7 + 5×6 + 3×5 + 0×4 + 8×3 + 2×2 + 1×1 = 99 ≡ 0 (mod 11). So the ISBN is valid. Note that positions can also be counted from left, in which case the check digit is multiplied by 10, to check validity: 0×1 + 2×2 + 0×3 + 1×4 + 5×5 + 3×6 + 0×7 + 8×8 + 2×9 + 1×10 = 143 ≡ 0 (mod 11).

While this may seem more complicated than the first scheme, it can be validated simply by adding all the products together then dividing by 11. The sum can be computed without any multiplications by initializing two variables, t and sum, to 0 and repeatedly performing t = t + digit; sum = sum + t; (which can be expressed in C as sum += t += digit;). If the final sum is a multiple of 11, the ISBN is valid.

Pretty simple, isn't it.

Initial Solution

This is how initial code looks like:

public static class Isbn
{
    // ********************************************************************
    // * ISBN Reference:                                                  *
    // * http://en.wikipedia.org/wiki/International_Standard_Book_Number  *
    // ********************************************************************
 
    /// <summary>
    /// This method will validate a ISBN 10
    /// or ISBN 13 code.
    /// </summary>
    /// <param name="isbn">code to validate</param>
    /// <returns>true, if valid, otherwise false</returns>
    public static bool IsValid(string isbn)
    {
        bool result = false;
 
        if (!string.IsNullOrEmpty(isbn))
        {
            if (isbn.Contains("-")) isbn = isbn.Replace("-", "");

                long j;

                // Length must be 10 and only the last character could be a char('X') or a numeric value,
                // otherwise it's not valid.
                if (isbn.Length != 10 || !long.TryParse(isbn.Substring(0, isbn.Length - 1), out j))
                    return false;

                char lastChar = isbn[isbn.Length - 1];

                // Using the alternative way of calculation
                int sum = 0;
                for (int i = 0; i < 9; i++)
                    sum += int.Parse(isbn[i].ToString()) * (i + 1);

                // Getting the remainder or the checkdigit
                int remainder = sum % 11;

                // If the last character is 'X', then we should check if the checkdigit is equal to 10
                if (lastChar == 'X')
                {
                    result = (remainder == 10);
                }
                // Otherwise check if the lastChar is numeric
                // Note: I'm passing sum to the TryParse method to not create a new variable again
                else if (int.TryParse(lastChar.ToString(), out sum))
                {
                    // lastChar is numeric, so let's compare it to remainder
                    result = (remainder == int.Parse(lastChar.ToString()));
                }

            return result;
        }

        return false;
    }
}

I also wrote a console app which invokes Isbn.IsValid method.

namespace Console
{
    class Program
    {
        static void Main(string[] args)
        {
            Isbn.IsValid("99921-58-10-7");
        }
    }
}

I decided to run this code under Visual Studio memory profiler and to look at memory allocations made by the algorithm. Here are the results:

Oh my God! 195 memory allocations for a simple method. It is evident that we should somehow deal with that.

The same issues can be found with the help of a hard core tool - WinDbg. To do this:

• Run the app under WinDbg
• Execute sxe ld clrjit command to wait for CLR to be loaded into process address space
• Run g command to continue program's execution
• Load sos extension. To to that, just execute .loadby sos clr
• Load sosex extension. To to that, just execute .loadby sosex clr
• Create a breakpoint at the beginning of the Main method. Here is the command: !bpmd Console Console.Program.Main
• Run g command. Program's execution will break at the beginning of the Main method.
• Run !dumpheap -stat -type System.String. It will print out the number of string objects allocated on heap. On my machine, the output looks like the following:

• Statistics:
        MT    Count    TotalSize Class Name
  60baab9c        2          104 System.Object[]
  60bfacc4       38         2366 System.String
  Total 40 objects

• There are 38 objects of type System.String at the moment when method Main starts
• Create breakpoint at the line of source code after Isbn.IsValid method invocation. We can use sosex extension and its !mbp command in the following way - !mbp Program.cs 34
• Run g command again. Program execution will break at the end of Main method.
• Run !dumpheap -stat -type System.String again. In my case, the output is:

• Statistics:
        MT    Count    TotalSize Class Name
  60bfd6ac        1           12 System.Collections.Generic.GenericEqualityComparer`1[[System.String, mscorlib]]
  60812348        1           48 System.Collections.Generic.Dictionary`2
                              [[System.String, mscorlib],[System.Globalization.CultureData, mscorlib]]
  60bfd7b8        1           60 System.Collections.Generic.Dictionary`2+Entry
                              [[System.String, mscorlib],[System.Globalization.CultureData, mscorlib]][]
  60baab9c       19          736 System.Object[]
  60bfacc4      185         5822 System.String
  Total 207 object
  

There are 185 objects of type System.String allocated on the heap! Very inefficient. It seems obvious that the ISBN validation algorithms, ideally, should not allocate System.String objects at all.

I decided to rewrite the algothms to minimize the number of memory allocations.

Optimized Solution

I created a class named IsbnEx with the optimized version of an algorithm.

using System.Text;
using Utils;

public static class IsbnEx
{
    unsafe public static bool IsValid(object value)
    {
        if (value == null)
        {
            return true;
        }

        string val = (string)value;

        if (!string.IsNullOrEmpty(val))
        {
            long length = 0;

            char[] array = val.ToCharArray();

            fixed (char* left = array)
            {
                char* right = left;
                char* mLeft = left;

                while (*right != '\0')
                {
                    if (*right == '-')
                    {
                        right++;
                    }
                    else
                    {
                        *mLeft = *right;
                        mLeft++;
                        right++;
                        length++;
                    }
                }
                *mLeft = '\0';
            }

            if (length == 10)
            {
                return IsValidIsbn10(array);
            }
         
            return false;
        }

        return false;
    }

    private static bool IsValidIsbn10(char[] isbn)
    {
        int sum = 0;
        int val;

        for (int i = 0; i < 9; ++i)
        {
            char c = isbn[i];
            if (c.TryParse(out val))
            {
                sum += (i + 1) * val;
            }
            else
            {
                return false;
            }
        }

        int remainder = sum % 11;
        char lastCharacter = isbn[9];

        if (lastCharacter == 'X')
        {
            return remainder == 10;
        }

        if (lastCharacter.TryParse(out val))
        {
            return remainder == val;
        }

        return false;
    }
}

I extracted character's parsing algorithm into a separate Utils class.

namespace Utils
{
    public static class Utils
    {
        public static bool TryParse(this char c, out int val)
        {
            if (c < '0' || c > '9')
            {
                val = 0;
                return false;
            }
            val = (c - '0');
            return true;
        }
    }
}

I also rewrite my console app to invoke IsbnEx.IsValid method.

namespace Console
{
    class Program
    {
        static void Main(string[] args)
        {
            IsbnEx.IsValid("99921-58-10-7");
        }
    }
}

Let's check whether we gained performance benefits.

Results

Here are the results of Visual Studio memory profiling:

There is only one memory allocation. It is made by the line of code below:

char[] array = val.ToCharArray();

And WinDbg output:

Before Isbn.IsValid invocation:

Statistics:
      MT    Count    TotalSize Class Name
60baab9c        2          104 System.Object[]
60bfacc4       38         2366 System.String
Total 40 objects

After Isbn.IsValid invocation:

Statistics:
      MT    Count    TotalSize Class Name
60baab9c        2          104 System.Object[]
60bfacc4       38         2366 System.String
Total 40 objects

Thus, method Isbn.IsValid hasn't allocated System.String objects at all. Fab!

Now, it is time to measure and compare execution time of 2 methods. I created a benchmark (thanks Andrey Akinshin for his fantastic BenchmarkDotNet library)

using BenchmarkDotNet;
using BenchmarkDotNet.Tasks;

[BenchmarkTask(platform: BenchmarkPlatform.X86, jitVersion: BenchmarkJitVersion.LegacyJit)]
public class IsbnBenchmark
{
    [Benchmark]
    public void IsbnTest()
    {
        Isbn.IsValid("99921-58-10-7");
    }

    [Benchmark]
    public void IsbnExTest()
    {
        IsbnEx.IsValid("99921-58-10-7");
    }
}

namespace Console
{
    class Program
    {
        static void Main(string[] args)
        {
            new BenchmarkRunner().Run<IsbnBenchmark>();
        }
    }
}

And the output:

180.9 versus 1719.9. Not so bad.

Further Optimization

After a while, I realised that it is possible to go further and tune the algorithm a little bit. The obvious way for improvement is to completely remove any memory allocations. Thus, I decided to eliminate the following line of code and change the algorithm accordingly.

char[] array = val.ToCharArray();

Apart from that, I investigated the assembly code generated by JIT and found out that the method Utils.TryParse wasn't inlined. I don't know the reason for that - it is a black magic how JIT makes decisions about whether to inline methods or not. I assume that it is due to out parameter. So I split Utils.TryParse method into 2 separate methods - the one which checks if a character is a digit and another one which converts a character into an integer. And voila - both methods were inlined during JIT compilation. My final code looks like the following:

IsbnEx class:

using Utils;

public static class IsbnEx
{
    public static bool IsValid(string val)
    {
        if (!string.IsNullOrEmpty(val))
        {
            int length = 0;

            for (int i = 0; i < val.Length; ++i)
            {
                if (val[i] == '-')
                {
                    continue;
                }
                length++;
            }

            if (length == 10)
            {
                return IsValidIsbn10(val);
            }

            return false;
        }

        return false;
    }

    private unsafe static bool IsValidIsbn10(string isbn)
    {
        int i = 0, sum = 0, val;
        char lastCharacter = '\0';

        fixed (char* left = isbn)
        {
            char* right = left;

            while (*right != '\0')
            {
                if (*right == '-')
                {
                    right++;
                    continue;
                }

                if (i < 9)
                {
                    char c = *right;
                    if (c.TryParse())
                    {
                        val = c.Parse();
                        sum += (i + 1) * val;
                        ++i;
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                {
                    lastCharacter = *right;
                }

                right++;
            }
        }

        int remainder = (sum) % 11;

        if (lastCharacter == 'X')
        {
            return remainder == 10;
        }

        if (lastCharacter.TryParse())
        {
            val = lastCharacter.Parse();
            return remainder == val;
        }

        return false;
    }
}

Utils class:

namespace Utils
{
    public static class Utils
    {
        public static bool TryParse(this char c)
        {
            if (c < '0' || c > '9')
            {
                return false;
            }
            return true;
        }

        public static int Parse(this char c)
        {
            return (c - '0');
        }
    }
}

And finally - benchmark output:

76.6 ns. Better!

The source code is available here Download Isbn.zip

History

• Version 1 - December 2015
• Version 2 - December 2015 - Further optimization section was added