Back to home

快速实现Python C 拓展 - ctypesgen.py

Introduction

运行效率在Python中一直倍受诟病,但是作为[胶水语言],除了具有自身逻辑快速实现能力,还能够很容易将复杂运算抽象到其他平台上去,比如C .

这是由一个 [Probabilistic Counting]问题。在大数据量的情况下,又转化为基数估计问题(见[基数估计算法概览])。
业务层面是需要解决某个站点访问用户总数,这里用Python表示

counting = defaultdict(int)
for site_id, user_id in logs:
    counting[site_id] += 1

pprint(len(counting)) #Total User
pprint(len(counting)) #Users per site

大量的数据情况下,counting自身容量会面临严重考验,假设每项数据在字典中的大小均等(Key: 8 * 38 byte per String , Value: 28 byte per Long),那么在百万项时,关统计就需要 332 * 1000000 / 1024 /1024 bytes = 316 MB,问题是去重免不了维护整个统计记录,捉襟见肘的内存很难维护这么大一个列表,这是难免拆分日志,合并统计,但是其中存储结构等等又是何其繁琐。

在大量数据的情况下,准确度未必会要求地很严格,所以基数估计应运而生。
这里直接给出几个已有的实现,具体原理请翻阅[Reference]。

  • [Stream-lib] Java版本的基数估计实现,提供了Couting,TopN方法的实现
  • [ccard-lib] 参照[Stream-lib]给出的C实现,由淘宝的chaoslawful同学维护,该同学还是另外一个开源项目[nginx-lua]的作者

Python C extension

我的目标平台是Python,对于Java版本的类库就不做考虑了,所以直接拿来[ccard-lib],编译获得动态链接库后,开始编写Python拓展。

关于Python拓展,isnowfy同学有一个简易的介绍
这里我就地使用[ctypes]实现,这里有一篇很好的教程([ctypes tutorial])。

声明

为了建立Python接口和C接口的联系,我们需要再次定义C中*.h文件里的声明。

from ctypes import *

class Ctx(Structure):
    _fields_ = [
        ("err", c_int),
        ("k", c_int8),
        ("m", c_int32),
        ("Ca", c_double),
        ("Rsum", c_int32),
        ("b_e", c_int32),
        ("hf", c_int8),
        ("M", c_int8*1),
    ]

f = 'libccard-lib.0.1.dylib'
cdll.LoadLibrary(f)
api = CDLL(f)
api.adp_cnt_init.argtypes = [c_void_p, c_uint32, c_uint8]
api.adp_cnt_init.restype = Ctx

我定义这些后,运行api.adp_cnt_init(None, 16, 1),获得了一个Ctx对象,但是在余下的接口声明,以及人肉切换C类型和Python类型的工作中,让我抓狂,其中调试时的段错误,更是添油加醋。

作为懒惰的本能,这种机械工作应该都会有自动mapping的工具,在PYPI中找到了今天的主角[ctypesgen]。

ctypesgen

安装简单,直接通过Pip

pip-2.7 install ctypesgen

然后通过它生成ctypes映射文件

$ ctypesgen.py -a -l libccard-lib.0.1.dylib -i include/*.h -o ccard_head.py

接下来就可以通过和ccard C库一样名称的API使用ccard-lib

import random
from ccard_head import *
ctx = adp_cnt_init(None, 16, CCARD_HASH_MURMUR)
for i in xrange(500000):
    ci = c_int(i)
    rs = adp_cnt_offer(ctx, byref(ci), sizeof(ci))

esti = adp_cnt_card(ctx)
print esti # Target Count

但是作为一个类库,这样的API显然是不达标的,所以需要加一层封装,使之变得友好。

Conclusion

ctypes的优势是作为内置库,无需安装第三方拓展,但这里有个前提,我们是针对需要编译后的链接库进行封装,所以这个“无需安装第三方拓展”也仅仅是针对Python包装而言,如果真的应用在项目里,必然涉及编译。

另外对比Python C Extensionctypes的包装开销也不得不考虑,在ctype performance benchmark中给出一个评测结果,ctypes拓展的时间开销是Python C Exetension的2~3倍。
这在一些效率敏感的地方是致命的,不过对于快速实现,或者较少的交互调用(ctypes的主要开销,来自C对象和Python对象的转换),ctypesctypesgen不失为一种便捷选择。

如果你想快速实现,Python已经提供了原生实现的基数估计包[hyperloglog(http://pypi.python.org/pypi/hyperloglog/0.0.2),可以直接通过PIP进行安装。
经本机测试,[hyperloglog]的时间开销比ctypes包装的[ccard-lib]多2~3倍。

Reference