Alois Kraus

blog

  Home  |   Contact  |   Syndication    |   Login
  106 Posts | 8 Stories | 294 Comments | 162 Trackbacks

News



Article Categories

Archives

Post Categories

Image Galleries

Programming

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 ...


Formatting Algo Elapsed Time in s Specialities
String.Format 5,54  
StringBuilder.AppendFormat 4,92  
Bruce ToString 3,36  
Bruce FastFormat 1,81  
My Best Function So Far 1,75 Unsafe Code
FastFormat4 by Greg Young 1,15 Unsafe Code
NewFastestFormat 1,08 Unsafe Code
DansFormat 0,83 Unsafe Code
FormatFastSafe by Jeffrey 0,53  
FastFormat6 by Jeffrey Sax 0,42 Unsafe Code
NewFastestStringFormatting 0,43 Unsafe Code
FormatFast7 by Greg Young 0,33 Unsafe Code, Breakes the CLR string handling!

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)

        {

            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

Feedback

# re: Performance Quiz: Fastest way to format time 4/23/2006 8:12 PM Bruce Dunwiddie
Here's what I would normally expect to see in our company's production code where it's not do or die on speed, and it's the cleanest method I know of.

private static string FormatWithToString(DateTime time)
{
return time.ToString("HH:mm:ss.fff");
}

And here's the best function I could come up with speedwise, which based off your number comparisons is probably a little slower than your best method.

private static string FormatFast(DateTime time)
{
char[] dateData = new char[12];
dateData[0] = (char)(time.Hour / 10 + '0');
dateData[1] = (char)(time.Hour % 10 + '0');
dateData[2] = ':';
dateData[3] = (char)(time.Minute / 10 + '0');
dateData[4] = (char)(time.Minute % 10 + '0');
dateData[5] = ':';
dateData[6] = (char)(time.Second / 10 + '0');
dateData[7] = (char)(time.Second % 10 + '0');
dateData[8] = '.';
dateData[9] = (char)(time.Millisecond / 100 + '0');
dateData[10] = (char)(time.Millisecond / 10 % 10 + '0');
dateData[11] = (char)(time.Millisecond % 10 + '0');
return new string(dateData);
}



# re: Performance Quiz: Fastest way to format time 4/24/2006 8:49 AM Greg Young
Bruce is definatly on the right track but I think I have the winner ... and the 3% was generous I got a 50% improvement with the following code

private unsafe static string FormatFast3(DateTime time)
{
char[] dateData = new char[12]; fixed (char* p = dateData)
{
long ticks = time.Ticks;
char* a = p;
int hour = (int)((ticks / 0x861c46800L)) % 24;
int minute = (int)((ticks / 0x23c34600L)) % 60;
int second = (int)(((ticks / 0x989680L)) % 60L);
int ms = (int)(((ticks / 0x2710L)) % 0x3e8L);
*a = (char)(hour / 10 + '0');
a++;
*a = (char)(hour % 10 + '0');
a++;
*a = ':';
a++;
*a = (char)(minute / 10 + '0');
a++;
*a = (char)(minute % 10 + '0');
a++;
*a = ':';
a++;
*a = (char)(second / 10 + '0');
a++;
*a = (char)(second % 10 + '0');
a++;
*a = '.';
a++;
*a = (char)(ms / 100 + '0');
a++;
*a = (char)(ms / 10 % 10 + '0');
a++;
*a = (char)(ms % 10 + '0');
}
return new String(dateData);
}

explanation is here http://geekswithblogs.net/gyoung/archive/2006/04/24/76187.aspx

# re: Performance Quiz: Fastest way to format time 4/24/2006 9:02 AM Greg Young
and a bit more of a gain with the following.

private unsafe static string FormatFast4(DateTime time)
{
char[] dateData = { ' ', ' ', ':', ' ', ' ', ':', ' ', ' ', '.', ' ', ' ', ' ' };
fixed (char* p = dateData)
{
long ticks = time.Ticks;
char* a = p;
int hour = (int)((ticks / 0x861c46800L)) % 24;
int minute = (int)((ticks / 0x23c34600L)) % 60;
int second = (int)(((ticks / 0x989680L)) % 60L);
int ms = (int)(((ticks / 0x2710L)) % 0x3e8L);
*a = (char)(hour / 10 + '0');
a++;
*a = (char)(hour % 10 + '0');
a+=2;
*a = (char)(minute / 10 + '0');
a++;
*a = (char)(minute % 10 + '0');
a+=2;
*a = (char)(second / 10 + '0');
a++;
*a = (char)(second % 10 + '0');
a+=2;
*a = (char)(ms / 100 + '0');
a++;
*a = (char)(ms / 10 % 10 + '0');
a++;
*a = (char)(ms % 10 + '0');
}
return new String(dateData);
}



# re: Performance Quiz: Fastest way to format time 4/24/2006 6:35 PM Greg Young
I am a bit confused here ... I originally had mine using a static array (external) which was supposedly not allowed ... this adds about 8% of my overhead.

"Static inits do not count and are not part of the quiz."

Are you saying that you consider it to be different by re-using an instance array instead of a static array?

in running an apples - apples comparison ...
I am getting opposite results here.


# re: Performance Quiz: Fastest way to format time 4/24/2006 6:39 PM Greg Young
1 million per run ... multiple runs to allow for fluctuations of other processes etc (both using static initialization)

newest, ff00:00:00.6286406, 00:00:00.5942612
newest, ff00:00:00.6268878, 00:00:00.5914943
newest, ff00:00:00.6192816, 00:00:00.5889954
newest, ff00:00:00.6199655, 00:00:00.5893585
newest, ff00:00:00.6240222, 00:00:00.5860858
newest, ff00:00:00.6228850, 00:00:00.5833606
newest, ff00:00:00.6186141, 00:00:00.5858331
newest, ff00:00:00.6166680, 00:00:00.5860434
newest, ff00:00:00.6187861, 00:00:00.5770714
newest, ff00:00:00.6169843, 00:00:00.5787987
newest, ff00:00:00.6141091, 00:00:00.5787815
newest, ff00:00:00.6137976, 00:00:00.5836728
newest, ff00:00:00.6136590, 00:00:00.5830932
newest, ff00:00:00.6154047, 00:00:00.5794708
newest, ff00:00:00.6175635, 00:00:00.5788110
newest, ff00:00:00.6209061, 00:00:00.5804462
newest, ff00:00:00.6160663, 00:00:00.5794970
newest, ff00:00:00.6125530, 00:00:00.5793162
newest, ff00:00:00.6133430, 00:00:00.5766974
newest, ff00:00:00.6140230, 00:00:00.5783897
newest, ff00:00:00.6330252, 00:00:00.5776782
newest, ff00:00:00.6156125, 00:00:00.5794389
newest, ff00:00:00.6806186, 00:00:00.5762781
newest, ff00:00:00.6153356, 00:00:00.5774192
newest, ff00:00:00.6156210, 00:00:00.5857161
newest, ff00:00:00.6190502, 00:00:00.5809238
newest, ff00:00:00.6216776, 00:00:00.5888538
newest, ff00:00:00.6239190, 00:00:00.5930860
newest, ff00:00:00.6233750, 00:00:00.5854750

but I agree yours is far more readable :)

# re: Performance Quiz: Fastest way to format time 4/24/2006 7:09 PM Alois Kraus
Hi Greg,

sorry for the confusion. I did mean that the static inits are not measured. Since we do the conversion millions of times the init times do not matter. As for the performance I did use an instance array and dit get nearly identical values. But mine was still a bit faster. I did use:

GC.Collect();
Stopper.CheckTime("FastFormat4 by Greg Young", FormatFast4);
GC.Collect();
Stopper.CheckTime("Format by NewFastestFormat", NewFastestFormat);
GC.Collect();

My results were obtained with a 2 million count. I did also try 1 million but the result did not change.
Action Format with String.Format did consume 2,73 s
Action Format with String.Format did consume 2,71 s
Action Format with String.Format did consume 2,53 s
Action Format with Bruce ToString did consume 1,68 s
Action Format with Bruce FormatFast did consume 0,87 s
Action Format with StringBuilder.AppendFormat did consume 2,41 s
Action Format with StringBuilder[i] indexer did consume 1,22 s
Action Format by using fixed generic char array did consume 1,08 s
Action Format by using fixed char array did consume 0,87 s
Action FastFormat4 by Greg Young did consume 0,52 s
Action Format by NewFastestFormat did consume 0,51 s

Perhaps you experience some GC collections during the one or the other tests. To prevent this I did use

Stopper.CheckTime("Format with String.Format", FormatWithStringFormat);
GC.Collect();

Stopper.CheckTime("Format with Bruce ToString", FormatWithToString);
GC.Collect();
Stopper.CheckTime("Format with Bruce FormatFast", FormatFast);
GC.Collect();
Stopper.CheckTime("Format with StringBuilder.AppendFormat", FormatWithStringBuilder);
GC.Collect();
Stopper.CheckTime("Format with StringBuilder[i] indexer", FormatWithStringBuilderIndex);
GC.Collect();
Stopper.CheckTime("Format by using fixed generic char array", FormatWithGenericCharArray);
GC.Collect();
Stopper.CheckTime("Format by using fixed char array", FormatWithCharArray);
GC.Collect();
Stopper.CheckTime("FastFormat4 by Greg Young", FormatFast4);
GC.Collect();
Stopper.CheckTime("Format by NewFastestFormat", NewFastestFormat);
GC.Collect();

to get some systematic tests and I did also some warmup loops to get rid of startup effects. Perhaps a GC.Collect does change the results?

Yours,
Alois Kraus


# re: Performance Quiz: Fastest way to format time 4/24/2006 7:47 PM Greg Young
no change what so ever based upon garbage collection ... and it makes sense that yours would actually be slower if for no other reason than the additional overhead of the property calls which add to the clarity may not be much overhead but 3,000,000 method calls starts to add up.

Are you running mine with a pre-initialized array as well? or is mine still generating a new array every time vs the one with an instance pre-load.

How many tests are you running through on the comparison? I am running many tests and taking the average of the values in order to do my comparison (maybe another process got a bit greedy during that few second etc) ... To think that garbage collection is only affecting one of the functions over the course of 100 or 1000 runs would be an amazing coincidence.

I am including the shortest possible code I could come up with to run a comparison between the two.

static char[] dateData = new char[12];

public static unsafe string NewFastestFormat(DateTime time)
{

fixed (char* charP = dateData) // 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(dateData);
}

private unsafe static string FormatFast4(DateTime time)
{
fixed (char* p = dateData)
{
long ticks = time.Ticks;
char* a = p;
int hour = (int)((ticks / 0x861c46800L)) % 24;
int minute = (int)((ticks / 0x23c34600L)) % 60;
int second = (int)(((ticks / 0x989680L)) % 60L);
int ms = (int)(((ticks / 0x2710L)) % 0x3e8L);
*a = (char)(hour / 10 + '0');
a++;
*a = (char)(hour % 10 + '0');
a+=2;
*a = (char)(minute / 10 + '0');
a++;
*a = (char)(minute % 10 + '0');
a+=2;
*a = (char)(second / 10 + '0');
a++;
*a = (char)(second % 10 + '0');
a+=2;
*a = (char)(ms / 100 + '0');
a++;
*a = (char)(ms / 10 % 10 + '0');
a++;
*a = (char)(ms % 10 + '0');
}
return new String(dateData);
}

static void Main(string[] args)
{
const int iterations = 1000000;
DateTime start = DateTime.Now;
Stopwatch timer = new Stopwatch();
timer.Start();
for (int j = 0; j < 100; j++)
{

timer.Reset();
timer.Start();
for (int i = 0; i < iterations; i++)
{
string foo = NewFastestFormat(start);
}
TimeSpan newest = timer.Elapsed;
long ticks = start.Ticks;
timer.Reset();
timer.Start();
for (int i = 0; i < iterations; i++)
{
string foo = FormatFast4(start);
}
TimeSpan ff = timer.Elapsed;
Console.WriteLine("newest, ff" + newest.ToString() + ", " + ff.ToString());
}
}


# re: Performance Quiz: Fastest way to format time 4/24/2006 8:14 PM Alois Kraus
Hi Greg,
I did run your program and got:

newest, ff00:00:00.5303931, 00:00:00.5393288
newest, ff00:00:00.5348025, 00:00:00.5377157
newest, ff00:00:00.5336137, 00:00:00.5391632
newest, ff00:00:00.5298823, 00:00:00.5405854
newest, ff00:00:00.5317513, 00:00:00.5381498
newest, ff00:00:00.5302754, 00:00:00.5396609
newest, ff00:00:00.5308748, 00:00:00.5393509
newest, ff00:00:00.5311548, 00:00:00.5390515
newest, ff00:00:00.5312365, 00:00:00.5431012
newest, ff00:00:00.5273175, 00:00:00.5429678
newest, ff00:00:00.5297094, 00:00:00.5394536
newest, ff00:00:00.5353443, 00:00:00.5454910
newest, ff00:00:00.5300067, 00:00:00.5409097

I think we are here measuring sth. else, perhaps our own hardware. Do you have two or more processors installed? The High performance counter are processor specific counters and are not synchronized as far as I know. Since the JIT optimizer does processor specifc optimizations I would not be surprised if there are AMD and Intel optimizations inside the JITer. My PC is a P4 3.0 GHz with 1GB Ram. A property get should not hurt performance sice the JITer does inline them (at least the small ones). You can check this if you debug the release build and look at the generated assembly when you have turned Tools->Options->Debugging->Suppress JIT optimization on module load, Enable Just My Code off.

The the generated Assembly code (NOT MSIL) is
int ms = time.Millisecond;
000000e3 mov eax,dword ptr [ebp+8]
000000e6 mov edx,dword ptr [ebp+0Ch]
000000e9 and edx,3FFFFFFFh
000000ef push edx
000000f0 push eax
000000f1 push 0
000000f3 push 2710h // / 0x2710h
000000f8 call 792E1146
000000fd mov esi,3E8h // % 0x3E8
00000102 cmp edx,1F4h
00000108 jb 0000011D
0000010a mov ecx,eax
0000010c mov eax,edx
0000010e cdq
0000010f idiv eax,esi
00000111 mov eax,ecx
00000113 mov ecx,7D0h
00000118 idiv eax,ecx
0000011a mov eax,edx
0000011c cdq
0000011d idiv eax,esi
0000011f mov esi,edx
Which is the same as the inlined get Millisecond property of the DateTime structure:

public int get_Millisecond()
{
return (int) ((this.InternalTicks / ((long) 0x2710)) % ((long) 0x3e8));
}

Your optimization is already done by the JITer which allows me to write more readable code ;-).

Yours,
Alois Kraus

# re: Performance Quiz: Fastest way to format time 4/24/2006 9:25 PM Greg Young
btw I think I might be able to get this a bit faster (through bad programming practice).

forgot this line in the ECMA

Paragraph 10 (Page 335, Line 49)
1 Modifying objects of managed type through fixed pointers can result in undefined behavior. Note: For example, because strings are immutable, it is the programmer's responsibility to ensure that the characters referenced by a pointer to a fixed string are not modified. end note




# re: Performance Quiz: Fastest way to format time 4/24/2006 9:27 PM Greg Young
my other comment got lost I guess ...

This was fun, albeit odd to have the slightly different behaviors .. I will have to go check out the assembly generated here tomorrow to see what the differences are.

Will have to do this again!

oh if you enjoy this sort of stuff there is an OCD blog post that is slightly similar from when I was waiting on my session at code camp saturday.



# re: Performance Quiz: Fastest way to format time 4/26/2006 3:19 PM Jeffrey Sax
There is a way to have this run 2.5 times faster. Really.

See http://blogs.extremeoptimization.com/jeffrey/archive/2006/04/26/13824.aspx

# re: Performance Quiz: Fastest way to format time 4/27/2006 2:52 AM Greg Young
I'm surprised it got that much of a gain, I had considerred changing some of the operations into shifts but didn't expect such a huge pickup.

Great Job!

# re: Performance Quiz: Fastest way to format time 4/28/2006 4:19 AM Dan Bellandi
private unsafe static string arm(DateTime time) {
fixed (char* p = dateData) {
uint* q=(uint*)(p);
long ticks = time.Ticks;

int hour = (int)((ticks / 0x861c46800L)) % 24;
int minute = (int)((ticks / 0x23c34600L)) % 60;
int second = (int)(((ticks / 0x989680L)) % 60L);
uint ms = (uint)(((ticks / 0x2710L)) % 0x3e8L);

uint z = (uint)((hour + (0xF6 * ((hour*13)>>7))) | 0x3030);
*q = ((z & 0xFF) << 16) | (z >> 8);

q=(uint*)(p+3);
z = (uint)((minute + (0xF6 * ((minute*13)>>7))) | 0x3030);
*q = ((z & 0xFF) << 16) | (z >> 8);

q=(uint*)(p+6);
z = (uint)((second + (0xF6 * ((second*13)>>7))) | 0x3030);
*q = ((z & 0xFF) << 16) | (z >> 8);

q++;
z = (ms / 100);
z = (uint)((z + (0xF6 * ((z*13)>>7))) | 0x3030);
*q = ((z & 0xFF) << 16); // | (z >> 8); don't need high byte

q++;
z = (ms % 100);
z = (uint)((z + (0xF6 * ((z*13)>>7))) | 0x3030);
*q = ((z & 0xFF) << 16) | (z >> 8);

}
return new String(dateData);
}



# re: Performance Quiz: Fastest way to format time 4/28/2006 4:32 AM Dan Bellandi
As you can see (maybe) the basic idea is to take each of the component parts as a whole instead of calculating each a digit at a time.

Here are some results.

The numbers are (mine is armleg), the ratio on the end is armleg/ff, so 0.8 would be 80% of the time or 20% faster.

(newest), (ff), (armleg) - best - (armleg/ff) :
newest, ff, armleg : 0.614, 0.600, 0.490 - armleg - 0.817
newest, ff, armleg : 0.621, 0.606, 0.489 - armleg - 0.806
newest, ff, armleg : 0.617, 0.606, 0.492 - armleg - 0.811
newest, ff, armleg : 0.620, 0.603, 0.489 - armleg - 0.811
newest, ff, armleg : 0.621, 0.609, 0.487 - armleg - 0.799
newest, ff, armleg : 0.616, 0.606, 0.482 - armleg - 0.795
newest, ff, armleg : 0.619, 0.610, 0.490 - armleg - 0.803
newest, ff, armleg : 0.613, 0.601, 0.480 - armleg - 0.798
newest, ff, armleg : 0.649, 0.602, 0.483 - armleg - 0.802
newest, ff, armleg : 0.612, 0.601, 0.481 - armleg - 0.801
newest, ff, armleg : 0.621, 0.600, 0.480 - armleg - 0.800
newest, ff, armleg : 0.614, 0.604, 0.480 - armleg - 0.795
newest, ff, armleg : 0.621, 0.607, 0.485 - armleg - 0.798
newest, ff, armleg : 0.616, 0.604, 0.479 - armleg - 0.792
newest, ff, armleg : 0.619, 0.614, 0.488 - armleg - 0.795
newest, ff, armleg : 0.616, 0.605, 0.480 - armleg - 0.792
newest, ff, armleg : 0.617, 0.613, 0.498 - armleg - 0.813
newest, ff, armleg : 0.651, 0.598, 0.480 - armleg - 0.803
newest, ff, armleg : 0.619, 0.615, 0.495 - armleg - 0.806
newest, ff, armleg : 0.625, 0.606, 0.490 - armleg - 0.808



Here's my adjustments to Main()...

static void Main(string[] args) {

const int iterations = 1000000;
DateTime start = DateTime.Now;
Stopwatch timer = new Stopwatch();
timer.Start();

for (int j = 0;j < 20;j++) {

timer.Reset();
timer.Start();
for (int i = 0;i < iterations;i++) {
string foo = NewFastestFormat(start);
}
TimeSpan newest = timer.Elapsed;

timer.Reset();
timer.Start();
for (int i = 0;i < iterations;i++) {
string foo = FormatFast4(start);
}
TimeSpan ff = timer.Elapsed;

timer.Reset();
timer.Start();
for (int i = 0;i < iterations;i++) {
string foo = arm(start);
}
TimeSpan leg = timer.Elapsed;

string best=((newest<ff) ? ((newest<leg) ? "newer" : "armleg") : ((ff<leg) ? "ff" : "armleg"));
double ratio=(double)leg.Ticks / (double)ff.Ticks;
best+=" - "+ratio.ToString("0.000");

Console.WriteLine(
"newest, ff, armleg : " +
newest.TotalSeconds.ToString("0.000") + ", " +
ff.TotalSeconds.ToString("0.000") + ", " +
leg.TotalSeconds.ToString("0.000") + " - " +
best
);
}
}



# re: Performance Quiz: Fastest way to format time 4/28/2006 6:19 AM Dan Bellandi
So, at least on my computer anyway, I'm seeing around a 20% improvement.

I'll go into it a bit more what I'm doing here, using the minute part.

From Jeffrey Sax's we have the bit shifting magic of:

int temp = (minute * 13) >> 7;
*a = (char)(temp + '0');
a++;
*a = (char)(minute - 10 * temp + '0');

My first thought on this was there has to be a way to get the entire minute at once.

I thought, what if instead of accessing our result memory 8 bits for one ASCII character at a time, we can do 16 bits and get both characters that make up the ASCII representation of the minute. This could be big, I thought.

A little overly optimistic I was. You may already see a couple of immediate problems, and I'll get those shortly.

I was focused on the actual "translation" from the binary (or hex) format of it numerically (int minute), into the decimal, ASCII format of it in the string. I felt I had this part, so I wrote some code to check my logic.

I consider the minute as a (byte) 8-bit value, or 2 hex digits. Then I looked at what I wanted to turn that into, 2 ASCII characters, or a (short) 16-bit value, 4 hex digits.

We'll look at the (decimal) N0 and N9 possible minute values where N = 0 to 5, where DD is the decimal value, HH is the hex, and RRRR is the desired hex result (0x3030 = "00"):

DD HH RRRR
-- -- ----
00 00 3030
09 09 3039
10 0A 3130
19 13 3139
20 14 3230
29 1D 3239
30 1E 3330
39 27 3339
40 28 3430
49 31 3439
50 32 3530
59 3B 3539

You can see for 00-09 it's easy, you just add 0x3030, but the trouble comes in that we need our result to "wrap" every dec 10 but our input value "wraps" every 16. After some work I figure out that if we take the "tens" place of the minute (which we can calculate quickly with the multiply by 13, shift right 7 thanks to Jeffrey) we can multiply that by 0xF6 and add that to the original value we will get a value that when OR'd with 0x3030 will be our desired RRRR from above.

An example, with a decimal value of 29, hex 0x1D, so tens = 2.

0x1D + (2 * 0xF6) = 0x1D + 0x1EC = 0x209

See we neatly get the "2" into hex and shift it one left one, while simply getting the "9" into hex. Once we're here, we're home, since the 0x3030 can just be OR'd on, as our result values never share bits with the "00" base of 0x3030. Done.

Or so I thought. A couple of issues lie ahead but I had yet to think it all through.

But first, why 0xF6? Simply put, because the hex base of 16 minus the decimal base of 10 equals 6. Let's consider decimal 14, which is hex 0x0E. Basically we want to make that into hex 0x14, from which we "expand" to 0x0104 and OR to 0x3030.

See that for any decimal 10-19, if we add 6 to it, we get the "same" thing in hex, which is because we "skipped" 6 starting "10" at 0x0A instead of 0x10.

For decimals 20-29, we've now "skipped" 12 (0x0C), and so on up through 50-59 when we've "skipped" 30 (0x1E).

So that's the "6" part of the 0xF6.

Going back to decimal 14, hex 0x0E, we add that 6 to get hex 0x14. But we need 0x104.

So if we also add 0xF0 that single bit that higher hex digit received when 0x0E became 0x14 will travel another whole hex digit upwards (4 bits, 0xF in binary = 1111).

Altogether, in binary:

dec=14 hex=0x0E 0000 0000 0000 1110
plus 6 + 0000 0110
---- ----
= 0001 0100 = 0x14
plus 0xF0 + 1111 0000
---- ---- ---- ----
=0000 0001 0000 0100 = 0x0104


Yay. This does it, two digits at once.

Two problems I quickly found.

First, (char) is not 8 bits, it's 16. Damn Unicode.

So our two output digits characters need 32 bits, which we can access as (int), and 0x14 needs to become 0x00010004.

Almost. We still have the endian issue. The x86 is little-endian, which means the less significant bytes come first in memory. But of course for our string we need the more significant bytes to come first, otherwisde 14 will be 41.

So we need 0x3134 to become 0x00340031 (doing both the Unicode expansion and endian correction together).

We can take our 4-byte int value 0x00003134 from above, AND with 0xFF to get the least significant byte and shift it left 16 bits to get the 0x34 in the right place, and then OR that with the original value shifted right 8 bits pushing the 0x31 down to the least significant byte spot.

That basically does it.

There are some further optimizations here I think. I got lazy with the milliseconds for one thing. I did the divide and mod by 100 cause I wanted to test it out. These could be changed to the correct multiply / bitshift operations we do (Thanks to Jeffrey again) other places.

Comments?


# re: Performance Quiz: Fastest way to format time 4/28/2006 8:56 PM Alois Kraus
Hi Dan,

nice work. It is much faster than the original functions but it is not the fastest. On my PC it is twice as slow as Jeffreys solution. I have updated the performance charts to get a better overview.

Yours,
Alois Kraus

# Safe/unsafe, legal/illegal 4/29/2006 12:48 AM Jeffrey Sax
You can squeeze out another 5-7% over my previous solution by replacing the expression for ms with:

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 = (int)((((Math.BigMul(50, n2) - Math.BigMul(1244382467, n1) - (int)(Math.BigMul(1244382467, n2) >> 32)) >> 32))) + n1 * 50;
int ms = (int)(ticks - Math.BigMul(q, 86400000));

It would be even faster if Math.BigMul had an overload that takes unsigned ints.

The collaborative effort of Greg, Dan and my optimizations should be an amazingly fast solution. Having said that, and as Greg admitted, it's also not entirely fair to have a solution that breaks the rules.

I would suggest you add one or two columns to your summary table. The first says if the code uses unsafe code. The last says how 'evil' the code is.

For the 100% safe and managed code category, I submit the following solution, which should clock at around 0.63s on your machine:

private static string FormatFastSafe(DateTime time)
{
char[] s = { '\0', '\0', ':', '\0', '\0', ':', '\0', '\0', '.', '\0', '\0', '\0' };

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;
s[0] = ((char)(n2 + '0'));
s[1] = ((char)(unit - 10 * n2 + '0'));

unit = (int)((Math.BigMul(n1 >> 5, 2290650)) >> 32);
n1 -= 60000 * unit;
n2 = (unit * 13) >> 7;
// s[2] = ':';
s[3] = ((char)(n2 + '0'));
s[4] = ((char)(unit - 10 * n2 + '0'));
//s[5] = ':';

unit = ((n1 >> 3) * 67109) >> 23;
n1 -= 1000 * unit;
n2 = (unit * 13) >> 7;
s[6] = ((char)(n2 + '0'));
s[7] = ((char)(unit - 10 * n2 + '0'));

n2 = (n1 * 41) >> 12;
// s[8] = '.';
s[9] = ((char)(n2 + '0'));
n1 -= 100 * n2;
n2 = (n1 * 205) >> 11;
s[10] = ((char)(n2 + '0'));
s[11] = ((char)(n1 - 10 * n2 + '0'));

return s.ToString();
}


# re: Performance Quiz: Fastest way to format time 4/30/2006 6:37 PM Dan Bellandi

Ok. I optimized my function. Pretty significant improvement.

I also realized last time I was comparing my results to FormatFast4 as opposed to Jeffrey's FormatFast6.

Anyway, here it is. It seems very, very close to Jeffrey's FormatFast6. I appear to be getting maybe 5% faster but I wouldn't call it with that close without someone else checking.

Note that it is still running maybe 15-20% slower than the crazy, but very cool, FormatFast7.

I actually think I have a method for another 25-35% improvement, while remaining CRL-happy, but it needs a little more thought.

I thought I'd post this now though.




public unsafe static string newarm(DateTime time) {
fixed (char* pd = dateData) {
byte* b=(byte*)(pd);
long ticks = time.Ticks;

uint x = (uint)(((ticks / 0x2710L)) % 86400000);

uint d = x / 0xA;

x+=(d*0x6);
d/=0x0A;
x+=(d*0x6)<<4;
d/=0x0A;
x+=(d*0x6)<<8;
d/=0x0A;
x+=(d*0x6)<<12;

b[22]=(byte)x;
b[20]=(byte)(x>>4);
b[18]=(byte)((ushort)x>>8);
b[14]=(byte)(b[18]>>4);

x=d;
d/=0x06;
x+=(d*0xA);
d/=0x0A;
x+=(d*0x6)<<4;
d/=0x06;
x+=(d*0xA)<<8;
d/=0x0A;
x+=(d*0x6)<<12;

b[12]=(byte)x;
b[8]=(byte)(x>>4);
b[6]=(byte)((ushort)x>>8);
b[2]=(byte)(b[6]>>4);
b[0]=(byte)(x>>16);

}
return new String(dateData);
}



This is definitely fun. Maybe a little too much.





# re: Performance Quiz: Fastest way to format time 11/28/2006 10:16 AM Anders Dalvander
Allocating the buffer on the stack (using stackalloc), creates reentrant but unsafe code.

I took the FormatFastSafe by Jeffrey and changed FixedCharArray to be allocated within the method made the code a bit faster.

unsafe string FormatFastUnsafe(DateTime time)
{
char* FixedCharArray = stackalloc char[12];
// Same code as FormatFastSafe by Jeffrey.
return new String(FixedCharArray);
}

Another observation, the code:
return new String(FixedCharArray);
seems to be much faster than this code:
return FixedCharArray.ToString();
At least on my computer.

# re: Performance Quiz: Fastest way to format time 11/6/2007 10:01 AM Jon Dahl
A little late in the ball game, but how come there is only time formatting and not the date as well?

# re: Performance Quiz: Fastest way to format time 3/17/2008 12:22 AM Volker Klein
On my machine, the performance of Gregs FormatFast7 increases by 20% when combining it with Dans idea of storing multiple characters at a time and using precalculated lookup tables instead of calculations for getting the two or three digits that make up a number.

The actual code to store the numbers then reduces to

*(uint*)&p[0] = twoDigits[hour]; // Hour
*(uint*)&p[3] = twoDigits[minute]; // Minute
*(uint*)&p[6] = twoDigits[second]; // Second
*(ulong*)&p[8] = threeDigits[ms]; // Milisecond

note that threeDigits[] contains the decimal point and is therefore storead at offset 8.

This technique can be combines with a less evil approach than FormatFast7, but then the performance gain is not as dramatic. Sadly, its not possible to do this in a safe version because of the unaligned accesses.

The complete source code is

unsafe static class FormatWithLUT
{
static char* p = null;
static string foo = " : : . ";
static uint[] twoDigits = new uint[100];
static ulong[] threeDigits = new ulong[1000];

static FormatWithLUT()
{
for ( uint n = 0; n < 100; ++n )
{
twoDigits[n] = n / 10 + '0' + ((n % 10 + '0') << 16);
}
for ( ulong n = 0; n < 1000; ++n )
{
threeDigits[n] = '.' + ((n / 100 + '0') << 16) + ((n / 10 % 10 + '0') << 32) + ((n % 10 + '0') << 48);
}
GCHandle test = GCHandle.Alloc( foo, GCHandleType.Pinned );
p = (char*)test.AddrOfPinnedObject().ToInt32();
}
public unsafe static string Format( DateTime time )
{
long ticks = time.Ticks;
int n1 = (int)(ticks >> 32);
int n2 = (int)ticks;
if ( n2 < 0 )
n1++;
ticks = ((((429497L * n2) - (int)((1161359156L * n2) >> 32) - (1161359156L * n1)) >> 32)) + (n1 * 429497L);

n1 = (int)(ticks >> 32);
n2 = (int)ticks;
if ( n2 < 0 )
n1++;
int q = (int)(((((50L * n2) - (1244382467L * n1) - (int)((1244382467L * n2) >> 32)) >> 32))) + n1 * 50;
int ms = (int)(ticks - (q * 86400000L));

int hour = (int)(Math.BigMul( ms >> 7, 9773437 ) >> 38);
ms -= 3600000 * hour;
int minute = (int)((Math.BigMul( ms >> 5, 2290650 )) >> 32);
ms -= 60000 * minute;
int second = ((ms >> 3) * 67109) >> 23;
ms -= 1000 * second;

*(uint*)&p[0] = twoDigits[hour]; // Hour
*(uint*)&p[3] = twoDigits[minute]; // Minute
*(uint*)&p[6] = twoDigits[second]; // Second
*(ulong*)&p[8] = threeDigits[ms]; // Milisecond
return foo;
}
}


# re: Performance Quiz: Fastest way to format time 3/25/2008 7:35 PM Faisal
Could you guys help me in converting the string to date or datetime faster?
Currently i am using DateTime.TryParseExact, which is very slow.

Thanks in advance,
Faisal

# re: Performance Quiz: Fastest way to format time 3/31/2008 7:04 AM Thomas Strauss
I have a solution which performs with some 2/3 of the time of FastFormat6 from Jeffrey.

I used some inspiration from Hacker's Delight / Henry S. Warren, Jr; Addison-Wesley 2003; ISBN 0-201-91465-4 for getting around the division.

public static class FastFormatter {

private static char[] buf = new char[11];
private readonly static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
private static char[] timeTemplate = "00:00:00.000".ToCharArray();
private static long dayTicks = DateTime.Now.Date.Ticks;
private readonly static string minValueString = int.MinValue.ToString();

private readonly static char[] hunderdDigits = {
'0', '0', '0',
'0', '0', '1',
'0', '0', '2',
'0', '0', '3',
'0', '0', '4',
'0', '0', '5',
'0', '0', '6',
'0', '0', '7',
'0', '0', '8',
'0', '0', '9',
'0', '1', '0',
...
'9', '9', '3',
'9', '9', '4',
'9', '9', '5',
'9', '9', '6',
'9', '9', '7',
'9', '9', '8',
'9', '9', '9',
};

public static string ToStringTimeFormat(long ticks) {
long u = ticks - dayTicks;
ulong u0 = (uint) u; // divide by 10000.
long u1 = u >> 32;
long t = u1 * 0x3886594b + (long) (u0 * 0x3886594b >> 32);
int totalMilliSeconds = (int) (((u1 * 0x346dc5d6L + (t >> 32) + (((long) u0 * 0x346dc5d6L + (uint) t) >> 32)) >> 11));

int totalSec = (int) ((0x10624dd3L * totalMilliSeconds) >> 38); // totalMilliSeconds / 1000
int milliIndex = (totalMilliSeconds - totalSec * 1000) * 3;

int totalMin = (int) ((0x88888889L * totalSec) >> 37); // totalSec / 60
int secIndex = (totalSec - totalMin * 60) * 3 + 1;

int totalHour = (0x8889 * totalMin) >> 21; // totalMin / 60
int minIndex = (totalMin - totalHour * 60) * 3 + 1;

int hourIndex = (totalHour * 3) + 1;

timeTemplate[0] = hunderdDigits[hourIndex];
timeTemplate[1] = hunderdDigits[hourIndex + 1];
timeTemplate[3] = hunderdDigits[minIndex];
timeTemplate[4] = hunderdDigits[minIndex + 1];
timeTemplate[6] = hunderdDigits[secIndex];
timeTemplate[7] = hunderdDigits[secIndex + 1];
timeTemplate[9] = hunderdDigits[milliIndex];
timeTemplate[10] = hunderdDigits[milliIndex + 1];
timeTemplate[11] = hunderdDigits[milliIndex + 2];

return new string(timeTemplate);
}

The routine uses save code ;-)

# FormatFastSafe 5/25/2011 1:58 AM Nicola
Hi,

I found a value that is not converted correctly:
28.01.2004 23:00:00
Bye

Nicola

# re: Performance Quiz: Fastest way to format time 5/26/2011 2:02 AM Simon Hewitt
Some of these plain don't work; some work but are unusable in real life code. All are inflexible but I enjoyed reading all of it!

Here is my attempt: I've used a combination of the ideas here and refactored to make some of the code reusable. - Its fast, safe/reentrant, flexible and it works!:

public class TimeFormatter
{
const uint TicksPerMillisecond = 10000;
const uint MillisecondsPerDay = 86400000;
const uint MillisecondsPerHour = 3600000;
const uint MillisecondsPerMinute = 60000;
const uint MillisecondsPerSecond = 1000;

readonly int hoursPosition;
readonly int minutesPosition;
readonly int secondsPosition;
readonly int millisecondsPosition;
readonly char[] buffer;

public TimeFormatter(string format = "hh:mm:ss.fff")
{
buffer = format.ToCharArray();

hoursPosition = format.IndexOf("hh");
minutesPosition = format.IndexOf("mm");
secondsPosition = format.IndexOf("ss");
millisecondsPosition = format.IndexOf("fff");
}

public string FormatTime(DateTime time)
{
// Calculate time of day milliseconds
uint ms = (uint) ((((ulong) time.Ticks) / TicksPerMillisecond) % MillisecondsPerDay);

// Hours
uint value = (uint) (ms * 39093747UL >> 47);
ms -= MillisecondsPerHour * value;
if (hoursPosition != -1)
{
BufferHelper.WriteTwoDigits(value, buffer, hoursPosition);
}

// Minutes
value = (uint) (ms * 4581299UL >> 38);
ms -= MillisecondsPerMinute * value;
if (minutesPosition != -1)
{
BufferHelper.WriteTwoDigits(value, buffer, minutesPosition);
}

// Seconds
value = ms * 67109 >> 26;
ms -= MillisecondsPerSecond * value;
if (secondsPosition != -1)
{
BufferHelper.WriteTwoDigits(value, buffer, secondsPosition);
}

// Milliseconds
if (millisecondsPosition != -1)
{
BufferHelper.WriteThreeDigits(ms, buffer, millisecondsPosition);
}

return new string(buffer);
}
}

public static class PreformatHelper
{
internal static readonly uint[] TwoDigits = new uint[100];
internal static readonly ulong[] MillisecondDigits = new ulong[1000];

static PreformatHelper()
{
for (uint n = 0; n < 100; ++n)
{
TwoDigits[n] = n / 10 + '0' + ((n % 10 + '0') << 16);
}

for (ulong n = 0; n < 1000; ++n)
{
MillisecondDigits[n] = '.' + ((n / 100 + '0') << 16) + ((n / 10 % 10 + '0') << 32) + ((n % 10 + '0') << 48);
}
}
}

public static class BufferHelper
{
// Local references speed up access by 5% - don't know why.
static readonly uint[] TwoDigits = PreformatHelper.TwoDigits;
static readonly ulong[] MillisecondDigits = PreformatHelper.MillisecondDigits;

public static void WriteTwoDigits(uint value, char[] buffer, int offset)
{
var chars = TwoDigits[value];
buffer[offset] = (char) (chars);
buffer[offset + 1] = (char) (chars >> 16);
}

public static void WriteThreeDigits(uint value, char[] buffer, int offset)
{
var chars = MillisecondDigits[value];
buffer[offset] = (char) (((uint) chars) >> 16);
buffer[offset + 1] = (char) (chars >> 32 & 0xffff);
buffer[offset + 2] = (char) (chars >> 48);
}
}


# re: Performance Quiz: Fastest way to format time 5/26/2011 2:03 AM Simon Hewitt
for completeness (and to justify separating out PreformatHelper) here is an unsafe version which is slightly faster:

public unsafe class TimeFormatterUnsafe
{
const uint TicksPerMillisecond = 10000;
const uint MillisecondsPerDay = 86400000;
const uint MillisecondsPerHour = 3600000;
const uint MillisecondsPerMinute = 60000;
const uint MillisecondsPerSecond = 1000;

// Local references speed up access by 5% - don't know why.
static readonly uint[] TwoDigits = PreformatHelper.TwoDigits;
static readonly ulong[] MillisecondDigits = PreformatHelper.MillisecondDigits;

readonly int hoursPosition;
readonly int minutesPosition;
readonly int secondsPosition;
readonly int millisecondsPosition;
readonly char[] buffer;

public TimeFormatterUnsafe(string format = "hh:mm:ss.fff")
{
buffer = format.ToCharArray();

hoursPosition = format.IndexOf("hh");
minutesPosition = format.IndexOf("mm");
secondsPosition = format.IndexOf("ss");
millisecondsPosition = format.IndexOf(".fff");
}

public string FormatTime(DateTime time)
{
fixed (char* bufferPtr = &buffer[0])
{
// Calculate time of day milliseconds
uint ms = (uint) ((((ulong) time.Ticks) / TicksPerMillisecond) % MillisecondsPerDay);

// Hours
uint value = (uint) (ms * 39093747UL >> 47);
ms -= MillisecondsPerHour * value;
if (hoursPosition != -1)
{
*(uint*) &bufferPtr[hoursPosition] = TwoDigits[value];
}

// Minutes
value = (uint) (ms * 4581299UL >> 38);
ms -= MillisecondsPerMinute * value;
if (minutesPosition != -1)
{
*(uint*) &bufferPtr[minutesPosition] = TwoDigits[value];
}

// Seconds
value = ms * 67109 >> 26;
ms -= MillisecondsPerSecond * value;
if (secondsPosition != -1)
{
*(uint*) &bufferPtr[secondsPosition] = TwoDigits[value];
}

// Milliseconds
if (millisecondsPosition != -1)
{
*(ulong*) &bufferPtr[millisecondsPosition] = MillisecondDigits[ms];
}
}

return new string(buffer);
}
}


# re: Performance Quiz: Fastest way to format time 5/30/2011 6:19 PM ashigakari
FormatFastSafe (the fastest)



FixedArray.ToString() returns


System.Char[]


shouldn't it be..



return new String(FixedCharArray,0,FixedCharArray.Length);

Post A Comment
Title:
Name:
Email:
Comment:
Verification: