8

Lua和Python：列表的性能比较

 3 years ago
source link: https://zhuanlan.zhihu.com/p/169826413
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Lua和Python：列表的性能比较

最近在写的一些程序，经常涉及到列表的操作，比如往一个列表追加数据，如下面这样的代码：

local t = {}
local tinsert = table.insert
for i = 1, 1000 do
    tinsert(t, i)
end

以我的常识， 我知道上面的代码还可以再优化成这样：

local t = {}
for i = 1, 1000 do
    t[#t+1] = i
end

这减少了一次C API的调用，性能会快一点点。Lua在脚本语言中以高效简洁著称，那同样的操作总应该比Python要快吧，于是我写了下面的对比代码：

Lua代码：

local tm = os.clock()
local t = {}
for i = 1, 1000000 do
    t[#t+1] = i
end
print("Lua", os.clock() - tm)

Python代码

import time
a = []
tm = time.time()
for i in xrange(1000000):
    a.append(i)
print "Python", time.time() - tm

结果消耗的时间如下：

lua     0.15625
python  0.0809590816498

神奇，Lua比Python慢了一倍，问题出在哪儿呢？看来看去只能是#t这个操作了，如果我把代码变成这样：

local t = {}
local c = 0
local tm = os.clock()
for i = 1, 1000000 do
    c = c + 1
    t[c] = i
end
print("lua", os.clock() - tm)

运行时间变成了：

lua     0.046875

反超成功，现在比Python快了一倍，比#t的版本将近快了4倍。

看起来#t并不是立即返回数组长度，而是做了更耗时的操作，翻开Lua的源码，相关的函数是：

lua_Unsigned luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && ttisnil(&t->array[j - 1])) {
    /* there is a boundary in the array part: (binary) search for it */
    unsigned int i = 0;
    while (j - i > 1) {
      unsigned int m = (i+j)/2;
      if (ttisnil(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  /* else must find a boundary in hash part */
  else if (isdummy(t)) {  /* hash part is empty? */
    return j;  /* that is easy... */
  }
  else {
       return unbound_search(t, j);
  }
}

问题就在if (j > 0 && ttisnil(&t->array[j - 1]))这一段，如果数组部分最后一个元素是nil，那么就用二分查找找到最后不是nil的元素，返回这个索引。

我们不断地往Table增加数据时，数组部分会动态地按2的幂扩充，比如现在数组长度是2，再加一个值，数组就动态扩充成4，后面再扩充成8，16...，多出来的槽位填充为nil。所以除非数组刚好满了，否则#t都会用二分查找来确定长度。时间复杂度一样子从O(1)变成了O(logN)。这样分析下来，甚至比Python慢也是可以理解了。

这个问题的根源，我认为是Lua把哈希表和数组融合在一起，很多对数组的操作，也不得不考虑哈希部分；而且在rehash的时候，数据经常在数组和哈希表转移。这种融合在我看来一点好处都没有：增加了Table代码的复杂度，且很难针对数组的操作作出更优化的写法。比如没有办法提供数组的精确长度，只能通过二分查找找到最右边的非空元素。

在Lua中，把Table当成数组操作，是会比其他语言承担更多的性能开销的，后面有时间，会再谈谈往数组前面插入或删除元素的性能，足足比Python慢了20倍以上。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK