JRuby

BigDecimal#log is performance-broken

Details

  • Type: Improvement Improvement
  • Status: Resolved Resolved
  • Priority: Minor Minor
  • Resolution: Won't Fix
  • Affects Version/s: JRuby 1.4
  • Fix Version/s: None
  • Component/s: Core Classes/Modules
  • Labels:
    None
  • Environment:
    Mac OS X 10.6.3
  • Number of attachments :
    0

Description

BigDecimal#log is performance-broken for arguments x with x < 0.1 or x > 10. This is an old issue, see for example Ruby Cookbook, O'Reilly 2006. Their fix is several times faster for small or large arguments:

require "bigdecimal"
require "bigdecimal/math"
require "benchmark"

include BigMath

module BigMath
    def fast_log(x, prec)
        sign, fraction, power, exponent = x.split
        fraction = BigDecimal("0.#{fraction}")
        power = BigDecimal("#{power}")
        log(fraction, prec) + (log(power, prec) * exponent)
    end
end

prec = 100
Benchmark.bmbm(15) do |results|
	results.report("fast_log 0.0001:") { BigMath.fast_log(BigDecimal("0.0001"), prec) }  
	results.report("fast_log 0.001:") { BigMath.fast_log(BigDecimal("0.001"), prec) }  
	results.report("fast_log 1000:") { BigMath.fast_log(BigDecimal("1000"), prec) }  
	results.report("fast_log 10000:") { BigMath.fast_log(BigDecimal("10000"), prec) }  
	results.report("log 0.0001:") { BigMath.log(BigDecimal("0.0001"), prec) }  
	results.report("log 0.001:") { BigMath.log(BigDecimal("0.001"), prec) }  
	results.report("log 1000:") { BigMath.log(BigDecimal("1000"), prec) }  
	results.report("log 10000:") { BigMath.log(BigDecimal("10000"), prec) }  
end
jruby 1.5.0.RC3 (ruby 1.8.7 patchlevel 249) (2010-05-04 603f15a) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_17) [x86_64-java]
                       user     system      total        real
fast_log 0.0001:   0.019000   0.000000   0.019000 (  0.018000)
fast_log 0.001:    0.030000   0.000000   0.030000 (  0.030000)
fast_log 1000:     0.019000   0.000000   0.019000 (  0.019000)
fast_log 10000:    0.018000   0.000000   0.018000 (  0.019000)
log 0.0001:        7.050000   0.000000   7.050000 (  7.050000)
log 0.001:         0.687000   0.000000   0.687000 (  0.687000)
log 1000:          0.673000   0.000000   0.673000 (  0.673000)
log 10000:         6.658000   0.000000   6.658000 (  6.658000)

Activity

Hide
Hiro Asari added a comment -

I haven't tested the code here, but what's the license for its use? (Is the link you provided licensed to distribute O'Reilly's content?)

BigDecimal.log is a part of MRI's standard library, so I tend to shy away from overriding it unless there is a good reason. Assuming that the suggested change is a good one, then, all the Ruby implementations will benefit if MRI took up the change.

Show
Hiro Asari added a comment - I haven't tested the code here, but what's the license for its use? (Is the link you provided licensed to distribute O'Reilly's content?) BigDecimal.log is a part of MRI's standard library, so I tend to shy away from overriding it unless there is a good reason. Assuming that the suggested change is a good one, then, all the Ruby implementations will benefit if MRI took up the change.
Hide
Hiro Asari added a comment -

Reformatted for readability, and removed the questionable link.

Show
Hiro Asari added a comment - Reformatted for readability, and removed the questionable link.
Hide
Hans-Georg Höhne added a comment -

I can't link to the physical copy on my desk, so I used the first google link for "Ruby Cookbook BigDecimal log". The fourth link is on Google books:
http://books.google.de/books?id=bJkznhZBG6gC&pg=PA54&lpg=PA54&dq=Ruby+Cookbook++bigdecimal+log&source=bl&ots=AkO0h5oZVF&sig=WU19jlNaL7Iqg5mfGuXoqdBFLEk&hl=de&ei=NBfqS4K2CKOjOLz3tPEK&sa=X&oi=book_result&ct=result&resnum=4&ved=0CCwQ6AEwAw#v=onepage&q&f=false

They are using really basic math, which can't be licensed in my opinion. The result for the latest 1.9.3dev is

ruby 1.9.3dev (2010-05-11 trunk 27724) [x86_64-darwin10.3.0]
user system total real
fast_log 0.0001: 0.010000 0.000000 0.010000 ( 0.009294)
fast_log 0.001: 0.010000 0.000000 0.010000 ( 0.009113)
fast_log 1000: 0.010000 0.000000 0.010000 ( 0.009050)
fast_log 10000: 0.010000 0.000000 0.010000 ( 0.009732)
log 0.0001: 0.010000 0.000000 0.010000 ( 0.015347)
log 0.001: 0.000000 0.000000 0.000000 ( 0.010230)
log 1000: 0.530000 0.010000 0.540000 ( 0.554249)
log 10000: 5.260000 0.160000 5.420000 ( 5.465983)

Show
Hans-Georg Höhne added a comment - I can't link to the physical copy on my desk, so I used the first google link for "Ruby Cookbook BigDecimal log". The fourth link is on Google books: http://books.google.de/books?id=bJkznhZBG6gC&pg=PA54&lpg=PA54&dq=Ruby+Cookbook++bigdecimal+log&source=bl&ots=AkO0h5oZVF&sig=WU19jlNaL7Iqg5mfGuXoqdBFLEk&hl=de&ei=NBfqS4K2CKOjOLz3tPEK&sa=X&oi=book_result&ct=result&resnum=4&ved=0CCwQ6AEwAw#v=onepage&q&f=false They are using really basic math, which can't be licensed in my opinion. The result for the latest 1.9.3dev is ruby 1.9.3dev (2010-05-11 trunk 27724) [x86_64-darwin10.3.0] user system total real fast_log 0.0001: 0.010000 0.000000 0.010000 ( 0.009294) fast_log 0.001: 0.010000 0.000000 0.010000 ( 0.009113) fast_log 1000: 0.010000 0.000000 0.010000 ( 0.009050) fast_log 10000: 0.010000 0.000000 0.010000 ( 0.009732) log 0.0001: 0.010000 0.000000 0.010000 ( 0.015347) log 0.001: 0.000000 0.000000 0.000000 ( 0.010230) log 1000: 0.530000 0.010000 0.540000 ( 0.554249) log 10000: 5.260000 0.160000 5.420000 ( 5.465983)
Hide
Hiro Asari added a comment -

Hans,

I'm saying that the change should happen in MRI, not in JRuby. MRI issues should go to http://redmine.ruby-lang.org

I just tried the code in Rubinius (1.0.0-rc4), and the result is atrocious.

fast_log 0.0001:   0.044482   0.000000   0.044482 (  0.044504)
fast_log 0.001:    0.043302   0.000000   0.043302 (  0.043351)
fast_log 1000:     0.062222   0.000000   0.062222 (  0.062274)
fast_log 10000:    0.048588   0.000000   0.048588 (  0.048653)
log 0.0001:      158.414237   0.000000 158.414237 (158.414292)
log 0.001:        30.425944   0.000000  30.425944 ( 30.426015)
log 1000:         33.184419   0.000000  33.184419 ( 33.184483)
log 10000:       532.979404   0.000000 532.979404 (532.979462)

Perhaps this would motivate MRI for adoption of this improvement, and it strengthens my view that we should "WONTFIX" this.

Show
Hiro Asari added a comment - Hans, I'm saying that the change should happen in MRI, not in JRuby. MRI issues should go to http://redmine.ruby-lang.org I just tried the code in Rubinius (1.0.0-rc4), and the result is atrocious.
fast_log 0.0001:   0.044482   0.000000   0.044482 (  0.044504)
fast_log 0.001:    0.043302   0.000000   0.043302 (  0.043351)
fast_log 1000:     0.062222   0.000000   0.062222 (  0.062274)
fast_log 10000:    0.048588   0.000000   0.048588 (  0.048653)
log 0.0001:      158.414237   0.000000 158.414237 (158.414292)
log 0.001:        30.425944   0.000000  30.425944 ( 30.426015)
log 1000:         33.184419   0.000000  33.184419 ( 33.184483)
log 10000:       532.979404   0.000000 532.979404 (532.979462)
Perhaps this would motivate MRI for adoption of this improvement, and it strengthens my view that we should "WONTFIX" this.
Hide
Hans-Georg Höhne added a comment -

"MRI issues should go to http://redmine.ruby-lang.org." Actually, it was already there in 2006:

http://rubyforge.org/tracker/?func=detail&atid=1700&aid=6323&group_id=426

6323 BigMath::log can be made much faster

On ruby-core, Matz said: "The maintainer, Shigeo Kobayashi, refused to apply this patch, since he thinks this kind of optimization should be done in application level."

Show
Hans-Georg Höhne added a comment - "MRI issues should go to http://redmine.ruby-lang.org." Actually, it was already there in 2006: http://rubyforge.org/tracker/?func=detail&atid=1700&aid=6323&group_id=426 6323 BigMath::log can be made much faster On ruby-core, Matz said: "The maintainer, Shigeo Kobayashi, refused to apply this patch, since he thinks this kind of optimization should be done in application level."
Hide
Charles Oliver Nutter added a comment -

If the maintained of 1.8.* or 1.8.7 won't include it, I suppose we could. We haven't in the past because of the difficulty of updating stdlib when we have lots of patches in place, but that's mostly mitigated by our new stdlib-updating process. I would not object to including a faster version if we can confirm that it's ok to do so (i.e. public-domain or pull the version that 1.9 uses...the latter would be ideal).

Show
Charles Oliver Nutter added a comment - If the maintained of 1.8.* or 1.8.7 won't include it, I suppose we could. We haven't in the past because of the difficulty of updating stdlib when we have lots of patches in place, but that's mostly mitigated by our new stdlib-updating process. I would not object to including a faster version if we can confirm that it's ok to do so (i.e. public-domain or pull the version that 1.9 uses...the latter would be ideal).
Hide
Thomas E Enebo added a comment -

I am also confused what the objection was from Koboyashi on the MRI side? This is math right? I don't understand why someone would want versions which were much slower...

Show
Thomas E Enebo added a comment - I am also confused what the objection was from Koboyashi on the MRI side? This is math right? I don't understand why someone would want versions which were much slower...
Hide
Hiro Asari added a comment -

So, I opened a new ticket with MRI (http://redmine.ruby-lang.org/issues/show/3279).

I think BigMath's maintainer has changed since Matz's comment; Murata-san agreed to take in the patch to the trunk and the 1.9.2 branch. (I think we'll be able to incorporate it in the 1.9 when we update the 1.9 stdlib.)

He says he'd leave it to Shyouhei whether or not it will be back ported to the 1.8 branch. As long as we are OK license-wise (which I think is the case; it showed up in the ruby-core back in 2006), we can either wait for the MRI update, or just stick it in the 1.8 branch.

Show
Hiro Asari added a comment - So, I opened a new ticket with MRI (http://redmine.ruby-lang.org/issues/show/3279). I think BigMath's maintainer has changed since Matz's comment; Murata-san agreed to take in the patch to the trunk and the 1.9.2 branch. (I think we'll be able to incorporate it in the 1.9 when we update the 1.9 stdlib.) He says he'd leave it to Shyouhei whether or not it will be back ported to the 1.8 branch. As long as we are OK license-wise (which I think is the case; it showed up in the ruby-core back in 2006), we can either wait for the MRI update, or just stick it in the 1.8 branch.
Hide
Hans-Georg Höhne added a comment -

So in the 1.9 branch of jruby 1.6.0.dev this bug is already fixed (I'm trying to learn formatting)

jruby 1.6.0.dev (ruby 1.9.2dev trunk 27758) (2010-05-07 6300e03) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_17) [x86_64-java]
                       user     system      total        real
fast_log 0.0001:   0.049000   0.000000   0.049000 (  0.049000)
fast_log 0.001:    0.029000   0.000000   0.029000 (  0.030000)
fast_log 1000:     0.041000   0.000000   0.041000 (  0.041000)
fast_log 10000:    0.017000   0.000000   0.017000 (  0.017000)
log 0.0001:        0.019000   0.000000   0.019000 (  0.019000)
log 0.001:         0.025000   0.000000   0.025000 (  0.025000)
log 1000:          0.017000   0.000000   0.017000 (  0.018000)
log 10000:         0.033000   0.000000   0.033000 (  0.033000)

And by the way, Leonard Richardson, who wrote the rejected patch #6323 in 2006, is also one of the two authors of the Ruby Cookbook.

Show
Hans-Georg Höhne added a comment - So in the 1.9 branch of jruby 1.6.0.dev this bug is already fixed (I'm trying to learn formatting)
jruby 1.6.0.dev (ruby 1.9.2dev trunk 27758) (2010-05-07 6300e03) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_17) [x86_64-java]
                       user     system      total        real
fast_log 0.0001:   0.049000   0.000000   0.049000 (  0.049000)
fast_log 0.001:    0.029000   0.000000   0.029000 (  0.030000)
fast_log 1000:     0.041000   0.000000   0.041000 (  0.041000)
fast_log 10000:    0.017000   0.000000   0.017000 (  0.017000)
log 0.0001:        0.019000   0.000000   0.019000 (  0.019000)
log 0.001:         0.025000   0.000000   0.025000 (  0.025000)
log 1000:          0.017000   0.000000   0.017000 (  0.018000)
log 10000:         0.033000   0.000000   0.033000 (  0.033000)
And by the way, Leonard Richardson, who wrote the rejected patch #6323 in 2006, is also one of the two authors of the Ruby Cookbook.
Hide
Hiro Asari added a comment -

Actually, I didn't expect the improvement with 1.9 mode, since the commit has not yet been made to MRI. The improvement comes from changes in MRI itself, then.

$ git diff --no-ext-diff origin/ruby_1_8 trunk ext/bigdecimal/lib/bigdecimal/math.rb
diff --git a/ext/bigdecimal/lib/bigdecimal/math.rb b/ext/bigdecimal/lib/bigdecim
index 24e928b..41fc69f 100644
--- a/ext/bigdecimal/lib/bigdecimal/math.rb
+++ b/ext/bigdecimal/lib/bigdecimal/math.rb
@@ -1,3 +1,5 @@
+require 'bigdecimal'
+
 #
 #--
 # Contents:
@@ -29,6 +31,7 @@
 #   puts sin(a,100) # -> 0.10000000000000000000......E1
 #
 module BigMath
+  module_function
 
   # Computes the square root of x to the specified number of digits of
   # precision.
@@ -49,6 +52,14 @@ module BigMath
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
     two  = BigDecimal("2")
+    x = -x if neg = x < 0
+    if x > (twopi = two * BigMath.PI(prec))
+      if x > 30
+        x %= twopi
+      else
+        x -= twopi while x > twopi
+      end
+    end
     x1   = x
     x2   = x.mult(x,n)
     sign = 1
@@ -65,7 +76,7 @@ module BigMath
       d   = sign * x1.div(z,m)
       y  += d
     end
-    y
+    neg ? -y : y
   end
 
   # Computes the cosine of x to the specified number of digits of precision.
@@ -77,6 +88,14 @@ module BigMath
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
     two  = BigDecimal("2")
+    x = -x if x < 0
+    if x > (twopi = two * BigMath.PI(prec))
+      if x > 30
+        x %= twopi
+      else
+        x -= twopi while x > twopi
+      end
+    end
     x1 = one
     x2 = x.mult(x,n)
     sign = 1
@@ -98,12 +117,16 @@ module BigMath
 
   # Computes the arctangent of x to the specified number of digits of precision
   #
-  # If x is infinite or NaN, returns NaN.
-  # Raises an argument error if x > 1.
+  # If x is NaN, returns NaN.
   def atan(x, prec)
     raise ArgumentError, "Zero or negative precision for atan" if prec <= 0
-    return BigDecimal("NaN") if x.infinite? || x.nan?
-    raise ArgumentError, "x.abs must be less than 1.0" if x.abs>=1
+    return BigDecimal("NaN") if x.nan?
+    pi = PI(prec)
+    x = -x if neg = x < 0
+    return pi.div(neg ? -2 : 2, prec) if x.infinite?
+    return pi / (neg ? -4 : 4) if x.round(prec) == 1
+    x = BigDecimal("1").div(x, prec) if inv = x > 1
+    x = (-1 + sqrt(1 + x**2, prec))/x if dbl = x > 0.5
     n    = prec + BigDecimal.double_fig
     y = x
     d = y
@@ -117,6 +140,9 @@ module BigMath
       y += d
       r += 2
     end
+    y *= 2 if dbl
+    y = pi / 2 - y if inv
+    y = -y if neg
     y
   end
 
@@ -132,6 +158,7 @@ module BigMath
     return BigDecimal("NaN") if x.infinite? || x.nan?
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
+    x = -x if neg = x < 0
     x1 = one
     y  = one
     d  = y
@@ -145,7 +172,11 @@ module BigMath
       d  = x1.div(z,m)
       y += d
     end
-    y
+    if neg
+      one.div(y, prec)
+    else
+      y.round(prec - y.exponent)
+    end
   end
 
   # Computes the natural logarithm of x to the specified number of digits
@@ -159,6 +190,11 @@ module BigMath
     one = BigDecimal("1")
     two = BigDecimal("2")
     n  = prec + BigDecimal.double_fig
+    if (expo = x.exponent) < 0 || expo >= 3
+      x = x.mult(BigDecimal("1E#{-expo}"), n)
+    else
+      expo = nil
+    end
     x  = (x - one).div(x + one,n)
     x2 = x.mult(x,n)
     y  = x
@@ -171,7 +207,11 @@ module BigMath
       d  = x.div(i,m)
       y += d
     end
-    y*two
+    y *= two
+    if expo
+      y += log(BigDecimal("10"),prec) * BigDecimal(expo.to_s)
+    end
+    y
   end
 
   # Computes the value of pi to the specified number of digits of precision.

I'll update the MRI ticket of this finding, and ask strongly for back porting the change to 1.8.

Show
Hiro Asari added a comment - Actually, I didn't expect the improvement with 1.9 mode, since the commit has not yet been made to MRI. The improvement comes from changes in MRI itself, then.
$ git diff --no-ext-diff origin/ruby_1_8 trunk ext/bigdecimal/lib/bigdecimal/math.rb
diff --git a/ext/bigdecimal/lib/bigdecimal/math.rb b/ext/bigdecimal/lib/bigdecim
index 24e928b..41fc69f 100644
--- a/ext/bigdecimal/lib/bigdecimal/math.rb
+++ b/ext/bigdecimal/lib/bigdecimal/math.rb
@@ -1,3 +1,5 @@
+require 'bigdecimal'
+
 #
 #--
 # Contents:
@@ -29,6 +31,7 @@
 #   puts sin(a,100) # -> 0.10000000000000000000......E1
 #
 module BigMath
+  module_function
 
   # Computes the square root of x to the specified number of digits of
   # precision.
@@ -49,6 +52,14 @@ module BigMath
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
     two  = BigDecimal("2")
+    x = -x if neg = x < 0
+    if x > (twopi = two * BigMath.PI(prec))
+      if x > 30
+        x %= twopi
+      else
+        x -= twopi while x > twopi
+      end
+    end
     x1   = x
     x2   = x.mult(x,n)
     sign = 1
@@ -65,7 +76,7 @@ module BigMath
       d   = sign * x1.div(z,m)
       y  += d
     end
-    y
+    neg ? -y : y
   end
 
   # Computes the cosine of x to the specified number of digits of precision.
@@ -77,6 +88,14 @@ module BigMath
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
     two  = BigDecimal("2")
+    x = -x if x < 0
+    if x > (twopi = two * BigMath.PI(prec))
+      if x > 30
+        x %= twopi
+      else
+        x -= twopi while x > twopi
+      end
+    end
     x1 = one
     x2 = x.mult(x,n)
     sign = 1
@@ -98,12 +117,16 @@ module BigMath
 
   # Computes the arctangent of x to the specified number of digits of precision
   #
-  # If x is infinite or NaN, returns NaN.
-  # Raises an argument error if x > 1.
+  # If x is NaN, returns NaN.
   def atan(x, prec)
     raise ArgumentError, "Zero or negative precision for atan" if prec <= 0
-    return BigDecimal("NaN") if x.infinite? || x.nan?
-    raise ArgumentError, "x.abs must be less than 1.0" if x.abs>=1
+    return BigDecimal("NaN") if x.nan?
+    pi = PI(prec)
+    x = -x if neg = x < 0
+    return pi.div(neg ? -2 : 2, prec) if x.infinite?
+    return pi / (neg ? -4 : 4) if x.round(prec) == 1
+    x = BigDecimal("1").div(x, prec) if inv = x > 1
+    x = (-1 + sqrt(1 + x**2, prec))/x if dbl = x > 0.5
     n    = prec + BigDecimal.double_fig
     y = x
     d = y
@@ -117,6 +140,9 @@ module BigMath
       y += d
       r += 2
     end
+    y *= 2 if dbl
+    y = pi / 2 - y if inv
+    y = -y if neg
     y
   end
 
@@ -132,6 +158,7 @@ module BigMath
     return BigDecimal("NaN") if x.infinite? || x.nan?
     n    = prec + BigDecimal.double_fig
     one  = BigDecimal("1")
+    x = -x if neg = x < 0
     x1 = one
     y  = one
     d  = y
@@ -145,7 +172,11 @@ module BigMath
       d  = x1.div(z,m)
       y += d
     end
-    y
+    if neg
+      one.div(y, prec)
+    else
+      y.round(prec - y.exponent)
+    end
   end
 
   # Computes the natural logarithm of x to the specified number of digits
@@ -159,6 +190,11 @@ module BigMath
     one = BigDecimal("1")
     two = BigDecimal("2")
     n  = prec + BigDecimal.double_fig
+    if (expo = x.exponent) < 0 || expo >= 3
+      x = x.mult(BigDecimal("1E#{-expo}"), n)
+    else
+      expo = nil
+    end
     x  = (x - one).div(x + one,n)
     x2 = x.mult(x,n)
     y  = x
@@ -171,7 +207,11 @@ module BigMath
       d  = x.div(i,m)
       y += d
     end
-    y*two
+    y *= two
+    if expo
+      y += log(BigDecimal("10"),prec) * BigDecimal(expo.to_s)
+    end
+    y
   end
 
   # Computes the value of pi to the specified number of digits of precision.
I'll update the MRI ticket of this finding, and ask strongly for back porting the change to 1.8.
Hide
Hiro Asari added a comment -

Here's MRI's backport ticket: http://redmine.ruby-lang.org/issues/show/3280

Show
Hiro Asari added a comment - Here's MRI's backport ticket: http://redmine.ruby-lang.org/issues/show/3280
Hide
Hiro Asari added a comment -

1.8.7p299 was released moments earlier, but the backport to 1.8.7 ran into problems, so this patch didn't make it.

Show
Hiro Asari added a comment - 1.8.7p299 was released moments earlier, but the backport to 1.8.7 ran into problems, so this patch didn't make it.
Hide
Charles Oliver Nutter added a comment -

I'm going to call this WONTFIX at this point for the following reasons:

  • 1.9 mode does not exhibit the problem
  • in 1.8 mode the problem exists in stdlib files we inherit from MRI

If you would like to see this fixed in 1.8 mode, you can lobby us to include a fix or lobby MRI folks to have it backported to the 1.8.7 branch. The former case would have to be pretty compelling, since we strongly prefer to get stdlib fixes via the latter case.

Show
Charles Oliver Nutter added a comment - I'm going to call this WONTFIX at this point for the following reasons:
  • 1.9 mode does not exhibit the problem
  • in 1.8 mode the problem exists in stdlib files we inherit from MRI
If you would like to see this fixed in 1.8 mode, you can lobby us to include a fix or lobby MRI folks to have it backported to the 1.8.7 branch. The former case would have to be pretty compelling, since we strongly prefer to get stdlib fixes via the latter case.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: