美文网首页Python笨办法学PythonPython收藏
Python源码剖析笔记4-内建数据类型

Python源码剖析笔记4-内建数据类型

作者: __七把刀__ | 来源:发表于2015-07-15 23:58 被阅读315次

    Python源码剖析笔记4-内建数据类型

    Python内建数据类型包括整数对象PyIntObject,字符串对象PyStringObject,列表对象PyListObject以及字典对象PyDictObject等。整数对象之前已经分析过了,这一篇文章准备分析下余下几个对象,这次在《python源码剖析》中已经写的很详细的部分就不赘述了,主要是总结一些之前看书时疑惑的地方。

    1 整数对象-PyIntObject

    参见 python整数对象

    2 字符串对象-PyStringObject

    2.1 基本定义

    python中的字符串对象PyStringObject,对应的类型对象是PyString_Type。PyStringObject对象的定义如下:

    #define PyObject_VAR_HEAD   \                                                                                                                                 
      Py_ssize_t ob_refcnt;   \
      struct _typeobject *ob_type;  \
      Py_ssize_t ob_size;
      
     
    typedef struct {
        PyObject_VAR_HEAD //对象头
        long ob_shash; //字符串哈希值
        int ob_sstate; //对象状态
        char ob_sval[1]; //字符串内容
    
        /* Invariants:
         *     ob_sval contains space for 'ob_size+1' elements.
         *     ob_sval[ob_size] == 0.
         *     ob_shash is the hash of the string or -1 if not computed yet.
         *     ob_sstate != 0 iff the string object is in stringobject.c's
         *       'interned' dictionary; in this case the two references
         *       from 'interned' to this object are *not counted* in ob_refcnt.
         */
    } PyStringObject;
    

    字符串长度在头部PyObject_VAR_HEAD的ob_size字段中维护,而ob_sval则是指向一段长度为ob_size+1个字节的内存,比如字符串'hello',ob_size=5,而ob_sval长度为6,ob_sval[6] = '\0'。 ob_sstate是字符串状态,标示字符串是否经过intern机制处理。ob_shash是字符串的哈希值,在字典以及字符串比较等多处有用到这个哈希值。

    2.2 字符串interned机制

    当然在字符串对象中一个比较重要的就是intern机制。那么问题来了,什么样的字符串才会interned呢?实验一下先,可以发现如果字符串有空格是不会被interned的,实际上,字符串中的字符必须都是属于"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"才会interned。例子中的hello world因为有空格不在interned字符集中,所以该字符串不会interned。这个是在构建PyCodeObject对象的时候进行的。之前已经分析过,python的py文件需要编译成字节码执行,当然直接执行和import导入模块有所不同,不过都会构建PyCodeObject对象。在构建PyCodeObject对象函数PyCode_New(Objects/codeObject.c文件)中,会执行变量名、常量等字符串的interned操作。

    另外一个需要说明的是,在编译py文件成字节码并保存到pyc文件过程中,字符串对象分为三种情况处理。其一是非interned字符串,比如刚刚说的hello world字符串,对象标识是s。其二是interned字符串,比如hello,对象标识是t。其三是已经interned过的字符串,在pyc中记录的对象标识是R。之所以有R标记的字符串,是为了节省空间,因为它最终只记录一个字符串的偏移位置。比如之前已经有了字符串'hello',则写入标记s以及字符串内容'hello',第二次遇到'hello'时则只是写入标记R以及'hello'在常量元组co_consts中的索引值。这样从pyc内容中构建PyCodeObject对象的时候,根据R标识类型字符串记录的索引得到字符串。

    #测试intern机制test_interned.py
    a = 'hello world'
    b = 'hello'
    
    def test():
        c = 'hello world'
        d = 'hello'
        print c is a  #False,'hello world' 没有interned
        print d is b  #True, 'hello' 已经interned
        
    test()
    

    关于R标记,还要多说一点,我之前看书的时候也有点疑惑什么情况下会用到R标记呢,因为你在一个模块里面对一个字符串多次引用,在PyCodeObject对象的co_consts中还是只会存在一份的。比如下面的代码,显然s和t针对test.py对应的PyCodeObject对象,只会有一个常量'hello',虽然这个字符串会被interned,那么R标记是用在哪里呢?其实是用在另外的PyCodeObject中。比如下面的代码,对应两个PyCodeObject,其中test_stringref.py本身一个,以及函数test对应一个PyCodeObject。编译后得到的pyc文件内容如下所示,根据前面的文章pyc格式分析,可以看到在test_stringref.py本身对应的PyCodeObject中,co_consts为('hello', <code object test at 0x10c130af8, file "str.py"", line 4>, None),这里看到s和t引用的是同一个字符串,这一点通过字节码指令也可以看到。 在pyc中'hello'存储的是标识t以及字符串内容。而函数test对应的PyCodeObject中,对应的co_consts为(None, hello),但是在pyc中对应字符串hello存储的是标记R以及索引0。

    此外,如果直接运行python xxx.py,虽然也会编译成PyCodeObject对象,但是不会生成pyc文件,也不会有R标识类型这些东西了,不过interned机制在运行的时候同样会生效。不同的地方在于,如果是从pyc文件运行会根据R标识类型来将对应字符串指向同一个对象,而如果是直接运行的,则需要通过interned字典来对后面遇到的相同的可以interned字符串对象赋值为interned字符串对象的地址,进行并回收后面遇到的那个字符串。

    单个字符和空字符都会interned,这个可以很简单的验证。

    #测试字符串类型标识 test_stringref.py
    s = 'hello'
    t = 'hello'
    def test():
        k = 'hello'
        
    #test_stringref.py对应的字节码
              0 LOAD_CONST          0 (0)
              3 STORE_NAME          0 (0)
              6 LOAD_CONST          0 (0)
              9 STORE_NAME          1 (1)
             12 LOAD_CONST          1 (1)
             15 MAKE_FUNCTION       0
             18 STORE_NAME          2 (2)
             21 LOAD_CONST          2 (2)
             24 RETURN_VALUE   
       
    #test_stringref.pyc文件
    00000000  03 f3 0d 0a 78 3e 99 55  63 00 00 00 00 00 00 00  |....x>.Uc.......|
    00000010  00 01 00 00 00 40 00 00  00 73 19 00 00 00 64 00  |.....@...s....d.|
    00000020  00 5a 00 00 64 00 00 5a  01 00 64 01 00 84 00 00  |.Z..d..Z..d.....|
    00000030  5a 02 00 64 02 00 53 28  03 00 00 00 74 05 00 00  |Z..d..S(....t...|
    00000040  00 68 65 6c 6c 6f 63 00  00 00 00 01 00 00 00 01  |.helloc.........|
    00000050  00 00 00 43 00 00 00 73  0a 00 00 00 64 01 00 7d  |...C...s....d..}|
    00000060  00 00 64 00 00 53 28 02  00 00 00 4e 52 00 00 00  |..d..S(....NR...|
    00000070  00 28 00 00 00 00 28 01  00 00 00 74 01 00 00 00  |.(....(....t....|
    00000080  6b 28 00 00 00 00 28 00  00 00 00 73 1d 00 00 00  |k(....(....s....|
    00000090  2f 55 73 65 72 73 2f 73  73 6a 2f 50 72 6f 67 2f  |/Users/ssj/Prog/|
    000000a0  70 79 74 68 6f 6e 2f 73  74 72 2e 70 79 74 04 00  |python/str.pyt..|
    000000b0  00 00 74 65 73 74 04 00  00 00 73 02 00 00 00 00  |..test....s.....|
    000000c0  01 4e 28 03 00 00 00 74  01 00 00 00 73 74 01 00  |.N(....t....st..|
    000000d0  00 00 74 52 02 00 00 00  28 00 00 00 00 28 00 00  |..tR....(....(..|
    000000e0  00 00 28 00 00 00 00 73  1d 00 00 00 2f 55 73 65  |..(....s..../Use|
    000000f0  72 73 2f 73 73 6a 2f 50  72 6f 67 2f 70 79 74 68  |rs/ssj/Prog/pyth|
    00000100  6f 6e 2f 73 74 72 2e 70  79 74 08 00 00 00 3c 6d  |on/str.pyt....<m|
    00000110  6f 64 75 6c 65 3e 01 00  00 00 73 04 00 00 00 06  |odule>....s.....|
    00000120  01 06 02                                          |...|
    00000123
    

    2.3 字符串拼接效率问题

    另外一个需要注意的就是字符串拼接的效率问题。如果是简单的 s1+s2+s3这样拼接,那么每次拼接都要分配一次内存,这样需要分配两次内存。而如果通过''.join([s1, s2, s3])来拼接,则只需要分配一次内存,在拼接字符串较多的时候,通过join操作拼接字符串效率会有大幅提高。

    3 列表对象-PyListObject

    Python中的List对象实现有点类似STL中的vector,依托的是数组形式来实现列表。定义如下:

    typedef struct {
        PyObject_VAR_HEAD
        /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
        PyObject **ob_item;
        Py_ssize_t allocated;
    } PyListObject;
    

    可以看到前面跟PyStringObject是一样的头部,其中的ob_size是当前列表元素数目,而allocated是分配的空间大小, ob_size <= allocated,也就是说一般情况下会多分配一点空间,以减少多次分配带来性能问题。列表初始化分为两部分,列表本身结构初始化和列表维护的对象列表ob_item初始化。当然,列表本身初始化也采用了缓冲池机制,如果缓冲池列表中有空闲的列表可以用,就可以直接拿来用而不需要再次分配内存了。当然,虽然列表结构本身可以通过缓冲池复用,但是其中维护的对象列表ob_item是不会复用的,从缓冲池中得到列表结构后还需要给ob_item分配空间(空间大小为 size * sizeof(PyObject *),size为创建的列表大小

    列表分配的空间大小allocated在通过insert,append操作插入元素时或者通过remove, del操作时会进行调整,也就是说即可能变大也可能变小。调整列表大小的函数是list_resize(),调整条件如下:

    (1) newsize <= allocated && newsize >= allocated / 2:简单调整ob_size的值,不需要扩容。
    (2) 否则,调整大小为 new_allocated = (newsize >> 3) + (newsize < 9 ? 3: 6) + newsize.
    

    那么,假定有一个语句如下list = [1],则字节码其实就是创建一个大小为1(ob_size和allocated此时都是1)的列表,然后将列表list中的ob_item的第0个元素设置为整数对象1。需要注意的是,当你创建一个空列表然后直接赋值则会出错的,比如下面那样,这是因为你创建一个空列表时ob_item被设置为NULL,并没有分配内存,因此会报错。

    ##test1.py 未分配对象列表内存导致赋值错误
    list = []
    list[0] = 1 #错误
    

    还是继续刚刚那个栗子,现在有列表list=[1],然后执行list.append(2),此时ob_size=2,而根据上面的策略,allocated调整为5.再执行list.append(3)插入3,则此时ob_size=3,而allocated=5不变。如果接着list.remove(2),则ob_size=2,allocated=5不变。此时如果再执行list.remove(3),则根据上面的调整公式,ob_size=1,allocated减小到4。

    4 字典对象-PyDictObject

    python字典对象采用的散列冲突解决方法为开放定址法,不同于STL中的开链法。python采用的开放定址法在发生散列冲突时,会根据一个冲突探测函数计算下一个探测的位置,直到找到一个不冲突的位置。而在删除元素的时候,并不会直接删除,而是设置一个dummy标记,这样可以保证在冲突探测的时候不出错,此外这个dummy标记的元素下次插入新元素时可以被再次利用。

    字典中的一个键值对称为一个entry,字典由PyDictEntry的数组构成。定义如下:

    typedef struct {
      Py_ssize_t me_hash; //me_key的哈希值
      PyObject *me_key; 
      PyObject *me_value;
    } PyDictEntry;  
    
    #define PyDict_MINSIZE 8 
    typedef struct _dictobject PyDictObject;
    struct _dictobject {
      PyObject_HEAD
      Py_ssize_t ma_fill;  /* # Active + # Dummy */
      Py_ssize_t ma_used;  /* # Active */
      Py_ssize_t ma_mask;
      PyDictEntry *ma_table;
      PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
      PyDictEntry ma_smalltable[PyDict_MINSIZE];
    };
    

    键值对有active, dummy以及unused三个状态。初始为unused状态,me_key == NULL, me_value == NULL。而如果是active状态,则me_key != NULL, me_key != dummy, me_value != NULL,如果是dummy状态,则me_key == dummy, me_value == NULL.三个状态的转换则是:执行插入操作则由unused或者dummy状态变成active状态,执行删除操作则从active状态变成dummy状态。

    PyDictObject定义如上面所示,其中ma_fill是元素总数目,包括active和dummy状态的键值对。而ma_used是active键值对数目,ma_mask用来定位元素在数组中的索引,大小为数组长度减一。如果数组ma_table为8,则ma_mask值为7.注意,这里还有个ma_smalltable,大小初始为8,初始化时,字典的ma_table会指向ma_smalltable,当装载率大于等于2/3时,字典扩容。(即ma_fill / (ma_mask + 1)) >=2/3),会将ma_table指向新分配的空间,并搬移键值对到新的table中。

    PyDictObject也采用了缓冲池机制,其原理类似PyListObject,这里不再赘述。需要额外提到的一点是字典中的元素搜索机制,这里说下常用的lookdict_string函数,其针对的是字符串键的查找。查找流程如下:

    a. 查找的时候会先根据字符串hash值获取键值对索引,如果对应的键值对entry为unused状态,则表示搜索失败,如果freeslot不为NULL,则返回freeslot(freeslot指向dummy状态的entry),否则返回entry。
    b. 如果entry为其他状态,则检查me_key引用是否相同,相同则返回该entry.
    c. 如果me_key引用不同,则检查me_key值是否相同(即比较hash值以及me_key的值),如果相同,则返回entry,否则继续下一轮查询。
    

    python中冲突探测函数如下,其中j为当前的索引,perturb初始化为me_key的hash值,通过不断调整j和perturb值,会不断探测ma_table数组中的元素。由于perturb值是不断减小的,所以最终会退化为j = 5 * j + 1,假定元素数为8,初始j = 0, 使用退化后的探测函数探测到的索引依次是 0, 1, 6, 7, 4, 5, 2, 3, 0。这个探测函数顺序有一定随机性,这其实是通过一个线性同余方程来获取2**i范围内的伪随机数作为索引,比线性探测函数如f(x) = x + 1效果要好一些。其中2**i是哈希表大小。至于为什么 j = (5*j) + 1; j % 2**i;这样能够得到0...2**i-1范围内的数字后再从头开始循环,证明方法暂时没有找到,不过简单验证确实是没有问题的。

     j = (5*j) + 1 + perturb; // perturb初始值为键的hash值
     perturb >>= PERTURB_SHIFT; // PERTURB_SHIFT=5,据说效果比较好
     use j % 2**i as the next table index;
    

    根据这个冲突探测算法,可以看到字典中插入键值对时的冲突探测和解决流程。具体例子参见http://www.laurentluce.com/posts/python-dictionary-implementation/

    相关文章

      网友评论

        本文标题:Python源码剖析笔记4-内建数据类型

        本文链接:https://www.haomeiwen.com/subject/ustpqttx.html