17

Lua和Python：实现一个高效的List对象(1)

 3 years ago
source link: https://zhuanlan.zhihu.com/p/179294918
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：实现一个高效的List对象(1)

自从上次简单比较了Lua和Python的列表性能之后，我对Lua的列表性能深感忧虑，为了进一步弄清其他操作的状况，我写了一些测试用例。

Lua的如下：

local function test_table1()
    local linsert = table.insert
    local ls = {}
    local c = 1000000
    local tm = os.clock()
    for i = 1, c do
        linsert(ls, i)
    end
    print("lua.table - insert after(1000000): ", os.clock() - tm)
end

local function test_table2()
    local linsert = table.insert
    local ls = {}
    local c = 100000
    local tm = os.clock()
    for i = 1, c do
        linsert(ls, 1, i)
    end
    print("lua.table - insert before(100000)", os.clock() - tm)
end

local function test_table3()
    local ls = {}
    local c = 1000000
    local linsert = table.insert
    local lremove = table.remove
    for i = 1, c do
        linsert(ls, i)
    end

    local tm = os.clock()
    for i = 1, c do
        lremove(ls)
    end
    print("lua.table - remove after(1000000)", os.clock() - tm)
end

local function test_table4()
    local ls = {}
    local c = 100000
    local linsert = table.insert
    local lremove = table.remove
    for i = 1, c do
        linsert(ls, i)
    end

    local tm = os.clock()
    for i = 1, c do
        lremove(ls, 1)
    end
    print("lua.table - remove before(100000)", os.clock() - tm)
end
test_table1()
test_table2()
test_table3()
test_table4()

Python的如下：

def test1():
    c = 1000000
    a = []
    tm = time.time()
    for i in xrange(c):
        a.append(i)
    print "python-append(1000000)",  time.time() - tm

def test2():
    c = 100000
    a = []
    tm = time.time()
    for i in xrange(c):
        a.insert(0, i)
    print "python-insert(100000)",  time.time() - tm

def test3():
    c = 1000000
    a = []
    for i in xrange(c):
        a.append(i)

    tm = time.time()
    for i in xrange(c):
        a.pop()
    print "python-pop-after(1000000)",  time.time() - tm

def test4():
    c = 100000
    a = []
    for i in xrange(c):
        a.append(i)

    tm = time.time()
    for i in xrange(c):
        a.pop(0)
    print "python-pop-before(100000)",  time.time() - tm

test1()
test2()
test3()
test4()
  • test1 1000000个元素往最后追加
  • test2 100000个元素往最前插入
  • test3 1000000个元素从最后删除
  • test4 100000个元素从最前删除

分别运行lua test.lua，python test.lua，结果如下:

lua.table - insert after(1000000):      0.171875
lua.table - insert before(100000)       44.859375
lua.table - remove after(1000000)       0.203125
lua.table - remove before(100000)       44.421875

python-append(1000000)      0.0735228061676
python-insert(100000)       1.67143321037
python-pop-after(1000000)   0.0515899658203
python-pop-before(100000)   0.863451004028

Lua全面的落后，往后面追加和删除还在可接受范围之内，往前插入和删除就有点惨不忍睹了。

为了探究原因，我仔细查看Lua的源码，甚至还去翻Python的代码，终于发现向前插入删除巨慢无比的原因：竟然是函数调用。以插入为例，列表后面的元素要一个个地往后移动，Python的处理就很简单：

...
items = self->ob_item;
for (i = n; --i >= where; )
    items[i+1] = items[i];
...

就是原地一个个的向后移，Lua则要调用两个函数：

lua_geti(L, 1, i - 1);
lua_seti(L, 1, i);  /* t[i] = t[i - 1] */

别小看这两个函数，里面还涉及到其他的函数调用，但是单单从逻辑上看，代码没有执行很慢的操作，就是每个元素在移动的时候不得不调用一些函数，而性能的影响恰恰是这些函数调用的开销引起的。

我们把插入简化成下面的C程序：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

double getclock() {
    return (double)clock() / (double)CLOCKS_PER_SEC;    
}

int main(int argc, char const *argv[]) {
    int c = 100000;
    int *a = (int*)malloc(c * sizeof(int));
    double tm = getclock();

    int size = 0;
    int i, j;
    for (i = 0; i < c; ++i) {
        ++size;
        for (j = size-1; j > 0; --j) {
            //----------------------
            a[j] = a[j-1];
            //----------------------
        }
        a[0] = i;
    }

    printf("c - insert before: %f\n", getclock() - tm);
    free(a);
    return 0;
}

打开O3编译优化之后，消耗的时间只需要0.34秒，比Python都要快几倍。

c - insert before: 0.343750

现在把中间那部分抽成一个函数，并且强制不让编译器优化成内联：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

double getclock() {
    return (double)clock() / (double)CLOCKS_PER_SEC;    
}

void __attribute__ ((noinline)) move(int *a, int j) {
    a[j] = a[j-1];
}

int main(int argc, char const *argv[]) {
    int c = 100000;
    int *a = (int*)malloc(c * sizeof(int));
    double tm = getclock();

    int size = 0;
    int i, j;
    for (i = 0; i < c; ++i) {
        ++size;
        for (j = size-1; j > 0; --j) {
            //----------------------
            // a[j] = a[j-1];
            move(a, j);
            //----------------------
        }
        a[0] = i;
    }

    printf("c - insert before: %f\n", getclock() - tm);
    free(a);
    return 0;
}

同样打开O3优化，结果却是：

c - insert before: 6.390625

可见时间几乎消耗在函数调用上。

Lua的列表性能还有得救吗？如果一定要直接用Table，那几乎没有办法做任何优化，可是我们又绕不开Table，因为Lua只有Table能做容器。

经过这几天的思考，我想到一种方法，既然直接用Table没法提高性能，那不如用间接的方式，我们操作的列表是自己实现的，列表的元素是指向Table值的“引用”；如此一来，这个列表即能保存Lua对象，又能只针对引用做操作，而不用涉及到Table的增删。

具体如何实现这个列表，看下回分析。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK