Ruby: 提升性能的几点尝试

January 29, 2008 – 11:20 pm

近日做一个 Ruby 的程序需要用到一个大约 2 MB 大小的词典,我把它构造在一个 Ruby 的 Hash 里,然而程序启动需要花上大约 4 秒多的时间,主要都是花在加载词典上了。虽然这个程序许多情况下可以在初始化之后处理许多数据,因此可以把启动时间忽略掉,但是在测试的时候还是让人相当不爽。于是就想看看是否可以改进。

首先我测试了只读入一个大约 2 M 的文件的操作,速度非常快,在我这里大约在 0.16 秒左右,然后尝试在读入每行的时候把数据加入到一个 Hash 中去,速度降低到了越 0.43 秒左右:

h = Hash.new
File.open("words.dic", "r") do |f|
  f.each_line { |l|
    h[l] = l
  }
end

虽然速度下降了,但是显然不是我前面的 4 秒多。问题在于:我的辞典并不是简单的每行一个单词。不过需要明确一点,如果要在 Hash 中构建一个辞典,上面是最基本的代码,因此上面这段代码的性能应该是性能极限。

我要用到的词典格式其实很简单,每一个数据项是一个词,可能还有一个附加的表示单词频率的整数值。原来的格式是每行一个词,如果有频率数据,则数据放在词后面由一个空格分开,如果第一个字符是 # 则表示注释。

我最先想到的方法就是用另外的数据结构,比如用一种树状的数据结构:

dictionary.png

然而树的插入和查询时间其实是 O(log(n)) ,不如 Hash 的 O(1) 。我还想过用 C 来实现部分代码,这也许是大多数人在发现脚本运行太慢的第一反应吧,但是我最终还是没有那么做,这样带来的复杂度的增加恐怕只会得不偿失,而且我写出来的东西多半不会比 Ruby 自带的 Hash 性能更好。

还是回过头来分析速度慢的原因吧,如果只是插入到 Hash 中的话,应该如上面的程序片段那样有 0.4 秒左右的速度,这个速度还是可以接受的,说明问题并不是出在数据结构上。我的代码大致是这个样子:

File.open(file, "r") { |f|
  f.each_line { |line|
    arr = line.split(" ")
    if arr.length > 1
      @dic[arr[0]] = Word.new(arr[0], Word::TYPES[:cjk_word], arr[1].to_i)
    else
      word = Word.new(arr[0])
      @dic[word.value] = word
    end
  }
}

我已经去除了辞典文件里面的注释,并且去掉了注释的支持,速度没有得到什么提升。想了半天,心想可能问题处在构造 Word 对象上,我一直觉得 Word 是一个相当小的对象,不应该会成为瓶颈,但是一想到要构造十多万个对象,还是没有一个底,转念一想,其实词典里面应该有很大一部分是没有用到的,就凭这个,给它来个按需构造也是有好处的。

于是我将 f.each_line 循环中构造 Word 的代码去掉了,而是直接把字符串保存在 Hash 中:

File.open(file, "r") { |f|
  f.each_line { |line|
    arr = line.split(" ")
    @dic[arr[0]] = line
  }
}

再在需要的时候进行构造:

def get_word(value)
  word = @dic[value]
  # Construct a Word lazily
  if word.is_a? String
    arr = word.split(" ")
    word = Word.new(arr[0], Word::TYPES[:cjk_word], arr[1].to_i)
    @dic[value] = word
  end
  word
end

令我吃惊的是,性能一下子提升了大约 4 倍!看来瓶颈果然出在 Word 对象的构造上,也许是大量分配小内存块还造成了许多碎片。这下我知道窍门了:要尽量降低大循环内代码的复杂度。开始我觉得 split 操作可能会比较费时,经过测试发现 line.split(" ")[0] 的性能比 line[0...line.index(" ")] 要高,我想也许是 split 是相当常见的操作,必定经过了不少优化吧。

然而我始终是看 split 不顺眼。后来我注意到词典文件主要是两个,一个有频率信息,另一个没有频率信息,没有频率信息的那个文件比另一个大了许多,而且在解析它的时候就不需要用 split 了。因此我写了两个函数 load_dictionaryload_dictionary_with_freq 。这一下子,性能又提升了不少,大约在 0.5 秒左右,已经很接近极限值了。

后来我还尝试把词和频率写在两行上,避免使用 split ,发现并不能有多大程度改善性能,为了可维护性,还是改回来了。这是我的最终代码:

def load_dictionary_with_freq(file)
  File.open(file, "r") { |f|
    f.each_line { |line|
      pair = line.split(" ")
      @dic[pair[0]] = line
    }
  }
end
def load_dictionary(file)
  File.open(file, "r") { |f|
    f.each_line { |line|
      line.chomp!.freeze
      @dic[line] = line
    }
  }
end

这是按需构造的代码:

def has_word?(value)
  @dic.has_key?(value)
end
 
def get_word(value)
  word = @dic[value]
  # Construct a Word lazily
  if word.is_a? String
    arr = word.split(" ")
    word = Word.new(arr[0], Word::TYPES[:cjk_word], arr[1].to_i)
    @dic[value] = word
  end
  word
end

总结为如下几点:

  • 改进性能要找程序的性能瓶颈,不要盲目地优化,更不要一发现慢就赶紧换 C/C++ 。
  • 尽量使用内置的 HashString 等类,因为它们是被大量使用的,已经被进行了大量优化。
  • 优化最常见的情况,这有点类似于 80/20 原则,就是要尽量让会被大量运行的代码片段简单快速。前面说的两次性能提升基本上都是用了这个原则:
    1. 观察到 Hash 中的大部分元素自始至终都没有被用到过,因此不必构造一个 Word 对象进行辅助操作,所以进行按需构造,在大部分情况下省掉了构造对象的麻烦,不管从时间还是从空间上来看都是一个节省。
    2. 注意到没有频率信息的词比有频率信息的词多了许多,因此对有频率信息的词的加载过程特殊处理,进而将没有频率信息的词的加载过程中简化,进一步提升了性能。
  • 不要盲目追求性能。所谓“鱼与熊掌不可兼得”,通常性能好的代码可读性和可维护性会有所下降。盲目追求任何一个方面都是非常极端的态度,在合适的情形下找到二者的平衡点才是最佳办法。至于什么地方是平衡点,那就只有凭感觉了。 :p
  • 熟悉 Ruby 标准库里面的 Benchmark ,用来做性能对比非常方便。
  1. 2 Responses to “Ruby: 提升性能的几点尝试”

  2. 这下我知道窍门了:要尽量降低大循环内代码的复杂度
    =
    就是说如果有一个
    for i in 0..4
    for j in 0..4
    #something
    end
    end

    改为
    for i in 0..2
    for j in 0..8
    #something
    end
    end
    这样性能比较好?
    外层的循环造成大量分配小内存块还造成了许多碎片了?

    By g.zhen.ning on Mar 31, 2008

  3. 本来愁了半天,以为自己碰到的问题是因为文件太大不好处理,照着你的原则改了,代码效率提高了得有100倍,,,可见以前写的有多么不注重性能。
    不过改了后的代码没以前容易读了,,,值了,起码要work~

    By WANG Lei on May 14, 2009

Post a Comment