Ways to improve string memory allocation

Question

This question is more theoretical than practical, but still.

I've been looking for a chance to improve the following code from the string memory allocation standpoint:

/* Output for n = 3:
*
*  '  #'
*  ' ##'
*  '###'
*
*/
public static string[] staircase(int n) {
    string[] result = new string[n];

    for(var i = 0; i < result.Length; i++) {
        var spaces = string.Empty.PadLeft(n - i - 1, ' ');
        var sharpes = string.Empty.PadRight(i + 1, '#');

        result[i] = spaces + sharpes;
    }

    return result;
}

PadHelper is the method, that is eventually called under the hood twice per iteration.

So, correct me if I'm wrong, but it seems like memory is allocated at least 3 times per iteration.

Any code improvements will be highly appreciated.

Answer 1

how about:

result[i] = new string('#',i).PadLeft(n)

?

Note that this still allocates two strings internally, but I honestly don't see that as a problem. The garbage collector will take care of it for you.

Answer 2

You can save on both allocations and speed by starting with a string that contains all the Spaces and all the Sharpes you're ever going to need, and then taking substrings from that, as follows:

public string[] Staircase2()
{
    string allChars = new string(' ', n - 1) + new string('#', n); // n-1 spaces + n sharpes

    string[] result = new string[n];
    for (var i = 0; i < result.Length; i++)
        result[i] = allChars.Substring(i, n);

    return result;
}

I used BenchmarkDotNet to compare Staircase1 (your original approach) with Staircase2 (my approach above) from n=2 upto n=8, see the results below.

It shows that Staircase2 is always faster (see the Mean column), and it allocates fewer bytes starting from n=3.

|     Method | n |        Mean |      Error |     StdDev | Allocated |
|----------- |-- |------------:|-----------:|-----------:|----------:|

| Staircase1 | 2 |   229.36 ns |  4.3320 ns |  4.0522 ns |      92 B |
| Staircase2 | 2 |    92.00 ns |  0.7200 ns |  0.6735 ns |     116 B |

| Staircase1 | 3 |   375.06 ns |  3.3043 ns |  3.0908 ns |     156 B |
| Staircase2 | 3 |   114.12 ns |  2.8933 ns |  3.2159 ns |     148 B |

| Staircase1 | 4 |   507.32 ns |  3.8995 ns |  3.2562 ns |     236 B |
| Staircase2 | 4 |   142.78 ns |  1.4575 ns |  1.3634 ns |     196 B |

| Staircase1 | 5 |   650.03 ns | 15.1515 ns | 25.7284 ns |     312 B |
| Staircase2 | 5 |   169.25 ns |  1.9076 ns |  1.6911 ns |     232 B |

| Staircase1 | 6 |   785.75 ns | 16.9353 ns | 15.8413 ns |     412 B |
| Staircase2 | 6 |   195.91 ns |  2.9852 ns |  2.4928 ns |     292 B |

| Staircase1 | 7 |   919.15 ns | 11.4145 ns | 10.6771 ns |     500 B |
| Staircase2 | 7 |   237.55 ns |  4.6380 ns |  4.9627 ns |     332 B |

| Staircase1 | 8 | 1,075.66 ns | 26.7013 ns | 40.7756 ns |     620 B |
| Staircase2 | 8 |   255.50 ns |  2.6894 ns |  2.3841 ns |     404 B |

This doesn't mean that Staircase2 is the absolute best possible, but certainly there is a way that is better than the original.