Python PyObject

本文主要对Python的基本数据类型做简单的介绍

在Python中,对象就是为C中的结构体在堆上申请的一块内存,一般来说,对象是不能被静态初始化的,并且不能再栈空间上生存。

PyObject

在python中,所有东西都是对象,而所欲的对象都拥有一些共性(object.h/PyObject)。
PyObject是整个python对象机制的核心。

1
2
3
typedef struct _object {
PyObject_HEAD
} PyObject;

在release模式下编译python时,PyObject如下:

1
2
3
4
typedef struct _object {
int ob_refcnt; //引用计数
struct _typeobject *ob_type; //类型
} PyObject;

其中,ob_refcnt为int整型,实现了基于引用计数的垃圾收集机制。对于某一对象A,当有一个新的PyObject引用该对象时,A的引用计数应该增加;而当这个PyObject被删除时,A的引用计数应该减少;当A的引用计数减少到0时,A就可以从堆上被删除,以释放出内存供别的对象使用。

引用计数

PyObject中的ob_refcnt是一个32位的整形变量,这实际蕴含着Python所有的一个假设,既对一个对象的引用不会超过一个整形变量的最大值。

整数对象

小整数对象

在python中,所有对象都存活在堆上,python重复地使用malloc申请空间,大大降低了运行效率,造成大量内存碎片,影响整体性能。因此,在python中,对小整数对象使用了对象池技术,用来缓存所有的小整形对象(对重复的对象不需要重复的malloc)。

NSMALLPOSINTS和NSMALLNEGINTS来修改小整数对象池的范围(默认分别为257和-5)。

大整数对象

对于小整数,使用对象池技术完全缓存其PyIntObject对象,而对于其他整数,python提供了一种PyIntBlock结构供大整形对象使用。PyIntBlock是通过维护一块内存(Block)来供大整数使用,并通过单向列表block_list来维护。

Python的设计者为了提高代码执行效率放弃了类型安全使用了宏来代替函数。

当一个PyIntObject对象被销毁时,它所占用的内存并不会被释放,而是继续被python保留着,加入到free_list所维护的自有内存链表,为其他需要创建对象的内存使用。

字符串对象

在python中,PyStringObject是字符串对象的实现,它是一个拥有可变长度内存的对象。

1
2
3
4
5
6
trpdef struct {
PyObject_VAR_HEAD //ob_size字符串长度
long ob_shash; //字符串hash值
int ob_sstate;
char ob_sval[1];
} PyStringObject;

在PyStringObject中,还使用了intern机制和缓存池技术。

###intern机制和缓存池

intern机制的目的:保证被intern之后的字符串在python整个运行期间只对应唯一的一个PyStringObject对象。

intern机制的关键是在系统中有一个(key,value)映射的集合,记录所有被intern机制处理过的PyStringObject对象。当python在创建一个字符串时,会首先在interned中检查是否已经有该字符串对应的PyStringObject对象了,如果有,则不用创建新的,这样可以节省内存空间。其实,Python始终会为字符串创建PyStringObject对象,intern机制是在创建之后才会生效的,通常python在运行时创建一个PyStrhingObject对象temp后,基本就会销毁该对象(引用计数减1)。

类似小整形的缓存池,python为PyStringObject中的一个字节的字符对应的PyStringObject对象设计对象池characters。

Python中的处理顺序:

  • 判断是否为一个字符
  • 创建PyStringObject对象进行intern操作
  • 将intern结果缓存到字符缓冲池中

###PyStringObject效率问题

在Python中”+”操作符进行字符串连接的方法效率极其低下,其根源在于python中的PyStringObject对象是一个不可变对象。这就意味着当进行字符串连接时,实际上必须要创建一个新的PyStringObject对象。因此,如果需要连接N个PyStringObject对象,就必须进行N-1次内存申请及内存搬运工作,严重影响python的执行效率。

官方推荐利用PyStringObject对象的join操作来对存储在list和tuple中一组PyStringObject对象进行连接操作,只需要分配一次内存,执行效率大大提高。

join操作会统计出list中所有PyStringObject对象的字符串长度,然后申请内存。

##列表对象

PyListObject是Python提供的对列表的抽象。它类似于C++中的vector,而不是list。

1
2
3
4
5
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item; //元素首地址
int allocated; //实际申请内存的个数(部分没有被使用,类似于vector)
} PyListObject;

其中,ob_item为指向元素列表的指针。

python所采用的内存管理策略和c++中vector采取的内存管理策略一样,并不是寸多少数据就要申请对应大小的空间,这样内存管理的效率较低,因此,在每一次申请内存时PyListObject总会申请一大块内存,该内存的大小就记录在allocated中,而实际被使用的内存数量记录在ob_size中。

###对象缓存池

在创建一个新的list时,首先创建PyListObject对象,然后创建PyListObject对象所维护的元素列表;在销毁一个List时,首先销毁PyListObject所维护的列表,然后释放掉PyListObject本身,但是在释放之前python会检查缓冲池free_lists,查看其中缓存的PyListObject的数量是佛已经满了,如果没有,就将该数据对象加入到穿存池中,否则删除。

##Dict对象

与map不同,PyDictObject采用散列表(hash table)。在最优情况下,散列表能提供O(1)复杂度的搜索效率。

###散列表

散列表的基本思想是通过一个函数将需搜索的键值映射为一个整数,将这个整数视为索引值访问某片连续性的内存区域。

在使用散列表的过程中,不同的对象经过散列函数的作用,可能被映射为相同的散列值。随着需要存储的数据的增多,这样的冲突就会发生得越来越频繁。散列冲突是散列表不可避免的问题,当散列表的装载率(已使用空间和总空间的比值)大于2/3时,散列冲突发生的概率就会大大增加。

在STL库的hash table采用开链法来解决冲突,而python中采用开放地址法。当产生冲突时,python会通过一个二次探测函数f计算下一个候选位置,如果该候选位置可用,则可将待插入元素放到该位置,否则再次调用探测函数f,寻找可用位置。

###关联容器entry

1
2
3
4
5
typedef struct {
Py_ssize me_hash; //散列值
PyObject *me_key;
PyObject *me_value;
}

在PyDictObject对象生存变化的过程中,其中entry会在不同的状态间转换:Unused、Active和Dummy。

  • Unused:当一个entry的me_key和me_value都是NULL;
  • Active:当entry中存储了一个(key,value)对时;
  • dummy:当entry中存储的(key,value)被删除后,entry的状态不能直接从Active转到unused(伪删除),否则会出现冲突探测链中断。