Alter logic in Time.leap_year? for performance #5575

rab · 2018-01-11T21:49:27Z

Let the && short-circuit the evaluation for all years that are not
divisible by 4 (i.e., 75% of them!).

Can close #5572

straight-shoota · 2018-01-11T21:57:39Z

spec/std/time/time_spec.cr

@@ -745,6 +745,29 @@ describe Time do
    Time.days_in_year(1990).should eq(365)
  end

+  it "knows which years are leap_year?" do
+    { 1900 => false,


Great to include a spec for this!

Though I'd suggest to write it like this:

{1900, 1965, 1999, 2001, 2018, 2019, 2021, 2099, 2100, 2101, 2200}.each do |year| Time.leap_year?(year).should be_false end {1968, 1972, 2000, 2004, 2020, 2400}.each do |year| Time.leap_year?(year).should be_true end

I'd prefer this but it's just a nitpicking suggestion...

Assuming that you also meant to change those to be valid syntax for Array(Int32) with […] rather than {…}, I'd be OK with that. Let me know if you intended that to be an action item, too, or just a nitpick.

I think it would be better that way, but I don't know what others think...
{ ... } was intended, that's a tuple literal.

Ah, very new to crystal so that's my first encounter with a tuple literal!

It might also be quite reasonable to split this into 4 separate test cases:

400-year leap years: {1600, 2000, 2400}

100-year normal years: {1700, 1800, 1900, 2100, 2200, 2300}

typical non-century leap years: {1968, 1972, 2004, 2020}

a smattering of non-century normal years: {1965, 1999, 2001, 2018, 2019, 2021, 2099, 2101}

asterite · 2018-01-11T22:30:41Z

Benchmark:

require "benchmark"

def leap_year_old?(year)
  unless 1 <= year <= 9999
    raise ArgumentError.new "Invalid year"
  end

  (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)
end

def leap_year_new?(year)
  unless 1 <= year <= 9999
    raise ArgumentError.new "Invalid year"
  end

  year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
end

numbers = Array.new(100_000) { rand(1..9999) }

a = 0
b = 0

Benchmark.ips do |x|
  x.report("old") do
    a = numbers.count { |i| leap_year_old?(i) }
  end
  x.report("new") do
    b = numbers.count { |i| leap_year_new?(i) }
  end
end

puts a, b

Output:

old    3.6k (277.51µs) (± 5.24%)  0 B/op        fastest
new   2.66k (376.01µs) (± 3.68%)  0 B/op   1.35× slower

It seems slower. So 👎 for me.

asterite · 2018-01-11T22:36:58Z

Actually... when I try with all numbers from 1 to 9999 without randomness:

numbers = Array.new(9999) { |i| i + 1 }

I get:

old  36.49k (  27.4µs) (± 3.02%)  0 B/op   1.99× slower
new  72.79k ( 13.74µs) (± 3.15%)  0 B/op        fastest

Then when I try it with more numbers (uniformly distributed):

numbers = Array.new(100_000) { |i| (i % 9999) + 1 }

I get:

old   3.68k (271.93µs) (± 2.53%)  0 B/op   1.95× slower
new   7.18k (139.29µs) (± 4.10%)  0 B/op        fastest

So it seems to be faster if the numbers are uniformly distributed. But if they are random (I would suppose that's uniform too?) it's slower. I don't know what's going on.

rab · 2018-01-11T22:51:58Z

Well, If you "randomly" got a bunch of multiples of 4, then it would tend to even out.

Here's a take:

require "benchmark"

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

def leap_year_old?(year)
  unless 1 <= year <= 9999
    raise ArgumentError.new "Invalid year"
  end

  (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)
end

def leap_year_new?(year)
  unless 1 <= year <= 9999
    raise ArgumentError.new "Invalid year"
  end

  year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
end

# valid years repeated so all arrays are the same length
all_valid_years = Array.new(1_000_000) {|i| 1 + (i%9998) }
random_numbers  = Array.new(1_000_000) { rand(1..9999) }
typical_numbers = Array.new(1_000_000) { 1900 + rand(401) }

a = {} of Symbol => Int32
b = {} of Symbol => Int32

Benchmark.ips do |x|
  x.report("old valid") do
    a[:valid] = all_valid_years.count { |i| leap_year_old?(i) }
  end
  x.report("new valid") do
    b[:valid] = all_valid_years.count { |i| leap_year_new?(i) }
  end
  x.report("old random") do
    a[:random] = random_numbers.count { |i| leap_year_old?(i) }
  end
  x.report("new random") do
    b[:random] = random_numbers.count { |i| leap_year_new?(i) }
  end
  x.report("old typical") do
    a[:typical] = typical_numbers.count { |i| leap_year_old?(i) }
  end
  x.report("new typical") do
    b[:typical] = typical_numbers.count { |i| leap_year_new?(i) }
  end
end

puts a, b

$ /usr/local/bin/crystal spec/std/time/time_benchmark.cr --release

  old valid 341.52  (  2.93ms) (± 8.10%)  2.15× slower
  new valid 735.86  (  1.36ms) (± 9.61%)       fastest
 old random 369.68  (  2.71ms) (± 5.04%)  1.99× slower
 new random  271.1  (  3.69ms) (± 3.49%)  2.71× slower
old typical 353.97  (  2.83ms) (± 9.15%)  2.08× slower
new typical 271.25  (  3.69ms) (± 4.72%)  2.71× slower
{:valid => 242448, :random => 242901, :typical => 242677}
{:valid => 242448, :random => 242901, :typical => 242677}

rab · 2018-01-11T23:20:25Z

Just to beat this dead 🐴 a bit more. (Noting that the best, bad, and worst case numbers are based on the order of operations in leap_year_new?)

# valid years repeated so all arrays are the same length
all_valid_years = Array.new(1_000_000) { |i| 1 + (i % 9999) }
random_numbers = Array.new(1_000_000) { rand(1..9999) }
typical_numbers = Array.new(1_000_000) { 1900 + rand(401) }
best_case = Array.new(1_000_000) { 2018 }  # Not divisible by 4
bad_case = Array.new(1_000_000) { 2000 }   # divisible by 400
worst_case = Array.new(1_000_000) { 2100 } # Not divisible by 400

Gives: (after reordering from "best" to "worst")

   new best   1.07k (930.46µs) (±12.05%)       fastest
  new valid 677.23  (  1.48ms) (± 7.60%)  1.59× slower
    new bad  354.0  (  2.82ms) (± 7.65%)  3.04× slower
  new worst  353.6  (  2.83ms) (± 6.76%)  3.04× slower
old typical  350.3  (  2.85ms) (± 6.73%)  3.07× slower
 old random 348.99  (  2.87ms) (± 7.70%)  3.08× slower
    old bad 342.91  (  2.92ms) (± 6.31%)  3.13× slower
  old worst 339.02  (  2.95ms) (± 5.63%)  3.17× slower
  old valid 334.82  (  2.99ms) (± 5.28%)  3.21× slower
   old best 306.54  (  3.26ms) (±14.62%)  3.51× slower
new typical 256.27  (   3.9ms) (± 3.52%)  4.19× slower
 new random 251.54  (  3.98ms) (±11.37%)  4.27× slower
{:valid => 242424, :random => 242412, :typical => 242375, :best => 0, :bad => 1000000, :worst => 0}
{:valid => 242424, :random => 242412, :typical => 242375, :best => 0, :bad => 1000000, :worst => 0}

Let the && short-circuit the evaluation for all years that are *not* divisible by 4 (i.e., 75% of them!).

rab · 2018-01-11T23:22:43Z

Didn't realize that the CI would be so picky about formatting.

Sija · 2018-04-09T17:55:50Z

Merge 🕦?

straight-shoota reviewed Jan 11, 2018

View reviewed changes

Alter logic in Time.leap_year? for performance

ff7a62b

Let the && short-circuit the evaluation for all years that are *not* divisible by 4 (i.e., 75% of them!).

rab force-pushed the slightly-better-leap_year-calc branch from 31e97d1 to ff7a62b Compare January 11, 2018 23:21

Separate .leap_year? test cases

6164a0d

jhass approved these changes Jan 12, 2018

View reviewed changes

RX14 approved these changes Apr 9, 2018

View reviewed changes

RX14 added this to the Next milestone Apr 9, 2018

RX14 added topic:stdlib kind:refactor labels Apr 9, 2018

RX14 merged commit 1ce052c into crystal-lang:master Apr 9, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Alter logic in Time.leap_year? for performance #5575

Alter logic in Time.leap_year? for performance #5575

rab commented Jan 11, 2018

straight-shoota Jan 11, 2018

rab Jan 11, 2018

straight-shoota Jan 12, 2018

rab Jan 12, 2018

rab Jan 12, 2018

asterite commented Jan 11, 2018

asterite commented Jan 11, 2018

rab commented Jan 11, 2018

rab commented Jan 11, 2018

rab commented Jan 11, 2018

Sija commented Apr 9, 2018

Alter logic in Time.leap_year? for performance #5575

Alter logic in Time.leap_year? for performance #5575

Conversation

rab commented Jan 11, 2018

straight-shoota Jan 11, 2018

Choose a reason for hiding this comment

rab Jan 11, 2018

Choose a reason for hiding this comment

straight-shoota Jan 12, 2018

Choose a reason for hiding this comment

rab Jan 12, 2018

Choose a reason for hiding this comment

rab Jan 12, 2018

Choose a reason for hiding this comment

asterite commented Jan 11, 2018

asterite commented Jan 11, 2018

rab commented Jan 11, 2018

rab commented Jan 11, 2018

rab commented Jan 11, 2018

Sija commented Apr 9, 2018