Python Object

对象机制

  1. python中对象机制的核心只有两点，p18
  2. 如何理解这个python的“对象核心机制”？
  • 在python中，所有的东西都是对象，而所有的对象都拥有一些相同的内容，p19 图1-1，而这些内容都定义在一个宏之中，p17
  • python创建了任何类型的对象后，在其内部，只会用PyOjbect *来指向，就是*ob_type实现了Python这种对象的多态,p25
  1. 当我们谈论python对象时，要关注两个struct及各自存储的内容（为什么会有如此分离的设计？）
  • 对象本身，保存在“对象类型”的定义中，例如PyIntObject定义了整数对象
  • 对象元信息，保存在对象对应的“类型对象”中，包括的元信息有p31

其实，无论在“交互模式”还是在“.py模式”使用python时，我们无时不刻不是在访问对象及其元信息：

1
2
3
4
#访问的是静态的整数对象的定义PyIntObject中的属性ob_ival
>>>a = 1
#访问的是元信息，即“类型对象”中的属性int_doc
>>>print(a.__doc__)
  1. python中，所有的对象都存活在“系统堆”上

类型对象

  • 每个类型对象其实就是一个PyTypeObject实例
  • 类型对象就是面向对象理论中“类”这个概念的实现

对象的行为

什么叫“对象的行为”？5+6，a[‘key’], b[0], print(10),等等

为什么数值型、序列型和关联型对象有如此不同的行为？由类型对象中三个函数指针所指向的“函数族”的实现情况决定p23

python允许数值型对象拥有关联型对象的行为吗？允许的，从客户端代码的表现形式就是p23 图1-4；从底层实现来看，p24第一段

对象的行为属于对象的“元信息”，由对应的类型对象来定义

类型对象的初始化

为什么python中的“内建类型对象”都是被静态初始化的？意味着它们不在内存的堆栈区，而是在全局区（静态区）p16，所以，类型对象永远不会被析构p27

对象分类

p28 图1-7，书中根据什么把python对象分为这5类（类型对象），是对象行为吗？

对象的静态实现

静态对象定义 类型对象  
PyIntObject PyInt_Type  
     
  1. 为什么像js， python这样的语言，把一切都当成对象呢？连类型都是“类型对象” p15

对象的运行时

当谈论对象运行时，可以从两个维度来看：

  1. 运行时，对象及其类型之间的关系，p25 图1-6
  2. 对象生命周期（尤其是创建和销毁）各个阶段，在内存中的形态及组织形式

对象和类型之间的关系

运行时整数对象及其类型之间的关系，p25 图1-6

对象池

  1. 为什么几乎所有的内建对象，都有自己特有的“对象池机制”？
  • 缓解因采用“引用计数机制”，“系统堆”会面临着对象访问瓶颈——当引用计数减为0时，频繁申请、释放内存空间会使python的执行效率大打折扣，p17 ob_refcnt, p43 惊天隐秘
  • 对象并非独立对象，而是通过一定结构连接在一起的庞大的对象系统
  1. 从两个方面来考虑对象池：

1）新建对象的内存空间从哪里来

2）销毁对象时，空间去哪里

INT对象（定长对象）运行时

运行时整数对象及其类型之间的关系

p25 图1-6

INT对象池

整体内存布局

把两幅图结合起来，就是INT对象池的整体内存布局

  1. p40 图2-6
  2. p43 图2-9

全局指针

int对象池由三个全局指针来维护,small_ints(p36), block_list和free_list（p37），注意这三个指针的数据类型。

PyIntBlock

int对象池的基础结构是PyIntBlock，这个基础结构的构建代码（p36-37,2.2.3）和内存布局（p39图2-4）

在同一个对象池中存在两个单向链表，block_list指向的”block chain”，free_list指向的”空闲PyIntObject对象”链表

基于PyIntBlock，可以回答如下的问题:

  • 是否每新建一个int对象，都要在堆中申请一次size(PyIntObject)空间？不是。当free_list=NULL时，表示对象池中无剩余空间，一次性申请size(PyIntBlock)的空间，创建对象池的代码见p38代码清单2-3
  • 内存中int对象是否是离散存在的？不是。每个int对象都存在于“PyIntBlock链表”的某个PyIntBlock中。
  • 新建的int对象如何利用free_list指向的“空闲内存块单向链表”？如果对象池中存在空闲空间，那么新创建的int对象肯定使用的是free_list指向的那个，这个被使用的空闲空间的ob_type指针转而指向PyInt_Type，以表明这是一个int对象
  • 引用为0的int对象的空间是否被释放？不会释放。从两个方面来考虑这个问题：1）本来申请空间时就不是以size(PyIntObject)为单位申请的；2）这种对象会被对象池回收，即重新链入由free_list指向的“空闲内存块单向链表”中，可以参见p41 int_dealloc()实现，以及p41-42对这个函数的解释。
  • “空闲空间单向列表”是如何形成的？分为两个阶段，1)初始化，见p38-2.2.4.2-函数fill_free_list()；2）当某个int对象的引用计数为0时，见p41 int_dealloc()实现，以及p41-42对这个函数的解释。在整个链接过程中，使用了PyObject中的ob_type指针作为连接指针

小整数和大整数

小整数 大整数
存储于int block chain中 同左
[-5, 257] 其他
在程序初始化时就创建好了 只在需要时才创建
内存中只会存在唯一值的小整数对象，p46图2-13 ob_ival相同的大整数对象使用一次就创建一次， 存于不同的地址，见p45图2-11
永远不会被释放，因为p43 ob_refcnt==0就释放

变长对象

变长对象的实现机制

因为对于变长对象而言，对象维护的数据的长度在对象定义时时不知道的。所以，p48，其机制主要由三个不同部分来共同实现：

  1. 指针，指向变长对象所维护的实际内容的一段内存。在某个具体的“变长对象”中定义，例如，p48,PyStringObject
  2. ob_size, 这段内存的实际长度（字节）。在PyVarObject中定义
  3. tp_itemsize,由变长对象保存的元素的单位长度。在类型对象中定义，例如，PyString_Type中tp_itemsize=sizeof(char),p49

String对象

PyStringObject定义

PyStringObject的定义p48，有两个重要的成员：

  • ob_shash
  • ob_sstate

其对应的类型对象的定义PyString_Type,p49

全局指针和内存池

string对象在运行时有两个全局指针作为内存池在起作用:

  1. interned, p54
  2. characters, p56

内存布局

一个string对象是如何创建出来的？PyString_FromString()，这个函数书中分了两个部分来讲，1) p49-代码清单3-1, 2) p52。

  • 内存中string header和payload是不连续的空间吗？非也，p51图3-1，由图可得，对象header和对象payload是连续的内存空间。
  • 是否每新建一个string对象就申请一次内存空间呢？只要payload的size>1就会申请内存，而无论这个string对象是否在对象池中，p55。然后再进行检查，如果interned dict中存在维护着相同原生字符串的PyStringObject对象，就会释放新申请的堆空间，让对象变量转而指向已经存在于dict中的PyStringObject对象。
  • 所有的string对象是松散的存在于内存中吗？非也，python提供一个interned指向的dict，作为部分PyStringObject对象的内存池，称为“intern机制”。
  • 这个interned dict是怎么缓存PyStringObject对象的呢，是放在dict的value中吗？非也，dict的key和value都是PyStringObject对象的指针，p54图3-2。
  • 哪些string对象可以进入这个dict呢？从p52中创建string对象的后半部分代码可得，只有长度较短的（长度为0或者1）string才能进入和dict缓存。
  • 对一个string对象的intern操作包括哪些动作？p53，代码清单3-2
  • 一个string对象的引用为0后，会销毁其占用的内存空间吗？会的。无论它是否加入了interned dict中。

List对象

PyListObject定义

PyListObject是一个变长、可变对象，这两个特征都要靠定义中的成员属性来体现，p63-64

可变对象的实现机制

ob_item, allocated&ob_size，这三个成员属性相互协作，实现了list对象的可变以及变长的特性。

allocated和ob_size的值有一些微妙的关系，详细讲解见p64-4.1。

在list的生命周期（对象的创建、对list元素进行插值和删除、list对象的销毁）中，这两个属性（allocated和ob_size）的取值有一些相应的联系，可见p75 4.4前半部分的例子。

创建对象

创建对象的代码见p64 代码清单4-1，创建完成后的内存布局见p67 图4-1

  1. 创建一个list对象包括创建list所维护的元素吗？

非也。创建一个list对象包括了两个部分，且其中，元素指针列表都为NULL

  1. list维护的“元素指针列表”和“PyListObject对象本身”是连续的内存空间吗？

非也。从p67 图4-1看的一清二楚。如此设计，也是为了实现list的可变对象属性。

  1. list_a = [1,2,’pyhton’]的实现过程。

应该是经历了两个阶段，1）新建list_a对象(size=4)，2)对list_a进行四次“设置元素”的操作。

  1. 创建list对象时所使用的内存空间来自于对象缓冲池吗？

非也且不全是。首先，从1）list对象内存池的定义p66，以及2）list对象的销毁操作（p74）来看，PyListObject对象缓冲池只是一个“指针数组”而已，先有list对象销毁，才会把其中PyListObject对象本身那一个部分存入缓冲池，也就是说，没有list对象销毁，缓冲池中无内存空间可用；其次，即使从对象缓冲池中获取内存，也只有“PyListObject对象本身”这一部分，而“元素指针列表”部分，还是要重新申请。

对象的销毁和缓冲池

  1. list对象内存池的定义p66

其实，就是一个指针数组

  1. list对象的销毁操作（p74）
  2. 销毁list对象的过程以及哪些内存空间可以进入缓冲池？

销毁list可以分为三步：

1） 销毁list维护的元素，各类型的元素有自己的内存回收方法；

2） 销毁list中ob_item指向的“元素指针数组”所占用的内存空间；

3） PyListObject对象本身占用的内存空间归入缓冲池。

  1. 缓冲池在程序初始化时就申请了内存空间了吗？

非也。list对象的缓冲池本质上就是一个指针数组，在初始化时只是申请了数组相应的全局变量空间。而真正的PyListObject对象空间却是来自于回收的要销毁的list对象的部分内存空间。

insert, append

  1. insert和append操作必然会导致ob_item指向的内存发生变化吗？

不会。是否需要增加ob_item指向的指针数组所占用的空间进行，需要看p69 list_resize()解释。

  1. 如果需要增加内存空间，是否和insert/append的元素个数相同呢？

非也。从p69 list_resize()可见，ob_item指向的指针数组所增加的内存空间会大于实际insert/append的元素个数。具体例子，可见p75-4.4的前半部分。

delete

  1. delete元素后，会减少ob_item指向的指针数组所占用的空间？

不一定，需要看p69 list_resize()解释。

Dict对象

定义

python的dict对象是可变、变长对象。在其struct的定义中肯定要有所体现。

PyDictObject的定义见p79-5.2，内存布局见p81-图5-3。

PyDictObject PyListObject
继承自PyObject，并无ob_size这个属性 继承自PyVarObject
在对象的连续地址空间中有一个长度为8的PyDictEntry数组 元素指针列表和对象自身在不连续的地址空间

引入了新的结构体PyDictEntry，用来存储(k,v)的指针。

所以指向可变部分的指针是PyDictEntry *ma_table

 Pyobject **ob_item
为了支持“散列表”实现的关联时容器，加入了多个属性  

内存池

p96-5.4 PyDictObject的内存池实现和PyListObject几乎一模一样。连填充对象缓冲池的方法都是一样的。

关联式容器的数据结构

关联式容器刻画着某种对应关系，实现关联式容器的数据结构有很多，例如

  • 平衡二元树，
  • python采用的“散列表”, p78

python本质上使用了两种数据结构来实现“散列表”

  1. PyDictEntry, p79-80
  2. PyDictObject(PyDictEntry *ma_table) , p80

无论采取何种方式来实现“关联式容器”，此容器的核心就是“搜索”，即，通过key找到一个位置，进而得到value

关联式容器的搜索算法

理解Dict的搜索

关联式容器的数据结构决定了搜索算法，如何理解Dict的搜索，对于理解Dict本质至关重要。

从使用Dict的方式来理解比较直观。我们对Dict无非是插入，设置和删除操作，操作对象都是dict[key]，而dict[key]必须返回一个Dict数据结构中的一个位置（绝对无可能是NULL），这个位置本身没有好和不好，而是不同的操作赋予了这个位置不同的意义。例如，

  • 同样是返回一个没有被占用的位置，插入就ok，而删除会报错
  • 返回一个被占用的位置，d[1]=1就是设置操作
  • 返回一个没有被占用的位置，d[1]=1就是插入操作

那么，问题来了，什么决定了dict[key]所返回的位置？

散列表算法的关键概念及python实现

散列表算法都是围绕着“从key得到一个位置”，散列表的关键概念如下，p78-5.1

  • 散列函数
  • 散列值
  • 散列冲突
  • 冲突解决算法，有“开链法”，“开放定址法”等
  • 装载率

“散列函数&冲突解决算法”两者合起来才能决定“一个key对应的位置”——如果散列函数计算的结果没有冲突，那么散列值就是位置；否则，就要采取某种“冲突解决算法”来得到其他的候选位置。

那么，判断“散列冲突”的标准是什么，是否可以脱离“冲突解决算法”来单独讨论什么才叫产生了“散列冲突”？从p83-5.3.2的代码来看，不行。

散列函数 将key的(修正过的)hash值和entry的数量做一个与操作
散列值 落在entry的数量之下
散列冲突的判断及解决办法 开放定址法
装载率  

冲突解决算法的关键概念及python实现

开放定址法是python采用的解决散列冲突的方法，p78，算法可以明显的分为三个部分：

  1. 第一次散列计算
  2. 判断是否冲突
  3. 冲突解决

开放定址法中涉及的关键概念：

  • 二次探测函数
  • 冲突探测链
  • 伪删除和entry状态

在开放定址法中，什么才加冲突呢？散列计算（无论是第一次还是冲突解决中的计算）得到的散列值对应的table中的entry

  • 是Active状态，有两种可能性，见p84-[4]，1）可能就是我们要找的位置；2）继续寻找
  • 是Unset状态，就是要找的位置
  • 是Dummy状态，继续寻找，这里要用到一个很重要的变量freeslot

开放定址算法的简化示例 p95-5.3.4，一目了然。

散列冲突的判断 entry状态转换，p80 图5-2
冲突探测链与伪删除
二次探测函数 根据冲突的位置，对key的hash值进行修正，p86 代码清单5-3 [5]
计算候选位置 用修正过的key的hash值带入散列函数得到散列值

变长的实现方式

Dict靠PyDictEntry *ma_table实现了变长，定义见p80,-5.2.2，图例见p81,图5-3

最佳实践

  1. Dict的key最好用string