Proposal to improve IsLeapYear and EndOfAMonth-Functions

[Zvoni]

Hi Folks,
this weekend i watched this fascinating video on youTube: https://www.youtube.com/watch?v=J9KijLyP-yg
"Implementing Fast Calendar Algorithms"

Up front: I didn't want to post this in the FPC Development Subforum, because, frankly, i'm not that good a programmer.

That said: Out of curiosity (and i know what killed the cat), i looked up, how IsLeapYear and EndOfAMonth is implemented in FPC
(IsLeapYear in dati.inc and EndOfAMonth in DateUtil.inc resp. datih.inc)

Color me surprised finding out, that the implementation is basically what the Presenter called the "classic" way.

Proposal (and request for speed-tests)
IsLeapYear

Code: Pascal  [Select][+][-]

1. function IsLeapYear(Year: Word): boolean;
2. begin
3.   Result := (Year mod 4 = 0) and ((Year mod 100 <> 0) or (Year mod 400 = 0));
4. end;  

Change to

Code: Pascal  [Select][+][-]

1. Function IsLeapYear(Year:Word):Boolean;
2. Begin
3.   If Year mod 100<>0 Then
4.      Result:=(Year mod 4)=0
5.   Else
6.      Result:=(Year mod 400)=0;
7. End;

In the video they even "optimized" above further, but this one escapes me
(modulo by 16 instead of 400 --> huh?)

Code: Pascal  [Select][+][-]

1. Function IsLeapYear(Year:Word):Boolean;
2. Begin
3.   If Year mod 100<>0 Then
4.      Result:=(Year mod 4)=0
5.   Else
6.      Result:=(Year mod 16)=0;
7. End;

EndOfAMonth --> the "classic" being a Lookup-Array
The presenter called it something like "cache-concurrency" (i think?!?!)
but, frankly, that one escaped me completely

Code: Pascal  [Select][+][-]

1. //in datih.inc
2. { True=Leapyear }
3.    MonthDays: array [Boolean] of TDayTable =
4.      ((31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31),
5.       (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31));    
6.  
7. //in DateUtil.inc
8. Function EndOfAMonth(const AYear, AMonth: Word): TDateTime;
9. begin
10.   Result:=EncodeDateTime(AYear,AMonth,MonthDays[IsLeapYear(AYear),AMonth],23,59,59,999);
11. end;

Change to (MonthDays becoming a Function instead of a Lookup-Array)

Code: Pascal  [Select][+][-]

1. Function MonthDays(const AYear, AMonth: Word): Word;
2. begin
3.   If AMonth=2 Then
4.      If IsLeapYear(AYear) Then
5.         Result:=29
6.      Else
7.         Result:=28
8.   Else
9.      Result:=30 Or (AMonth Xor (AMonth shr 3));
10. end;

If we all agree, that it is an improvement, we can maybe move this thread to FPC-Dev SubForum, but someone else would have to make a patch.
Never done that

Thoughts? Opinions?

btw: I found that "computational Calendar" fascinating.....placing March as the first Month of a Year

[rvk]

In the video they even "optimized" above further, but this one escapes me
(modulo by 16 instead of 400 --> huh?)

Not so strange.
The if-part only hits every 100 years and only 400 and 800 etc. is dividable by 16 in that range. And because mod 16 is more efficient than mod 400, the mod 16 is more optimized   

(Although not easier to understand obviously  )

[CCRDude]

Since the compiler optimizes and will not evaluate "b" if in "a and b" the "a" is already false, (Year mod 4 = 0) already finishes the tests for 3 out of 4 years with just one modulo (if the first condition fails, the others won't be tested any more). Your second code snippet executes at least 2 modulo operations. Same goes for third snippet.

So without having tested anything, I would strongly assume the original is way better.

You could make it inline to save a few nanoseconds maybe.

[cdbc]

Hi
Add to @ccrdude's post, indexing into an array is way faster than calling a function... Old-school "Sacrifice a few bytes on the stack to gain speed", 'Merge-Sort' springs to mind...
Regards Benny

[Zvoni]

Since the compiler optimizes and will not evaluate "b" if in "a and b" the "a" is already false, (Year mod 4 = 0) already finishes the tests for 3 out of 4 years with just one modulo (if the first condition fails, the others won't be tested any more). Your second code snippet executes at least 2 modulo operations. Same goes for third snippet.

So without having tested anything, I would strongly assume the original is way better.

You could make it inline to save a few nanoseconds maybe.

Hey, no Problem for me. That's why i asked for opinions.

Yes, i know about short-circuiting, but
if i understood the presenter correctly it has more to do with "branch prediction" (whatever that is) and it's "consequences" for the compiler

[Thaddy]

conditional jumps are bad and modulo calculations are worse.... at least in the olden days...

[wp]

A simple speed test using 200 millions of random years and months:

Code: Pascal  [Select][+][-]

1. program project1;
2.  
3. uses
4.   SysUtils;
5.  
6. const
7.   NUM_RUNS = 200*1000*1000;
8.  
9. type
10.   TLeapYearFunc = function (Year: Word): Boolean;
11.   TMonthDaysFunc = function (const AYear, AMonth: Word): Word;
12.  
13. { Leap year tests }
14.  
15. function EmptyLeapYear(Year: Word): Boolean;
16. begin
17.   Result := false;
18. end;
19.  
20. Function IsLeapYear1(Year:Word):Boolean;
21. Begin
22.   If Year mod 100<>0 Then
23.      Result:=(Year mod 4)=0
24.   Else
25.      Result:=(Year mod 400)=0;
26. End;
27.  
28. Function IsLeapYear2(Year:Word):Boolean;
29. Begin
30.   If Year mod 100<>0 Then
31.      Result:=(Year mod 4)=0
32.   Else
33.      Result:=(Year mod 16)=0;
34. End;
35.  
36. function LeapYearTest(Func: TLeapYearFunc): TDateTime;
37. var
38.   i: Integer;
39.   t: TDateTime;
40.   year: Word;
41. begin
42.   t := Now();
43.   for i := 1 to NUM_RUNS do
44.   begin
45.     year := Random(10000);
46.     Func(year);
47.   end;
48.   Result := Now() - t;
49. end;
50.  
51. { Month days tests }
52.  
53. function EmptyMonthDays(const AYear, AMonth: Word): Word;
54. begin
55.   Result := 30;
56. end;
57.  
58. Function MonthDaysFPC(const AYear, AMonth: Word): Word;
59. begin
60.   Result := MonthDays[IsLeapYear(AYear), AMonth];
61. end;
62.  
63. Function MonthDays1(const AYear, AMonth: Word): Word;
64. begin
65.   If AMonth=2 Then
66.      If IsLeapYear(AYear) Then
67.         Result:=29
68.      Else
69.         Result:=28
70.   Else
71.      Result:=30 Or (AMonth Xor (AMonth shr 3));
72. end;
73.  
74. function MonthDaysTest(Func: TMonthDaysFunc): TDateTime;
75. var
76.   i: Integer;
77.   t: TDateTime;
78.   year: Word;
79.   month: Word;
80. begin
81.   t := Now();
82.   for i := 1 to NUM_RUNS do
83.   begin
84.     year := Random(10000);
85.     month := Random(12) + 1;
86.     Func(year, month);
87.   end;
88.   Result := Now() - t;
89. end;
90.  
91. const
92.   FMT = 's.zzz" s"';
93. var
94.   t0, t1, t2, t3: TDateTime;
95. begin
96.   WriteLn('LEAP YEAR TESTS...');
97.   t0 := LeapYearTest(@EmptyLeapYear);
98.   t1 := LeapYearTest(@IsLeapYear);
99.   t2 := LeapYearTest(@IsLeapYear1);
100.   t3 := LeapYearTest(@IsLeapYear2);
101.   WriteLn('  Loop only: ', FormatDateTime(FMT, t0));
102.   WriteLn('  FPC:       ', FormatDateTime(FMT, t1), ', corrected: ', FormatDateTime(FMT, t1-t0), ' (100%)');
103.   WriteLn('  Variant 1: ', FormatDatetime(FMT, t2), ', corrected: ', FormatDateTime(FMT, t2-t0), ' (', (t2-t0)/(t1-t0)*100:3:0, '%)');
104.   WriteLn('  Variant 2: ', FormatDateTime(FMT, t3), ', corrected: ', FormatDateTime(FMT, t3-t0), ' (', (t3-t0)/(t1-t0)*100:3:0, '%)');
105.  
106.   WriteLn;
107.  
108.   WriteLn('MONTH DAYS TESTS...');
109.   t0 := MonthDaysTest(@EmptyMonthDays);
110.   t1 := MonthDaysTest(@MonthDaysFPC);
111.   t2 := MonthDaysTest(@MonthDays1);
112.   WriteLn('  Loop only: ', FormatDateTime(FMT, t0));
113.   WriteLn('  FPC:       ', FormatDateTime(FMT, t1), ', corrected: ', FormatDateTime(FMT, t1-t0), ' (100%)');
114.   WriteLn('  Variant 1: ', FormatDatetime(FMT, t2), ', corrected: ', FormatDateTime(FMT, t2-t0), ' (', (t2-t0)/(t1-t0)*100:3:0, '%)');
115.  
116.   WriteLn;
117.   Write('Test finished. Press ENTER to close...');
118.   ReadLn;
119. end.

Output:

Code: [Select]

LEAP YEAR TESTS...
  Loop only: 1.194 s
  FPC:       1.786 s, corrected: 0.592 s (100%)
  Variant 1: 1.744 s, corrected: 0.550 s ( 93%)
  Variant 2: 1.629 s, corrected: 0.435 s ( 73%)

MONTH DAYS TESTS...
  Loop only: 2.150 s
  FPC:       2.994 s, corrected: 0.844 s (100%)
  Variant 1: 2.425 s, corrected: 0.275 s ( 33%))
Result:

• IsLeapYear variant 1 (Year mod 400) takes almost the same time as the FPC routine.
• IsLeapYear variant 2 (Year mod 16) is faster by about 25%.
• The proposed MonthDays function is faster by 66% than the FPC lookup.

[cdbc]

Hi
@wp: I did your little experiment on my HP lappy, here are the results:

Code: Bash  [Select][+][-]

1. [bc@hp leapyear_speedtest]$ ~/laz_3/fpc/bin/x86_64-linux/fpc.sh project1.pp
2. Free Pascal Compiler version 3.3.1-15019-g664f8fc2ba-dirty [2024/01/28] for x86_64
3. Copyright (c) 1993-2024 by Florian Klaempfl and others
4. Target OS: Linux for x86-64
5. Compiling project1.pp
6. Linking project1
7. 119 lines compiled, 0.3 sec, 449568 bytes code, 188696 bytes data
8. [bc@hp leapyear_speedtest]$ ./project1
9. LEAP YEAR TESTS...
10.  
11.   Loop only: 3.713 s
12.   FPC:       4.095 s, corrected: 0.382 s (100%)
13.   Variant 1: 5.148 s, corrected: 1.435 s (376%)
14.   Variant 2: 4.925 s, corrected: 1.212 s (317%)
15.  
16. MONTH DAYS TESTS...
17.   Loop only: 6.242 s
18.   FPC:       7.947 s, corrected: 1.705 s (100%)
19.   Variant 1: 7.121 s, corrected: 0.879 s ( 52%)
20.  
21. Test finished. Press ENTER to close...[bc@hp leapyear_speedtest]$ fpc pr
22. project1     project1.o   project1.pp  
23. [bc@hp leapyear_speedtest]$ fpc project1.pp
24. Free Pascal Compiler version 3.2.2 [2023/06/16] for x86_64
25. Copyright (c) 1993-2021 by Florian Klaempfl and others
26. Target OS: Linux for x86-64
27. Compiling project1.pp
28. Linking project1
29. 119 lines compiled, 0.2 sec
30. [bc@hp leapyear_speedtest]$ ./project1
31. LEAP YEAR TESTS...
32.   Loop only: 5.038 s
33.   FPC:       6.908 s, corrected: 1.870 s (100%)
34.   Variant 1: 7.731 s, corrected: 2.693 s (144%)
35.   Variant 2: 7.774 s, corrected: 2.736 s (146%)
36.  
37. MONTH DAYS TESTS...
38.   Loop only: 9.109 s
39.   FPC:       12.535 s, corrected: 3.426 s (100%)
40.   Variant 1: 10.574 s, corrected: 1.465 s ( 43%)
41.  
42. Test finished. Press ENTER to close...
43. [bc@hp leapyear_speedtest]$
44.  

Can it really be, that the trunk compiler produces this much faster code?!?
Also my results seems to deviate from yours....
Regards Benny

[ASerge]

Windows x64, FPC 3.2.2:

Code: Text  [Select][+][-]

1. LEAP YEAR TESTS...
2.   Loop only: 2.232 s
3.   FPC:       6.088 s, corrected: 3.856 s (100%)
4.   Variant 1: 6.279 s, corrected: 4.047 s (105%)
5.   Variant 2: 6.326 s, corrected: 4.094 s (106%)
6.  
7. MONTH DAYS TESTS...
8.   Loop only: 4.146 s
9.   FPC:       8.112 s, corrected: 3.966 s (100%)
10.   Variant 1: 4.902 s, corrected: 0.756 s ( 19%)

The new MonthDays function looks faster.

[Thaddy]

note modulo 16 is wrong; try 2100 (not a leap year)!!!!!!
accuracy seems more important to me than speed.
so 400 plz.
although that single mod has likely not any influence on speed.

[rvk]

note modulo 16 is wrong; try 2100 (not a leap year)!!!!!!

And you think 2100 is dividable by 16 ???

mod 16 is perfectly fine here
(but the speed improvement would be really really small and debatably if it weighs heavier than the complexity, especially if our Thaddy can't even grasp this ).

[Thaddy]

nope mod 16 is wrong. basic math. turn exact into approximation.

[bytebites]

Code: Pascal  [Select][+][-]

1.   for i:=1 to 4000 do
2.     if IsLeapYear1(i)<>IsLeapYear2(i) then writeln('Error ',i);  

[paweld]

At my place it gives such results, Windows 10, all x86_64
- fpc trunk

Code: [Select]

LEAP YEAR TESTS...
  Loop only: 0.618 s
  FPC:       1.096 s, corrected: 0.478 s (100%)
  Variant 1: 1.132 s, corrected: 0.514 s (108%)
  Variant 2: 1.132 s, corrected: 0.514 s (108%)

MONTH DAYS TESTS...
  Loop only: 1.107 s
  FPC:       1.832 s, corrected: 0.725 s (100%)
  Variant 1: 1.660 s, corrected: 0.553 s ( 76%)
- fpc 3.2-fixes

Code: [Select]

LEAP YEAR TESTS...
  Loop only: 0.875 s
  FPC:       1.673 s, corrected: 0.798 s (100%)
  Variant 1: 1.124 s, corrected: 0.249 s ( 31%)
  Variant 2: 1.114 s, corrected: 0.239 s ( 30%)

MONTH DAYS TESTS...
  Loop only: 1.711 s
  FPC:       2.581 s, corrected: 0.870 s (100%)
  Variant 1: 2.019 s, corrected: 0.308 s ( 35%)
- fpc 3.2.2

Code: [Select]

LEAP YEAR TESTS...
  Loop only: 0.819 s
  FPC:       1.698 s, corrected: 0.879 s (100%)
  Variant 1: 1.127 s, corrected: 0.308 s ( 35%)
  Variant 2: 1.124 s, corrected: 0.305 s ( 35%)

MONTH DAYS TESTS...
  Loop only: 1.568 s
  FPC:       2.523 s, corrected: 0.955 s (100%)
  Variant 1: 1.920 s, corrected: 0.352 s ( 37%)
in trunk "FPC" version is faster, but "1" and "2" slower

[rvk]

nope mod 16 is wrong. basic math. turn exact into approximation.

I'm not sure what you mean by "turn exact into approximation".
(it seems you are getting more cryptic and short every year you get older )

mod 16 = 0 is the same as mod 400 = 0 if you only take the 100th numbers.
Period.
Nothing about approximation.

But I agree that the speed improvement for only once per 100 years would be negligible.