Improve codegen for concatenation of `string` and `char` (attempt 2)

[DoctorKrolic]

trafficstars

Closes https://github.com/dotnet/roslyn/issues/66827

This PR takes approach suggested in https://github.com/dotnet/roslyn/pull/70971#issuecomment-1886329321 by @AlekseyTs with some implementation details chaged. E.g. it turned out is's easier to handle constantChar.ToString() pattern in ConvertConcatExprToString rather than in TryFoldTwoConcatOperands and so on. ~~Also this PR implements merging user-provided span-based string.Concat with additional concatenation arguments, which was not described in the original proposal.~~ And @AlekseyTs I have a question for you regarding item 1 in your proposal: the suggestion looks reasonable but it seems to me that it is related not to our case of concatenation of strings and chars, but rather can be treated as a general optimization. If I am wrong, can you please provide an example of a unit test, which is related to the theme of the PR and where codegen can be improved by that change? I am of course open for implementing new optimizations, but this PR is quite big on its own, so if that optimization is not directly related to the main theme, maybe it's better to implement in a later PR rather than in this one

[AlekseyTs]

public void ConcatTwo_ConstantCharToString(int? missingUnimportantWellKnownMember)

Is it important to try them one by one, or could we simply mark them all missing in one go? #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:312 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

          IL_0001:  ldstr      "c"

Is it really better to not go with the span approach, use extra space in the string blob of the assembly image, and then allocate the string at runtime? #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:348 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

public void ConcatTwo_ConstantCharToString(int? missingUnimportantWellKnownMember)

I guess trying one by one doesn't hurt, but I would also add a flavor when all of them are missing together.

---

In reply to: 1912258587

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:312 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

          IL_0001:  ldstr      "c"

Looking at ConcatThree_ReadOnlySpan_OperandGroupingAndUserInputOfStringBasedConcats, it appears that if we have a constant, we allocate a string, but, if we have a parameter, we use spans. This behavior feels suspicious to me. #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:1134 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

          IL_0008:  call       "string string.Concat(string, string, string, string)"

I am surprised the span overload is not used when it is available along with necessary conversion helpers. For other methods as well. Probably there is a problem with decomposing/composing the arguments. I haven't looked at the implementation yet. #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:2503 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

          IL_0008:  call       "string string.Concat(string, string, string, string)"

Perhaps this is the same issue with "premature char to string conversion", which could probably be mitigated by going from a single character string constant back to char when we look at the decomposed arguments.

---

In reply to: 1912464476

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:2503 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

    // but in the second case we leave things untouched. Both lowerings produce correct output in the end, so this isn't much to worry about

~~I am not comfortable with this inconsistency. I think we should have a simpler approach, we either unwrap things, or we don't. The order of processing shouldn't matter. ~~ #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:4480 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[AlekseyTs]

    // but in the second case we leave things untouched. Both lowerings produce correct output in the end, so this isn't much to worry about

After a closer look, I changed my mind.

---

In reply to: 1912530749

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:4480 in e4e26f1. [](commit_id = e4e26f1e80639d3894cbd0405ded29a61ac0f4e9, deletion_comment = False)

[DoctorKrolic]

Is it important to try them one by one, or could we simply mark them all missing in one go?

I guess trying one by one doesn't hurt, but I would also add a flavor when all of them are missing together.

Are you ok if I replace existing tests, where we test positive scenarios with missing unimportant members 1 by 1 with equivalent ones, but where all unimportant members are missing? I agree that tests where all members are missing are better (since this is basically a real-life scenario on old target frameworks like .NET Framework), but new test file is already 4500+ lines long, so adding such tests on top of what we have will make things even harder to follow.

Is it really better to not go with the span approach, use extra space in the string blob of the assembly image, and then allocate the string at runtime?

Looking at ConcatThree_ReadOnlySpan_OperandGroupingAndUserInputOfStringBasedConcats, it appears that if we have a constant, we allocate a string, but, if we have a parameter, we use spans. This behavior feels suspicious to me.

Perhaps this is the same issue with "premature char to string conversion", which could probably be mitigated by going from a single character string constant back to char when we look at the decomposed arguments.

Compiler can take advantage of the fact, that constantChar.ToString() will always become a constant string when evaluated, so it lowers it to a constant string at compile time. I am not sure what is your concern here: it would take far more bytes in IL to use span-based lowering than just directly emitting a string and using string-based concat. In fact, performance of string-based approach is slightly better than using spans.

Benchmark

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22621.3007/22H2/2022Update/SunValley2)
AMD Ryzen 7 5800X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 8.0.200-preview.23624.5
  [Host]     : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2


| Method         | Length | Mean      | Error     | StdDev    | Gen0   | Allocated |
|--------------- |------- |----------:|----------:|----------:|-------:|----------:|
| UseConstString | 1      |  6.761 ns | 0.0462 ns | 0.0432 ns | 0.0019 |      32 B |
| UseSpan        | 1      |  7.667 ns | 0.0188 ns | 0.0157 ns | 0.0019 |      32 B |
| UseConstString | 1000   | 61.349 ns | 0.7080 ns | 0.5912 ns | 0.1209 |    2024 B |
| UseSpan        | 1000   | 62.136 ns | 0.8843 ns | 0.7839 ns | 0.1209 |    2024 B |

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<Benchmarks>();

[MemoryDiagnoser]
public class Benchmarks
{
    private string _s;

    [Params(1, 1000)]
    public int Length { get; set; }

    [GlobalSetup]
    public void Setup() => _s = new string('s', Length);

    [Benchmark]
    public string UseConstString() => M1(_s);

    [Benchmark]
    public string UseSpan() => M2(_s);

    private static string M1(string s) => string.Concat("a", s);

    private static string M2(string s)
    {
        char ch = 'a';
        return string.Concat(new ReadOnlySpan<char>(in ch), s);
    }
}

If you worry that we take space in string blob, than I don't think it matters. Just think about it: it took a decade of development and a project filled to the brim with IL baselines to reach string blob size limitation in only 1 project in the whole roslyn. An avarage developer would probably never face this error in his professional life at all. We save far more space in IL bytes by lowering that char to string than we can potentially save from a string blob.

[AlekseyTs]

If you worry that we take space in string blob, than I don't think it matters. Just think about it: it took a decade of development and a project filled to the brim with IL baselines to reach string blob size limitation in only 1 project in the whole roslyn. An avarage developer would probably never face this error in his professional life at all. We save far more space in IL bytes by lowering that char to string than we can potentially save from a string blob.

I prefer to have consistent/uniform handling for chars, whether they are constants or not. If I was working on the lowering from scratch, I wouldn't have an intention to treat them differently in scenarios like that. And I am going to speculate that this PR ended up there by accident, not by implementing some specific plan. Given that, I suggest unifying the handling. #Closed

[DoctorKrolic]

I prefer to have consistent/uniform handling for chars, whether they are constants or not.

That is already not the case - compiler understands constant chars and lowers them to constant strings to avoid calling char.ToString(). I just extended compiler's abilities, so it can also understand constantChar.ToString() and do the same thing. TBH I did this mostly because this was one of points in your original proposal, I feel like this is logically another optimization, not much related to the span lowering. So I suggest the following: I revert code chages, which makes this happen, but keep tests, which show codegen for these cases (and change them to satisfy new lowering ofc). Then after this PR is merged I can make a follow-up with this change alone, so we will clearly see what benifits it brings

[AlekseyTs]

I stopped reviewing implementation changes at iteration 15. I suggest simplifying it and following the suggested strategy more closely. #Closed

[AlekseyTs]

compiler understands constant chars and lowers them to constant strings to avoid calling char.ToString(). I just extended compiler's abilities, so it can also understand constantChar.ToString() and do the same thing. TBH I did this mostly because this was one of points in your original proposal, I feel like this is logically another optimization, not much related to the span lowering.

I think you are missing the point, I am not against understanding constantChar.ToString() am against leaving them as string literals when a span based approach on an original char can be used.

So I suggest the following: I revert code chages, which makes this happen, but keep tests, which show codegen for these cases (and change them to satisfy new lowering ofc). Then after this PR is merged I can make a follow-up with this change alone, so we will clearly see what benifits it brings

If you are suggesting revering a change in ConvertConcatExprToString that converts constantChar.ToString calls to a string literal, then I do not agree with this suggestion. Obviously added tests should be kept regardless. I think the unification that I am concerned about can be achieved with a simple change elsewhere. I think I will be able to point that place once suggested simplifications to the implementation are made. How about the following plan? Keep handling of the literals as is for now. Focus on the other suggestions. Once we reach a good state with them, I will suggest the "mitigation" that I have in mind. At that time we can see if both changes together (the conversion and the "mitigation") have an impact observable through the tests. Based on the nature of the impact, if any, we will decide whether we want to keep them, or revert them both. #Closed

[AlekseyTs]

I have a question for you regarding item 1 in your proposal: the suggestion looks reasonable but it seems to me that it is related not to our case of concatenation of strings and chars, but rather can be treated as a general optimization. If I am wrong, can you please provide an example of a unit test, which is related to the theme of the PR and where codegen can be improved by that change? I am of course open for implementing new optimizations, but this PR is quite big on its own, so if that optimization is not directly related to the main theme, maybe it's better to implement in a later PR rather than in this one

I am not ready to give the final answer to this question yet. It is quite possible that the concern I had is actually handled by TryExtractStringConcatArgs when it digs through a null-coalescing operator. So, don't implement the suggestion just yet. I will reevaluate its necessity later. #Closed

[DoctorKrolic]

@AlekseyTs You missed one of my questions from https://github.com/dotnet/roslyn/pull/71793#issuecomment-1914543738:

Is it important to try them one by one, or could we simply mark them all missing in one go?

I guess trying one by one doesn't hurt, but I would also add a flavor when all of them are missing together.

Are you ok if I replace existing tests, where we test positive scenarios with missing unimportant members 1 by 1 with equivalent ones, but where all unimportant members are missing? I agree that tests where all members are missing are better (since this is basically a real-life scenario on old target frameworks like .NET Framework), but new test file is already 4500+ lines long, so adding such tests on top of what we have will make things even harder to follow.

[AlekseyTs]

Are you ok if I replace existing tests, where we test positive scenarios with missing unimportant members 1 by 1 with equivalent ones, but where all unimportant members are missing? I agree that tests where all members are missing are better (since this is basically a real-life scenario on old target frameworks like .NET Framework), but new test file is already 4500+ lines long, so adding such tests on top of what we have will make things even harder to follow.

The answer really depends on the implementation, and I haven't had a chance diving into it to the point of making definitive decision. I suggest keeping the tests as is for now. If in the future I will feel like additions/changes are warranted, I will respond to the original thread #Closed

[AlekseyTs]

Done with review pass (commit 20) #Closed

[AlekseyTs]

Done with review pass (commit 21). The implementation changes are not fully reviewed, pending the suggested simplification. #Closed

[DoctorKrolic]

Yes, a bunch of work needs to be done here, I'll explicitly request review from you when this is ready

[AlekseyTs]

Done with review pass (commit 24) #Closed

[AlekseyTs]

        }

I think the problem with definition of new well known string members can be observed by adding a unit test like this one, but with ReadOnlySpan defined in this source. Please add a test like that, I suspect the optimization will be disabled in that case. #Closed

---

Refers to: src/Compilers/CSharp/Test/Emit2/CodeGen/CodeGenSpanBasedStringConcatTests.cs:34 in 53c529f. [](commit_id = 53c529f352acc3c0e070c8aff2ed937270f1b6ba, deletion_comment = False)

[AlekseyTs]

Done with review pass (commit 32) #Closed

[AlekseyTs]

Done with review pass (commit 36) #Closed

[AlekseyTs]

Done with review pass (commit 42). The CI failures are likely due to issues in CI infrastructure. #Closed

[DoctorKrolic]

I think the problem with definition of new well known string members can be observed by adding a unit test like this one, but with ReadOnlySpan defined in this source. Please add a test like that, I suspect the optimization will be disabled in that case.

ReadOnlySpan is used in definitions of all span-based string.Concats, thus it must be declared in the same assembly as System.String. If I try to redefine ReadOnlySpan in "user" source, I expectedly get an error saying that such type is already defined. How is your suggestion possble to implement then?

[AlekseyTs]

I think the problem with definition of new well known string members can be observed by adding a unit test like this one, but with ReadOnlySpan defined in this source. Please add a test like that, I suspect the optimization will be disabled in that case.

If I try to redefine ReadOnlySpan in "user" source, I expectedly get an error saying that such type is already defined.

A simple fact of defining any type in a user assembly should not cause an error on itself. I can see how some scenarios might get broken because of that. I cannot comment on errors you expect and you get unless you "show" what you are trying to do.

How is your suggestion possble to implement then?

It is always possible to add a test, whether the behavior matches expectations is another story. At the moment I am asking about a test. I am not making any suggestions how to change implementation yet. #Closed

[AlekseyTs]

/azp run

[azure-pipelines[bot]]

Azure Pipelines successfully started running 2 pipeline(s).

[AlekseyTs]

Done with review pass (commit 43) #Closed

[AlekseyTs]

Done with review pass (commit 45) #Closed