Forum > General

Proposal to improve IsLeapYear and EndOfAMonth-Functions

(1/10) > >>

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. :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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---function IsLeapYear(Year: Word): boolean;begin  Result := (Year mod 4 = 0) and ((Year mod 100 <> 0) or (Year mod 400 = 0));end;   Change to

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---Function IsLeapYear(Year:Word):Boolean;Begin  If Year mod 100<>0 Then     Result:=(Year mod 4)=0  Else     Result:=(Year mod 400)=0;End;
In the video they even "optimized" above further, but this one escapes me
(modulo by 16 instead of 400 --> huh?)

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---Function IsLeapYear(Year:Word):Boolean;Begin  If Year mod 100<>0 Then     Result:=(Year mod 4)=0  Else     Result:=(Year mod 16)=0;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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---//in datih.inc{ True=Leapyear }   MonthDays: array [Boolean] of TDayTable =     ((31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31),      (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31));     //in DateUtil.incFunction EndOfAMonth(const AYear, AMonth: Word): TDateTime;begin  Result:=EncodeDateTime(AYear,AMonth,MonthDays[IsLeapYear(AYear),AMonth],23,59,59,999);end;
Change to (MonthDays becoming a Function instead of a Lookup-Array)

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---Function MonthDays(const AYear, AMonth: Word): Word;begin  If AMonth=2 Then     If IsLeapYear(AYear) Then        Result:=29     Else        Result:=28  Else     Result:=30 Or (AMonth Xor (AMonth shr 3));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:

--- Quote from: Zvoni on February 26, 2024, 10:24:45 am ---In the video they even "optimized" above further, but this one escapes me
(modulo by 16 instead of 400 --> huh?)

--- End quote ---
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:
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:

--- Quote from: CCRDude 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.

--- End quote ---
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

Navigation

[0] Message Index

[#] Next page

Go to full version