Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

DateTime.DayOfWeek micro optimization

Tags:

First of all:

  1. I'm asking this question just for fun and eager to learn. I have to admit I love to mess around with micro-optimizations (Although they have never led to any significant increase in speed in any of my developments).

  2. The DateTime.DayOfWeek method does not represent a bottleneck in any application of mine.

  3. And it is highly unlikely to be a problem in any other. If anyone is thinking that this method has an impact on the performance of his application, he should think about When to optimize and then, he should perform a profiling.

Decompiling DateTime class with ILSpy, we find out how DateTime.DayOfWeek is implemented:

public DayOfWeek DayOfWeek {     [__DynamicallyInvokable, TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]     get     {         return (DayOfWeek)((this.InternalTicks / 864000000000L + 1L) % 7L);     } }  public long Ticks {     [__DynamicallyInvokable, TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]     get     {         return this.InternalTicks;     } } 

This method performs the following:

  1. The ticks corresponding to the current day are divided by the existing number of ticks in a day.

  2. We add 1 to the foregoing result, in order that the remainder of division of 7 is between the numbers 0 and 6.

Is this the only way to calculate the day of the week?

Would it be possible to reimplement this in order to make it run faster?

like image 783
rpax Avatar asked Mar 07 '14 18:03

rpax


1 Answers

Let's do some tunning.

  1. Prime factorization of TimeSpan.TicksPerDay (864000000000) : Prime factorization of 864000000000

DayOfWeek now can be expressed as:

public DayOfWeek DayOfWeek {                        get     {         return (DayOfWeek)(((Ticks>>14) / 52734375 + 1L) % 7L);     } } 

And we are working in modulo 7, 52734375 % 7 it's 1. So, the code above is equal to:

public static DayOfWeek dayOfWeekTurbo(this DateTime date) {     return (DayOfWeek)(((date.Ticks >> 14) + 1) % 7); } 

Intuitively, it works. But let's prove it with code

public static void proof() {     DateTime date = DateTime.MinValue;     DateTime max_date = DateTime.MaxValue.AddDays(-1);     while (date < max_date)     {         if (date.DayOfWeek != date.dayOfWeekTurbo())         {             Console.WriteLine("{0}\t{1}", date.DayOfWeek, date.dayOfWeekTurbo());             Console.ReadLine();         }         date = date.AddDays(1);     } } 

You can run it if you want, but I assure you it works fine.

Ok, the only thing left is a bit of benchmarking.

This is an auxiliary method, in order to make the code clearer:

public static IEnumerable<DateTime> getAllDates() {     DateTime d = DateTime.MinValue;     DateTime max = DateTime.MaxValue.AddDays(-1);     while (d < max)     {         yield return d;         d = d.AddDays(1);     } } 

I guess it needs no explanation.

public static void benchDayOfWeek() {      DateTime[] dates = getAllDates().ToArray();     // for preventing the compiler doing things that we don't want to     DayOfWeek[] foo = new DayOfWeek[dates.Length];     for (int max_loop = 0; max_loop < 10000; max_loop+=100)     {           Stopwatch st1, st2;         st1 = Stopwatch.StartNew();         for (int i = 0; i < max_loop; i++)             for (int j = 0; j < dates.Length; j++)                 foo[j] = dates[j].DayOfWeek;         st1.Stop();          st2 = Stopwatch.StartNew();         for (int i = 0; i < max_loop; i++)             for (int j = 0; j < dates.Length; j++)                 foo[j] = dates[j].dayOfWeekTurbo();         st2.Stop();          Console.WriteLine("{0},{1}", st1.ElapsedTicks, st2.ElapsedTicks);      }     Console.ReadLine();     Console.WriteLine(foo[0]);  } 

Output:

96,28 172923452,50884515 352004290,111919170 521851120,168153321 683972846,215554958 846791857,264187194 1042803747,328459950 Monday 

If we make a chart with the data, it looks like this:

Chart

╔══════════════════════╦════════════════════╦═════════════════════╦═════════════╗ ║ Number of iterations ║ Standard DayOfWeek ║ Optimized DayOfWeek ║   Speedup   ║ ╠══════════════════════╬════════════════════╬═════════════════════╬═════════════╣ ║                    0 ║                 96 ║                  28 ║ 3.428571429 ║ ║                  100 ║          172923452 ║            50884515 ║ 3.398351188 ║ ║                  200 ║          352004290 ║           111919170 ║ 3.145165301 ║ ║                  300 ║          521851120 ║           168153321 ║ 3.103424404 ║ ║                  400 ║          683972846 ║           215554958 ║ 3.1730787   ║ ║                  500 ║          846791857 ║           264187194 ║ 3.205272156 ║ ║                  600 ║         1042803747 ║           328459950 ║ 3.174827698 ║ ╚══════════════════════╩════════════════════╩═════════════════════╩═════════════╝ 

3x faster.

Note: the code was compiled with Visual Studio 2013, Release mode, and ran with everything closed but the application. (Including VS, of course).

I ran the tests in a toshiba Satellite C660-2JK, Intel® Core™ i3-2350M Processor, and Windows® 7 Home Premium 64-bit.

EDIT:

As Jon Skeet noticed, this method can fail when it's not on a date boundary.

Due to Jon Skeet's comment this answer,

dayOfWeekTurbo can fail when it's not on a date boundary. For example, consider new DateTime(2014, 3, 11, 21, 39, 30) - your method thinks it's Friday when actually it's Tuesday. The "we are working in modulo 7" is the wrong way round, basically... by removing that extra division, the day-of-week changes during the day.

I decided to edit it.

If we change the proof() method,

public static void proof() {     DateTime date = DateTime.MinValue;     DateTime max_date = DateTime.MaxValue.AddSeconds(-1);     while (date < max_date)     {         if (date.DayOfWeek != date.dayOfWeekTurbo2())         {             Console.WriteLine("{0}\t{1}", date.DayOfWeek, date.dayOfWeekTurbo2());             Console.ReadLine();         }         date = date.AddSeconds(1);     } } 

Fails!

Jon Skeet was right. Let's follow Jon Skeet's advice and apply the division.

public static DayOfWeek dayOfWeekTurbo2(this DateTime date) {     return (DayOfWeek)((((date.Ticks >> 14) / 52734375L )+ 1) % 7); } 

Also, we change the method getAllDates().

public static IEnumerable<DateTime> getAllDates() {     DateTime d = DateTime.MinValue;     DateTime max = DateTime.MaxValue.AddHours(-1);     while (d < max)     {         yield return d;         d = d.AddHours(1);     } } 

And benchDayOfWeek()

public static void benchDayOfWeek() {      DateTime[] dates = getAllDates().ToArray();     DayOfWeek[] foo = new DayOfWeek[dates.Length];     for (int max_loop = 0; max_loop < 10000; max_loop ++)     {           Stopwatch st1, st2;         st1 = Stopwatch.StartNew();         for (int i = 0; i < max_loop; i++)             for (int j = 0; j < dates.Length; j++)                 foo[j] = dates[j].DayOfWeek;         st1.Stop();          st2 = Stopwatch.StartNew();         for (int i = 0; i < max_loop; i++)             for (int j = 0; j < dates.Length; j++)                 foo[j] = dates[j].dayOfWeekTurbo2();         st2.Stop();          Console.WriteLine("{0},{1}", st1.ElapsedTicks, st2.ElapsedTicks);      }     Console.ReadLine();     Console.WriteLine(foo[0]);  } 

It will still be faster? the answer is yes

Output:

90,26 43772675,17902739 84299562,37339935 119418847,47236771 166955278,72444714 207441663,89852249 223981096,106062643 275440586,125110111 327353547,145689642 363908633,163442675 407152133,181642026 445141584,197571786 495590201,217373350 520907684,236609850 511052601,217571474 610024381,260208969 637676317,275558318 

Chart

╔══════════════════════╦════════════════════╦════════════════════════╦═════════════╗ ║ Number of iterations ║ Standard DayOfWeek ║ Optimized DayOfWeek(2) ║  Speedup    ║ ╠══════════════════════╬════════════════════╬════════════════════════╬═════════════╣ ║                    1 ║           43772675 ║               17902739 ║ 2.445026708 ║ ║                    2 ║           84299562 ║               37339935 ║ 2.257624766 ║ ║                    3 ║          119418847 ║               47236771 ║ 2.528090817 ║ ║                    4 ║          166955278 ║               72444714 ║ 2.304588821 ║ ║                    5 ║          207441663 ║               89852249 ║ 2.308697504 ║ ║                    6 ║          223981096 ║              106062643 ║ 2.111781205 ║ ║                    7 ║          275440586 ║              125110111 ║ 2.201585338 ║ ║                    8 ║          327353547 ║              145689642 ║ 2.246923958 ║ ║                    9 ║          363908633 ║              163442675 ║ 2.226521519 ║ ║                   10 ║          407152133 ║              181642026 ║ 2.241508433 ║ ║                   11 ║          445141584 ║              197571786 ║ 2.25306251  ║ ║                   12 ║          495590201 ║              217373350 ║ 2.279903222 ║ ║                   13 ║          520907684 ║              236609850 ║ 2.201546909 ║ ║                   14 ║          511052601 ║              217571474 ║ 2.348895246 ║ ║                   15 ║          610024381 ║              260208969 ║ 2.344363391 ║ ║                   16 ║          637676317 ║              275558318 ║ 2.314124725 ║ ╚══════════════════════╩════════════════════╩════════════════════════╩═════════════╝ 

2x faster.

like image 71
rpax Avatar answered Nov 02 '22 13:11

rpax