Recent

Author Topic: Proposal to improve IsLeapYear and EndOfAMonth-Functions  (Read 3737 times)

Zvoni

  • Hero Member
  • *****
  • Posts: 2374
Proposal to improve IsLeapYear and EndOfAMonth-Functions
« on: February 26, 2024, 10:24:45 am »
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. :D

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
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

rvk

  • Hero Member
  • *****
  • Posts: 6208
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #1 on: February 26, 2024, 10:40:50 am »
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   8-)

(Although not easier to understand obviously  ;) )

CCRDude

  • Hero Member
  • *****
  • Posts: 602
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #2 on: February 26, 2024, 10:47:12 am »
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

  • Hero Member
  • *****
  • Posts: 1172
    • http://www.cdbc.dk
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #3 on: February 26, 2024, 11:05:16 am »
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
If it ain't broke, don't fix it ;)
PCLinuxOS(rolling release) 64bit -> KDE5 -> FPC 3.2.2 -> Lazarus 2.2.6 up until Jan 2024 from then on it's: KDE5/QT5 -> FPC 3.3.1 -> Lazarus 3.0

Zvoni

  • Hero Member
  • *****
  • Posts: 2374
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #4 on: February 26, 2024, 11:57:48 am »
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
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

Thaddy

  • Hero Member
  • *****
  • Posts: 14657
  • Sensorship about opinions does not belong here.
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #5 on: February 26, 2024, 12:15:44 pm »
conditional jumps are bad and modulo calculations are worse.... at least in the olden days... 8-)
bitrate is always calculated like this:sample rate * bitdepth * number of channels.

wp

  • Hero Member
  • *****
  • Posts: 12045
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #6 on: February 26, 2024, 01:06:29 pm »
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

  • Hero Member
  • *****
  • Posts: 1172
    • http://www.cdbc.dk
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #7 on: February 26, 2024, 01:50:37 pm »
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
If it ain't broke, don't fix it ;)
PCLinuxOS(rolling release) 64bit -> KDE5 -> FPC 3.2.2 -> Lazarus 2.2.6 up until Jan 2024 from then on it's: KDE5/QT5 -> FPC 3.3.1 -> Lazarus 3.0

ASerge

  • Hero Member
  • *****
  • Posts: 2263
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #8 on: February 26, 2024, 02:04:30 pm »
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

  • Hero Member
  • *****
  • Posts: 14657
  • Sensorship about opinions does not belong here.
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #9 on: February 26, 2024, 02:10:24 pm »
note modulo 16 is wrong; try 2100 (not a leap year)!!!!!!
accuracy seems more important to me than speed. >:D
so 400 plz.
although that single mod has likely not any influence on speed.
« Last Edit: February 26, 2024, 02:21:58 pm by Thaddy »
bitrate is always calculated like this:sample rate * bitdepth * number of channels.

rvk

  • Hero Member
  • *****
  • Posts: 6208
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #10 on: February 26, 2024, 02:18:32 pm »
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

  • Hero Member
  • *****
  • Posts: 14657
  • Sensorship about opinions does not belong here.
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #11 on: February 26, 2024, 02:23:37 pm »
nope mod 16 is wrong. basic math. turn exact into approximation.
« Last Edit: February 26, 2024, 02:27:36 pm by Thaddy »
bitrate is always calculated like this:sample rate * bitdepth * number of channels.

bytebites

  • Hero Member
  • *****
  • Posts: 645
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #12 on: February 26, 2024, 02:35:33 pm »
Code: Pascal  [Select][+][-]
  1.   for i:=1 to 4000 do
  2.     if IsLeapYear1(i)<>IsLeapYear2(i) then writeln('Error ',i);  

paweld

  • Hero Member
  • *****
  • Posts: 1038
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #13 on: February 26, 2024, 02:36:08 pm »
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
« Last Edit: February 26, 2024, 02:39:17 pm by paweld »
Best regards / Pozdrawiam
paweld

rvk

  • Hero Member
  • *****
  • Posts: 6208
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #14 on: February 26, 2024, 02:44:45 pm »
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.

 

TinyPortal © 2005-2018