Project

General

Profile

Feature #12484

Optimizing Rational

Added by tad (Tadashi Saito) about 1 year ago. Updated 9 months ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:75960]

Description

Abstract

I optimized built-in library Rational. It is more than 3.7 times faster now in some cases.

Background

Rational is increasing its importance year by year. Ruby 1.9.2 uses Rational as internal representation of Time. Ruby 2.1 introduced Rational literal ("r" suffix).

But it's performance is not good enough because its implementation uses Ruby-level method calling with rb_funcall(), in spite of it's implemented in C since Ruby 1.9.1.

Proposal

I tried to improve its performance with decreasing rb_funcall(). They have been replaced with more direct representation as C.

Implementation

2 patches attached. 0001 is exporting some numeric.c functions (Is this OK?) that needed to 0002. 0002 is the main.

This is an example of typical modification:

- return f_mul(f_to_f(self), other);
+ return DBL2NUM(RFLOAT_VALUE(nurat_to_f(self)) * RFLOAT_VALUE(other));

In this code, f_mul() and f_to_f() calls rb_funcall(). I replaced those with * (native multiply) and nurat_to_f() (the body of Rational#to_f).

Evaluation

Performance and testing evaluation is done with r55389 of trunk.

Performance is improved in most of methods. Attached ratios.png shows times of improvement (bigger is better).
The benchmark is done with attached benchmark.rb script. result-trunk.tsv and result-optimized.tsv are raw scores.

Notably, Rational + Bignum became 3.7 times or more faster.

These patches also pass make test, make test-all and make test-rubyspec.
https://drone.io/github.com/tadd/ruby/70

Discussion

I have some concerns about compatibilities but I believe it's not a real problem.

Current implementation uses Ruby-level method calling as written above. If some user redefined Integer method in Ruby level, it effects to Rational calculation.

class Integer
  alias mul *
  def *(o)
    p "I'm *"
    mul(o)
  end
end

r = Rational(1<<64)
r * r

Current implementation prints "I'm *" but nothing printed with my patch. This is compatibility breakage in a strict sense, but I don't think it is used as valuable behavior from library users.

Other concern is my prerequisites. I assumed that Rational have a pair of ::Integer (internally bignum or fixnum) only because I couldn't define subclass of Integer to work with Rational.
If user can pass a subclass of Integer to the constructor of Rational, it may cause some weird behavior.

If I should care about above or other things, please let me know.

Summary

Most of Rational methods are optimized and those speed are up with more direct C representation.
I believe there is no real compatibility problem with my implementation.

Note that my codes are supported by a grant of Ruby Association. I thank to Ruby Association and grant committee members.
http://ruby.or.jp/en/news/20160406.html

0001-export-functions.patch (5.27 KB) 0001-export-functions.patch tad (Tadashi Saito), 06/12/2016 12:55 PM
0002-optimize-Rational-methods.patch (25.4 KB) 0002-optimize-Rational-methods.patch tad (Tadashi Saito), 06/12/2016 12:55 PM
ratios.png (80 KB) ratios.png tad (Tadashi Saito), 06/12/2016 12:56 PM
benchmark.rb (2.52 KB) benchmark.rb tad (Tadashi Saito), 06/12/2016 01:04 PM
result-optimized.tsv (1.19 KB) result-optimized.tsv tad (Tadashi Saito), 06/12/2016 01:05 PM
result-trunk.tsv (1.18 KB) result-trunk.tsv tad (Tadashi Saito), 06/12/2016 01:05 PM
test_rational.rb.patch (1.07 KB) test_rational.rb.patch mrkn (Kenta Murata), 06/13/2016 03:36 PM

Associated revisions

Revision 56831
Added by tadd 9 months ago

  • NEWS: Added entry for optimized Rational. [Feature #12484] [ci skip]

Revision 56831
Added by tadd 9 months ago

  • NEWS: Added entry for optimized Rational. [Feature #12484] [ci skip]

History

#1 [ruby-core:75961] Updated by tad (Tadashi Saito) about 1 year ago

I also created PR for detailed information.
https://github.com/ruby/ruby/pull/1381

#2 [ruby-core:75962] Updated by nobu (Nobuyoshi Nakada) about 1 year ago

  • Description updated (diff)

Tadashi Saito wrote:

Other concern is my prerequisites. I assumed that Rational have a pair of ::Integer (internally bignum or fixnum) only because I couldn't define subclass of Integer to work with Rational.
If user can pass a subclass of Integer to the constructor of Rational, it may cause some weird behavior.

It should be impossible, as a subclass of Integer can't instantiate.

#3 [ruby-core:75964] Updated by mrkn (Kenta Murata) about 1 year ago

It should be impossible, as a subclass of Integer can't instantiate.

Users can instantiate subclasses of Integer in extension library, I think.

#4 [ruby-core:75973] Updated by matz (Yukihiro Matsumoto) about 1 year ago

Accepted. I will give you committer right.

Matz.

#5 [ruby-core:75977] Updated by mrkn (Kenta Murata) about 1 year ago

@ttad I'll check your patch. Please wait a moment.

#6 [ruby-core:75983] Updated by tad (Tadashi Saito) about 1 year ago

Thank you so much, Matz!
I'll wait for muraken's review.

#7 [ruby-core:75993] Updated by hsbt (Hiroshi SHIBATA) about 1 year ago

  • Assignee set to tad (Tadashi Saito)
  • Status changed from Open to Assigned

Hi, tad.

We discussed this issue on Developer Meeting June.
We hope to merge this patch by yourself with a review of other committers like mrkn.

I'm going to send an invitation of Ruby committer tomorrow.

#8 [ruby-core:76003] Updated by mrkn (Kenta Murata) about 1 year ago

  • File diff added

I've checked the attached patch, and I found a case that should be fixed.
It's related to Integer subclasses.

Nobuyoshi Nakada wrote:

Tadashi Saito wrote:

Other concern is my prerequisites. I assumed that Rational have a pair of ::Integer (internally bignum or fixnum) only because I couldn't define subclass of Integer to work with Rational.
If user can pass a subclass of Integer to the constructor of Rational, it may cause some weird behavior.

It should be impossible, as a subclass of Integer can't instantiate.

Using Bug::Integer::MyInteger class, Kernel.Rational method couldn't work correctly.
Please apply my attachment diff, and check the result of TestRational#test_new.

#9 Updated by mrkn (Kenta Murata) about 1 year ago

  • File deleted (diff)

#10 [ruby-core:76004] Updated by mrkn (Kenta Murata) about 1 year ago

I've uploaded a wrong file.
The correct one is this.

#11 [ruby-core:76233] Updated by tad (Tadashi Saito) about 1 year ago

Muraken:

Thank you for your investigation. Certainly it was reproduced,
but did you test with trunk? I got almost same error message
with and without my patch.

trunk (without my patch):

Rational_Test#test_new:
SystemStackError: stack level too deep
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `-@'
(snip)
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `-@'
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `convert'
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `Rational'
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `test_new'

with my patch:

Rational_Test#test_new:
SystemStackError: stack level too deep
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `-@'
(snip)
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `-@'
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `Rational'
    /home/tadashi/git/ruby/test/ruby/test_rational.rb:29:in `test_new'

So I believe the error is not due to my patch and it's a current spec.

Allowing Integer subclass for Kernel.Rational may (or may not) be
useful, but it's an another story IMHO.

#12 [ruby-core:76272] Updated by mrkn (Kenta Murata) about 1 year ago

but it's an another story IMHO.

I agree with you.

#13 [ruby-core:78098] Updated by mrkn (Kenta Murata) 9 months ago

  • Status changed from Assigned to Closed

I've merged all of your commits into trunk with some modifications.
The commits exist between r56695 and r56761.

#14 [ruby-core:78105] Updated by tad (Tadashi Saito) 9 months ago

Thank you very much, muraken!

Also available in: Atom PDF