Project

General

Profile

Actions

Bug #13503

closed

Improve performance of some Time & Rational methods

Added by watson1978 (Shizuo Fujita) almost 7 years ago. Updated almost 7 years ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:80843]

Description

Some Time methods will call internal quov() function.
quov() calls Rational#quo -> f_muldiv() -> i_gcd() in rational.c
i_gcd() will calculate GCD using Euclidean's Algorithm and it lose a long time in modulo method (ie "x = y % x;").

This patch will replace i_gcd() with Stein's algorithm which is faster algorithm for GCD.
(https://en.wikipedia.org/wiki/Binary_GCD_algorithm)

Some Rational methods also call i_gcd().

Before

Calculating -------------------------------------
         Time#subsec      2.017M (± 8.6%) i/s -     10.052M in   5.020331s
              Time#-      4.246M (± 1.1%) i/s -     21.259M in   5.006968s
          Time#round    402.944k (±11.0%) i/s -      1.996M in   5.014424s
           Time#to_f      5.627M (± 1.3%) i/s -     28.195M in   5.011366s
           Time#to_r      1.927M (± 8.2%) i/s -      9.590M in   5.009198s
          Rational#+      3.894M (± 1.0%) i/s -     19.545M in   5.019923s
          Rational#-      3.811M (± 1.0%) i/s -     19.125M in   5.018842s
          Rational#*      5.148M (± 1.1%) i/s -     25.858M in   5.023586s

After

Calculating -------------------------------------
         Time#subsec      2.648M (± 3.0%) i/s -     13.257M in   5.010600s
              Time#-      4.265M (± 1.4%) i/s -     21.372M in   5.012480s
          Time#round    393.309k (±12.5%) i/s -      1.934M in   5.000319s
           Time#to_f      5.638M (± 2.0%) i/s -     28.223M in   5.008422s
           Time#to_r      2.313M (± 5.2%) i/s -     11.568M in   5.015379s
          Rational#+      4.366M (± 1.6%) i/s -     21.846M in   5.004487s
          Rational#-      4.443M (± 1.2%) i/s -     22.255M in   5.009509s
          Rational#*      5.776M (± 1.1%) i/s -     28.888M in   5.002322s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
  x.report "Time#subsec" do |t|
    time = Time.now
    t.times { time.subsec }
  end

  x.report "Time#-" do |t|
    time1 = Time.now
    time2 = Time.now
    t.times { time1 - time2 }
  end

  x.report "Time#round" do |t|
    time = Time.now
    t.times { time.round }
  end

  x.report "Time#to_f" do |t|
    time = Time.now
    t.times { time.to_f }
  end

  x.report "Time#to_r" do |t|
    time = Time.now
    t.times { time.to_r }
  end

  x.report "Rational#+" do |t|
    rat1 = 1/2r
    rat2 = 1/3r
    t.times { rat1 + rat2 }
  end

  x.report "Rational#-" do |t|
    rat1 = 1/3r
    rat2 = 1/2r
    t.times { rat1 - rat2 }
  end

  x.report "Rational#*" do |t|
    rat1 = 1/3r
    rat2 = 1/2r
    t.times { rat1 * rat2 }
  end
end

Related issues 1 (0 open1 closed)

Has duplicate Ruby master - Feature #15161: making gcd faster for 3x3ClosedActions
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0