《松本行弘的程序世界》之让程序飞（Ruby版）

为什么要做性能优化？
      “过早优化是万恶之源”，作为一名程序员，无可否认让程序高速运行是一种智力的挑战，让程序的运行速度提高10倍甚至上千倍，这种成就感不能不说是一种极大的乐趣，这对于程序员来说，倒不是什么坏事，但是，做一个项目的时候，都是有目标的，性能优化是实现目标的一个手段，切忌把手段当成了一个目标。因此，性能优化是需要权衡。预算，开发效率，开发周期，客户需求等等制约因素都应考虑在内，提高性能的价值应该大于我们付出的代价。

如何做性能优化？
      再重复的啰嗦一句，“如无必要，无需做优化”。中医常说，对症方能下药，如果不知道系统有多慢，慢在什么地方，那么性能优化也就无从谈起了。因此性能优化的第一步就是：测定性能，以数据说话
      标准的Linux的系统中有自带测定执行时间的工具，time命令，以下面这段Ruby程序为例：

require "complex"

def mandelbrot(cr,ci)
  limit = 95
  iterations=0
  c=Complex.new(cr,ci)
  z=Complex.new(0,0)
  while iterations<limit and z.abs<10 do
    z=z*z+c
    iterations+=1
  end
  return iterations
end

def mandel_calc(min_r,min_i,max_r,max_i,res)
  cur_i=min_i
  while cur_i>max_i
    print "|"
    cur_r = min_r
    while cur_r < max_r
      ch = 127 - mandelbrot(cur_r,cur_i)
      printf "%c",ch
      cur_r +=res
    end
    print "|\n"
    cur_i -=res
  end
end

mandel_calc(-2,1,1,-1,0.04)

执行命令time ruby mandel.rb 会得到如下结果：

……..
real    0m1.148s
user    0m1.143s
sys     0m0.003s

各个版本也许格式不同，但大多包含如下三个数据：
      real：程序开始到终止的时间
      user：程序本身执行的时间
      sys：系统调用花费的时间
      real表述了系统的性能，user和sys可以用来判断是否是因为系统调用导致程序变慢。
除了time命令外，各个语言也有一些专门用于性能调优的工具，在Ruby中有自带的profile,得到结果如下：

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 22.09    23.72     23.72   229539     0.10     0.28  Object#Complex
 17.36    42.37     18.65   237039     0.08     0.10  Complex#initialize
 12.01    55.27     12.90   114769     0.11     0.45  Complex#*
  7.36    63.18      7.91  1181444     0.01     0.01  Kernel.kind_of?
  7.36    71.08      7.90     3750     2.11    28.54  Object#mandelbrot
  6.53    78.09      7.01   114769     0.06     0.36  Complex#+
  4.07    82.46      4.37   459078     0.01     0.01  Numeric#real
  3.86    86.61      4.15   237039     0.02     0.12  Class#new
  3.68    90.56      3.95   459078     0.01     0.01  Numeric#imag
  2.70    93.46      2.90   443822     0.01     0.01  Float#*
  2.25    95.88      2.42   336751     0.01     0.01  Float#-
  2.23    98.27      2.39   117551     0.02     0.03  Complex#abs
  2.07   100.49      2.22   355614     0.01     0.01  Fixnum#+
  1.98   102.62      2.13   336751     0.01     0.01  Float#+
  1.51   104.24      1.62   225709     0.01     0.01  Float#==
  0.96   105.27      1.03   118569     0.01     0.01  Fixnum#<
  0.78   106.11      0.84   117551     0.01     0.01  Math.hypot
  0.65   106.81      0.70   121301     0.01     0.01  Float#<
  0.19   107.01      0.20        1   200.00 107400.00  Object#mandel_calc
  0.16   107.18      0.17    15254     0.01     0.01  Fixnum#*
  0.07   107.25      0.07     3830     0.02     0.02  Fixnum#==
  0.07   107.32      0.07     3750     0.02     0.03  Kernel.printf
  0.05   107.37      0.05    11357     0.00     0.00  Fixnum#-
  0.03   107.40      0.03     3850     0.01     0.01  IO#write
  0.00   107.40      0.00        2     0.00     0.00  Module#attr
  0.00   107.40      0.00        1     0.00     0.00  Kernel.require
  0.00   107.40      0.00      100     0.00     0.00  Kernel.print
  0.00   107.40      0.00       50     0.00     0.00  Float#>
  0.00   107.40      0.00        1     0.00     0.00  Class#inherited
  0.00   107.40      0.00       37     0.00     0.00  Kernel.singleton_method_added
  0.00   107.40      0.00       76     0.00     0.00  Module#method_added
  0.00   107.40      0.00        7     0.00     0.00  Module#method_undefined
  0.00   107.40      0.00       34     0.00     0.00  Module#module_function
  0.00   107.40      0.00        1     0.00     0.00  Fixnum#>
  0.00   107.40      0.00        1     0.00 107400.00  #toplevel

real    1m54.226s
user    1m47.404s
sys     0m6.814s

还有ruby-prof，得到结果如下：

Total: 11.942691
Sort by: self_time

 %self     total     self     wait    child    calls   name
 17.77      3.06     2.12     0.00     0.93   237039   Complex#initialize 
 14.48      7.52     1.73     0.00     5.79   229539   Object#Complex 
  9.81      1.17     1.17     0.00     0.00  1181444   Kernel#kind_of? 
  8.37      5.64     1.00     0.00     4.64   114769   Complex#* 
  6.18      4.80     0.74     0.00     4.06   114769   Complex#+ 
  5.73      0.68     0.68     0.00     0.00   459078   Numeric#imag 
  5.69      0.68     0.68     0.00     0.00   459078   Numeric#real 
  4.94     11.89     0.59     0.00    11.30     3750   Object#mandelbrot 
  4.51      3.86     0.54     0.00     3.32   237039   Class#new 
  3.94      0.47     0.47     0.00     0.00   443822   Float#* 
  3.04      0.36     0.36     0.00     0.00   355614   Fixnum#+ 
  2.87      0.34     0.34     0.00     0.00   336751   Float#+ 
  2.77      0.33     0.33     0.00     0.00   336751   Float#- 
  2.24      0.27     0.27     0.00     0.00   237039   <Class::Object>#allocate 
  2.21      0.39     0.26     0.00     0.12   117551   Complex#abs 
  1.84      0.22     0.22     0.00     0.00   225709   Float#== 
  1.03      0.12     0.12     0.00     0.00   117551   <Module::Math>#hypot 
  1.01      0.12     0.12     0.00     0.00   121301   Float#< 
  0.98      0.12     0.12     0.00     0.00   118569   Fixnum#< 
  0.17     11.94     0.02     0.00    11.92        1   Object#mandel_calc 
  0.13      0.02     0.02     0.00     0.00    15254   Fixnum#* 
  0.10      0.01     0.01     0.00     0.00    11357   Fixnum#- 
  0.08      0.02     0.01     0.00     0.01     3750   Kernel#printf 
  0.06      0.01     0.01     0.00     0.00     3850   IO#write 
  0.03      0.00     0.00     0.00     0.00     3831   Fixnum#== 
  0.01      0.00     0.00     0.00     0.00        1   Kernel#gem_original_require 
  0.00      0.00     0.00     0.00     0.00       34   Module#module_function 
  0.00      0.00     0.00     0.00     0.00      100   Kernel#print 
  0.00     11.94     0.00     0.00    11.94        1   Kernel#load 
  0.00      0.00     0.00     0.00     0.00       72   Module#method_added 
  0.00      0.00     0.00     0.00     0.00       50   Float#> 
  0.00     11.94     0.00     0.00    11.94        1   Global#[No method] 
  0.00      0.00     0.00     0.00     0.00       37   Kernel#singleton

      细心的朋友可能已经发现，使用time命令总执行时间为1.148s，使用profile总执行时间为1m54.26s，使用ruby-prof总执行时间为11.94s，因此，使用profiler工具要关注3点：
     1、工具能为我们提供程序性能消耗的细节
     2、工具本身也会有性能消耗
     3、选择一个好的工具能帮我们节省时间。

从上面的profiler工具的结果，程序中的性能杀手就是：
     1、Object#Complex 调用229539次
     2、Complex#initialize调用237039次
     3、Complex#* 调用114769次
因此接下来就需要有针对性的对性能杀手进行优化：

       首先，减少对象，很明显最耗时间的就是Complex类的生成和初始化,可以尝试不使用Complex对象，那么mandel.rb程序可以改为如下的样子：

def mandelbrot(cr,ci)
  limit = 95
  iterations=0
  zr=zi=0
  while iterations<limit and Math.sqrt(zr**2+zi**2)<10 do
    zr,zi=zr*zr-zi*zi+cr,zr*zi+zi*zr+ci
    iterations+=1
  end
  return iterations
end

执行时间如下：

Total: 3.149811
Sort by: self_time

 %self     total     self     wait    child    calls   name
 36.86      3.11     1.16     0.00     1.95     3750   Object#mandelbrot 
 16.10      0.51     0.51     0.00     0.00   443822   Float#* 
 15.51      0.49     0.49     0.00     0.00   450500   Float#+ 
  8.58      0.27     0.27     0.00     0.00   227473   Float#** 
  4.38      0.14     0.14     0.00     0.00   117551   <Module::Math>#sqrt 
  4.00      0.13     0.13     0.00     0.00   111017   Float#- 
  3.95      0.12     0.12     0.00     0.00   129877   Fixnum#+ 
  3.83      0.12     0.12     0.00     0.00   121301   Float#< 
  3.73      0.12     0.12     0.00     0.00   118569   Fixnum#< 
  0.85      0.04     0.03     0.00     0.02     7629   Fixnum#** 
  0.57      3.15     0.02     0.00     3.13        1   Object#mandel_calc 
  0.47      0.01     0.01     0.00     0.00    15254   Fixnum#* 
  0.25      0.01     0.01     0.00     0.00     3750   Kernel#printf 
  0.24      0.01     0.01     0.00     0.00     7629   Fixnum#>= 
  0.24      0.01     0.01     0.00     0.00     7552   Fixnum#- 
  0.23      0.01     0.01     0.00     0.00     7629   Fixnum#power! 
  0.17      0.01     0.01     0.00     0.00     3850   IO#write 
  0.01      0.00     0.00     0.00     0.00      100   Kernel#print 
  0.01      3.15     0.00     0.00     3.15        1   Kernel#load 
  0.00      0.00     0.00     0.00     0.00       50   Float#> 
  0.00      3.15     0.00     0.00     3.15        1   Global#[No method] 
  0.00      0.00     0.00     0.00     0.00        1   Fixnum#== 
  0.00      0.00     0.00     0.00     0.00        2   Module#method_added 
  0.00      0.00     0.00     0.00     0.00        1   Fixnum#> 

可以看到执行时间从11.94s提升到了3.15s,细心的同学可能会发现整个程序的方法调用也少了很多，因此ruby性能调优的第一个法则就是：
少使用对象，减少对象方法调用.
注：减少使用对象，不仅会省掉创建对象的时间，对于垃圾收集处理器的性能也有很大帮助。

      现在，程序性能的瓶颈转移到了Object#mandelbrot方法，Ruby是一种解释型语言，对于mandelbrot方法这种单纯计算的循环不是很快，如果我们能把该部分通过C语言来实现会有效的提升的性能，在Ruby中，可以很容易的通过RubyInline直接嵌入C语言代码，于是mandebrot方法改为：

require "inline"
class Object
  inline :C do |builder|
    builder.include "<math.h>"
    builder.c "
      int mandelbrot(double cr,double ci){
        long limit = 95;
        long iter = 0;
        double zr = 0, zi =0 ,zzr,zzi;
        while(iter<limit && sqrt(zr*zr+zi*zi)<10){  
          zzr = zr*zr-zi*zi+cr;
          zzi = zr*zi+zi*zr+ci;
          zr=zzr;
          zi=zzi;
          iter++;
        }
        return iter;
      }
    "
  end
end

执行结果：

Total: 0.094613
Sort by: self_time

 %self     total     self     wait    child    calls   name
 20.28      0.02     0.02     0.00     0.00      369   <Class::File>#file? 
 18.28      0.05     0.02     0.00     0.03        1   Object#mandel_calc 
  8.09      0.01     0.01     0.00     0.00     3750   Kernel#printf 
  4.88      0.00     0.00     0.00     0.00     3750   Object#mandelbrot 
  4.87      0.01     0.00     0.00     0.01       10  *Kernel#gem_original_require 
  4.78      0.00     0.00     0.00     0.00     3851   IO#write 
  4.02      0.00     0.00     0.00     0.00     3700   Float#+ 
  3.97      0.00     0.00     0.00     0.00     3753   Fixnum#- 
  3.74      0.00     0.00     0.00     0.00     3750   Float#< 
  1.65      0.03     0.00     0.00     0.03      118   Gem::Specification#contains_requirable_file? 
  1.31      0.03     0.00     0.00     0.03      262  *Array#each 
  1.11      0.00     0.00     0.00     0.00      120   Gem::Specification#full_gem_path 
  1.04      0.00     0.00     0.00     0.00        1   Kernel#` 
  0.62      0.00     0.00     0.00     0.00      123   <Module::Gem>#suffixes 
  0.42      0.00     0.00     0.00     0.00      116   Kernel#=== 
  0.31      0.00     0.00     0.00     0.00      127   String#==

程序的运行时间从3.15s提升到了0.09秒。因此，在一些瓶颈点，使用C语言实现，也不失为提升性能的一个好办法。
      还能再优化吗？从ruby-prof的结果可以看到，Object#mandelbrot方法被调用了3750次，如果能降低这个调用次数，对性能的提升应该也有帮助,这里可以使用特别的数据结构和算法，比如使用Narray（http://narray.rubyforge.org/demo/mandel.html.en ）来实现mandelbrot方法。
       另外，整个程序都使用C语言实现也是进一步提高程序运行速度的方法；还有以空间换时间的方法，把中间结果保存起来避免多次重复的处理。

总结：
     性能优化是一个项目各方面制约因素权衡的产物，如无必要，毋做优化。
     性能优化是一个“查找瓶颈点→选择适当的方法改善瓶颈点性能”反复迭代的过程。
     选择一个好的工具能使查找瓶颈点的工作事半功倍。
    常用的改善性能的技巧有：
          1、减少对象的创建，减少Ruby实现方法的调用
          2、选择高性能的算法和数据结构实现程序
          3、使用C语言等编译型语言实现瓶颈点程序。
          4、以空间换时间