Performance Quiz: Fastest way to format time

We want a good performing application but it is hard to get it right. We all know how to format strings in a fast and efficient way don’t we? Let me challenge you if anybody can beat my lightning fast fixed string formatting function. The rules are easy:

1. We want to format the content of DateTime structure into a string of the form:  “08:44:45.423”
2. The performance measured is the time needed to return the formatted string when the DateTime structure is as input given.
3. .NET 2.0 and C# only.

For starters I publish here the class which measures the performance

public static class Stopper

{
  public delegate string TestFunction(DateTime time);

  static int myIterations;

  public static int Iterations

      {
    get { return myIterations; }

    set { myIterations = value; }
  }

  public static void CheckTime(string action, TestFunction func)

  {
    Stopwatch Watch = Stopwatch.StartNew();

    DateTime curTime = DateTime.Now;

    for (int i = 0; i < Iterations; i++)

    {
      func(curTime);
    }

    Watch.Stop();

    Console.WriteLine("Action {0} did consume {1:F2} s",

                      action, Watch.ElapsedMilliseconds / 1000.0f);
  }
}

The test functions are executed in the Tests function describing itself during
    their execution :

    public void Tests() {
  Stopper.CheckTime("Format with String.Format", FormatWithStringFormat);

  Stopper.CheckTime("Format with StringBuilder.AppendFormat",
                    FormatWithStringBuilder);
}

A possible solution to the String format question is the good old String.Format
    :

    public string FormatWithStringFormat(DateTime time)

{
  return String.Format("{0:D2}:{1:D2}:{2:D2}.{3:D3}",

                       time.Hour, time.Minute, time.Second, time.Millisecond);
}

Or is StringBuilder the best one?

    StringBuilder sb = new StringBuilder();

public string FormatWithStringBuilder(DateTime time)

{
  sb.Length = 0;  // reset string builder buffer

  sb.AppendFormat("{0:D2}:{1:D2}:{2:D2}.{3:D3}",

                  time.Hour, time.Minute, time.Second, time.Millisecond);

  return sb.ToString();
}

Static inits do not count and are not part of the quiz. I will post the code of the fastest(?) string time formatting function in a few days. Perhaps somebody out there can beat my function. This are the results at my home PC (P4 3.0 GHz 1 GB RAM) after doing 2 million string formats. As you can see the String.Format is not the best option to choose …

Bruce did submit some samples which perform already very good. His FastFormat is looks very promising. By realizing that you can use a fixed char array and also knowing that the string constructor can take an char array we can get an impressive performance boost by a factor three compared to the most obvious solution. But the very creative solution from Greg Young did really surprise me. He did:

• Realize that the DateTime get properties do not simply return an int but do some calculations on a 64 bit value. Repeated access to the get properties do cost therefore quite a lot and can be minimized by doing it yourself and cache the calculated values for hour, minute, second and millisecond.
• Use unsafe access to the array (My Best Function does this already but the effect is quite small).

The result is a  40% speed improvement. Very impressive Greg. There proves once again that there is always somebody around who is smarter than you. But all is not all lost. I did even optimize Gregs function a little bit and made it more readable. I strongly believe that reflector had something to do with his success. Here is the code for my NewFastFormat function which is by the way much more comprehensible:

public unsafe string NewFastestFormat(DateTime time)

{
  fixed(char* charP = &FixedCharArray[0])  // Get rid of bounds checking

  {
    int hour = time.Hour;  // Cache property values

    int minute = time.Minute;

    int second = time.Second;

    int ms = time.Millisecond;

    // hour

    charP[0] = (Char)('0' + hour / 10);

    charP[1] = (Char)('0' + hour % 10);

    // minute

    charP[3] = (Char)('0' + minute / 10);

    charP[4] = (Char)('0' + minute % 10);

    // seconds

    charP[6] = (Char)('0' + second / 10);

    charP[7] = (Char)('0' + second % 10);

    // miliseconds

    charP[9] = (Char)('0' + ms / 100);

    charP[10] = (Char)('0' + ms % 100 / 10);

    charP[11] = (Char)('0' + ms % 10);
  }

  return new String(FixedCharArray);
}

My last trick I came up with is that I do not need to recreate the array at every call. And that I can initialize the “: : .” characters only once in the ctor of my class. This squeezes the last(?) bit of performance out of it. I can only say: WOW. I did not think that this big improvement was possible. After some test runs with and without unsafe array access it turned out I was not able to measure any difference! Strange but true which proves that you should not trust other peoples claims about performance. I am surprised that nobody did try it with a generic List<Char>. Many say that generics are faster but the string constructor does not take such a thing. So we have to convert it back to a char array which kills performance. Another interesting thing is that the StringBuilder index operator [] is significantly slower than the char array indexer. Now we can safely say that we have here the fastest time to string formatting function known to C# programmers until somebody finds an even faster solution.
Update: There is somebody out there who did find an even faster solution: Jeffrey Sax is obviously a real number crack and plays dirty tricks by creeping around expensive divisions by turning them into multiplications with a following bit shift. I had numerical maths at university during my studies of nuclear physics but this is really tough stuff. To push my ego up I must say that he does this for a living at Extreme Optimizations, which explains why he did find such a dam good function. He did make it by a factor 2.6 faster that our previously fastest function! This means that we posses now a string formatting function which is over 14 times faster than our original String.Format. Unbelievable. Now I think we have reached a limit where we have used all our tricks that are imaginable. I do not expect that there is room for another big improvement such as this. But one never knows…. As usual I did a little reformat and added some comments to make it easier for normal people to get the idea:

unsafe string NewFastestStringFormatting(DateTime time)

{
  fixed(char* charP = &FixedCharArray[0])

  {
    // Calculate values by getting the ms values first and do then

    // shave off the hour minute and second values with multiplications

    // and bit shifts instead of simple but expensive divisions.

    long ticks = time.Ticks;

    int ms = (int)((ticks / 10000) %
                   86400000);  // Get daytime in ms which does fit into an int

    int hour = (int)(Math.BigMul(ms >> 7, 9773437) >> 38);  // well ... it works

    ms -= 3600000 * hour;

    int minute = (int)((Math.BigMul(ms >> 5, 2290650)) >> 32);

    ms -= 60000 * minute;

    int second = ((ms >> 3) * 67109) >> 23;

    ms -= 1000 * second;

    // Hour

    int temp = (hour * 13) >>
               7;  // 13/128 is nearly the same as /10 for values up to 65

    charP[0] = (char)(temp + '0');

    charP[1] =
        (char)(hour - 10 * temp +
               '0');  // Do subtract to get remainder instead of doing % 10

    // Minute

    temp = (minute * 13) >>
           7;  // 13/128 is nearly the same as /10 for values up to 65

    charP[3] = (char)(temp + '0');

    charP[4] =
        (char)(minute - 10 * temp +
               '0');  // Do subtract to get remainder instead of doing % 10

    // Second

    temp = (second * 13) >>
           7;  // 13/128 is nearly the same as /10 for values up to 65

    charP[6] = (char)(temp + '0');

    charP[7] = (char)(second - 10 * temp + '0');

    // Milisecond

    temp = (ms * 41) >> 12;  // 41/4096 is nearly the same as /100

    charP[9] = (char)(temp + '0');

    ms -= 100 * temp;

    temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

    charP[10] = (char)(temp + '0');

    ms -= 10 * temp;

    charP[11] = (char)(ms + '0');
  }

  return new String(FixedCharArray);
}

As you can see this is not exactly rocket science it is worse than that. You have to be very careful to not get biten by a rounding error due to a too big value. The initial version of Jeffrey did have a small error which caused for some ms values strange characters. Really great work Jeffrey. For educational purposes I do also post there the fastest format function which does no unsafe tricks. Credits for FormatFastSafe go also to Jeffrey. If  still more solutions are required to be considered I am forced to rate the solutions in categories. Fastest function ever is Gregs solution but you would not use this function really since it does break the CLR promise that string objects are immutable. The fastest function which does contain unsafe code and works correctly was sent by Jeffry. And the fastest (correct working) function which uses no unsafe tricks was also sent by Jeffrey. The fastest safe function is this one:

private string FormatFastSafe(DateTime time)

private string FormatFastSafe(DateTime time)

{
  long ticks = time.Ticks;

  int n1 = (int)(ticks >> 32);

  int n2 = (int)ticks;

  if (n2 < 0)

    n1++;

  ticks =
      (((Math.BigMul(429497, n2) - (int)(Math.BigMul(1161359156, n2) >> 32) -
         Math.BigMul(1161359156, n1)) >>
        32))

      + Math.BigMul(n1, 429497);

  n1 = (int)(ticks >> 32);

  n2 = (int)ticks;

  if (n2 < 0)

    n1++;

  int q = n1 * 50 + ((50 * (n2 >> 16)) >> 16) -
          (int)(System.Math.BigMul(1244382467, n1) >> 32) - 1;

  int r = (int)(ticks - System.Math.BigMul(q, 86400000));

  if (r > 86400000)

    r -= 86400000;

  int unit = (int)(Math.BigMul(r >> 7, 9773437) >> 32) >> 6;

  n2 = (unit * 13) >> 7;

  n1 = r - 3600000 * unit;

  FixedCharArray[0] = ((char)(n2 + '0'));

  FixedCharArray[1] = ((char)(unit - 10 * n2 + '0'));

  unit = (int)((Math.BigMul(n1 >> 5, 2290650)) >> 32);

  n1 -= 60000 * unit;

  n2 = (unit * 13) >> 7;

  FixedCharArray[3] = ((char)(n2 + '0'));

  FixedCharArray[4] = ((char)(unit - 10 * n2 + '0'));

  unit = ((n1 >> 3) * 67109) >> 23;

  n1 -= 1000 * unit;

  n2 = (unit * 13) >> 7;

  FixedCharArray[6] = ((char)(n2 + '0'));

  FixedCharArray[7] = ((char)(unit - 10 * n2 + '0'));

  n2 = (n1 * 41) >> 12;

  FixedCharArray[9] = ((char)(n2 + '0'));

  n1 -= 100 * n2;

  n2 = (n1 * 205) >> 11;

  FixedCharArray[10] = ((char)(n2 + '0'));

  FixedCharArray[11] = ((char)(n1 - 10 * n2 + '0'));

  return FixedCharArray.ToString();
}

This contest was really fun and I did not expect to get so many good solutions. Thanks to everyone who did submit sample code. The code presented here is a very good example of highly optimized C# code which (I guess) cannot be found anywhere else on the net. I hope it does help other programmers to see where they burn CPU cycles and by what means you can solve a performance problem.

posted on Sunday, April 23, 2006 5:55 PM