From: jzakiya@... Date: 2017-02-14T00:10:03+00:00 Subject: [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: