Cleaner (and more performant!) implementation of Time.leap_year?

[rab]

In Mark Siemers (@marksiemers) post Top 5 Reasons for Ruby-ists to Use Crystal, he used an example of a leap year predicate early in the article to demonstrate the similarity of Ruby and Crystal code. In one of the comments, an alternate implementation of a leap_year? predicate was offered and Mark said it looked better:

Yeah, I like that too. More readable, and in most cases, it is one less operation.

Since I've written this same predicate in multiple languages and system across 30 years or more, I chimed in with a brief analysis confirming that it was better, but didn't go far enough if minimizing operations was a goal. Mark suggested that I offer my implementation as a PR.

$ git --no-pager diff --unified=5

diff --git a/src/time.cr b/src/time.cr
index 79ee7ba..2460171 100644
--- a/src/time.cr
+++ b/src/time.cr
@@ -475,11 +475,11 @@ struct Time
   def self.leap_year?(year : Int) : Bool
     unless 1 <= year <= 9999
       raise ArgumentError.new "Invalid year"
     end
 
-    (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)
+    year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
   end
 
   def inspect(io : IO)
     Format.new("%F %T").format(self, io)

Briefly, since 75% of all years will fail the year % 4 == 0 test, letting the && short-circuit before checking for century years is a big win.

[RX14]

Please can you make a PR, would be cool to benchmark Time.leap_year? too.

[rab]

Yes, I'm planning on it, but it's taking a while to get all the crystal infrastructure installed. 🙁

[RX14]

@rab what exactly are you finding difficult or time-consuming, just for reference.

[rab]

$ brew install crystal-lang --with-llvm
==> Auto-updated Homebrew!
Updated 2 taps (caskroom/cask, caskroom/fonts).
Updating Homebrew...

==> Installing dependencies for crystal-lang: libatomic_ops, bdw-gc, sphinx-doc, cmake, llvm, gmp
...

Also, trying to concurrently run

$ crystal spec/std/time/time_spec.cr 

in another window. (on a Mac)

[RX14]

Fair enough.

[marksiemers]

For reference, here is the theoretical performance gain:
Existing implementation:

4 operations if year % 4 != 0 (75%)
4 operations if year % 4 == 0 && year % 100 != 0 (24%)
6 operations if year % 4 == 0 && year % 100 == 0 (1%)

(4 * 0.75) + (4 * .24) + (6 * 0.01) = 4.02

Average 4.02 calculations per call

Proposed implementation:

2 if year%4 ∈ {1, 2, 3} (75% of the time)
4 if year%4=0, but year%100 != 0 (24% of the time)
6 if year%100=0 (1% of the time)

So the expected operations is 2*0.75 + 4*0.24 + 6*0.01 = 2.52

Average 2.52 calculations per call

These calculations assume even distribution of years as input. Any suggestions on a different distribution for benchmarking? A normal distribution centered around 2018? A random distribution from 1800 - 2100?

[marksiemers]

If a normal distribution is used, this might be a good tool:
https://www.random.org/gaussian-distributions/?num=10000&mean=2018&stdev=20&dec=4&col=1&notation=scientific&format=plain&rnd=id.year-distribution-for-benchmarking

[rab]

It's rather pedantic, but there far too much detail at the Wikipedia entry for Proleptic Gregorian calendar. The current crystal implementation already declares years outside of 1–9999 as invalid so there are additional comparisons on the year that aren't even being taken into account.

As for a distribution, it would be more realistic (in my opinion) so consider that the most likely year is the current one with near future years and perhaps the past 100 years occupying most of the long-tail. Most programs rarely have to deal with years outside of a 2-lifetime-span around the current date. Given that is roughly 1918–2118, you could get by with simply year % 4 == 0 and be correct 99.5% of the time.

irb2.5.0> Date.class_eval do
?>            def bad_leap?
irb2.5.0>     year % 4 == 0
irb2.5.0>     end
irb2.5.0>   end
#2.5.0 => :bad_leap?
irb2.5.0> (Date.new(1918,1,1)..Date.new(2118,12,31)).count_by {|_|_.leap? == _.bad_leap?}
#2.5.0 => {true=>73049, false=>365}
irb2.5.0> _[true].to_f/_.values.sum
#2.5.0 => 0.9950281962568447

[straight-shoota]

It's a performance improvement in theory and maybe chops off half a nanosecond here and there. So it's a valuable contribution. I don't see a point in overcomplicating this.

[rab]

OK, here's a benchmark:

==> spec/std/time/time_benchmark.cr <==
require "benchmark"

n = 10_000_000_000
Benchmark.bm do |x|
  x.report { n.times { Time.leap_year?(rand(1..2400)) } }
end

First with the original code:

   def self.leap_year?(year : Int) : Bool
     unless 1 <= year <= 9999
       raise ArgumentError.new "Invalid year"
     end
 
     (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)
   end

[ruby-2.5.0p0] projects/crystal (master *%✓) $ time /usr/local/bin/crystal spec/std/time/time_benchmark.cr  --release
        user     system      total        real
    33.670000   0.230000   33.900000 (  35.152710)

real	0m42.402s
user	0m40.664s
sys	0m0.435s

And again with the new code:

   def self.leap_year?(year : Int) : Bool
     unless 1 <= year <= 9999
       raise ArgumentError.new "Invalid year"
     end
 
     year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
   end

[ruby-2.5.0p0] projects/crystal (master *%✓) $ time /usr/local/bin/crystal spec/std/time/time_benchmark.cr  --release
        user     system      total        real
    33.130000   0.200000   33.330000 (  33.789967)

real	0m34.537s
user	0m33.765s
sys	0m0.349s

So @straight-shoota is definitely in the ballpark in that 0.54s faster over 10_000_000_000 runs is saving 0.054 ns per call on average.

[marksiemers]

Yeah, seems that any change in the distribution isn't worth the effort.

[ysbaddaden]

Instead of running benchmarks after benchmark, what about looking at the generated LLVM IR and compiled ASM, to check for LLVM optimizations?