Add String.Format overloads to avoid unnecessary allocations

[justinvp]

It's pretty common to pass value types to String.Format, unfortunately this results in unnecessary boxing allocations.

Rationale

Consider the following:

long id = ...;
int index = ...;
int length = ...;

// Traditional call to String.Format
string foo = string.Format("{0}: Index = {1}, Length = {2}", id, index, length);

// Use of the string interpolation language feature
string bar = $"{id}: Index = {index}, Length = {length}";

Both the traditional call to String.Format and the use of the string interpolation language feature (which is just syntactic sugar for String.Format) requires 3 boxing allocations.

Proposed API

namespace System
{
    public sealed class String : ...
    {
        // Proposed methods
        public static string Format<T0>(string format, T0 arg0);
        public static string Format<T0, T1>(string format, T0 arg0, T1 arg1);
        public static string Format<T0, T1, T2>(string format, T0 arg0, T1 arg1, T2 arg2);
        public static string Format<T0>(IFormatProvider provider, string format, T0 arg0);
        public static string Format<T0, T1>(IFormatProvider provider, string format, T0 arg0, T1 arg1);
        public static string Format<T0, T1, T2>(IFormatProvider provider, string format, T0 arg0, T1 arg1, T2 arg2);

        // Existing methods
        public static string Format(string format, object arg0);
        public static string Format(string format, object arg0, object arg1);
        public static string Format(string format, object arg0, object arg1, object arg2);
        public static string Format(string format, params object[] args);
        public static string Format(IFormatProvider provider, string format, object arg0);
        public static string Format(IFormatProvider provider, string format, object arg0, object arg1);
        public static string Format(IFormatProvider provider, string format, object arg0, object arg1, object arg2);
        public static string Format(IFormatProvider provider, string format, params object[] args);

        ...
    }
}

namespace System.Text
{
    public sealed class StringBuilder
    {
        // Proposed methods
        public StringBuilder AppendFormat<T0>(string format, T0 arg0);
        public StringBuilder AppendFormat<T0, T1>(string format, T0 arg0, T1 arg1);
        public StringBuilder AppendFormat<T0, T1, T2>(string format, T0 arg0, T1 arg1, T2 arg2);
        public StringBuilder AppendFormat<T0>(IFormatProvider provider, string format, T0 arg0);
        public StringBuilder AppendFormat<T0, T1>(IFormatProvider provider, string format, T0 arg0, T1 arg1);
        public StringBuilder AppendFormat<T0, T1, T2>(IFormatProvider provider, string format, T0 arg0, T1 arg1, T2 arg2);

        // Existing methods
        public StringBuilder AppendFormat(string format, object arg0);
        public StringBuilder AppendFormat(string format, object arg0, object arg1);
        public StringBuilder AppendFormat(string format, object arg0, object arg1, object arg2);
        public StringBuilder AppendFormat(string format, params object[] args);
        public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0);
        public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0, object arg1);
        public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0, object arg1, object arg2);
        public StringBuilder AppendFormat(IFormatProvider provider, string format, params object[] args);

        ...
    }
}

namespace System.Runtime.CompilerServices
{
    public static class FormattableStringFactory
    {
        // Proposed methods
        public static FormattableString Create<T0>(string format, T0 argument0);
        public static FormattableString Create<T0, T1>(string format, T0 argument0, T1 argument1);
        public static FormattableString Create<T0, T1, T2>(string format, T0 argument0, T1 argument1, T2 argument2);

        // Existing method
        public static FormattableString Create(string format, params object[] arguments);
    }
}

I'd be happy to contribute an implementation and tests.

[ellismg]

Do the additional FormattableStringFactory members require Roslyn changes to be consumed with the nice syntax?

[svick]

I think the parameters in the new overloads should have exactly the same names as in the old overloads, so that if someone called string.Format() with named parameters, their code also starts using the new overloads just by recompiling.

[justinvp]

Do the additional FormattableStringFactory members require Roslyn changes to be consumed with the nice syntax?

I need to double-check, but I'm pretty sure Roslyn is already designed to make use of such overloads to String.Format and FormattableStringFactory.Create, if they exist. So, no Roslyn changes would be required.

[justinvp]

I think the parameters in the new overloads should have exactly the same names as in the old overloads

The 0-based parameter names seem a little strange, but now that you mention keeping the naming the same as the old overloads, the format items in the format string are 0-based, so it makes sense that the parameter names match that. In that case, I'm guessing we'd want the naming of the generic type parameters to match the naming of the arguments:

So instead of this:

public static string Format<T>(string format, T arg);
public static string Format<T1, T2>(string format, T1 arg1, T2 arg2);
public static string Format<T1, T2, T3>(string format, T1 arg1, T2 arg2, T3 arg3);

This:

public static string Format<T0>(string format, T0 arg0);
public static string Format<T0, T1>(string format, T0 arg0, T1 arg1);
public static string Format<T0, T1, T2>(string format, T0 arg0, T1 arg1, T2 arg2);

Or maybe even TArgument0, TArgument1, and TArgument2 vs. T0, T1, and T2.

[weshaggard]

We did talk about the generic overloads on FormattableStringFactory as part of the review but we didn't believe we had enough runway to get the compiler to actually use those in this product release. (cc @gafter).

As for the string.Format overloads we did end up doing some work this release to make the arg0/arg1/arg2 overloads actually avoid the params array allocation internally (yeah until recently we didn't actually even optimize that even though we had the overloads). While we did do that one thing we realized is that string.Format is extremely bad about allocations internally and we don't believe that even eliminating the params array allocation ended up improving performance as much as we would have liked it to. I'm primarily saying that because I have to wonder if a few boxing allocations is really going to have much of an impact when what is really needed is a much larger redoing of the underlying formatting code (which I'm not sure is even possible in a compatible way). Do you have any data about whether or not eliminating these boxing allocations will end up helping much? By the way this doesn't mean these aren't worth adding I'm just trying to collect some more data.

[gafter]

The C# and VB compilers will use appropriate overloads on FormattableStringFactory if those exist. What we didn't have enough runway for was writing those overloads.

[pharring]

My experience is that the inner workings of string.Format (actually StringBuilder.AppendFormat) is quite efficient. The allocations are what you'd expect. Most of the time we get a hit in StringBuilderCache, so there's no char[] allocation.
Allocations in this area usually show up in serialization and logging routines. Serialization usually arrives via TextWriter.Write (which calls string.Format).
Removing the params array in 4.6 was nice.
Roslyn analyzers can help locate and eliminate boxing.

It would be interesting to see if one could implement this, avoiding boxing but at the same time avoiding stamping out 3 new generic versions of StringBuilder.AppendFormat.

[mattwarren]

Roslyn analyzers can help locate and eliminate boxing.

There's already an analyser that does this. The tricky part is keeping it up to date with the changes, for instance it currently doesn't handle the recent changes that got rid of unnecessary boxing in String.Concat. Probably the same applies for the change that removed params array allocations, that has been mentioned elsewhere in this thread.

The robust way to do this would be for it to look at the IL produced, but that's going to be expensive for an Analyser (although I did give it a go and Roslyn combined with Cecil makes it nice and easy).

[justinvp]

Do you have any data about whether or not eliminating these boxing allocations will end up helping much?

@weshaggard, I have some data in the conclusion below, but first some background...

Consider the following example:

DateTime now = DateTime.UtcNow;
Guid id = Guid.NewGuid();
decimal value = 3.50m;

string result = string.Format("{0:s} - {1:B}: The value is: {2:C2}", now, id, value);

Let's track of the allocations with the current implementation:

1. The now parameter is boxed.
2. The id parameter is boxed.
3. The value parameter is boxed.
4. A new StringBuilder is allocated to build-up the "s" (in "{0:s}") format string.
5. The actual "s" string is allocated.
6. The resulting string for now.ToString("s", null) is allocated.
7. A new StringBuilder is allocated to build-up the "B" (in "{1:B}") format string.
8. The actual "B" string is allocated.
9. The resulting string for id.ToString("B", null) is allocated.
10. A new StringBuilder is allocated to build-up the "C2" (in "{2:C2}") format string.
11. The actual "C2" string is allocated.
12. The resulting string for value.ToString("C2", null) is allocated.
13. The overall resulting string is allocated.

13 allocations!

Note that there's also a StringBuilder instance used for the overall resulting string that I left out of the allocation count as this allocation is mitigated by the use of the internal StringBuilderCache.

These allocations can be reduced significantly!

• A) Generic overloads would reduce this by 3, down to 10 allocations.
• B) There is some low-hanging fruit inside the String.Format (StringBuilder.AppendFormat) implementation that would avoid the StringBuilder allocations for the argument format strings, using string.Substring for the common case and falling back to a single StringBuilder instance only when necessary (more on this below), which would reduce the allocations by another 3, down to 7 allocations.
• C) Using an alternative design to IFormattable (even if just used internally for the built-in BCL types) could reduce this by another 6 allocations, down to just 1 allocation!

Down to just 1 allocation for the resulting string!

A) Generic overloads

Avoids the boxing allocations. Pretty straightforward.

B) Low-hanging fruit (avoiding/mitigating the internal StringBuilder allocations)

Right now with the current implementation, a new StringBuilder is allocated for each argument that has a format string associated with it (e.g. the "C2" in "{0:C2}"). This can be trivially improved by simply reusing the StringBuilder instance for multiple args. It involves just moving the StringBuilder variable to the top of the loop, still lazily allocating it, clearing it when finished, and reusing it for the next argument that needs it. However, even better, in the common case when there aren't any escaped braces in the argument's format string (e.g. "{{" and "}}") then a StringBuilder isn't needed at all; the more light-weight String.Substring can be used.

C) IFormattable alternative

Optimizing String.Format (StringBuilder.AppendFormat) is ultimately limited by the design of IFormattable, and to a lesser extent the less commonly used ICustomFormatter.

public interface IFormattable
{
    string ToString(string format, IFormatProvider formatProvider);
}

This design is perfectly reasonable, but there are a couple issues that prevent optimizations inside String.Format (StringBuilder.AppendFormat):

1. The format parameter is typed as string, which means an instance of string must be allocated for format, as opposed to accepting a StringSpan.
2. The result is a string, which means an instance of string must be allocated for the result, as opposed to appending the resulting characters to a destination StringBuilder.

An alternative design might look something like the following:

public interface IFormattableTo // (no pun intended, heh)
{
    void FormatTo(StringSpan format, IFormatProvider formatProvider, StringBuilder destination);
}

It may not be worth exposing such an interface publicly (at least for now) as it would basically be a replacement for IFormattable and it requires the StringSpan or Span<char> type, which hasn't landed yet. But it could be included as internal for now and implemented on all the built-in BCL types that currently implement IFormattable for improved String.Format perf for these very commonly used types.

[MikePopoloski]

Shameless plug of my own work: https://github.com/MikePopoloski/StringFormatter
Might be useful to mine for ideas.

I too needed string formatting without allocations. It'd be nice to take advantage of some of that dedicated code built into the CLR to make it faster, but it does alright on its own as pure C#.

[justinvp]

@terrajobst, Immo, this is an API suggestion. Could this be added to the agenda for an API review? Even if there's some opposition to the String and StringBuilder overloads, I think the FormattableStringFactory overloads are a no-brainer (would have been added for 4.6, but ran out of time).

[chintsan]

Hi Justin,
thanks for the explanation ans benchmarks.

how does one include the above overloads. i mean defining a new class "System" throws error - no body implementation for the overload methods or they arent defined as abstract, partial, extern etc.

[NickCraver]

I know it's been a while, but we'd love to see this over at Stack Overflow - @terrajobst can you please ping here when the API review is up next so we can listen in?

[terrajobst]

@justinvp

Could this be added to the agenda for an API review?

Generally yes, I believe with have everything we need. However, we're currently focusing on getting RTM ready, which means we're focusing our reviews on exposing APIs that already exist in .NET Framework to simplify porting as well as adding new APIs that are required to unblock other components and tools. That's why it's currently in the Future milestone. I hope that we'll be able to move some of these to a post-RTM milestone.

[AdamSpeight2008]

We could get the maximum .ToString() of most of core types. Eg .MaxValue.ToString.Length + 1

ApproxMaxCharLength<T>( obj : T ) : Int
{ 
  return match( typeof( T ) ) with
  {
    | string -> ((string)obj).Length; 
    |   bool ->  5; //  false
    |   byte ->  3; //  256
    |  sbyte ->  4; // -128
    |   char ->  1; // 
    | uint16 ->  6; //  65535
    |  int16 ->  6; // -32768
    | uint32 -> 11; // -2147483648 
    |  int32 -> 10; //  4294967295
    | uint64 -> 20; //  18446744073709551615
    |  int64 -> 20; // –9223372036854775808
    |    ... ->  0;
    // not done the floating point ones.
  }
}  

An initial first approximation of the string length, could be calculated thus.

var intialSize = args.Sum( ApproxMaxCharLength ) + TextOfFormatString.Length; 

I think this would be an over allocation. Note this is excluding any variation caused by the culture and additional alignment and format specifiers on the arg hole eg { x , -16 : X4 }

At which point (not done any deep analysis) would the extra processing to get a good estimate of the size of string to allocate, outweighs the processing cost of just blindly doing the building of the string?

[gafter]

@AdamSpeight2008 This issue is mainly about the allocations due to boxing.

[terrajobst]

The APIs look fine, however, the only way we could benefit from this work is if our implementation avoids the boxing all the way down, which would be non-trivial amount of work. Also, it's questionable without a benchmark how big the savings are, because formatting will probably cause a bunch of allocations anyway.

It might be better to leave these APIs as-is and instead use the new formatting APIs that @KrzysztofCwalina is working on.

@KrzysztofCwalina, what are your thoughts on this?

[NickCraver]

Remember that the benefits here are extreme because just by recompiling, you get them. That huge, free adoption should be factored into the effort costing. This helps all code, rather than just new code. I don't see string.Format() or $"" going anywhere for a long time.

Perhaps I'm missing something though - doesn't $"" continue to map to string.Format in future plans as well, or is that being re-pointed to some new API? That'd be a pretty extreme breaking change, but worth asking...

[gafter]

$"..." always maps to an invocation of string.Format (if the target type is string).

[KrzysztofCwalina]

I like the improvement in-place for the reson @NickCraver spells out. I think we should add these APIs.
The only concern I would have is that it might cause Generics instantiation explosion that runtime people are really concerned about lately. @jkotas?

BTW, the new formatting APIs @terrajobst mentioned are described at https://github.com/dotnet/corefxlab/wiki/System.Text.Formatting. But I think an in-place addition will be complementary.

[jkotas]

This should be data-driven decision. It is unclear to me whether saving extra allocations is worth it to justify the extra code in this case. String.Format will always allocate and it will always be relatively slow API. It is unclear to me whether changing it to allocate a bit less garbage at the cost of pile of extra code is going to measurable improve anything important.

[benaadams]

The trouble is string interpolation is too good a feature not to use, even for those of use that normally try to avoid allocations at all costs... (though normally used in lesser taken paths like exception handling)

[jkotas]

Agree. In the above @justinvp example, there 13 allocations. 9 of them are internal. It should be possible to eliminate all internal ones without changing the shape of the API, so that should be done first.

[karelz]

Next step: Improve current memory allocations of existing APIs as much as possible -- the result will tell us if we still need new APIs.

[NickCraver]

How would we ever eliminate the boxing here without the API additions? I agree with internal eliminations being the first step, but if we're after absolute performance, I don't see a way around the second step.

[jkotas]

we're after absolute performance, I don't see a way around the second step.

The no-allocation formatters being developed in corefxlab are going after absolute performance.

String.Format will always allocate the string. The string is likely short-lived garbage - it is unlikely that it is stored for long. I do not think that the difference between allocating a string vs. allocating a string and a box for each argument is going to be that significant.

[JonHanna]

(Aside regarding the original proposed API rather than the current discussion, would public static string Format<T>(string format, params T[] args); be useful or overkill? It's not rare to have to output a bunch of integers or a bunch of dates or otherwise format several items of the same type).

[NickCraver]

@jkotas I agree on String.Format(), but our much more common use case (localization in views, etc.) is on the StringBuilder.AppendFormat() side of the fence, which has more to win here overall. An example of this is in ASP.NET views, especially when we're doing localization.

Either way, we need to measure. The trouble is measuring this accurately means really doing it for comparison...to see if it's worth doing. Vicious circle we have here :)

[stephentoub]

@geeknoid, what are the advantages of that over my cited proposal? From a usability perspective, I'd prefer being able to write Foo($"Hi. My name is {name}, and my age is {age}.") rather than private static readonly StringFormatter s_nameFormat = new StringFormatter("Hi. My name is {0}, and my age is {1}."); ...; Foo(s_nameFormat.Format(name, age));, and I don't believe the proposed StringFormatter works well with spans, which can't be used as generic arguments. The cited proposal also similarly avoids all boxing (when the builder exposes an Append<T> or an Append method specific to the type), only allocates for the final string (if a string is even needed... a consumer could just access a span from the builder), etc., plus it not only precomputes the holes, but does so at compile time.

[davidfowl]

How do format specifiers work in your proposal @stephentoub ?

[stephentoub]

How do format specifiers work in your proposal @stephentoub ?

We'd define a pattern for Append methods, where the first argument is the thing to be formatted, if there's a second it's a format string, etc.

[geeknoid]

I've now added support for a Span-based TryFormat version which results in no allocations. This version is over 4x as fast as String.Format and induces no garbage. After 20 years, there's finally a formatting function in .NET that can compare in perf with C's sprintf :-)

Here are the benchmark results

|                      Method |     Mean |    Error |   StdDev |     Gen 0 |     Gen 1 |    Gen 2 |  Allocated |
|---------------------------- |---------:|---------:|---------:|----------:|----------:|---------:|-----------:|
|     TestClassicStringFormat | 46.02 ms | 0.865 ms | 1.515 ms | 2909.0909 | 1181.8182 | 363.6364 | 16800057 B |
|           TestInterpolation | 47.91 ms | 0.943 ms | 1.523 ms | 3000.0000 | 1250.0000 | 416.6667 | 16800523 B |
|         TestStringFormatter | 25.59 ms | 0.508 ms | 0.903 ms | 2187.5000 |  906.2500 | 281.2500 | 12000025 B |
| TestStringFormatterWithSpan | 10.86 ms | 0.182 ms | 0.224 ms |         - |         - |        - |        4 B |

[geeknoid]

@stephentoub The benefits to my proposal is that:

• It doesn't require any significant new patterns across types, it leverages IFormattable and ISpanFormattable
• I believe it is both smaller IL and faster than what you propose.
• The implementation exposes a span-based version which completely eliminates all allocations.
• It's fully implemented and can be played around with.
• It works with IFormatProvider like String.Format

I think the C# compiler can be taught about this type and magically generate the static StringFormatter instances for any use of string interpolation. Thus, existing code would just suddenly get faster by recompiling. Additionally, I think there could be a Roslyn code fixer which offers to convert any use of String.Format with a static format string into an interpolated string. Those cases would also then magically benefit from improved perf.

Also I think my implementation for a non-boxing version of the ParamsArray type could be used to eliminate boxing in existing APIs like String.Format, making those a touch faster too.

[En3Tho]

@geeknoid can you share benchmark code or link it please? While this is kinda off topic but I feel that there might be a way to make faster F# printf with things you're proposing.

[danmoseley]

@En3Tho looks like it's at https://github.com/geeknoid/FastFormatting

[stephentoub]

The benefits to my proposal is that

Thanks.

I believe it is both smaller IL and faster than what you propose.

I expect it would be smaller IL. I'm skeptical it'd be meaningfully faster for creating strings. And it would almost certainly result in more asm, in particular as every unique combination of arguments involving a value type would result in generic specialization for all of the generic pieces, and that's likely to be non-trivial; in contrast, with the builder approach, you only end up worst case with a generic-specialization per type formatted rather than per combination of types formatted.

The implementation exposes a span-based version which completely eliminates all allocations.

I agree the TryFormat aspect of it is nice. With the builder approach, you can get that as well, but it involves a copy.

In both approaches, it's also hard to claim all allocations are completely eliminated, as the moment you need to utilize IFormattable, you're likely incurring string allocations for each argument being formatted, only not when the instance is able to utilize a cached string.

I also don't see how the proposed approach supports arbitrary numbers of arguments without allocation. At some point you need one more argument than can be supported by the explicit strongly-typed overloads provided, and you end up with the params object[] overload. One of the nice things about the builder approach is it supports any number of arguments strongly-typed, as each argument is formatted independently with a single Append call.

It doesn't require any significant new patterns across types

This also hints at one of its biggest flaws IMO, but maybe you have a good solution for this. I think anything new we do in this space must support formatting ReadOnlySpan<char> as arguments. One of the nice things about the builder approach is this is easily supported just by having an Append(ReadOnlySpan<char>) overload on the builder. I don't see how this is easily supported in your proposal, as spans can't currently be used as generic arguments. How would you propose to support span being used as one or more of the arguments?

Also I think my implementation for a non-boxing version of the ParamsArray type could be used to eliminate boxing in existing APIs like String.Format, making those a touch faster too.

With the existing overloads? I don't see how, since the boxing is inherent to the existing APIs. It's also inherent to the existing implementation, which relies heavily on being able to pass the arguments around as object. If you're suggesting new generic string.Format overloads like those proposed in the very first post, that would also require plumbing that through the whole formatting implementation; I'd be interested in understanding what that implementation would look like, and similar to my previous comments, what impact that would have on bloating asm size in a typical apps (especially for AOT compilations, Blazor, Xamarin apps, etc., where presumably existing usage would start binding to the new more-strongly-typed overloads).

[geeknoid]

Yes, you've found all the flaws of the current implementation :-). Some more thoughts:

• It's only allocation-free up to 3 arguments. This could be extended to a larger number, but there's clearly an upper bound. With the way the API is designed, the first 3 arguments are captured in a strongly-typed fashion and the rest are in a params object?[]

• I made a specific point of keeping the code that has multiple generics as simple as possible. There is actually very little code in that regime, the generic code calls out ASAP to non-generic functions when possible. I learned my lesson about the impact of multi-generic types when we tried to implement a 4-parameter finger tree years ago. It was enormous! Anyway, I think the amount of code generated is within reason.

• Of course, if the implementation calls out to an IFormattable instance, an allocation will happen as a result. There's no getting around that given how IFormattable works. The code deals with all primitive types without boxing however. It would be good to make ISpanFormattable public so more types could implement it and improve formatting efficiency in general.

• My design works, today, in any version of .NET that supports Span without requiring any changes in the system. I think that makes it pretty compelling to adopt immediately given the substantial perf improvement it delivers.

• Don't underestimate the value of the 2x perf boost you get with TryFormat. This is huge. We have a lot of services that do a lot of string formatting and enabling them to be 0 alloc in the common case would likely lead to measurable COGs savings.

I can't think of a way to support ReadOnlySpan in my current design, just like it can't be supported by any of the existing formatting code in .NET. That doesn't make me too sad though. The solution there is to fix the GC to allow Span in the heap :-)

[geeknoid]

@stephentoub So what I've done in my stuff is three things:

• Extend ValueStringBuilder to support Append methods for the various primitive types. These overloads support argument formatting.

• Create the machinery to preparse a composite format strings to a dense form that can be interpreted faster during formatting and provide a formatting loop that leverages this.

• Implement a hack to prevent the params array allocation and boxing for the first 3 formatting arguments.

Exposing the extended ValueStringBuilder as a public type would be sufficient to implement the builder pattern you describe. String interpolation would immediately benefit. This could support all the normal formatting features (width, justification, etc)

Exposing ValueStringBuilder would make it possible for developers to implement 0-alloc string concatenation by supplying a span to the constructor of ValueStringBuilder. It's a bit clumsy, but it'll be quite fast.

To let developers do 0 alloc string formatting, then you can add the StringFormatter type with its TryFormat method. Or, you could get fancy and enhance string interpolation with new syntax such as:

Span<char> target = new Span<char>(new char[256]);
target <= $"Hello {name}"

This would let the C# compiler pass the span to the ValueStringBuilder constructor and voila, slick no-alloc string formatting.

[En3Tho]

That syntax is too vague in this case. Should it return bool and chars written, should it only return chars written and -1 in bad case, or should it completely hide details and just suddenly blow up with our of memory if anything goes wrong? I think that sticking to Method calls is better here.
Also, I think the problem here (as whole) is that you need a compiler support to make code as efficient as possible and the way of the builder seems better as it can be easily integrated to support any number of parameters and so on. But at the same time I can't really understand how builder will solve explicit Format calls. Like for example when you programmatically build format and then call the function.
@geeknoid while I think that making a specialized builder calls is probably better in case of known constant format and known arguments, maybe your approach could help the second case?

[geeknoid]

@stephentoub I've updated the design at https://github.com/geeknoid/FastFormatting. From the README:

• The StringMaker type is a supercharged version of the classic StringBuilder type. It
  is designed for efficiently building up a string or span by appending together bits and
  pieces. The implementation tries to avoid any memory allocations when it can, and if you
  supply your own span to the constructor, it can operate entirely without allocating memory.
  When used in this memory, totally performance is around 4x faster than using StringBuilder.

• The StringFormatter type is built on top of StringMaker and is designed to support the
  normal .NET composite formatting model, such as you use with String.Format. The type splits
  the normal formatting step in two in order to boost performance of the formatting process.
  The first step is parsing the composite format string into an efficient form. This step is done
  by create a StringFormatter instance. Once you have this instance, you can use it to format
  a set of arguments by calling the Format method, which is about 2x as fast as String.Format.
  You can also use the TryFormat method to format directly into your own span, which is 4x faster
  than String.Format.

This new code maintains the same perf characteristics as I had previously. The code has nearly 100% code coverage and compatibility with classic String.Format semantics is explicitly tested for.

I think StringMaker can be used directly by the C# compiler to implement efficient interpolation with a single allocation for the final string. Some magic C# syntax can also enable 0 allocation by outputting to an existing span. The StringFormatter type on its side is useful as a faster replacement of String.Format for when interpolation is not an option (for localized text for example).

How's that sound?

[geeknoid]

Latest perf tests. These are all trying to format the same set of inputs and produce the same final string:

|                      Method |      Mean |     Error |    StdDev |     Gen 0 |     Gen 1 |    Gen 2 |  Allocated |
|---------------------------- |----------:|----------:|----------:|----------:|----------:|---------:|-----------:|
|     TestClassicStringFormat | 44.866 ms | 0.8916 ms | 1.4897 ms | 3000.0000 | 1250.0000 | 416.6667 | 16800539 B |
|           TestInterpolation | 45.272 ms | 0.8490 ms | 1.5524 ms | 3000.0000 | 1250.0000 | 416.6667 | 16800515 B |
|           TestStringBuilder | 49.877 ms | 0.9750 ms | 1.3016 ms | 2888.8889 | 1111.1111 | 333.3333 | 16800055 B |
|         TestStringFormatter | 25.101 ms | 0.5015 ms | 0.9170 ms | 2187.5000 |  906.2500 | 281.2500 | 12000022 B |
| TestStringFormatterWithSpan |  9.574 ms | 0.1785 ms | 0.1490 ms |         - |         - |        - |        4 B |
|             TestStringMaker |  7.308 ms | 0.1203 ms | 0.1564 ms | 2859.3750 |         - |        - | 11999924 B |
|     TestStringMakerWithSpan |  5.043 ms | 0.0988 ms | 0.1832 ms |         - |         - |        - |        2 B |

[stephentoub]

I think StringMaker can be used directly by the C# compiler to implement efficient interpolation with a single allocation for the final string

Isn't StringMaker essentially just ValueStringBuilder, and basically the same builder approach I was proposing? The only thing that differs is I was suggesting a pattern in addition, but that's just to enable additional scenarios, namely an API that wants to take a particular builder so as to a) have raw access to its underlying buffer and b) have control over the Append methods exposed so as to have more control over the formatting. But we'd have a built-in implementation of it that the compiler could use when targeting string, such that existing string interpolation just go more efficient in its implementation without semantic changes. So, I'm not clear on fundamentally what's different here? (Note that if we do go with such an approach, such a type would likely live in the compiler services namespace, and would be discouraged for general direct use: in general we're wary of exposing structs that wrap pooled resources, even if ref structs, that would make it easy to accidentally copy them and dispose multiple times, double-freeing a buffer.)

The StringMaker type is a supercharged version of the classic StringBuilder type.

As noted above, this seems like it's just ValueStringBuilder. If from an implementation perspective there are things you've done in your implementation that you've found to be more efficient, please feel free to submit a PR to improve ValueStringBuilder's implementation / reduce its overheads.

How's that sound?

I think you're now proposing two separate things:

1. Basically what I proposed (waving hands at minor API-level differences here and there)
2. In addition a separate StringFormatter class, with the primary goals of a) supporting the existing .NET formatting model pre-interpolated strings but with as much precomputed as possible and with generic arguments and b) exposing a TryFormat.

Am I understanding correctly?

[stephentoub]

ps I'm on a stay-cation now and will be slow to respond until the new year. Thanks, and happy holidays.

[geeknoid]

@stephentoub Yes, that is correct. A layered model with a builder pattern and a composite format string formatter built on top.

Indeed, StringMaker exposes the builder pattern that you suggested. I realized that my original StringFormatter could easily be cleaved into two parts. One being a builder, and the other being the preprocessed string formatting functionality. And as you can see from the benchmarks, you were totally right that the builder pattern is faster at runtime. Makes sense, since StringFormatter is extra crap on top of the builder and is thus slower.

StringMaker is based on the same principle as ValueStringBuilder, but it is different in a few ways:

• It is a more specialized type designed strictly for high-speed append operations.
• It has a large selection of Append methods to address all primitive types without boxing.
• Some of the Append overloads support (string format, int width, IFormatProvider?) arguments, making them suitable to implement a full fidelity replacement for all the String.Format formatting features. This is needed for the C# compiler use case.
• It supports the TryFormat pattern such that dynamically reallocation of the buffer is blocked, ensuring no allocs occur.

I think as it is, the StringMaker type can handle random types efficiently:

• If a type implements ISpanFormattable, it should just work, without boxing by virtue of the Append overload.
• If a type implements IFormattable, it would be boxed beforehand.
• Alternatively, the C# compiler could automatically detect extension methods against StringMaker which follow the TryFormat pattern and generate calls to those extension methods automatically.

In the common case, the C# compiler should be able to use the 0-alloc variant of StirngMaker and deliver a near optimal formatting experience. The only thing better would be if the compiler support syntax to do interpolation into an existing span.

[stephentoub]

Sorry for the delay, @geeknoid.

It is a more specialized type designed strictly for high-speed append operations.
It has a large selection of Append methods to address all primitive types without boxing.
Some of the Append overloads support (string format, int width, IFormatProvider?) arguments, making them suitable to implement a full fidelity replacement for all the String.Format formatting features. This is needed for the C# compiler use case.

Yes, all of those are part of productizing a ValueStringBuilder-like type for the purposes of a C#-based string interpolation target. We've been saying "ValueStringBuilder" just because it's the general approximation of what's needed. There are other aspects of it that would differ as well; as noted, for example, we would likely want to hide it away in System.Runtime.CompilerServices and with some less appealing name to highlight that it's a relatively dangerous type to use directly (as is any struct that rents/returns arrays from a global pool that others use).

I spoke about all of this with @jaredpar last week, and it's definitely something he's interested in pushing ahead, but I don't know if it'll make C# 10 or not. For me, this is really about the C# language feature being made more efficient rather than it being about a type a developer can use directly, though if someone wanted to directly use something from System.Runtime.CompilerServices, of course they could (we would need to decide whether to support the TryFormat approach even if it wasn't going to be used by the compiler). I think the 90% case here is just enabling:

string result = $"A={a} B={b}";

to efficiently generate that string. This does bump up against something we'll need to solve, though, which is how does the compiler get the stack space to use to seed the ValueStringBuilder, or is it forced to always use a rented buffer. In other words, it'd be nice if the compiler could generate for the above something like:

var vsb = new ValueStringBuilder(stackalloc char[SomethingReasonable]);
vsb.Append("A=");
vsb.Append(a);
vsb.Append(" B=");
vsb.Append(b);
string result = vsb.ToString();

but it's not clear at present exactly what it should do for SomethingReasonable. We could pick an arbitrary small-ish number that should generally be ok, and it could use that same stackalloc for other interpolations in the same method, and hoist it out of loops to ensure we don't overflow, but all that needs to be worked out. Or we could start by just always using rented space:

ValueStringBuilder vsb = default;
vsb.Append("A=");
vsb.Append(a);
vsb.Append(" B=");
vsb.Append(b);
string result = vsb.ToString();

[geeknoid]

@stephentoub thanks for the feedback.

Improving the interpolated string perf is key, but I think strictly focusing on that use case is missing other significant opportunities for perf gains.

As I mentioned above, there are two other key scenarios I'm enabling here:

• A direct replacement for String.Format which is fully compatible and 2x the perf. If you use spans and other options, it can get considerably faster still. But as a drop-in replacement, you get direct benefits. String builder is still useful as it supports localized string substitution.

• A slightly more complicated model that delivers yet more performance. Users create a StringFormatter object by passing a format string, and then repeatedly reuse this object to format text. This eliminates the redundant and expensive format string parsing that normally occurs every time a string is formatted. For hot paths, it takes only a few minutes to adopt to this pattern and you get instant speed up.

I'm content to deploy these technologies within our broad team and reap the benefits, but I would rather these improvements be rolled into .NET proper so that everyone can benefit. Just point me in the right direction...

[stephentoub]

I would rather these improvements be rolled into .NET proper so that everyone can benefit

Until something else happens, you can of course ship a nuget package that anyone can use :)

[jaredpar]

I spoke about all of this with @jaredpar last week, and it's definitely something he's interested in pushing ahead, but I don't know if it'll make C# 10 or not

For the interpolated string case I feel very good about the C# 10 chances assuming that runtime has the bandwidth to get the ValueStringBuilder type into .NET 6 as well.

but I think strictly focusing on that use case is missing other significant opportunities for perf gains.

This is the only part that makes me hesitate a bit. If we feel like interpolated strings can be solved independently of other string formatting issues then I'd actually hoped to move forward rather soon. If we think they're related though then we'll need to push forward with the other design points before the C# work.

Or we could start by just always using rented space:

This is the starting point I would prefer. There are several types which would benefit from the use case of "pass me a pre-allocated Span I can use as an initial buffer". One other case was a FrugalList<T> style implementation of @geeknoid. That feels like something we should generalize and can push back into ValueStringBuilder at a later time.

Alternatively if it helps the compiler could also pass some additional info to the constructor. For example it can give the length of the constant part of the string plus the number of arguments if that would be beneficial to ValueStringBuilder (swear that was already brought up in this thread, but having trouble finding it).

[stephentoub]

FWIW, I do like the additional support of being able to a) TryFormat the result of string interpolation rather than always going into a string, and b) being able to seed the builder with the destination output buffer so that there's no additional copying needed. For (a), I could imagine us implementing that for string interpolation where the compiler transforms something like:

bool success = $"A={a} B={b}".TryFormat(span, out int charsWritten);

into code like:

var vsb = new ValueStringBuilder();
vsb.Append("A=");
vsb.Append(a);
vsb.Append(" B=");
vsb.Append(b);
bool success = vsb.TryFormat(span, out int charsWritten);

And for (b), I could imagine us implementing that for string interpolation where the compiler transformed that same example into something along the lines of:

charsWritten = 0;
var vsb = new ValueStringBuilder(span, ref charsWritten);
bool success =
    vsb.TryFormat("A=") &&
    vsb.TryFormat(a) &&
    vsb.TryFormat(" B=") &&
    vsb.TryFormat(b) &&
    vsb.TryComplete();

[geeknoid]

@jaredpar As written, you can use my StringMaker type (a.k.a. ValueStringBuilder per your name) independent of the other layers. The StringFormatter type I've got defined is an independent thing that uses StringMaker in its implementation. So it's easy to peal off StringMaker and use that directly.

[stephentoub]

Just to circle back, @333fred has a spec that we're moving forward with that enables something very similar to what I outlined in #14484 (comment) and #14484 (comment). He can share the details when he's ready, but I think folks will be happy.

[333fred]

I was just submitting a PR with the spec: dotnet/csharplang#4486.

Edit: fixed link.

[teo-tsirpanis]

The interpolated string handlers feature in .NET 6 is much more flexible, usable and performant than these proposed APIs. I'm going to close this issue, please correct me if I'm wrong.