CODEWITHSUNDEEP
c#.netstringoptimizationstringbuilder
Maxim Zhukov
Maxim Zhukov

Reputation: 10140

Ways to improve string memory allocation

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.

Upvotes: 2

Views: 2510

Answers (5)

fbf
fbf

Reputation: 163

You can also try putting things on the stack where it makes sense.

public void StaircaseSpan()
    {
        Span<char> characters = stackalloc char[n];
        characters.Fill(' ');
        var rows = new string[n];

        for (int i = n - 1; i >= 0; i--)
        {
            characters[i] = '#';
            rows[i] = characters.ToString();
        }
    }

n=3

|          Method |     Mean |    Error |   StdDev |   Gen0 | Allocated |
|---------------- |---------:|---------:|---------:|-------:|----------:|
|   StaircaseSpan | 33.26 ns | 0.161 ns | 0.151 ns | 0.0688 |     144 B |
| StaircaseString | 67.98 ns | 0.494 ns | 0.438 ns | 0.1223 |     256 B |

n=8

|          Method |      Mean |    Error |   StdDev |   Gen0 | Allocated |
|---------------- |----------:|---------:|---------:|-------:|----------:|
|   StaircaseSpan |  85.79 ns | 0.940 ns | 0.880 ns | 0.1950 |     408 B |
| StaircaseString | 209.93 ns | 0.499 ns | 0.417 ns | 0.4170 |     872 B |

Upvotes: 1

Peter B
Peter B

Reputation: 24136

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.

Upvotes: 2

GSerg
GSerg

Reputation: 78134

StringBuilder is always an answer when it comes to string allocations; I'm sure you know that so apparently you want something else. Well, since your strings are all the same length, you can declare a single char[] array, populate it every time (only requires changing one array element on each iteration) and then use the string(char[]) constructor:

public static string[] staircase(int n)
{
    char[] buf = new char[n];
    string[] result = new string[n];

    for (var i = 0; i < n - 1; i++)
    {
        buf[i] = ' ';
    }

    for (var i = 0; i < n; i++)
    {
        buf[n - i - 1] = '#';
        result[i] = new string(buf);
    }

    return result;
}

Upvotes: 1

Canica
Canica

Reputation: 2738

You can project your desired results using the Linq Select method. For example, something like this:

public static string[] staircase(int n) {
    return Enumerable.Range(1, n).Select(i => new string('#', i).PadLeft(n)).ToArray();
}

Alternate approach using an int array:

public static string[] staircase(int n) {
    return (new int[n]).Select((x,i) => new string('#', i+1).PadLeft(n)).ToArray();
}

HTH

Upvotes: 1

D Stanley
D Stanley

Reputation: 152501

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.

Upvotes: 3

Related Questions