ruby 中的快速/快速整数乘法？

发布于 2024-08-12 10:42:47 字数 1459 浏览 7 评论 0原文

我正在尝试在 Ruby 中快速/高效地实现 Mandelbrot。很久很久以前，加速它的一种方法是使用定点整数而不是浮点数。

所以我做了以下基准测试，使用乘法或平方 ** 操作数将浮点数和整数提升与平方进行比较。

require 'benchmark'

Benchmark.bmbm(10) do |x|  
  x.report("float-multip") do
    for z in 0..100000 
      zf = z.to_f
      y = zf*zf
    end
  end  

  x.report("float-square") do
    for z in 0..100000 
      zf = z.to_f
      y = zf**2
    end
  end  

  x.report("int-multip") do
    zo = 0
    for zi in 0..100000 
      y2 = zo*zo
      zo += 1
    end
  end   

  x.report("int-multip") do
    for zi in 0..100000 
      y2 = zi**2
    end
  end  
end

这会生成以下输出：

Rehearsal ------------------------------------------------
float-multip   0.125000   0.000000   0.125000 (  0.125000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.250000   0.000000   0.250000 (  0.250000)
int-multip     0.282000   0.000000   0.282000 (  0.282000)
--------------------------------------- total: 0.782000sec

                   user     system      total        real
float-multip   0.110000   0.000000   0.110000 (  0.110000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.219000   0.016000   0.235000 (  0.235000)
int-multip     0.265000   0.015000   0.280000 (  0.282000)

它清楚地表明 Fixnum 乘法几乎是浮点乘法的两倍。

我有两个问题：

谁能解释一下？我可以想象的一个原因是 Fixnum 乘法速度较慢，因为内部检查是否需要转换为 Bignum。
其次，Ruby 有没有快速的整数乘法？

原文

I am trying to make a quick/efficient Mandelbrot implementation in Ruby. A long long time ago, one way to speed it up was using fixed point integers instead of floats.

So i made the following benchmark, comparing float and integer raising to a square, using multiplication or square ** operand.

require 'benchmark'

Benchmark.bmbm(10) do |x|  
  x.report("float-multip") do
    for z in 0..100000 
      zf = z.to_f
      y = zf*zf
    end
  end  

  x.report("float-square") do
    for z in 0..100000 
      zf = z.to_f
      y = zf**2
    end
  end  

  x.report("int-multip") do
    zo = 0
    for zi in 0..100000 
      y2 = zo*zo
      zo += 1
    end
  end   

  x.report("int-multip") do
    for zi in 0..100000 
      y2 = zi**2
    end
  end  
end

and this generates the following output:

Rehearsal ------------------------------------------------
float-multip   0.125000   0.000000   0.125000 (  0.125000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.250000   0.000000   0.250000 (  0.250000)
int-multip     0.282000   0.000000   0.282000 (  0.282000)
--------------------------------------- total: 0.782000sec

                   user     system      total        real
float-multip   0.110000   0.000000   0.110000 (  0.110000)
float-square   0.125000   0.000000   0.125000 (  0.125000)
int-multip     0.219000   0.016000   0.235000 (  0.235000)
int-multip     0.265000   0.015000   0.280000 (  0.282000)

which clearly shows the the Fixnum multiplication is almost twice as slow as floating point.

I have two questions:

Can anyone explain this? A reason I can imagine is that Fixnum multiplication is slower because of the internal checking whether or not it needs to be converted to a Bignum.
secondly is there than a quick integer multiplication for ruby?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

思念绕指尖 2024-08-19 10:42:47

我想到了一些事情。您没有指定您正在使用什么 Ruby 实现。由于您在 Windows 上运行 Ruby 1.8.6，因此我假设您使用的是通过 Windows 一键安装程序安装的 MRI。

这是最坏的情况：

MRI 是所有 Ruby 实现中最慢的
Windows 上的 MRI甚至比 Linux 或 OSX 上的 MRI 慢
一键式安装程序使用来自以下位置的预编译二进制文件Ruby-Lang.Org，从 1996 年起使用 Microsoft Visual C++ 6.0 编译，因此比使用 Microsoft Visual C++ 10.0 或 GCC 4.x 甚至 GCC 3.x 编译的 Windows 上的 MRI甚至更慢。

以下是您可以尝试提高性能的一些技巧：

使用 RubyInstaller 项目，该项目使用使用 GCC 3 编译的解释器.x 而不是 MSVC6，
也许可以自己重新编译解释器（使用 RubyInstaller 项目），使用 GCC 4.x 和/或不同的优化选项（RubyInstaller 使用中等优化选项编译，适用于通用 386 CPU），
使用比 1.8.6 更新的 MRI 版本，
使用不同的 Ruby 实现：
- YARV 比 MRI 快得多（不幸的是，它仅实现 Ruby 1.9，因此您可能需要更改代码），
- JRuby 在很多情况下比 YARV 快得多，并且它同时实现了 Ruby 1.8 和 Ruby 1.9 (它还有一个 -fast 命令行选项，与 Ruby 略有不兼容，但提高了性能，包括算术性能）和
- IronRuby 也可能比 YARV 更快，具体取决于工作负载。

在后两种情况下，您可能需要稍微修改一下基准。两者最终都可以将 Ruby 代码编译为本机机器代码，但这可能需要一段时间。例如，JRuby 在方法执行 20 次后编译为 JVM 字节码，HotSpot Server 在执行 20000 次后将 JVM 字节码编译为本机机器代码。此外，编译本身也需要时间，因此程序需要运行一段时间才能通过提高性能来收回成本。

特别是，JRuby 首席开发人员之一 Charles Oliver Nutter 表示，根据工作负载，JRuby 可能需要 5-15 秒才能达到全速。你的基准测试大约快了 100 倍（这是你每天都不会听到的一句话......）。

A couple of things come to mind. You do not specify what Ruby implementation you are using. Since you run Ruby 1.8.6 on Windows, I am going to assume that you are using MRI installed via the Windows One-Click Installer.

This is kind of a worst-case scenario:

MRI is the slowest of all the Ruby implementations
MRI on Windows is even slower than MRI on Linux or OSX
The One-Click Installer uses the pre-compiled binaries from Ruby-Lang.Org, which are compiled with Microsoft Visual C++ 6.0 from 1996, and thus are even slower than MRI on Windows compiled with Microsoft Visual C++ 10.0 or GCC 4.x or even GCC 3.x.

Here's a couple of tips that you could try to improve performance:

use the RubyInstaller project, which uses interpreters compiled with GCC 3.x instead of MSVC6,
maybe recompile the interpreter yourself (it's not that hard with the Rakefiles provided by the RubyInstaller project) with GCC 4.x and/or different optimization options (RubyInstaller is compiled with moderate optimization options and for generic 386 CPUs),
use a newer version of MRI than 1.8.6,
use a different implementation of Ruby:
- YARV is significantly faster than MRI (unfortunately, it only implements Ruby 1.9, so you might have to change your code),
- JRuby is significantly faster than YARV in a lot of scenarios, and it implements both Ruby 1.8 and Ruby 1.9 (it also has a -fast commandline option, which is slightly incompatible with Ruby, but improves performance, including arithmetic performance) and
- IronRuby might also be faster than YARV, depending on the workload.

In the latter two cases you might want to revise your benchmarks a bit. Both eventually can compile Ruby code to native machine code, but it might take a while. JRuby for example compiles to JVM bytecode after a method has been executed 20 times and HotSpot Server compiles JVM bytecode to native machine code after it has executed 20000 times. Also, compilation itself takes time, so the program needs to run a while to gain back that cost through improved performance.

In particular, Charles Oliver Nutter, one of the JRuby lead developers, said that depending on the workload, JRuby might take up to 5-15 seconds to ramp up to full speed. Your benchmarks are about 100x too fast (here's a sentence you don't hear every day ...).

回复收藏 0 原文

迷迭香的记忆 2024-08-19 10:42:47

1.8.6 在这方面只是速度较慢。 1.8.7 做得更好一点，1.9.1 做得更好。我无法说出为什么，但 rvm 同意你和 Pavel 的观点，即 1.8.6 异常慢。

1.8.6: 
Rehearsal ------------------------------------------------
float-multip   0.140000   0.000000   0.140000 (  0.141560)
float-square   0.150000   0.000000   0.150000 (  0.146286)
int-multip     0.220000   0.000000   0.220000 (  0.223255)
int-multip     0.180000   0.000000   0.180000 (  0.183850)
--------------------------------------- total: 0.690000sec

1.8.7:
Rehearsal ------------------------------------------------
float-multip   0.090000   0.000000   0.090000 (  0.092346)
float-square   0.080000   0.000000   0.080000 (  0.080335)
int-multip     0.070000   0.000000   0.070000 (  0.068012)
int-multip     0.080000   0.000000   0.080000 (  0.081713)
--------------------------------------- total: 0.320000sec

1.9.1:
Rehearsal ------------------------------------------------
float-multip   0.070000   0.000000   0.070000 (  0.065532)
float-square   0.080000   0.000000   0.080000 (  0.081620)
int-multip     0.060000   0.000000   0.060000 (  0.065371)
int-multip     0.070000   0.000000   0.070000 (  0.065761)
--------------------------------------- total: 0.280000sec

1.8.6 is just slower in this area. 1.8.7 does a little better and 1.9.1 does better still. I couldn't say why but rvm agrees with you and Pavel that 1.8.6 is oddly slow.

1.8.6: 
Rehearsal ------------------------------------------------
float-multip   0.140000   0.000000   0.140000 (  0.141560)
float-square   0.150000   0.000000   0.150000 (  0.146286)
int-multip     0.220000   0.000000   0.220000 (  0.223255)
int-multip     0.180000   0.000000   0.180000 (  0.183850)
--------------------------------------- total: 0.690000sec

1.8.7:
Rehearsal ------------------------------------------------
float-multip   0.090000   0.000000   0.090000 (  0.092346)
float-square   0.080000   0.000000   0.080000 (  0.080335)
int-multip     0.070000   0.000000   0.070000 (  0.068012)
int-multip     0.080000   0.000000   0.080000 (  0.081713)
--------------------------------------- total: 0.320000sec

1.9.1:
Rehearsal ------------------------------------------------
float-multip   0.070000   0.000000   0.070000 (  0.065532)
float-square   0.080000   0.000000   0.080000 (  0.081620)
int-multip     0.060000   0.000000   0.060000 (  0.065371)
int-multip     0.070000   0.000000   0.070000 (  0.065761)
--------------------------------------- total: 0.280000sec

回复收藏 0 原文

不羁少年 2024-08-19 10:42:47

我无法解释你的表格。但我可以解释我的（ruby 1.8.7）：

                   user     system      total        real
float-multip   0.600000   0.000000   0.600000 (  0.612311)
float-square   0.650000   0.000000   0.650000 (  0.649399)
int-multip     0.450000   0.010000   0.460000 (  0.457004)
int-multip     0.690000   0.000000   0.690000 (  0.692879)

哎呀。整数乘法胜过浮点乘法。

由于你的处理器比我的处理器慢 5 倍（我将你的基准测试中的重复次数增加了十倍），所以一定有一些与 ruby 无关的东西。

** 运算可能使用浮点运算(exp(x*ln(2))，因此它和其他浮点运算一样慢。

I can't explain your tables. But I can explain mine (ruby 1.8.7):

                   user     system      total        real
float-multip   0.600000   0.000000   0.600000 (  0.612311)
float-square   0.650000   0.000000   0.650000 (  0.649399)
int-multip     0.450000   0.010000   0.460000 (  0.457004)
int-multip     0.690000   0.000000   0.690000 (  0.692879)

Whoops. Integer multiplication beats floating point ones.

Since your processor is 5 times slower than mine (I increased the number of repeats in your benchmark in ten times), there must be something not ruby-concerned.

** operation probably used floating-point arithmetic(exp(x*ln(2)), so it is as slow as other floating-point operations.

回复收藏 0 原文