Boost performance of localized, non-static or incremental string formatting.

[geeknoid]

EDITED by @stephentoub 1/13/2023:
Latest API proposal at #50330 (comment)

---

Background and Motivation

The strides in .NET around string formatting over the last few years have been significant, and .NET 6 with C# 10 promise further substantial improvements to string interpolation performance. However, string interpolation has a serious constraint: it only works when the format strings are known at compilation time.

For any scenario where the text to format is not known at compilation time, such as for localized content being pulled from a resource file, then classic String.Format and StringBuilder.AppendFormat remain the workhorses.

This proposal is designed to deliver substantial performance improvements to classic composite string formatting by hoisting the expensive process of parsing the composite format string to initialization time, enabling the hot path of performing string formatting to execute up to 5x faster than using classic functions.

The model is logically similar to how you can compile a regex a priori and use it repeatedly to seek matches. Here, you parse and process the format string once, and then use it to repeatedly format strings.

Please see here for a fully functional implementation, with complete test coverage and a banchmark.

Proposed API

The primary API surface proposed here is fairly minimal. The CompositeFormat type has a primary constructor, then various overloads for Format and TryFormat.

/// <summary>
/// Provides highly efficient string formatting functionality.
/// </summary>
/// <remarks>
/// This type lets you optimize string formatting operations common with the <see cref="string.Format(string,object?)"  />
/// method. This is useful for any situation where you need to repeatedly format the same string with
/// different arguments.
///
/// This type works faster than <c>string.Format</c> because it parses the composite format string only once when
/// the instance is created, rather than doing it for every formatting operation.
///
/// You first create an instance of this type, passing the composite format string that you intend to use.
/// Once the instance is created, you call the <see cref="Format{T}(IFormatProvider?,T)"/> method with arguments to use in the
/// format operation.
/// </remarks>
public readonly struct CompositeFormat
{
    /// <summary>
    /// Initializes a new instance of the <see cref="CompositeFormat"/> struct.
    /// </summary>
    /// <param name="format">A classic .NET format string as used with <see cref="string.Format(string,object?)"  />.</param>
    /// <remarks>
    /// Parses a composite format string into an efficient form for later use.
    /// </remarks>
    public CompositeFormat(ReadOnlySpan<char> format);

    /// <summary>
    /// Initializes a new instance of the <see cref="CompositeFormat"/> struct.
    /// </summary>
    /// <param name="format">A template-based .NET format string as used with <c>LoggerMessage.Define</c>.</param>
    /// <param name="templates">Holds the named templates discovered in the format string.</param>
    /// <remarks>
    /// Parses a composite format string into an efficient form for later use.
    /// </remarks>
    public CompositeFormat(ReadOnlySpan<char> format, out IList<string> templates)

    /// <summary>
    /// Formats a string with a single argument.
    /// </summary>
    /// <typeparam name="T">Type of the single argument.</typeparam>
    /// <param name="arg">An argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T>(T arg);

    /// <summary>
    /// Formats a string with a single argument.
    /// </summary>
    /// <typeparam name="T">Type of the single argument.</typeparam>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg">An argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T>(IFormatProvider? provider, T arg);

    /// <summary>
    /// Formats a string with two arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1>(T0 arg0, T1 arg1);

    /// <summary>
    /// Formats a string with two arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1>(IFormatProvider? provider, T0 arg0, T1 arg1);

    /// <summary>
    /// Formats a string with three arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1, T2>(T0 arg0, T1 arg1, T2 arg2);

    /// <summary>
    /// Formats a string with three arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1, T2>(IFormatProvider? provider, T0 arg0, T1 arg1, T2 arg2);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <param name="args">Additional arguments to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1, T2>(T0 arg0, T1 arg1, T2 arg2, params object?[]? args);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <param name="args">Additional arguments to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format<T0, T1, T2>(IFormatProvider? provider, T0 arg0, T1 arg1, T2 arg2, params object?[]? args);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <param name="args">Arguments to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format(params object?[]? args);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="args">Arguments to use in the formatting operation.</param>
    /// <returns>The formatted string.</returns>
    public string Format(IFormatProvider? provider, params object?[]? args);

    /// <summary>
    /// Formats a string with one argument.
    /// </summary>
    /// <typeparam name="T">Type of the single argument.</typeparam>
    /// <param name="destination">Where to write the resulting string.</param>
    /// <param name="charsWritten">The number of characters actually written to the destination span.</param>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg">An argument to use in the formatting operation.</param>
    /// <returns>True if there was enough room in teh destination span for the resulting string.</returns>
    public bool TryFormat<T>(Span<char> destination, out int charsWritten, IFormatProvider? provider, T arg);

    /// <summary>
    /// Formats a string with two arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <param name="destination">Where to write the resulting string.</param>
    /// <param name="charsWritten">The number of characters actually written to the destination span.</param>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <returns>True if there was enough room in teh destination span for the resulting string.</returns>
    public bool TryFormat<T0, T1>(Span<char> destination, out int charsWritten, IFormatProvider? provider, T0 arg0, T1 arg1);

    /// <summary>
    /// Formats a string with three arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="destination">Where to write the resulting string.</param>
    /// <param name="charsWritten">The number of characters actually written to the destination span.</param>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <returns>True if there was enough room in teh destination span for the resulting string.</returns>
    public bool TryFormat<T0, T1, T2>(Span<char> destination, out int charsWritten, IFormatProvider? provider, T0 arg0, T1 arg1, T2 arg2);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <typeparam name="T0">Type of the first argument.</typeparam>
    /// <typeparam name="T1">Type of the second argument.</typeparam>
    /// <typeparam name="T2">Type of the third argument.</typeparam>
    /// <param name="destination">Where to write the resulting string.</param>
    /// <param name="charsWritten">The number of characters actually written to the destination span.</param>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="arg0">First argument to use in the formatting operation.</param>
    /// <param name="arg1">Second argument to use in the formatting operation.</param>
    /// <param name="arg2">Third argument to use in the formatting operation.</param>
    /// <param name="args">Additional arguments to use in the formatting operation.</param>
    /// <returns>True if there was enough room in teh destination span for the resulting string.</returns>
    public bool TryFormat<T0, T1, T2>(Span<char> destination, out int charsWritten, IFormatProvider? provider, T0 arg0, T1 arg1, T2 arg2, params object?[]? args);

    /// <summary>
    /// Formats a string with arguments.
    /// </summary>
    /// <param name="destination">Where to write the resulting string.</param>
    /// <param name="charsWritten">The number of characters actually written to the destination span.</param>
    /// <param name="provider">An optional format provider that provides formatting functionality for individual arguments.</param>
    /// <param name="args">Arguments to use in the formatting operation.</param>
    /// <returns>True if there was enough room in teh destination span for the resulting string.</returns>
    public bool TryFormat(Span<char> destination, out int charsWritten, IFormatProvider? provider, params object?[]? args);

    /// <summary>
    /// Gets the number of arguments required in order to produce a string with this instance.
    /// </summary>
    public int NumArgumentsNeeded { get; }
}

In addition to the feature set shown above, it's also desirable to add extension methods to the StringBuilder which leverage the same model for enhanced formatting performance in that context. See here for the prototype API for these.

Usage Examples

// preprocess the format string statically at startup
private static readonly _cf = new CompositeFormat(MyResources.MyHelloFormatString);

public void Foo(string name)
{
    // format the string
    var str = _cf.Format(name);    // logically equivalent to String.Format(MyResources.MyHelloFormatString, name);
    Console.WriteLine(str);

    str = new StringBuilder().AppendFormat(_cf, name).ToString();
    Console.WriteLine(str);
}

Alternative Designs

Rather than implementing the Format/TryFormat methods as instance methods on the CompositeFormat type, they could be integrated directly into the String type as first class methods. This would provide a clean model. Similarly, the extensions methods for StringBuilder could be baked in directly to the StringBuilder type.

Using such an approach doesn't yield additional performance, it's really just a matter of how the API is suraced.

Benchmarks

Here are benchmarks for the current prototype implementation:

|                  Method |      Mean |     Error |    StdDev |     Gen 0 |     Gen 1 |    Gen 2 |  Allocated |
|------------------------ |----------:|----------:|----------:|----------:|----------:|---------:|-----------:|
|     ClassicStringFormat | 45.036 ms | 26.859 ms | 1.4723 ms | 3083.3333 | 1333.3333 | 416.6667 | 16800613 B |
|           Interpolation | 43.340 ms |  3.324 ms | 0.1822 ms | 3000.0000 | 1187.5000 | 312.5000 | 16799929 B |
|           StringBuilder | 51.144 ms |  3.827 ms | 0.2098 ms | 2900.0000 | 1100.0000 | 200.0000 | 16799922 B |
|         CompositeFormat | 26.178 ms | 16.042 ms | 0.8793 ms | 2062.5000 |  781.2500 | 156.2500 | 11999929 B |
| CompositeFormatWithSpan | 10.382 ms |  1.172 ms | 0.0642 ms |         - |         - |        - |        2 B |
|             StringMaker |  9.573 ms |  1.488 ms | 0.0816 ms | 5546.8750 |         - |        - | 23199601 B |
|     StringMakerWithSpan |  8.550 ms |  6.963 ms | 0.3817 ms | 2671.8750 |         - |        - | 11199680 B |

Risks

None that I'm aware.

Implementation Notes

The prototype implementation I linked to above requires .NET Standard 2.1 as a baseline.

The implementation as presented depends on an internal StringMaker type, which is a highly efficient replacement for StringBuilder packaged as a ref readonly struct. It would be easy to reimplement this code on top of equivalent data types being created to support the C# compiler's enhanced interpolation features in C# 10.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[davidfowl]

It occurs to me that this is very similar to

runtime/src/libraries/Microsoft.Extensions.Logging.Abstractions/src/LogValuesFormatter.cs

Line 15 in 7795971

internal sealed class LogValuesFormatter

. Might be able to reuse it if it supported named holes...

[geeknoid]

@davidfowl I think you could create a new constructor for StringFormatter that understands the named hole syntax and produces the same internal representation that drives the efficient formatting.

[geeknoid]

@davidfowl The prototype implementation has been updated to include support for the template-based model (a.k.a. named holes) model. It's just a different constructor for the CompositeFormat type, and the formatting operations then work the same as before. The new constructor returns an ordered set of template names. And unlike the semantics of LoggerMessage.Define, this version correctly handles having the same template repeated in the format string.

I believe integrating this functionality into the guts of Microsoft.Extensions.Logging.Abstractions would substantially improve the performance of the logging delegates returned by LoggerMessage.Define, thus reducing the overhead of application logging.

[davidfowl]

I concur, there's also overlap with #14484.

@stephentoub the one thing not addressed by the improved string interpolation proposal is strings loaded at runtime https://github.com/dotnet/aspnetcore/blob/1870441efdc00a6c253c2a5c54c20a313fb56ee2/src/Servers/Kestrel/Core/src/Middleware/HttpsConnectionMiddleware.cs#L509-L552

Can we include this issue and #14484 into that epic? It seems like some of the assets from the string interpolation epic could be used as part of this.

[stephentoub]

I'd be ok seeing something along those lines incorporated as an implementation detail into LoggerMessage.Define. I'm not excited right now at the idea of shipping such a CompositeFormat type publicly (in part for the same reasons we've been hesitant to expose generic overloads for string.Format itself, namely code size from generic instantiations... that ship has already sailed for LoggerMessage); even if we did, I expect you'd want any such optimization to be supported down level from .NET 6, and I don't think we'd ship such a type in its own OOB. If you did want to only target .NET 6, you could use InterpolatedStringBuilder as a building block if desired to actually build up the resulting string from the constituent components. (As an aside, #14484 isn't really an epic... it was a proposal for a specific set of APIs, which we largely declined, but the issue has stayed open as a discussion ground for alternatives.)

[davidfowl]

I'd be ok seeing something along those lines incorporated as an implementation detail into LoggerMessage.Define. I'm not excited right now at the idea of shipping such a CompositeFormat type publicly (in part for the same reasons we've been hesitant to expose generic overloads for string.Format itself, namely code size from generic instantiations... that ship has already sailed for LoggerMessage); even if we did, I expect you'd want any such optimization to be supported down level from .NET 6, and I don't think we'd ship such a type in its own OOB.

That sounds reasonable but it feels like we're saying we don't need to improve the performance of runtime generated strings because of generic instantiation bloat. Re-reading #14484 makes me feel like we don't see any value in avoiding boxing in string.Format overloads because we're allocating a string anyways. Is that right?

If you did want to only target .NET 6, you could use InterpolatedStringBuilder as a building block if desired to actually build up the resulting string from the constituent components. (As an aside, #14484 isn't really an epic... it was a proposal for a specific set of APIs, which we largely declined, but the issue has stayed open as a discussion ground for alternatives.)

I do want to start cross compiling the Extensions assemblies to target ns2.0, ns2.1, latest .NET build.

(As an aside, #14484 isn't really an epic... it was a proposal for a specific set of APIs, which we largely declined, but the issue has stayed open as a discussion ground for alternatives.)

I meant the "improve interpolated strings" epic.

@geeknoid how do you feel about burying this logic into the LoggerMessage code? We can potentially remove a bunch of it in .NET 6 by using built ins.

[stephentoub]

we don't see any value in avoiding boxing in string.Format overloads because we're allocating a string anyways. Is that right?

With string.Format, there are other costs involved, with few benefits to such a change other than avoiding the boxing, and so you're trading a potentially huge growth in generic instantiations (every different combination of T1, T2, T3 where at least one is a value type getting its own copy) for avoiding just one of the costs involved, and a cost that can be dwarfed by the typically larger string allocation happening. It's one of the reasons I've pushed for the interpolated strings improvements the way we're doing it:

• You avoid the boxing
• You avoid the params array
• You get generic specialization without combinatoric growth, and applying only to the code for formatting that type
• You get parsing done at compile time rather than at startup or steady-state
• You can support types that can't be boxed and can't be generic, e.g. ReadOnlySpan<char>
• It applies to scenarios other than just creating strings, including zero-alloc formatting into a span, formatting into a StringBuilder, etc.

It does have the limitation that it can't be applied dynamically to format strings at runtime, and I would like to address that at some point, but I'd like to do so:

• After we get more experience with how folks use interpolated strings and builders with C# 10
• When we have a better sense of if/when/how ref structs will be usable with generics so it can be factored in
• After reflecting on whether there's an approach that would work for localization as well but still at compile time

In the meantime, the two main places I see devs loading the same resource string to be processed many times in an app are:

• logging that requires localization
• exception messages that require localization

I'm not particularly concerned with reducing string formatting costs for the latter. I would like to for the former, and we can take a big swing at that now by incorporating such a preprocessing approach into LoggerMessage.Define under the covers. It already limits what types can be used (things that can be generics), it already has the generics explosion potential and so isn't introducing a new issue, its primary purpose is preprocessing, it's what ASP.NET uses, it focuses on a known problem space, etc., plus it won't encourage use of this for things like exception messages where the tradeoffs are likely to be wrong for the end developer who may not realize it. We can get experience from that and C# 10 interpolated strings, and see if/when/how more is desired in the future. In the meantime, I'd encourage Martin to release a nuget package with his CompositeFormat, so that anyone can use it, vote with their feet, and drive further learnings for future potential incorporation.

(That said, @jkotas had provided feedback on string.Format and boxing in that issue. I don't want to put words in his mouth, so he can comment here as well if he disagrees with my stance.)

[geeknoid]

Searching through our code base, it's clear that the vast majority of uses of String.Format is around error handling. In fact, for our (service code) these strings aren't localized or customized and hence could be converted to string interpolation (someone should write a code fixer to automate converting code over).

However, there are also several cases where the format string comes from either a resource file or config. For example, we format some URLs and file paths that way. And these things are done in our request paths, not in error paths. I suspect that many user-facing code is in the same boat. I suspect that framework code is not representative of application-level code in this respect, application-level code will tend to format localized content as part of main business logic.

@stephentoub The use of generics in the Format API could be removed/reduced which would trigger a teeny more boxing, but would still retain most of the value that CompositeFormat provides. It factors out parsing of the format string so that the work is not done on every use. My gut says that no matter what syntax the compiler may or may not provide, in order to handle dynamic string formatting, you will end up with something like CompositeFormat to separate parsing the input string from the format operation. Anyway, I would be happy to simplify the API to reduce generic explosion in order to get the overall benefits of this model.

@davidfowl As I mentioned to you this weekend, it took a few minutes to create a prototype of LoggerMessage.Define which used this new string formatting code in its implementation. It was pretty straightforward and did improve performance. If we can't get CompositeFormat in as a first class concept in the framework, I'd be totally fine to exploit it as an implementation detail of the logging system.

[geeknoid]

It's also worth considering StringBuilder.AppendFormat. With the extensions I've integrated into my code, AppendFormat can execute without any allocations in the happy path. Formatting occurs in an on-stack span which is then copied directly into the StringBuilder. Using interpolation there would produce a transient string (unless there's some new voodoo magic coming to address this in C# 10).

So barring new language features, my extensions to AppendFormat are likely the fastest way to format text into a string builder.