Feature #12484: Optimizing Rational

• Status: Closed
• Assignee: tad (Tadashi Saito)
• Target version: -

[tad (Tadashi Saito)]

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

[tad (Tadashi Saito)]

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

[nobu (Nobuyoshi Nakada)]

• 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.

[mrkn (Kenta Murata)]

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

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

[matz (Yukihiro Matsumoto)]

Accepted. I will give you committer right.

Matz.

[mrkn (Kenta Murata)]

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

[tad (Tadashi Saito)]

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

[hsbt (Hiroshi SHIBATA)]

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

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.

[mrkn (Kenta Murata)]

• 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.

[mrkn (Kenta Murata)]

• File deleted (diff)

[mrkn (Kenta Murata)]

• File test_rational.rb.patch test_rational.rb.patch added

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

[tad (Tadashi Saito)]

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.

[mrkn (Kenta Murata)]

but it's an another story IMHO.

I agree with you.

[mrkn (Kenta Murata)]

• 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.

[tad (Tadashi Saito)]

Thank you very much, muraken!