[ruby-core:79524] [Ruby trunk Misc#13209] fact.rb in ruby/sample variations

Issue #13209 has been updated by Jabari Zakiya.


For MRI Ruby (but not JRuby) **while** loops are consistently faster than all
the other loop constructs (times, each, step, etc). If the goal is fastest
possible speed for MRI Ruby 3x3 it seems internals should use **while** loops
wherever possible.

Here, **fact4** using a **while** loop is fastest for any value of n.

```
def fact(n)
  return 1 if n == 0
  f = 1
  n.downto(1) do |i|
    f *= i
  end
  return f
end

def fact1(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  f = 2 
  n.downto(3) do |i|
    f *= i
  end
  return f
end

def fact2(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  (2..n).reduce(:*)
end

def fact3(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  f = 2
  3.step(n){|i| f *= i }
  f
end

def fact4(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  f, i = 2, 3
  (f *= i; i += 1) while i <= n
  f
end

require 'benchmark/ips'

Benchmark.ips do |x|
  n = 100
  puts "factorials tests for n = #{n}"
  x.report("original factorial") { fact  n }
  x.report("modified factorial") { fact1 n }
  x.report("enhanced factorial") { fact2 n }
  x.report("withstep factorial") { fact3 n }
  x.report("usewhile factorial") { fact4 n }
  x.compare!
end
```
Example timings.

```
2.4.0 :010 > load 'factversiontest.rb'
factorials tests for n = 10
Warming up --------------------------------------
  original factorial   152.621k i/100ms
  modified factorial   169.295k i/100ms
  enhanced factorial   124.274k i/100ms
  withstep factorial   134.304k i/100ms
  usewhile factorial   208.290k i/100ms
Calculating -------------------------------------
  original factorial      2.074M (賊 2.5%) i/s -     10.378M in   5.006297s
  modified factorial      2.328M (賊 2.6%) i/s -     11.681M in   5.020649s
  enhanced factorial      1.623M (賊 2.7%) i/s -      8.202M in   5.058125s
  withstep factorial      1.736M (賊 2.7%) i/s -      8.730M in   5.032241s
  usewhile factorial      3.259M (賊 2.8%) i/s -     16.455M in   5.052772s

Comparison:
  usewhile factorial:  3259334.0 i/s
  modified factorial:  2328303.5 i/s - 1.40x  slower
  original factorial:  2074354.4 i/s - 1.57x  slower
  withstep factorial:  1736091.0 i/s - 1.88x  slower
  enhanced factorial:  1622837.9 i/s - 2.01x  slower

 => true 
2.4.0 :011 > load 'factversiontest.rb'
factorials tests for n = 25
Warming up --------------------------------------
  original factorial    50.369k i/100ms
  modified factorial    53.391k i/100ms
  enhanced factorial    56.290k i/100ms
  withstep factorial    60.209k i/100ms
  usewhile factorial    83.857k i/100ms
Calculating -------------------------------------
  original factorial    553.152k (賊 2.6%) i/s -      2.770M in   5.011731s
  modified factorial    598.668k (賊 2.7%) i/s -      3.043M in   5.087403s
  enhanced factorial    635.598k (賊 2.7%) i/s -      3.209M in   5.051865s
  withstep factorial    673.752k (賊 2.6%) i/s -      3.372M in   5.007842s
  usewhile factorial    996.703k (賊 2.6%) i/s -      5.031M in   5.051626s

Comparison:
  usewhile factorial:   996703.4 i/s
  withstep factorial:   673752.0 i/s - 1.48x  slower
  enhanced factorial:   635598.1 i/s - 1.57x  slower
  modified factorial:   598668.2 i/s - 1.66x  slower
  original factorial:   553152.2 i/s - 1.80x  slower

 => true 
2.4.0 :012 > load 'factversiontest.rb'
factorials tests for n = 50
Warming up --------------------------------------
  original factorial    13.772k i/100ms
  modified factorial    14.688k i/100ms
  enhanced factorial    17.696k i/100ms
  withstep factorial    17.501k i/100ms
  usewhile factorial    21.318k i/100ms
Calculating -------------------------------------
  original factorial    142.356k (賊 3.0%) i/s -    716.144k in   5.035290s
  modified factorial    152.404k (賊 3.0%) i/s -    763.776k in   5.016154s
  enhanced factorial    183.865k (賊 2.8%) i/s -    920.192k in   5.008924s
  withstep factorial    182.771k (賊 2.7%) i/s -    927.553k in   5.078797s
  usewhile factorial    222.403k (賊 3.0%) i/s -      1.130M in   5.085087s

Comparison:
  usewhile factorial:   222402.7 i/s
  enhanced factorial:   183865.0 i/s - 1.21x  slower
  withstep factorial:   182770.6 i/s - 1.22x  slower
  modified factorial:   152404.0 i/s - 1.46x  slower
  original factorial:   142355.6 i/s - 1.56x  slower

 => true 
2.4.0 :013 > load 'factversiontest.rb'
factorials tests for n = 100
Warming up --------------------------------------
  original factorial     4.933k i/100ms
  modified factorial     4.976k i/100ms
  enhanced factorial     5.752k i/100ms
  withstep factorial     5.607k i/100ms
  usewhile factorial     6.060k i/100ms
Calculating -------------------------------------
  original factorial     49.084k (賊 2.9%) i/s -    246.650k in   5.029407s
  modified factorial     49.886k (賊 3.4%) i/s -    253.776k in   5.093179s
  enhanced factorial     54.025k (賊 8.1%) i/s -    270.344k in   5.044646s
  withstep factorial     53.487k (賊 4.3%) i/s -    269.136k in   5.041225s
  usewhile factorial     58.795k (賊 9.2%) i/s -    296.940k in   5.096755s

Comparison:
  usewhile factorial:    58794.8 i/s
  enhanced factorial:    54024.6 i/s - same-ish: difference falls within error
  withstep factorial:    53486.8 i/s - same-ish: difference falls within error
  modified factorial:    49885.7 i/s - 1.18x  slower
  original factorial:    49084.0 i/s - 1.20x  slower

 => true 
2.4.0 :014 > 

```


----------------------------------------
Misc #13209: fact.rb in ruby/sample variations
https://bugs.ruby-lang.org/issues/13209#change-62970

* Author: Jabari Zakiya
* Status: Open
* Priority: Normal
* Assignee: 
----------------------------------------
I was looking at some of the Sample files that come with Ruby and
saw the example for doing factorials. It's an old example that I
thought I could make simpler/faster. Below are the results.

Maybe upgrading to show the difference between coding idioms can 
be instructive to newer Ruby programmers.

```
def fact(n)
  return 1 if n == 0
  f = 1
  n.downto(1) do |i|
    f *= i
  end
  return f
end

def fact1(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  f = 2 
  n.downto(3) do |i|
    f *= i
  end
  return f
end

def fact2(n)
  return 1 if n | 1 == 1  # if n 0 or 1
  (2..n).reduce(:*)
end

require 'benchmark/ips'

Benchmark.ips do |x|
  x.report("original factorial") { fact  100 }
  x.report("modified factorial") { fact1 100 }
  x.report("enhanced factorial") { fact2 100 }
  x.compare!
end

```

Timings using ruby-2.4.0 on Linux 64-bit, on I7 cpu system.

```
2.4.0 :001 > load 'factversiontest.rb'
Warming up --------------------------------------
  original factorial     4.501k i/100ms
  modified factorial     4.594k i/100ms
  enhanced factorial     5.271k i/100ms
Calculating -------------------------------------
  original factorial     44.962k (賊 4.2%) i/s -    225.050k in   5.015176s
  modified factorial     46.288k (賊 3.2%) i/s -    234.294k in   5.066948s
  enhanced factorial     53.425k (賊 3.1%) i/s -    268.821k in   5.036635s

Comparison:
  enhanced factorial:    53424.9 i/s
  modified factorial:    46288.0 i/s - 1.15x  slower
  original factorial:    44961.5 i/s - 1.19x  slower

 => true 
2.4.0 :002 > 

```



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>