2
\$\begingroup\$

As a beginner, I tried a programming drill. The method gets an Enumerable that contains numbers specifying how many "*" to print on each line.

public static void PrintStars(IEnumerable<int> neverEndingListOfInt)
{
    foreach (int item in neverEndingListOfInt)
    {
        Console.WriteLine(SetStars(item));
    }
}
private static string SetStars(int numberOfTimes)
{
    return string.Concat(Enumerable.Repeat("*", numberOfTimes));

}

I have another version here:

public static void PrintStars(IEnumerable<int> neverEndingListOfInt)
{

    foreach (int item in neverEndingListOfInt)
    {
        for (int i = 0; i < item; i++)
        {
            Console.Write("*");
        }
        Console.WriteLine();

    }
}

What impact on the GC will creating so many strings have? Which way is more efficient, and how would you prefer to do it?

\$\endgroup\$
3
\$\begingroup\$

I don't consider myself an expert when it comes to the internals of .NET's garbage collector, but as far as I understand:

  • Write("*") benefits from string interning, so there should be little to no GC overhead (other than what Write does internally, of course). However, Write has to be called for every single character, and that call overhead makes it (significantly) slower.
  • The WriteLine variant does allocate strings (among other things), so the GC will have to run more often. Whether that has any significant impact on performance is something you'll have to measure, but it's normally not something you need to worry about.
  • new string('*', numberOfTimes) is more efficient (both in terms of speed and in terms of allocations) than string.Concat(Enumerable.Repeat("*", numberOfTimes)).
  • You may run into different kinds of issues if you allocate a lot of very large objects (larger than 85.000 bytes), due to how the Large Object Heap works. But that's probably not relevant in this case.

Note that new .NET releases occasionally contain GC improvements, so while the general principles are probably fairly static, implementation details will change over time.

\$\endgroup\$
2
\$\begingroup\$

Use a single buffer

It seems (on my computer, at least) that the overhead of creating lots of strings way less important than the overhead of repeated calls to Console.Write(). However, we can pretty much get the best of both worlds by using a buffer of stars, and using the Console.WriteLine(char[] buffer, int index, int count) overload: create one big string (buffer) and just read as much as we need each time.

Code

public static void PrintStars5(IEnumerable<int> neverEndingListOfInt)
{
    char[] buffer = new char[1];

    foreach (int item in neverEndingListOfInt)
    {
        if (item > buffer.Length)
        { // increase size of buffer
            int c = buffer.Length;
            while (c < item)
            {
                c *= 2; // double size
            }
            buffer = new string('*', c).ToCharArray();
        }

        Console.WriteLine(buffer, 0, item);
    }
}

Benefits

  • Only one call to WriteLine() per item

  • Number of allocations (in our code) is logarithmic with respect to the largest item (not a function of the number of items)

  • Uses no-more than four as much memory as your solution.

Evidence

Here is a graph showing some time-measurements of 2 different methods on different sets of uniformly distributed numbers (warning: butchered log/log plot):

enter image description here

The x-axis the type of IEnumerable<int>: Acc<n> means count up to n, Dec<n> means count down from n, Rnd<n> means produce n random numbers in the range [0,n].

It shows what appears to be this 'buffered' method outperforming your first solution (with string.ctor(char, int) fix, as suggested by others) for longer/more strings.

It is interesting to see just how well string.ctor(char, int) performs. It is an externed function, which helps, but as the strings get longer, I would expect the buffering to pay off more and more.

The graph shouldn't be wholly convincing (if I could be bothered to leave it running for a while longer, we might see the buffered method really paying off for larger and more numbers. You should absolutely ignore the results for small n. Each data point is the total time taken for 100 repeats (shuffled every 10). I apologise for how terrible the plot styling is, I don't know how to use spread sheet software.

Caveats

Though I don't doubt that buffering is the way to go for this toy problem, it should be noted that although Console.Write methods were 2 orders of magnitude slower (on my machine) than the stringy methods (they aren't plotted because I gave up waiting for them), this won't apply to other streams. Note: I ran the code under release, piping stdout to nul, which I'd have thought would minimise the overhead in Console.Write, but I don't really know

Again, this is how this thing ran on my computer, it could well be different for you, and you shouldn't attempt to make general inferences from these results (or any results on such a contrived problem).

\$\endgroup\$
  • \$\begingroup\$ Have you used Excel for the graph or is there a secret tool for that? ;-] \$\endgroup\$ – t3chb0t Feb 2 '18 at 23:29
  • \$\begingroup\$ @t3chb0t I either use OxyPlot or (as in this case) INSERT INSTALLED SPREADSHEET SOFTWARE HERE for plotting ;) \$\endgroup\$ – VisualMelon Feb 3 '18 at 9:53
1
\$\begingroup\$

Strings in .NET are "interned" which means every string you create is cached for the life of the application, so if you use the same string twice, you are using the same instance as before. So as far as garbage collection goes, I don't think it matters. Using a for loop is probably faster than Enumerable though.

See this question: https://stackoverflow.com/questions/8054471/string-interning-in-net-framework-what-are-the-benefits-and-when-to-use-inter

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.