Recent

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

Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #15 on: February 26, 2024, 02:59:28 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.
Someone explained it to me, why that works is, because 400 ist the LCM (least common multiple) of 100 and 16, and  "... mod 16" is fast because 16 = 2 ^ 4 and therefore "...mod 16" gets "translated" to a bitwise And

EDIT:
i apologize.
I forgot to mention, that the Source of FPC i have is FPC3.2.2-32 Bit.
So sorry, if the Trunk-version has been "rewritten" (or not), i would have no idea.


--> Thx to wp for the Test-Program

Result on my Dell-Laptop
FPC 3.2.2-32 Bit
Quote
LEAP YEAR TESTS...
  Loop only: 1.421 s
  FPC:       2.117 s, corrected: 0.696 s (100%)
  Variant 1: 1.864 s, corrected: 0.443 s ( 64%)
  Variant 2: 1.834 s, corrected: 0.413 s ( 59%)

MONTH DAYS TESTS...
  Loop only: 2.373 s
  FPC:       3.503 s, corrected: 1.130 s (100%)
  Variant 1: 2.712 s, corrected: 0.339 s ( 30%)
« Last Edit: February 26, 2024, 03:08:54 pm by Zvoni »
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

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11459
  • FPC developer.
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #16 on: February 26, 2024, 04:27:47 pm »
My tests on 32-bit binaries windows 11 on a 5700X:

Quote
c:\testing>fpc -O4 bench -Sd
Free Pascal Compiler version 3.2.2 [2021/05/15] for i386
Copyright (c) 1993-2021 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling bench.pp
Linking bench.exe
118 lines compiled, 0.1 sec, 78544 bytes code, 4372 bytes data

c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.924 s
  FPC:       1.437 s, corrected: 0.513 s (100%)
  Variant 1: 1.025 s, corrected: 0.101 s ( 20%)
  Variant 2: 1.077 s, corrected: 0.153 s ( 30%)

MONTH DAYS TESTS...
  Loop only: 1.694 s
  FPC:       2.440 s, corrected: 0.746 s (100%)
  Variant 1: 1.939 s, corrected: 0.245 s ( 33%)

Test finished. Press ENTER to close...

c:\testing>dofpc

c:\testing>fpc -O4 bench -Sd
Free Pascal Compiler version 3.3.1 [2024/02/22] for i386
Copyright (c) 1993-2024 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling bench.pp
Linking bench.exe
118 lines compiled, 0.1 sec, 83376 bytes code, 4676 bytes data

c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.719 s
  FPC:       0.982 s, corrected: 0.263 s (100%)
  Variant 1: 0.744 s, corrected: 0.025 s ( 10%)
  Variant 2: 0.745 s, corrected: 0.026 s ( 10%)

MONTH DAYS TESTS...
  Loop only: 1.198 s
  FPC:       1.633 s, corrected: 0.435 s (100%)
  Variant 1: 1.328 s, corrected: 0.130 s ( 30%)

Test finished. Press ENTER to close...

64-bit  trunk only (about a month old:)

Quote
c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.823 s
  FPC:       1.080 s, corrected: 0.257 s (100%)
  Variant 1: 0.790 s, corrected: 0.033 s (-13%)
  Variant 2: 0.787 s, corrected: 0.036 s (-14%)

MONTH DAYS TESTS...
  Loop only: 1.329 s
  FPC:       1.726 s, corrected: 0.397 s (100%)
  Variant 1: 1.488 s, corrected: 0.159 s ( 40%)

Test finished. Press ENTER to close...

Negative percentages ?!?!  :)
« Last Edit: February 26, 2024, 04:29:34 pm by marcov »

Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #17 on: February 26, 2024, 05:02:09 pm »
My tests on 32-bit binaries windows 11 on a 5700X:

Quote
c:\testing>fpc -O4 bench -Sd
Free Pascal Compiler version 3.2.2 [2021/05/15] for i386
Copyright (c) 1993-2021 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling bench.pp
Linking bench.exe
118 lines compiled, 0.1 sec, 78544 bytes code, 4372 bytes data

c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.924 s
  FPC:       1.437 s, corrected: 0.513 s (100%)
  Variant 1: 1.025 s, corrected: 0.101 s ( 20%)
  Variant 2: 1.077 s, corrected: 0.153 s ( 30%)

MONTH DAYS TESTS...
  Loop only: 1.694 s
  FPC:       2.440 s, corrected: 0.746 s (100%)
  Variant 1: 1.939 s, corrected: 0.245 s ( 33%)

Test finished. Press ENTER to close...

c:\testing>dofpc

c:\testing>fpc -O4 bench -Sd
Free Pascal Compiler version 3.3.1 [2024/02/22] for i386
Copyright (c) 1993-2024 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling bench.pp
Linking bench.exe
118 lines compiled, 0.1 sec, 83376 bytes code, 4676 bytes data

c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.719 s
  FPC:       0.982 s, corrected: 0.263 s (100%)
  Variant 1: 0.744 s, corrected: 0.025 s ( 10%)
  Variant 2: 0.745 s, corrected: 0.026 s ( 10%)

MONTH DAYS TESTS...
  Loop only: 1.198 s
  FPC:       1.633 s, corrected: 0.435 s (100%)
  Variant 1: 1.328 s, corrected: 0.130 s ( 30%)

Test finished. Press ENTER to close...

64-bit  trunk only (about a month old:)

Quote
c:\testing>bench
LEAP YEAR TESTS...
  Loop only: 0.823 s
  FPC:       1.080 s, corrected: 0.257 s (100%)
  Variant 1: 0.790 s, corrected: 0.033 s (-13%)
  Variant 2: 0.787 s, corrected: 0.036 s (-14%)

MONTH DAYS TESTS...
  Loop only: 1.329 s
  FPC:       1.726 s, corrected: 0.397 s (100%)
  Variant 1: 1.488 s, corrected: 0.159 s ( 40%)

Test finished. Press ENTER to close...

Negative percentages ?!?!  :)
Because it's quicker than the loop?  :o :o :o
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

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11459
  • FPC developer.
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #18 on: February 26, 2024, 10:19:54 pm »
Because it's quicker than the loop?  :o :o :o

Faster than nothing? I think I need to redo it on my work machine tomorrow and change power management. I suspect it is on balanced, and not always on.

Then after a while running it might clock up, and then something can be faster than nothing.

Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #19 on: February 26, 2024, 11:54:32 pm »
Because it's quicker than the loop?  :o :o :o

Faster than nothing? I think I need to redo it on my work machine tomorrow and change power management. I suspect it is on balanced, and not always on.

Then after a while running it might clock up, and then something can be faster than nothing.
You do know, that if you travel faster than light you arrive before you left? :D


Marco, admit it: you already have a super-duper secret quantum computer for testing;)
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

TRon

  • Hero Member
  • *****
  • Posts: 2543
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #20 on: February 27, 2024, 12:37:09 am »
Marco, admit it: you already have a super-duper secret quantum computer for testing;)
Hush... Marco is still under NDA thus not at liberty to discuss  ;D

bytebites

  • Hero Member
  • *****
  • Posts: 642
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #21 on: February 27, 2024, 09:34:37 am »
What about running test without random?
Code: Pascal  [Select][+][-]
  1.  
  2. function LeapYearTest(Func: TLeapYearFunc): TDateTime;
  3. var
  4.   i: Integer;
  5.   t: TDateTime;
  6.   year: Word;
  7. begin
  8.   t := Now();
  9.   for i := 1 to NUM_RUNS do
  10.   begin
  11.     year := i mod 4000;
  12.     Func(year);
  13.   end;
  14.   Result := Now() - t;
  15. end;

wp

  • Hero Member
  • *****
  • Posts: 11923
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #22 on: February 27, 2024, 09:43:58 am »
Strange, now the "optimized" variants become slower by a factor 2...

Josh

  • Hero Member
  • *****
  • Posts: 1274
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #23 on: February 27, 2024, 10:33:37 am »
if the check is done on same dataset and the initial t0 test is run twice to optimize caches, iam getting little difference.
nb i copied the fpc version of isleapyear into prog, to force same code optimization.
also the test routine  check for year+3-1;

LEAP YEAR TESTS...
  Loop only: 1.706 s
  FPC:       4.851 s, corrected: 3.145 s (100%)
  Variant 1: 4.849 s, corrected: 3.143 s (100%)
  Variant 2: 5.050 s, corrected: 3.344 s (106%)

MONTH DAYS TESTS...
  Loop only: 3.969 s
  FPC:       6.213 s, corrected: 2.244 s (100%)
  Variant 1: 4.738 s, corrected: 0.769 s ( 34%)


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

Lazarus 3.1 (rev lazarus_3_0-101-g54c90de2f2) FPC 3.2.3 i386-win32-win32/win64
« Last Edit: February 27, 2024, 10:35:41 am by Josh »
The best way to get accurate information on the forum is to post something wrong and wait for corrections.

Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #24 on: February 27, 2024, 11:40:14 am »
There is something weird going on.....

i noticed in WP's testcode, that he uses the original FPC-Version of IsLeapYear in the MonthDays-Functions, so i changed MonthDays1 to use IsLeapYear1 (and in a second run to use IsLeapYear2)

Results (with -O3) FPC3.2.2-32Bit
LEAP YEAR TESTS...
  Loop only: 1.381 s
  FPC:       2.165 s, corrected: 0.784 s (100%)
  Variant 1: 1.945 s, corrected: 0.564 s ( 72%)
  Variant 2: 1.781 s, corrected: 0.400 s ( 51%)

MONTH DAYS TESTS...
  Loop only: 2.412 s
  FPC:       3.301 s, corrected: 0.889 s (100%)
  Variant 1: 2.705 s, corrected: 0.293 s ( 33%)
  Variant 2: 2.692 s, corrected: 0.280 s ( 31%)

How is it possible, that both MonthDays-Function (v1 and v2) are faster than the "solo" IsLeapYear runs?!?!?!
MonthDays-Function USE the IsLeapYear 1/2
Huh?

Here the "v2" of MonthDays (wanted to get rid of the Inner If-Condition)
Code: Pascal  [Select][+][-]
  1. Function MonthDays2(const AYear, AMonth: Word): Word;
  2. begin
  3.   If AMonth=2 Then
  4.      Result:=28+Ord(IsLeapYear2(AYear))
  5.   Else
  6.      Result:=30 Or (AMonth Xor (AMonth shr 3));
  7. end;        
« Last Edit: February 27, 2024, 11:45:04 am by Zvoni »
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

MarkMLl

  • Hero Member
  • *****
  • Posts: 6693
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #25 on: February 28, 2024, 09:09:16 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  ;) )

In which case there should be an explanatory comment in the source, or a citation to wherever the hack was first published.

Programming should not be an exercise in one-upmanship, with the author out to demonstrate his superiority by forcing the reader to analyse every line ab initio.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #26 on: February 28, 2024, 09:21:40 am »
In which case there should be an explanatory comment in the source, or a citation to wherever the hack was first published.

Programming should not be an exercise in one-upmanship, with the author out to demonstrate his superiority by forcing the reader to analyse every line ab initio.

MarkMLl
OK, agreed. Should have done that.
It's just, that i did understand the " ... mod 400" but not how that could be "translated" to "...mod 16"
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

MarkMLl

  • Hero Member
  • *****
  • Posts: 6693
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #27 on: February 28, 2024, 09:27:47 am »
OK, agreed. Should have done that.
It's just, that i did understand the " ... mod 400" but not how that could be "translated" to "...mod 16"

Please note that that was not intended as personal criticism, but it occurred to me overnight that there were a couple of current threads which discussed "improving" code which risked losing the clarity or precision of the original.

There's plenty of clever hacks in the seminal "Calendrical Calculations". If you enjoy Lisp.

https://en.wikipedia.org/wiki/Calendrical_Calculations

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

rvk

  • Hero Member
  • *****
  • Posts: 6171
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #28 on: February 28, 2024, 09:37:39 am »
It's just, that i did understand the " ... mod 400" but not how that could be "translated" to "...mod 16"
Because you only hit every 100 years... only 400, 800, 1200, 1600, 2000, 2400, 2800... etc is dividable by 16.
No other 100th number is dividable by 16.

So instead of checking for mod 400 = 0 you can also check for mod 16 = 0.

And otherwise... check with a loop ;) (no numbers will be found)

Code: Pascal  [Select][+][-]
  1. program Project1;
  2. var
  3.   i: integer;
  4.   mod400, mod16: boolean;
  5. begin
  6.   i := 100;
  7.   while i < 200000 do
  8.   begin
  9.     mod400 := (i mod 400 = 0);
  10.     mod16 := (i mod 16 = 0);
  11.     if mod400 and not mod16 then writeln('oops ', i);
  12.     i := i + 100;
  13.   end;
  14.   writeln('done');
  15.   readln;
  16. end.




Zvoni

  • Hero Member
  • *****
  • Posts: 2333
Re: Proposal to improve IsLeapYear and EndOfAMonth-Functions
« Reply #29 on: February 28, 2024, 09:39:43 am »
Because you only hit every 100 years... only 400, 800, 1200, 1600, 2000, 2400, 2800... etc is dividable by 16.
No other 100th number is dividable by 16.

So instead of checking for mod 400 = 0 you can also check for mod 16 = 0.
rvk, yeah, i finally got the gist of how it works, because you enter the "mod 16" branch only on an even "century" (1600, 1700, 1800 etc.)
and mod 16 can be "translated" to a bitwise And

btw: What's the final conclusion?
Is it an improvement (both "functions")?
and since i don't have access to the trunk/main source-code: could someone check how IsLeapyear is implemented there?
Because to me it's not making any sense, why with FPC3.2.2 "IsLeapYearV1/2" is faster than with the original in trunk
« Last Edit: February 28, 2024, 09:42:04 am by Zvoni »
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

 

TinyPortal © 2005-2018