Optimize code so that it executes faster.

Question

Hi, How can I optimize the following code so that it executes faster:

static void Main(string[] args) 
{
    String a = "Hello ";
    String b = " World! ";
    for (int i=0; i<20000; i++) 
    {
        a = a + b;
    }
    Console.WriteLine(a);
}

Answer 1

Since its output is predetermined, it would run faster if you just hardcoded the literal value that is built by the loop.

Answer 2

Parallelize it.

Answer 3

From the StringBuilder documentation:

Performance Considerations

The Concat and AppendFormat methods both concatenate new data to an existing String or StringBuilder object. A String object concatenation operation always creates a new object from the existing string and the new data. A StringBuilder object maintains a buffer to accommodate the concatenation of new data. New data is appended to the end of the buffer if room is available; otherwise, a new, larger buffer is allocated, data from the original buffer is copied to the new buffer, then the new data is appended to the new buffer.

The performance of a concatenation operation for a String or StringBuilder object depends on how often a memory allocation occurs. A String concatenation operation always allocates memory, whereas a StringBuilder concatenation operation only allocates memory if the StringBuilder object buffer is too small to accommodate the new data. Consequently, the String class is preferable for a concatenation operation if a fixed number of String objects are concatenated. In that case, the individual concatenation operations might even be combined into a single operation by the compiler. A StringBuilder object is preferable for a concatenation operation if an arbitrary number of strings are concatenated; for example, if a loop concatenates a random number of strings of user input.

static void Main(string[] args) {
    String a = "Hello ";
    String b = " World! ";
    StringBuilder result = new StringBuilder(a.Length + b.Length * 20000);
    result.Append(a);
    for (int i=0; i<20000; i++) {
        result.Append(b);
    }
    Console.WriteLine(result.ToString());
}

Answer 4

It's likely to be IO dominated ( writing the output to the console or a file will be the slowest part ), so probably won't benefit from a high degree of optimisation. Simply removing obvious pessimisations should suffice.

As a general rule, don't create temporary objects. Each iteration of your loop creates a temporary string, coping the entire previous string in a and the value of the string in b, so has to do up to 20000 times the length of b operations each time through the loop. Even so, that's only 3 billion bytes to copy, and so should complete in less than a second on a modern machine ( assuming the runtime uses the right operations for the target hardware ). Dumping 160,008 characters to the console may well take longer.

One technique is to use a builder or buffer to create fewer temporary objects, instead creating a long string in memory using a StringBuilder then copying that to a string, then outputting that string.

However, you can go one stage further and achieve the same functionality by writing the output directly, rather than creating any temporary strings or buffers, using Console.Write in the loop instead. That will remove two of copying operations ( the string b is copied to the buffer then the buffer is copied to a string object then the string's data to the output buffer; the final copy operation is the one internal to Console.Write so is not avoidable in C# ), but require more operating system calls, so may or may not be faster.

Another common optimisation is to unroll the loop. So instead of having a loop which has one line which writes one " World! " and is looped 20,000 times, you can have (say) five lines which write one " World! " each and loop them 4,000 times. That's normally only worth doing in itself if the cost of incrementing and testing the loop variable is high compared to what you're doing in the loop, but it can lead to other optimisations.

Having partially unrolled the loop, you can combine the code in the loop and write five or ten " World! "s with one call to Console.Write, which should save some time in that you're only making one fifth the number of system calls.

---

Writing to console, in cmd window, it appears limited by speed of console window:

( times in seconds for 100 runs )

     724.5312500 - concat
      53.2187500 - direct
      30.3906250 - direct writing b x10
      30.3750000 - direct writing b x100
      30.3750000 - builder
      30.3750000 - builder writing b x100

writing to file, the times for the different techniques differ:

     205.0000000 - concat
       9.7031250 - direct
       1.0781250 - direct writing b x10
       0.5000000 - builder
       0.4843750 - direct writing b x100
       0.4531250 - builder writing b x100

From this it's possible to draw two conclusions:

Most of the improvements don't matter if you're writing to the console in a cmd.exe window. You do have to profile the system as a whole, and (unless you're trying to reduce the energy use of the CPU ) there's no point optimising one component beyond the capbilities of the rest of the system.

Although apparently doing more work - copying the data more and calling the same number of functions, the StringBuilder approach is faster. This implies that there's quite a high overhead in each call to Console.Write, compared with the equivalent in non-managed languages.

writing to file, using gcc C99 on Win XP:

    0.375 - direct ( fputs ( b, stdout ) 20000 times )
    0.171 - direct unrolled ( fputs ( b x 100, stdout ) 200 times )
    0.171 - copy to b to a buffer 20000 times then puts once

The lower cost of the system call in C allows it to get towards being IO bound, rather than limited by the .net runtime boundaries. So when optimizing .net, managed/unmanaged boundaries become important.

Answer 5

static void Main(string[] args) 
{
    const String a = "Hello " +
        /* insert string literal here that contains " World! " 20000 times. */ ;
    Console.WriteLine(a);
}

I can't believe that they teach nonsense like this in schools. There isn't a real-world example of why you would ever do this, let alone optimize it. All this teaches is how to micro-optimize a program that does nothing useful, and that's counterproductive to the student's health as a programmer/developer.

Answer 6

I wonder, would this be any faster?

static void Main(string[] args) {
    String a = "Hello ";
    String b = " World! ";
    int worldCount = 20000;
    StringBuilder worldList = new StringBuilder(b.Length * worldCount);
    worldList.append(b);
    StringBuilder result = new StringBuilder(a.Length + b.Length * worldCount);
    result.Append(a);

    while (worldCount > 0) {

       if ((worldCount & 0x1) > 0) {  // Fewer appends, more ToStrings.
          result.Append(worldList);   // would the ToString here kill performance?
       }
       worldCount >>= 1;
       if (worldCount > 0) {
          worldList.Append(worldList);
       }
    }

    Console.WriteLine(result.ToString());
}

Answer 7

Depends on what's going in the String object I guess. If internally all they have is a null-terminated string, then you could optimize by storing the length of the string somewhere. Also, if you're just outputting to stdout, it would make more sense to move your output call inside the loop (less memory overhead), and it should also be faster.

Answer 8

MemoryStream is slightly faster than using StringBuilder:

    static void Main(string[] args)
    {
        String a = "Hello ";
        String b = " World! ";

        System.IO.MemoryStream ms = new System.IO.MemoryStream(20000 * b.Length + a.Length);
        System.IO.StreamWriter sw = new System.IO.StreamWriter(ms);

        sw.Write(a);
        for (int i = 0; i < 20000; i++)
        {
            sw.Write(b);
        }

        ms.Seek(0,System.IO.SeekOrigin.Begin);
        System.IO.StreamReader sr = new System.IO.StreamReader(ms);
        Console.WriteLine(sr.ReadToEnd());
    }

Answer 9

Perform output in the loop (5x faster, same result):

static void Main(string[] args) 
{
    Console.Write("Hello ");
    for (int i=0; i<20000; i++)
       Console.Write(" World! ");
    Console.Write(Environment.NewLine);
}

Or allocate the memory on forehand and fill it up (4x faster, same result):

static void Main(string[] args) 
{
   String a = "Hello "; 
   String b = " World! ";

   int it = 20000;
   char[] result = new char[a.Length + it*b.Length];

   a.ToCharArray().CopyTo(result, 0);

   for (int i = 0; i < it; i++) 
      b.ToCharArray().CopyTo(result, a.Length + i * b.Length);

   Console.WriteLine(result);    
}

Answer 10

Here are some timing results. Each test was conducted starting with 20000 iterations. Every test includes output in the timings, unless stated otherwise. Each number for a group means number of iterations was 10 times greater than the previous. If there are less than 4 numbers, the test was taking too long so i killed it. "Parallize it" means i split the number of concatenations evenly over 4 threads and appended the results when all had finished (could probable have saved a little time here and put them into a queue and appended them as they finished, but didn't think of that until now). All times are in milliseconds.

656 6658 66999 370717 output hello loop output world. no concatenation.

658 6641 65807 554546 build with stringbuilder then output

664 6571 65676 314140 build with stringbuilder with large initial size no output

2761 367042 OP, strings only (killed test while concatenating; nothing printed to screen)

167 43227 parallize it OP no output

27 40 323 1758 parallize it stringbuilder no output