Fast Named Format With Linq Expressions

This article describes how to implement “named format” functionality with C# and Linq Expressions. The .NET Framework supports string formats since the first day. String format patterns look like “My name is {0} and I am {1} years old”. Optionally, the placeholders inside the curly brackets, called format items, can include other format strings – e.g. to format numbers or dates in a special way. Great stuff. But what if I had an object whose properties I want to directly reference in the format string like “My name is {Name} and I am {Age} years old”?

Other Named Format Implementations

As you can guess, I am not the first one to write about this issue. For example, check out Phil Haacks blog post about this. That post deals a lot with the correct parsing of the format string and the correct interpretation of escaped and unescaped curly brackets. The emphasis in that post lies on correctness, not performance.

My Approach

We’ll, I like it fast and nasty 🙂 I needed a formatter that performs very fast, but does not need to support every twisted input string you can think of. So I settled with the single regular expression ([^{]|^){(\w+)}([^}]|$)|([^{]|^){(\w+)\:(.+)}([^}]|$). This is probably not the most elaborate way to parse a formatting input string (in fact, regular expressions are usually not powerful enough to handle brackets and bracket nesting), but it worked for all my scenarios (single-line, not too long strings).

Ok, let’s dig into that. The key to performance in this case is pre-compilation. The first call to the formatter will parse the input strings, convert it into the regular string format form, construct Linq Expressions to call the regular String.Format method with the proper arguments, compile these expressions and cache them. Every subsequent call will just execute the precompiled expression. Here’s an example:

Input format string: "My name is {Name} and I am {Age} years old"
Input object: var obj = new { Name = "Santa", Age = 1700 }
Generated code: string.Format("My name is {0} and I am {1} years old", obj.Name, obj.Age)

Named Format With Linq Expressions

Without further ado, here’s the code that does this:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
using System.Text.RegularExpressions;

namespace MunirHusseini
{
    public static class NamedFormat
    {
        private static readonly ConcurrentDictionary<string, object> PrecompiledExpressions = new ConcurrentDictionary<string, object>(StringComparer.OrdinalIgnoreCase);

        private static readonly Regex RegexFormatArgs = new Regex(@"([^{]|^){(\w+)}([^}]|$)|([^{]|^){(\w+)\:(.+)}([^}]|$)", RegexOptions.Compiled);

        public static string Format<T>(string pattern, T item)
        {
            // If we already have a compiled expression, just execute it.
            object o;
            if (PrecompiledExpressions.TryGetValue(pattern, out o))
            {
                return ((Func<T, string>)o)(item);
            }

            // Convert named format into regular format and return 
            // a list of the named arguments in order of appearance.
            string replacedPattern;
            var arguments = ParsePattern(pattern, out replacedPattern);
            // We'll be using the String.Format method to actually perform the formating.
            var formatMethod = typeof(string).GetMethod("Format", new[] { typeof(string), typeof(object[]) });

            // Now, construct code with Linq Expressions...

            // The constant that contains the format string:
            var patternExpression = Expression.Constant(replacedPattern, typeof(string));
            // The input object:
            var parameterExpression = Expression.Parameter(typeof(T));
            // An array containing a call to a property getter for each named argument :
            var argumentArrayElements = arguments.Select(argument => Expression.Convert(Expression.PropertyOrField(parameterExpression, argument), typeof(object)));
            var argumentArrayExpressions = Expression.NewArrayInit(typeof(object), argumentArrayElements);
            // The actual call to String.Format:
            var formatCallExpression = Expression.Call(formatMethod, patternExpression, argumentArrayExpressions);
            // The lambda expression we will be compiling:
            var lambdaExpression = Expression.Lambda<Func<T, string>>(formatCallExpression, parameterExpression);
            
            // The lambda expression will look something like this
            // input => string.Format("my format string", new[]{ input.Arg0, input.Arg1, ... });

            // Now we can compile the lambda expression
            var func = lambdaExpression.Compile();

            // Cache the pre-compiled expression 
            PrecompiledExpressions.TryAdd(pattern, func);

            // Execute the compiled expression
            return func(item);
        }

        private static IEnumerable<string> ParsePattern(string pattern, out string replacedPattern)
        {
            // Just replace each named format items with regular format items
            // and put all named format items in a list. Then return the 
            // new format string and the list of the named items.

            var sb = new StringBuilder();
            var lastIndex = 0;
            var arguments = new List<string>();
            var lowerarguments = new List<string>();

            foreach (var @group in from Match m in RegexFormatArgs.Matches(pattern)
                                   select m.Groups[m.Groups[6].Success ? 5 : 2])
            {
                var key = @group.Value;
                var lkey = key.ToLowerInvariant();
                var index = lowerarguments.IndexOf(lkey);
                if (index < 0)
                {
                    index = lowerarguments.Count;
                    lowerarguments.Add(lkey);
                    arguments.Add(key);
                }

                sb.Append(pattern.Substring(lastIndex, @group.Index - lastIndex));
                sb.Append(index);

                lastIndex = @group.Index + @group.Length;
            }

            sb.Append(pattern.Substring(lastIndex));
            replacedPattern = sb.ToString();
            return arguments;
        }
    }
}

Fast, you say?

So how fast is this? This is as fast as a normal string.format method! At least after the first call it is. I created a simple test to measure the time needed:

var input = new
{
    Name = "Santa",
    Age = 1700
};

var sw = Stopwatch.StartNew();

var text = NamedFormat.Format("{Name} is {Age:0.0} years old.", input);

Console.WriteLine(sw.ElapsedMilliseconds);
sw = Stopwatch.StartNew();

for (var i = 0; i < 1000000; i++)
{
    text = NamedFormat.Format("{Name} is {Age:0.0} years old.", input);
}

Console.WriteLine(sw.ElapsedMilliseconds);
Console.WriteLine(text);

When I run this on my Surface Pro (Intel i5-3317U), I get a measurements between 18ms and 25ms for the first call and 800ms to 1200ms for the next 1 million calls together. This equals 0.0008ms to 0.0012ms per call. Now that’s cooking with gas 🙂