使用cffi和re2实现部分Python内置re模块功能(兼容pypy)

从一些benchmark可以看出,Python内置的re模块比起re2是慢很多的。而Google的re2(https://code.google.com/p/re2/)是一个速度快的C++正则库。是否可以在Python内利用re2呢?有一些人已经做了相关的工作:facebook/pyre2 axiak/pyre2,但这些都是采用CPython扩展/Cython的方式编写,在pypy下不能正常使用。如何既能得到pypy的速度,也能利用re2?首先想到了CPython和pypy都内置的ctypes模块,可以用来访问C编写的so库。

但从实际测试结果来看,在pypy下使用ctypes是比较慢的,有人也报了BUG(https://bugs.pypy.org/issue1237),但仍未解决。测试数据如下:

还有另外一个第三方库:cffi(http://cffi.readthedocs.org/),可以实现类似ctypes的访问C库并调用其函数的功能。跟ctypes一样,cffi也只能访问C的so,无法直接访问C++的so,因此我们要为re2包装一层,暴露C接口。具体代码在github。从上面的测试可以看出,cffi_re2在某些正则下是原生re模块的速度的50倍,但有些正则却会比原生的慢……

使用了我们生产的真实数据和真实正则测试,测试代码:https://gist.github.com/vls/7539716(涉及公司数据,这里无法给出测试数据),在CPython和pypy下都能取得一些性能上的提升:)


Python循环中的local变量绑定问题

考虑以下代码

func_list = []

def foo(d):
    print 'num', num
    _num = num
    return d['level'] > _num

def get_f(num):
    _num = num
    def bar(d):
        print 'num', _num
        return d['level'] > _num
    return bar

for num in (30, 60):
    level_func = foo
    #level_func = get_f(num)
    func_list.append(level_func)


d = {'level': 40}

for f in func_list:
    print f(d)

当level_func是foo时,两次调用都会输出num=60,而level_func = get_f(num),才会输出期望的num=30, num=60。

原因是循环中level_func都绑定了同一个local变量num,而循环结束后,变量num的值为60,所以输出都是60。而get_f里面定义了_num=num,bar函数的_num是指向get_f里面所定义的_num,这是因为Python里def定义函数创造了一个新的variable scope;循环两次,get_f里形成闭包,保存了循环当时的值。

但每次都要定义一个辅助函数(上例的get_f)总觉得麻烦,如何解决?其实可以利用Python的一个“坑”
代码:

level_func = lambda d, num=num: return d['level'] > num

原理就是利用Python函数默认参数是在定义时绑定。

具体的差别可以用过dis模块来打印函数的bytecode查看。


pypy 2.0在CentOS 5.x 编译问题小结

pypy 2.0发布了,又要编译了。环境仍然是CentOS 5.x 64bit。

问题:tmp目录空间不够
解决:调用的是python里面的tempfile来获取临时目录的。所以定义环境变量TMP或者TEMP或者TMPDIR都可以。

问题:default value for ‘w_ignored1′ can only be None, got ”; (详细信息:http://bpaste.net/show/OUN1VScbqnuujKEkGHJ8/
解决:irc上说用新版本pypy或cpython来执行。我用的是pypy 1.9也不行,就用了cpython 2.6.7,通过。

问题:CentOS自带SQLite版本过低
解决:安装更新版本的SQLite再编译。


MySQL 5.6新特性测试

在微博上看到隔壁部门的同事发布了一个介绍MySQL 5.6新特性的slide。遂对其中几个对我们业务有用的特性做了测试。

Found a slide which introducing new features in MySQL 5.6, which is made by a colleague in other department. For our business, I ran some tests on some features.

  • InnoDB Compression
//压缩前(before compress)
Name: workticket
Engine: InnoDB
Version: 10
Row_format: Compact
Rows: 1471830
Avg_row_length: 328
Data_length: 483295232
Max_data_length: 0
Index_length: 260276224
Data_free: 5242880
Auto_increment: 3473533
Create_time: 2013-04-15 16:01:01
Update_time: NULL
Check_time: NULL
Collation: utf8_general_ci
Checksum: NULL
Create_options: 
Comment: 工单表
//压缩后(after compress)
Name: workticket
Engine: InnoDB
Version: 10
Row_format: Compressed
Rows: 1553544
Avg_row_length: 143
Data_length: 222281728
Max_data_length: 0
Index_length: 121192448
Data_free: 2621440
Auto_increment: 3473533
Create_time: 2013-04-15 16:06:33
Update_time: NULL
Check_time: NULL
Collation: utf8_general_ci
Checksum: NULL
Create_options: row_format=COMPRESSED
Comment: 工单表

但还是不够myisampack后的myisam省空间

But InnoDB Compression is less storage efficient than MyISAM after myisampack.

-rw-rw---- 1 mysql mysql 9.5K Apr 16 09:35 workticket.frm
-rw-rw---- 1 mysql mysql 9.5K Apr 16 09:45 workticket_innodb.frm
-rw-rw---- 1 mysql mysql 336M Apr 16 09:58 workticket_innodb.ibd
-rw-rw---- 1 mysql mysql 199M Apr 16 09:41 workticket.MYD
-rw-rw---- 1 mysql mysql  86M Apr 16 09:44 workticket.MYI
           Name: workticket
         Engine: MyISAM
        Version: 10
     Row_format: Dynamic
           Rows: 1593851
 Avg_row_length: 201
    Data_length: 321325744
Max_data_length: 281474976710655
   Index_length: 130242560
      Data_free: 0
 Auto_increment: 3473533
    Create_time: 2013-04-16 09:35:53
    Update_time: 2013-04-16 09:41:09
     Check_time: 2013-04-16 09:37:03
      Collation: utf8_general_ci
       Checksum: NULL
 Create_options: 
        Comment: 工单表
  • InnoDB Online DDL
mysql> ALTER TABLE `workticket` ADD COLUMN `test_col` INT NOT NULL AFTER sid, LOCK=NONE;
Query OK, 0 rows affected (5 min 25.17 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> set old_alter_table=1;
Query OK, 0 rows affected (0.00 sec)
mysql> ALTER TABLE `workticket` ADD COLUMN `test_col` INT NOT NULL AFTER sid, LOCK=NONE; 
ERROR 1846 (0A000): LOCK=NONE is not supported. Reason: COPY algorithm requires a lock. Try LOCK=SHARED.
mysql> ALTER TABLE `workticket` ADD COLUMN `test_col` INT NOT NULL AFTER sid, LOCK=SHARED;
Query OK, 1593851 rows affected (4 min 11.89 sec)
Records: 1593851  Duplicates: 0  Warnings: 0

虽然总体耗时更长,但DDL过程中不锁表(可query and/or 可DML)还是很吸引的(详细的DDL操作是否可query and/or 可DML可参见文档)。

Although costing more time, that the table can be query and/or execute DML query is very amazing. (Detail can be seen in documentation)

  • InnoDB-Transportable Tablespaces
    没什么可测试的,就是操作成功。用途?建slave?备份?
    Nothing interesting to test. It just works. What can I do with this feature? Maybe building up a slave server? Or backup up the database?

pypy 1.9+mysql_ctypes 0.5+libmysqlclient15 got Segmentation fault on CentOS 5.8 64bit

在一台CentOS 5.8 64bit的机器上使用pypy 1.9, mysql_ctypes 0.5查询数据库出现Segmentation fault。gdb了一下,堆栈都被破坏了。只好另觅他法。

When I use pypy 1.9, mysql_ctypes 0.5, I got a Segmentation fault querying MySQL database. First I try to gdb it, the stack is messed up. Have to find another way out.

想起有另一台机器使用同样程序与库一直正常,一番查找发现差别只在于libmysqlclient.so的版本。正常的机器有多个版本,最高版本是16;而出错的机器最高的是15。将libmysqlclient.so.16复制到出错机器,发现查询正常了。为了库的完整,找了一个libmysqlclient16的rpm安装。

Then I remember that there is another machine running the same version of program and library. Finally I found that the only difference between these two machines is the version of libmysqlclient.so. In the normal machine, there are multiple versions, the largest version is 16. And in the problem machine the largest version is 15. Then I try to copy the libmysqlclient.so.16 to the problem machine, everything is OK. For competence, I found a libmysqlclient16 rpm and install it.

问题解决。

Problem solved.


《游戏反垃圾聊天系统》分享

这是近日做的一个内部分享

html5 slide:

游戏反垃圾聊天系统

slideshare:

游戏反垃圾聊天系统


Nginx中HttpLimitReqModule的burst参数略解

Nginx有个HttpLimitReqModule,可以限制请求的频率,其中有个参数burst在文档http://wiki.nginx.org/HttpLimitReqModule不甚详尽,故读其代码了解之。

源码在src/http/modules/ngx\_http\_limit\_req\_module.c,关于burst的核心代码在这。

//src/http/modules/ngx_http_limit_req_module.c:396
ms = (ngx_msec_int_t) (now - lr->last);

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

if (excess < 0) {
    excess = 0;
}

*ep = excess;

if ((ngx_uint_t) excess > limit->burst) {
    return NGX_BUSY;
}

if (account) {
    lr->excess = excess;
    lr->last = now;
    return NGX_OK;
}

excess初始值是0,假设现在ctx->rate是2000(即2 request/s),这次请求距离上次请求是400ms。

那么excess = 0 – 2000 * 400 / 1000 + 1000 = 200。如果limit->burst是0,那么200 > 0,会返回NGX_BUSY即是503了。

假如burst是1,limit->burst即是1000,那么如果请求是每隔400ms来一个,共需5个才会填满limit->burst(每个请求将会增加200 excess),到第6个才会返回503。

推导出公式,假设设置频率是r request/s,每次请求距离上次请求t ms,设置burst为b,那么返回503的临界请求个数x是
\begin{equation}
x = floor(b * \frac {( 1000 / r )} {( 1000 / r – t )})
\end{equation}


使用并查集完成的一个需求

需求是这样的:有一个文件,每行有两个字段,帐号和IP。

规则:

  1. 同IP登录的帐号归为同一工作室
  2. 有帐号交叉的工作室归为同一工作室。

输出:

表1:工作室编号 帐号,表2:工作室编号 IP

思考:

从规则1可以想到,可以把一个工作室看作一棵树,根节点是一个IP,所有字节点是这个IP登录过的帐号。那么规则2就可以看成,两个树的某个子节点是交叉的,就把两棵树连成一个森林。

而其实可以看成有两个不相交的IP集合(例如刚开始两个IP下面的帐号并无交叉,此时每个IP集合里面只有1个IP),因为某个条件(帐号交叉了),需要把两个IP集合合并,很容易想到是并查集的应用。

具体的做法是:在遍历文件的过程中,生成字典ipdict,key是IP,value是一个set,元素是帐号。同时生成一个字典first_urs_dict,key是帐号,value是这个帐号第一次出现的IP,为什么要这个字典呢?是因为我们只关心登录了两个或以上IP的帐号,当帐号第一次出现时,就把其IP记下,当帐号第二次出现时,看到first_urs_dict存在key,那么这个帐号就是登录了两个IP了,可以把这个IP并到一个集合里了。

而并查集是提供查询某n个元素是否在同一个集合的算法。它只需要定义两个操作find(u)和union(u, v),使用Python描述就是:

root = {}
def find(u):
    if u not in root:
        root[u] = u  #初始化,每个元素的根是它自己
        return u

    if find(u) == u:
        #根是自己,立即返回
        return u
    else:
        _root = find(u)
        root[u] = _root #路径压缩
        return _root


def union(u, v):
    ru = find(u)
    rv = find(v)

    if ru != rv:
        #两个元素的根不同,把它们的并起来
        #做法就是把其中一个根成为另一个根的子节点
        root[rv] = ru

当find(x)和find(y)的结果是相等的,可以说明x和y在同一个集合里面。

至此,把两个IP-URS树合并的关键一步已经解决。到算法结束,同一个森林里面的IP和URS自然属于同一个工作室了。

附上完整的代码:

#!/usr/bin/env python

import os, sys
import time

root = {}
def find(ip):
    if ip not in root:
        root[ip] = ip
        return ip

    rip = root[ip]
    if rip == ip:
        return ip
    else:
        _root = find(rip)
        root[ip] = _root
        return _root

def union(u, v):
    ru = find(u)
    rv = find(v)
    if ru != rv:
        root[fv] = fu

def main():
    ip_dict = {}
    first_urs_dict = {}
    count = 0
    for line in sys.stdin:
        count += 1

        if count % 100000 == 0:
            print >> sys.stderr, count

        urs, ip = line.rstrip('\r\n').split('\t', 1)
        if ip not in ip_dict:
            s = set()
            ip_dict[ip] = s
        else:
            s = ip_dict[ip]

        if urs in first_urs_dict:

            fip = first_urs_dict[urs]
            if fip != ip:
                union(fip, ip)

        else:
            s.add(urs)
            first_urs_dict[urs] = ip

    total_dict = {}

    fname_ip = 'no_ip.txt'
    fname_urs = 'no_urs.txt'
    fip = open(fname_ip, 'w')
    furs = open(fname_urs, 'w')
    no = 0
    for ip, urs_set in ip_dict.iteritems():
        r = find(ip)

        if r not in total_dict:
            total_dict[r] = no
            _no = no
            no += 1
        else:
            _no = total_dict[r]

        print >> fip, "%s\t%s" % ( _no, ip)

        for urs in urs_set:
            print >> furs, "%s\t%s" % (_no, urs)

    fip.close()
    furs.close()



if __name__ == '__main__':
    main()

《Python高级编程》读书笔记:方法解释顺序浅析

Python在2.2引入了New-style object(ref),而且在2.3引入了新的方法解释顺序(Method resolution order,以下简称MRO),新的MRO解决了多继承下的方法解释顺序问题。

考虑如下代码:

class BaseBase:
	def foo(self):
		print 'BaseBase'

class Base1(BaseBase):
	pass

class Base2(BaseBase):
	def foo(self):
		print 'Base2'

class MyClass(Base1, Base2):
	pass

o = MyClass()
o.foo() // prints 'BaseBase'

因为在Old-style object,方法解释顺序是“深度优先且从左往右”,MyClass解释foo方法时,在Base1(左边这路)找到BaseBase,就返回BaseBase的foo方法了。这跟从最近的继承层次开始找的直觉不同。

对于New-style object,引用了C3解释方法:
定义一个列表的头和尾部。对于列表[C1, C2, C3],其头是C1,尾是[C2, C3]。(熟悉函数式编程的同学应该不陌生)

C3方法公式如下:
L[MyClass(Base1, Base2)] = MyClass + merge(L[Base1], L[Base2], Base1, Base2)
其中L为类的线性化继承层次

Merge算法是:
1. 取第一个列表的头(即L[Base1][0]),如果这个头没有出现在任何列表的尾部,就把它加到L[MyClass]中,并从合并中的列表删除;否则查找下一个列表的头,作同样的判断。
2. 如果所有类都被删除,则算法成功完成;如果不能找到符合条件的列表头(好的表头),则失败,Python拒绝创建MyClass类

通过类的__mro__可以看到类的MRO列表

In [13]: MyClass.__mro__
Out[13]: 
(<class '__main__.MyClass'>,
 <class '__main__.Base1'>,
 <class '__main__.Base2'>,
 <class '__main__.BaseBase'>,
 <type 'object'>)

对于很多更复杂的情形,附录文档有更详尽的解释

参考文档:
The Python 2.3 Method Resolution Order


《Python源码剖析》读书笔记:内存垃圾回收

  • Python内存回收的基石是引用计数,“当一个对象的引用被创建或复制时,对象的引用技术加1;当一个对象的引用被销毁时,对象的引用技术减1”,如果对象的引用计数减少为0,将对象的所占用的内存释放。
  • 引用计数的缺点是对循环引用无能为力,优点是将内存释放的操作时机离散化,不会引起瞬间的大波动。
  • Python采用Mark-Sweep算法来解决循环引用问题
  • Mark-Sweep过程
    ** 寻找root object集合,root object指全局引用和函数栈上的引用
    ** 从root object出发,通过其每一个引用到达的所有对象都标记为reachable(垃圾检测)
    ** 将所有非reachable的对象删除(垃圾回收)

  • 垃圾检测只需要跟踪可以保有其他对象引用的container对象(例如list,dict,class,instance等)即可。

  • Python创建container对象时,会在前面加入PyGC_Head。通过PyGC_Head串起来的双向链表把所有container对象串起来。
  • Python的GC有分代机制,分3代。最年轻代到最老代默认个数是700/10/10,当某代里的对象数超过阈值,将会引发一次GC动作。某个对象在一次GC中存活的话,就把它移到更老的一代。
  • 对象的引用计数存在PyGC_Head的ob_refcnt,GC时会使用此值的副本,PyGC_Head的gc.gc_refs
  • 在垃圾检测过程中,会先试探地把所有对象的引用计数减1。遇到一个引用计数为0的对象,先将其标记为GC_TENTATIVELY_UNREACHABLE。如果之后某个对象的遍历过程中遇到这个临时标记的对象,证明它还是有引用的,将其移回reachable列表并且把引用计数设为1。
  • 垃圾检测完成后,所有在unreachable链表的对象都可以释放了,除了那些定义了__del__方法的对象。之前一篇blog也提到,Python不会自动回收这些对象。