楔子


我们知道可以通过使用C语言编写动态链接库的方式来给python加速，但是方式是通过ctypes来加载，通过类CDLL将动态链接库加载进来得到一个对象之后，通过这个对象来调用动态链接库里面的函数。那么问题来了，我们可不可以使用C语言为python编写模块呢？然后在使用的时候不使用ctypes加载动态库的方式，而是通过python的关键字import进行加载。


答案是可以的，我们知道可以通过编写py文件的方式来得到一个模块，那么也可以使用C语言来编写C源文件，然后再通过python解释器进行编译得到import可以直接导入的模块，这样的模块我们称之为扩展模块。在Windows上文件后缀为pyd(等价于dll)，在linux上还是so文件，只不过此时的dll或者so，不再是通过ctypes进行加载了，而是python的import语法可以直接识别，然后调用。


到这里估计很多人已经明白了，C语言在编写原文件之后，是需要python解释器进行编译的，然后才能得到扩展模块。这一过程就决定了在编写C的代码的时候，是需要遵循一定的标准的，只有这样python才能正确得到扩展模块。所以我们在介绍如何使用C编写扩展模块之前，还需要一些python源码的知识。


python中的对象在C语言中的实现


估计用python比较长的人都知道，python中的对象在C中都是一个PyObject(一切皆对象)，事实上确实如此，我们下面来看一下python中的对象在C语言中都分别长什么样子。


首先python中的对象本质上就是C语言中的malloc函数为结构体实例在堆区申请的一块内存。python中对象在C中是遵循一定标准的，如果是实例对象，那么都是Py...Object，如果是类对象，那么都是Py..._Type。这些对象底层都是一个结构体或者结构体指针，并且对应的结构体都嵌套了PyObject这个结构体，我们后面会说。



  • int(): 一个PyLongObject结构体实例的指针, int: 一个PyTypeObject结构体实例(PyLong_Type)

  • str(): 一个PyUnicodeObject结构体实例的指针, str: 一个PyTypeObject结构体实例(PyUnicode_Type)

  • tuple(): 一个PyTupleObject结构体实例的指针, tuple: 一个PyTypeObject结构体实例(PyTuple_Type)

  • list(): 一个PyListObject结构体实例的指针, list: 一个PyTypeObject结构体实例(PyList_Type)

  • dict(): 一个PyDictObject结构体实例的指针, dict: 一个PyTypeObject结构体实例(PyDict_Type)

  • set(): 一个PySetObject结构体实例的指针, set: 一个PyTypeObject结构体实例(PySet_Type)

  • object(): 一个PyBaseObject结构体实例的指针, object: 一个PyTypeObject结构体实例(PyBaseObject_Type)

  • type(): 一个PyTypeObject结构体实例(PyType_Type), type: 一个PyTypeObject结构体实例(PyType_Type)

神秘的PyObjet


我们看到这些类型都非常固定，至于int和str，在python2中是PyIntObject和PyStrObject，但是在python3中改成了PyLongObject和PyUnicodeObject。刚才我们说python一切皆对象，类也是一个对象，它们都嵌套了PyObject这个结构体。下面我们看看这个结构体长什么样子：

我们看到这个结构体里面有两个字段，一个是ob_refcnt，一个是ob_type。ob_refcnt表示对象的引用计数，有多少个变量在引用它，Py_ssize_t可以看成是有符号的long long，当然还有一个Py_size_t表示无符号的long long。从这里我们可以知道，python中一个对象的引用计数不能超过Py_ssize_t的存储范围，不过如果不是吃饱了撑的写恶意代码，是不可能超过这个范围的；而ob_type表示对象的类型，就是我们在python中通过type函数、或者__class__得到的结果，我们看到这是一个结构体指针，从定义上来看，我们可以得出，python中内建的类对象在底层都是一个struct _typeobject。

或者是一个PyTypeObject，当然这个结构体里面也嵌套了PyObject，类对象也有引用计数和类型(我们知道是type)，只不过像int、str、dict这些类对象的引用计数我们不关心，这是python解释器初始化的时候内部就创建好了的，我们只关心根据类对象创建出来的实例对象。因此目前我们可以得到如下结论：



  • int()、str()、list()等等实例对象，底层都是不同的结构体实例。

  • int、str、list等等类对象，底层都是同一个结构体(PyTypeObject)实例

  • 无论是类对象还是实例对象，底层对应的结构体都嵌套了PyObject，都有引用计数、以及类型。

PyVarObject


我们说像str、tuple、list之类的实例对象，它们有一个共同的特点，就是它们都具有长度的概念，都可以使用len方法计算长度。这些实例对象可以看成是一个容器，里面可以容纳元素。因此像这样的对象，我们称之为变长对象，那么在底层就还需要一个变量，来专门维护变长对象的长度。而这个维护长度的变量和PyObject组合起来就是PyVarObject。而python中的对象大部分都是变长对象，所以我们说底层对应的结构体都嵌套了PyObject，也可以说大部分都嵌套了PyVarObject。

我们看到PyVarObject多了一个ob_size来维护变长对象的长度，另外先剧透一下，这个ob_size还具有其它的意义。比如int对象，我们知道python里面一个整型是没有len方法的，但是不好意思，在底层整型(PyLongObject)也是一个变长对象，而且这个ob_size在PyLongObject中还可以小于0，所以类型是Py_ssize_t，而不是Py_size_t。至于细节如何，我们介绍int实例对象(PyLongObject)的时候再说。


PyObject_HEAD和PyObject_VAR_HEAD


在C语言中有着一个宏的概念，其实就是简单的字符串的替换，为了书写方便。那么python针对PyObject实例和PyVarObject实例分别提供了一个宏。

我们看到PyObject_HEAD就是一个PyObject实例，PyObject_VAR_HEAD是一个PyVarObject实例，实例的名字都叫ob_base。另外在C中，一个Py_ssize_t占8个字节，一个指针也占8个字节，所以一个变长对象的大小至少占24个字节，至于具体占多少，则由其它的结构体成员决定了。


PyLongObject解密


整数算是最简单的对象了，我们就从它来"开刀"，既然要分析，那么是不是首先得知道长什么样子呢？


底层存储

我们看到PyLongObject是一个变长对象，关键里面还有一个ob_digit，这是一个digit(占四个字节的unsigned int)类型的数组，而ob_size维护的显然是这个数组的长度。很明显这个ob_digit就是存储整型具体的数值的，里面不一定只有一个元素，具体多少由整型的数值大小决定。


但是为什么要用数组呢？其实在python2中，用的就是一个long来存储的，当然那时候结构体名字还叫PyIntObject，而且也不是一个变长对象(PyVarObject)，而是一个定长对象(PyObject)。但是在python3中，它变成了数组，因为C中整型是有存储范围的，那么python的做法就是你一个数字存不下，我多用几个不就行啦，根据数值大小决定具体用多少个，用了多少个数组的长度就是多少。


我们说digit是一个unsigned int，总共32位，那么一个digit能表示的最大范围就是2 ** 32 - 1，如果我超过了这个范围呢？那就再来一个digit，存不下的位就用新的digit来存。而python的底层就是这么存储的，只是有一点和我们说的不一样，那就是一个digit有32位，但是python只用30位，这么做是为了保证计算的时候方便。


不过还有一个问题，我们说digit是无符号的，如果表示负数怎么办？还记得之前说的ob_size吗？这为老铁除了能表示这个数组用了几个元素之外，还能表示这个整型的正负，如果ob_size为正，说明这个整型为正，反之亦然，所以更准确的说：对于PyLongObject而言，ob_size的绝对值表示数组的元素个数。因此如果存在两个互为相反数的整型，那么它们对应PyLongObject的ob_digit完全一样、而ob_size互为相反数，很好理解吧。如果不好理解，我们来就画图来分析一下，整型的底层存储。


整数0


注意，当要表示的整数为0时，ob_digit这个数组为空，不存储任何值，ob_size为0，表示这个整数的值为0，这是一种特殊情况。



整数1


当存储的值为1的时候，可以看到ob_size变成了1，表示ob_digit这个数组里面只有一个元素。



整数-1


当存储的值为负数的时候，ob_size为-1，说明ob_size除了能表示对象的个数，对于PyLongObject来说，还可以表示值的正负。



整数(1 << 30) - 1


30位，表示可以存储的最大数字是(1<<30)-1



整数1 << 30


注意啦，我们说一个digit只用30位，能存储的最大数值为(1 << 30) - 1，现在超过了，那么肯定还需要一个digit



此时我想你应该明白了python中int对象在底层是如何存储的了。


既然弄清了底层存储，那么我相信对于python中的任何一个整型，你都能知道它占多少个字节。


我们说一个PyLongObject是一个变长对象，PyVarObject使得它至少占24个字节，那么具体占多少个字节就由ob_digit数组的元素个数决定了。假设有n个，那么这个整型的大小就是24 + 4 * n，很好理解。

比较大小


我们再来看看两个整数是怎么比较大小的。

所以我们看到，python底层数值的比较还是比较复杂的，当然这是由PyLongObject的存储结构所决定的，不过仔细分析的话，发现python的底层并不是那么让人望而生畏。


至于四则运算以及其它的运算，有兴趣的话可以自己杀进源码(Object/longobject.c)中查看，我们这里主要介绍最核心的东西，至于支持的API(比如四则运算、位运算)、缓存机制(比如这里的小整数对象池)等等、这些python提供的功能性的东西我们就不看了，我们只看一些存储结构、底层实现之类的。


创建PyLongObject


我们如何创建一个PyLongObject对象呢？首先在python中，我们怎么创建一个int对象？我们可以直接创建、或者使用int函数将别的类型的对象进行转化。


在底层也是如此，直接创建可以通过_PyLong_New，并且还可以通过其他对象进行转化。




  • 直接创建：_PyLong_New


  • 根据long来创建：PyLong_FromLong

  • 根据double来创建：PyLong_FromDouble

  • 根据char *来创建：PyLong_FromString


  • 根据python中的字符串来创建：PyLong_FromUnicode


PyUnicodeObject解密


python中的str在底层的存储比较复杂，因为我们知道在python3中默认都是unicode。


底层存储

我们看到结构体的定义很复杂，但是只要抓住核心即可。我们看到里面存在着三种unicode编码，分别是latin1、ucs2、ucs4，这三者编码的字符一个分别占1、2、4字节，所以python会根据不同的字符串选择不同的编码。关于介绍怎么选择编码之前，我们先来抛出一个问题。首先我们知道python支持通过索引查找一个字符串中指定位置的字符，而且python中默认是以字符的个数为单位的，比如s[2]搜索的就是字符串s中的第3个字符。


那么问题来了，我们知道python中通过索引查找字符串的指定字符，时间复杂度为O(1)。那么python是怎么通过索引、比如这里的s[2]，一下子就跳到第3个字符呢？显然是通过指针的偏移，用索引乘上每个字符占的大小，只有这样才能在定位到指定字符的同时保证时间复杂度为O(1)，但是这就需要一个前提：那么就是字符串中每个字符所占的大小必须是相同的，否则如果每个字符占的大小不同，只能通过扫描逐个字符，这样的话时间复杂度肯定不是O(1)，而是O(n)。


所以这上面有3个编码，编码的字符每一个分别是1、2、4字节。因此python在创建字符串的时候，会先扫描。或者尝试使用占字节数最少的latin1编码存储，但是范围肯定有限。如果发现了存储不下的字符，只能改变编码，使用ucs2，继续扫描。但是又发现了新的字符，这个字符ucs2也无法存储，因为两个字节最多存储65535个不同的字符，所以会再次改变编码，使用ucs4存储。ucs4占四个字节，肯定能存下了。


一旦改变编码，字符串中的所有字符都会使用同样的编码。比如这个字符串："hello古明地觉"，肯定都会使用ucs2，不存在说"hello"使用latin1，"古明地觉"使用ucs2，一个字符串只能有一个编码。所以尽管python明面上是可变长的utf-8，但那是在encode成字节的时候。对于python中的字符串unicode，所有的部分都是使用同一个编码。


另外关于字符串PyUnicodeObject所占的大小，我们说如果编码是latin1，那么这个结构体实例额外的部分会占49个字节，编码是ucs2，占74个字节，编码是ucs4，占76个字节。然后字符串所占的字节数就等于：额外的部分 + 字符个数 * 单个字符所占的字节

除此之外，我们再举一个例子更形象地证明这个现象。

因此，python面对不同的字符会采用不同的编码。需要注意的是，python中的每一个str都需要额外的占用49-76字节，因为要存储一些额外信息，比如：哈希、长度、字节长度、编码类型等等。这也是为什么一个空字符串要占49个字节。


如果字符串中的所有字符都在ASCII范围内，则使用1字节latin1对其进行编码。基本上，latin1能表示前256个Unicode字符。它支持多种拉丁语，如英语、瑞典语、意大利语、挪威语。但是它们不能存储非拉丁语言，比如汉语、日语、希伯来语、西里尔语。这是因为它们的代码点(数字索引)定义在1字节(0-255)范围之外。


大多数流行的自然语言都可以采用2字节(UCS2)编码。当字符串包含特殊符号、emoji或稀有语言时，使用4字节(UCS4)编码。Unicode标准有将近300个块(范围)。你可以在0XFFFF块之后找到4字节块。假设我们有一个10G的ASCII文本，我们想把它加载到内存中，但如果我们在文本中插入一个表情符号，那么字符串的大小将增加4倍。这是一个巨大的差异，你可能会在实践当中遇到，比如处理NLP问题。

为什么python底层存储字符串不使用utf-8


最著名和流行的Unicode编码都是utf-8，但是python不在内部使用它。至于原因我们上面已经解释的很清楚了：


当一个字符串使用utf-8编码存储时，根据它所表示的字符，每个字符使用1-4个字节进行编码。这是一种存储效率很高的编码，但是它有一个明显的缺点。由于每个字符的字节长度可能不同，因此就导致无法按照索引瞬间定位到单个字符，只能通过逐个扫描字符的方法。因此要对使用utf-8编码的字符串执行一个简单的操作，比如string[5]，就意味着python需要扫描每一个字符，直到找到需要的字符，这样效率是很低的。但如果是固定长度的编码就没有这样的问题，python只需要将索引乘上一个字符所占的长度(1、2或者4)，就可以瞬间定位到某一个字符。所以当Latin 1存储的"hello"，在和"憨"这个汉字组合之后，整体每一个字符都会向大的方向扩展、变成了2字节。这样定位字符的时候，只需要将索引成上2即可。但如果原来的"hello"还是一个字节、而汉字是2字节，那么只通过索引是不可能定位到准确字符的，因为不同类型字符的编码不同，必须要扫描整个字符串才可以。但是扫描字符串，效率又比较低。所以python内部才会使用这个方法，而不是使用utf-8。


创建PyUnicodeObject


创建一个PyUnicodeObject，常用方式如下：



  • 直接创建：PyUnicode_New。我们说Py..._New这种创建对象的方式很常见，但是对于int和str来说，还是通过Py..._From...这种形式比较常见。

  • 根据ascii字符创建：PyUnicode_FromASCII

  • 根据char *创建：PyUnicode_FromString

  • 根据unicode创建：PyUnicode_FromUnicode

  • 当然还可以根据其他对象创建，PyUnicode_FromWideChar根据宽字符、PyUnicode_FromObject根据对象创建等等

PyUnicodeObject的效率问题


我们说python中的对象除了定长对象和变长对象之外，还可以分为可变(mutable)对象和不可变(immutable)对象。对于可变对象，它维护的是值是可以动态改变的，但是对于不可变对象，如果想改变只能创建新的对象。


比如字符串的拼接，我们知道可以使用+将两个字符串拼接起来，但是这种做法的效率确是非常低下的。因为PyUnicodeObject是一个不可变对象，这就意味着当两个PyUnicodeObject相加时，必须要创建新的PyUnicodeObject对象，维护的字符串是之前的两个对象维护的字符串的拼接。每两个PyUnicodeObject相加就要创建一个新的，那如果n个PyUnicodeObject相加，就意味着除了本来的n个之外还要创建n-1个PyUnicodeObject对象，而且创建了还需要销毁。毫无疑问，这极大地影响了python的效率。


官方推荐的做法是，将n个PyUnicodeObject对象放在list或者tuple中，然后使用PyUnicodeObject的join操作，这样的话只需要分配一次内存，执行效率大大提高。我们来看看底层是如何实现的。


如果是相加的话

如果采用join的方式


join的话代码比较长，这里就不贴了，但是逻辑不难。就是获取列表或者元组里面的每一个PyUnicode的ob_size、也就是长度，然后加在一起，一次性申请对应的空间，然后再逐一进行拷贝。所以拷贝是避免不了的，+这种方式导致低效率的主要原因就在于大量PyUnicodeObject的创建和销毁。


因此如果我们要拼接大量的PyUnicodeObject，那么使用join列表的方式；如果数量不多，还是可以使用+的，毕竟维护一个列表也是需要资源的。使用join的方式，只有在PyUnicodeObject的数量非常多的时候，优势才会凸显出来。


PyListObject解密


当看到python中的list的时候，我的内心是惊奇的。我们知道python中的list对象是一个大仓库，什么都可以往里面装，里面的类型没有任何要求。于是这就产生了一个问题，我们知道列表也是支持通过索引查找指定位置的元素的，并且时间复杂度是O(1)，可是类型不同、占的字节大小也不同，那么它是怎么保证时间复杂度是O(1)的。


我们知道字符串是通过保证所以字符都具有相同的字节做到的，那么列表呢？我们先带着这些疑问，因为在分析列表之前，我们需要一些其它前置的知识，有了这些知识才能更好的理解列表，并且这些知识也会让你对python有一个更加高度的认识。


python中的变量存储与命名空间


我们知道a = 3这句代码表示创建了一个变量a，a的值为3。并且python和其他静态语言不同，python中是先有值再有变量，a = 3，表示先创建一个PyLongObject对象，这个对象里面的ob_digit数组维护的值是3，有了这个结构体 之后，再让a这个符号指向这个结构体。所以说python中的变量实际上相当于一个便利贴，可以贴在任何地方，至于类型就是对应结构体对象里面的ob_type。因此尽管我们创建变量的时候不需要声明类型，但它实际上是强类型语言，类型是根据python解释器根据创建的结构体对象推断出来的。如果创建的结构体是PyLongObject，那么ob_type就是PyLong_Type。如果此时我们再写上a = "satori"，就表示创建一个PyUnicodeObject，然后让a指向这个新创建的PyUnicodeObject，至于原来PyLongObject，则会因为引用计数变为0，而被回收。


那么问题来了，我们创建的变量a它存在什么地方呢？并且我们在使用a的时候，它是怎么找到a的呢？这里就引入了一个概念：命名空间。


命名空间，就是python用来存储变量以及查找变量的地方，它的底层是一个PyDictObject对象，也就是一个字典。a = 3就表示在命名空间里面添加一个键值对叫"a": 3，我们在使用a这个变量的时候，会从对应的命名空间那到key等于"a"所对应的value。


像函数、类、模块都有自己的命名空间，我们说对于一个普通的函数来讲，内部变量的查找会从本地作用域、全局作用域、内置作用域里面查找，这个本地作用域就是local命名空间、全局作用域就是global命名空间、内置作用域就是builtins命名空间，因此我们python中对于一个普通函数来讲，变量的查找遵循LGB规则。


对于函数来讲，它的local命名空间显然就是函数的局部作用域，但是global命名空间则是外层模块的全局命名空间。这里稍微扯远一点，python在执行函数的时候，会将其编译成PyFunctionObject对象，于此同时会将外层模块的全局命名空间传递到这个PyFunctionObject对象里面去，只有这样函数内部找不到对应的变量的时候，才会找我们在外部定义的变量。不过对于外层模块来讲，它的local空间和global空间显然是一样的，所以此时就不存在所谓本地和全局。但是对于函数来讲，它local空间和global空间显然是不一样的。这些我们后面还会介绍：

我们再来看看函数，我们说python如果看到了def关键字，那么知道这是一个函数，底层会编译成PyFunctionObject，同时会把global空间传进去，那么此时在函数内部就能访问外部的变量。

因此此时我想你应该明白python中的变量是怎么存储的了，核心就在于命名空间。变量=值，这种形式就等价于在对应的命名空间设置了 "变量": 值这么一个键值对，查找变量的时候，也就相当于在命名空间中查找key为"变量"对应的值。所以我们看到python中变量的存储是依赖于字典的，像类、实例对象、模块等等都有自己的属性字典。比如一个类的实例对象ins,我们通过ins.attr = "xx"设置属性，就等价于ins.__dict__["attr"] = "xx"，而ins.attr则等价于ins.__dict__["attr"]。所以字典在python内部是一个高度优化的数据结构，不仅仅是我们在使用，python的内部也在大量的使用这种数据结构。


另外我们说，函数内部的global空间和外层模块的global空间是一样的，其实很好理解，python为了保证函数内部找不到变量的时候能够去外部找，那么就必须要把global空间交给函数，不管这个函数嵌套了多少层。

我们看到每创建一个函数都会编译成PyFunctionObject对象，都会把global空间传进去。至于函数的local空间我们后面会详细介绍，其实global空间没啥难的，就是外层模块的global空间，但是函数的local空间显然就是自己独立的了，在函数内部使用locals()获取的就是函数内部的local空间，并且变量会先从local空间查找，这一方面我们后面会细说。


了解python中变量的存储以及命名空间之后，我们再来看看变量的传递，这是理解python中列表时间复杂度为O(1)的关键。


python中的变量传递


我们说python是引用传递，a = 1; b = a就表示将a的引用传递b，让b指向了a所指向的内存。但是有一点我比较好奇，传递引用，这个引用到底是个什么东西，指针吗？还是其他的什么东西，能不能更好量化、或者描述呢。我们还是先通过命名空间来解释这一过程：

我们知道a = 1，表示将"a": 1放到了命名空间里面，那么b = a毫无疑问肯定是把a对应的值交给b，组合成"b": 1塞到命名空间里面，我们还可以看看字节码：

LOAD_CONST表示加载一个常量1，STORE_NAME表示使用a这个变量存储起来，放到命名空间中；LOAD_NAME表示从命名空间中加载一个变量，相当于拿到变量对应的值，然后再STORE_NAME用变量b存储起来。所以我们看到LOAD_CONST表示加载常量，LOAD_NAME则表示加载变量对应的值，因此两者本质是类似的，最终都表示找1这个PyLongObject。那么函数呢？我们说函数的传递和变量的赋值本质是一样的：

正所谓bug不断，一生三、三生万物，我们的问题也是会不断地涌现。我们目前的分析看似拨开了python中变量传递的迷雾，但是如果仔细推敲的话会发现隐藏着一个致命的问题，当然这并不是我们的问题，我们当前的分析每一步都是正确的。只是说有一个点没有得到解决，那就是变量传递、函数参数传递到底传递的什么？这个问题我们之前就抛出来了，我们刚才是通过命名空间来解释的，那么就用命名空间的方式将问题再次转换一下，LOAD_NAME加载这一过程本质是什么？我们说b = a，表示先通过LOAD_NAME将a对应的值加载进来，然后STORE_NAME交给b，那么这个load加载过程是什么样子的，难道是将值拷贝一份吗？答案确实如此。我们先来看看C和golang：

我们看到对于C和golang来说，就是将1这个值拷贝了一份，那么python呢？

惊了，两者的id是一样的，因为按照我们之前的理解，知道python是引用传递，a和b指向的对象是一样的。可你不是又说python的load是把值拷贝一份吗？咋又变了？难道是因为小整数对象池，答案不是的，如果把a = 1换成其它的大整数，得到两个id还是一样的。b = a这个过程确确实实是把a对应的值拷贝了一份赋值给b，但为什么a和b的id一样，应该不一样啊。而且我们知道小整数是预先定义好的，只有一份，可按照当前这个逻辑，1这个小整数就应该变成两份啊。所以基于以上，我们就引出了下一个要分析的东西，也就是python中变量的本质，python中变量到底是什么？


python中变量的本质


python中变量的本质？变量不就是一个符号嘛，一个名字而已。a = 1，那么变量a就是一个整型，a = "xxx"，那么变量a就是一个字符串，不就是这样吗？


其实上面说的不是很准确，a = 1，我们知道底层就是一个PyLongObject，但是这个a存储的并不是这个PyLongObject本身，而是它的指针。是的，python中所有的变量对应的都不是值本身，而是这个值的指针、或者说是内存地址。a = 1，我们知道在命名空间中会存在"a": 1这么个键值对，那么在底层符号a就应该对应一个PyLongObject，但是实际上a对应并不是PyLongObject，而是它的内存地址。无论是整型、还是字符串、元组、列表、字典等，只要变量 = 值这种形式，那么这个变量本身存储的并不是值本身，而是这个值的内存地址。


在python中传递就是传递一个指针，a = 1; b = a，确实是把a的值拷贝了一份传递给了b，但是a它是一个指针啊，所以等于把指针拷贝了一份给了b，这个是b存储的也是一个地址、一个指向存储的值为1这块的内存的地址。然后在python中，如果操作一个变量，那么会自动操作这个变量存储的地址所指向的值。


因此id(a)表示获取a的内存地址，更准确的说是获取a指向的内存的内存地址。因为a本身就是一个地址，所以我们发现id(a)获取的就是a本身，只不过虽然变量a在底层存储的是一个地址，在python的层面上它代表的就是这个地址所指向的值。a既然存储了一个地址，但是a本身是不是也有一个地址，对的这在C中就是二级指针，只不过我们在python中看不到，最多只能看到一级指针。所以a在底层是一个指针变量，存储了一个地址，如果a = "xxx"的话，那么a存储的指针就指向了一个内部的值为"xxx"的PyUnicodeObject，要是再来b = a的话，那么把a的值拷贝一份(没错是把a的值拷贝一份，不是a的地址，因为a本身就是个地址，或者说把a指向的值的地址拷贝一份也可以，当然此时就是a本身)，赋值给b，此时b也存储的地址也是指向了"xxx"这个PyUnicodeObject结构体。所以id(a)和id(b)是一样的，因为a和b存储的地址是一样的，不过虽然存储的地址一样、但是这两个变量本身的地址肯定是不一样的，因为是两个不同的变量，只是存储的地址一样罢了，所以在python中我们说a和b两者本身也是没有关系的，只是它们指向了同一个值。所以还是那句话，在python中一切变量都是指针，只是在操作指针的时候会自动操作指针所指向的内存。


所以我们说python中变量的传递是引用传递，但是又说b = a会把a的值拷贝一份给b，而这两者又是不矛盾的。就是因为a存储的值并不是对象本身，而是对象的内存地址。传递的时候会拷贝指针，但是在操作这个变量的时候会自动操作指针指向的内存。因此我们知道了python中的变量在C的层面实际上就是一个指针，只是在python的层面上我们理解为值，因为操作会自动操作指向的内存。


所以我们说id(a)是获取a的内存地址这句话真要从底层抠起来，实际上不准确的，因为在底层a本身就是个地址，id(a)获取的是a本身才对。只不过在python中，操作a实际上操作的是a指向的内存，那么id(a)获取的是a指向的内存的地址，在结果上这不就是a本身吗？当然虽然底层是这样，但是在python的层面上，变量就代表值，尽管底层它存储的是指针。因此我们可以得出以下三点结论：



  • python中的变量存储的不是值本身， 值存储在堆区，变量存储实际是值的地址。每当有一个变量指向它，这个值内部的ob_refcnt就会自增1，当变量被销毁、或者指向了其它对象，那么ob_refcnt自减1，当ob_refcnt为0，这个值就会被销毁。

  • python中的变量在传递的时候等价于把变量对应的值(指针)拷贝一份，赋值给另一个变量。但是在python的层面变量就代表值，那么我们说把变量对应的值拷贝一份容易产生误解，尽管它存储的是指针、并且从底层分析我们知道这是正确的，但是为了避免歧义，我们也可以说成把变量指向的值的地址拷贝一份，这样说也是可以的。

  • python中的变量虽然存储的是地址，传递的时候也是拷贝地址，但是在操作该变量的时候、则是操作其指向的内存。

像我们在命名空间看到{"a": 1, "b": 1}，实际底层存储也不是1这个PyLongObject，而是PyLongObject的指针，但是正如我们说的，虽然存储的是指针，但是在操作的时候操作的是指向的内存，所以空间里面显示的是1这个PyLongObject。


我们看一下源码吧，比如两个整型a和b，我们知道这是两个PyLongObject对象，a + b会调用long_add方法。

函数的local空间


我们说对于global空间，python底层是通过字典来存储和查找的。但是对于函数，我们说python是通过先在local空间中查找，再去global空间查找，然而事实上python并没有创建local空间。


因为函数的局部变量在编译的时候就已经确定了，所以会事先通过静态的方式进行存储，而不会临时构建一个字典、然后动态添加。因为函数的参数也可以看成是一个局部变量，那么在编译的时候就已经连同内部的局部变量一起放到了字节码对象的符号表co_varnames中，并且这些是有顺序的。至于局部变量的值则都放在字节码对象的co_const这个域里面，两者是对应的。但是参数此时还是没有值的、那么就是NULL，即便有默认值我们也可以进行替换。当我们调用一个函数，传递的参数的值就会按照传参的规则和相应的符号一一对应。所以如果最后发现符号表还有符号对应的值为NULL，那就证明参数少传递了，当然python如何传递参数、参数怎么匹配、以及扩展位置参数、扩展关键字参数怎么处理，就又是一个新的问题了，这里我们暂时不讨论这些。


只是想告诉大家，python中的函数在编译成PyFunctionObject对象的时候，那个local空间是为NULL的，因为函数的参数在编译的时候就可以确定，是通过静态方式事先就已经定好了的，并不会在执行期间才临时构建这个local空间。而我们通过locals()函数确实可以获取局部变量的，而且它也是一个字典，这是怎么回事，其实你可以把local空间看成是根据前面静态存储的变量临时构建的字典，这个字典可以看成是前面空间的一个拷贝，由于变量和值都是一样的，所以我们也说函数查找变量会先从local空间里面查找，举个例子：

所以我们看到并没有受到影响，因为函数的变量在编译时候已经确定，local空间不过是一个拷贝。即便修改了，那么当我再次获取的时候依旧原来的变量和值。这里涉及的深入一些，如果不理解的话可以跳过。python在执行函数的时候会为其创建一个栈帧(PyFrameObject对象)，这个栈帧里面有一个f_localsplus，函数的局部变量就存在这个f_localsplus里面。



我们看到f_localsplus这块内存是给4个老铁使用的，当函数在执行的时候会把变量压入到运行时栈，而这个运行时栈也是位于f_localsplus里面的。这几个老铁虽然内存上是连续的，但是却又老死不相往来。这一部分如果不是很理解的话，可以百度一下，或者跳过也行。总之只需要记住：函数的参数在编译时就已经确定，通过静态的方式存储；local空间实际上就是对存储局部变量的那段空间的一个拷贝，修改local空间不会影响到局部变量。


为什么列表查找的时间复杂度为O(1)


估计这个问题已经不需要我来介绍了，list1 = [1, "xxx", (1, 2, 3), {"a": 1}]，存储的真的是这些值吗？显然不是，存储的是这些值对应的指针，指针的大小是固定的，所以通过索引能够瞬间定位到对应的指针，然后操作的时候操作指针指向的内存，再比如：

我们看到列表里面的第一个元素占了1049个字节，但是这个列表本身居然只占了64个字节。就是因为a、b、c本身是一个指针，不管你指向的内存有多大，但是指针的大小是固定的，在64位机器上固定是8字节。所以尽管a、b、c三个元素都指向了一个比较大的内存，而这些内存和该列表没有关系，尽管列表存储了a、b、c，但本质上是存储了3个指向内存的指针。我们说list1[0], list1[1]这些也可以看成是一个变量，那么就等于把a、b、c指向的内存的地址拷贝了一份放到列表里面，所以列表计算大小的时候计算的是指针的大小，至于list1，它在底层当然也是一个地址。那么list1.__sizeof__()，等价于获取list1指向的内存(PyListObject)的大小，list1[0].__sizeof__()则是等价于获取该PyListObject的第一个元素(一个指针)所指向的内存的大小。

我们画一下图，图形是个好东西。



我们此时可以自信的说，我们已经明白了列表明明可以存储不同类型的值(其实存储的是同一类型，都是指针，只不过指向的值的类型不同)，但是时间复杂度却是O(1)。所以我们前面要花费那么长的时间介绍变量的本质、以及传递方面的知识，因为只有明白了这些知识，我们再理解列表的时间复杂度的时候才会水到渠成。当然不光是时间复杂度，还有列表本身的数据结构，这些前置知识，都可以加速我们的理解。


底层存储


oh，shit！终于到了列表的结构了，老规矩，看看list对象底层对应的结构体PyListObject长什么样子吧。

我们还是来分析一下，一个list对象所占的字节数。首先PyObject_Var_HEAD还记的是什么吗？对了，是一个宏，PyVarObject ob_base，它占24个字节，一个ob_item二级指针，8个字节，然后allocated，也是8字节。所以一个列表至少要占5 * 8 = 40个字节。至于具体占多少就看里面的元素个数了，如果存储了n个元素，那么大小就是 40 + 8 * n，我们来测试一下。

列表的扩容


下面我们来看看列表是如何扩容的，扩容调用的函数是list_resize，我们看到接收的是指针PyListObject *，另外这个参数名叫做self，所以我们定义类的时候，方法的第一个参数也叫self

我们看到了python的扩容方式，当append或者extend的时候如果元素的个数超过了容量allocated，那么会进行扩容。至于扩容的规则，我们看到是按照new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)来的，我们来测试一下。

我们看到计算的结果是一样的，说明python底层就是按照这种方式来扩容的。python底层是使用C语言的数组存储的，当扩容的时候，实际上是会创建新的数组，并把原来数组存储的指针依次拷贝过去，并让ob_item指向这个新的数组。因此即便扩容了，PyListObject对象的地址是不会变的，变的是ob_item。但我们在python中通过id查看的是PyListObject的地址，所以即便列表扩容，id函数的返回结果也是不变的。


另外我们说，解释器是在往列表中添加元素发现容量不够、塞不进去的时候才会扩容，至于我们创建列表的时候，指定了多少元素、容量就是多少。


创建PyListObject


我们知道对于PyLongObject和PyUnicodeObject来说，更常用的方法是PyLong_FromXXX和PyUnicode_FromXXX，但是对于PyListObject来说，官方只提供了一种方式：PyList_New，这个函数接收一个size参数，表示申请多大空间的PyListObject。我们在python中创建列表的时候，可以将str、tuple、dict对象转成list对象啊，其实那是事先计算元素的个数，然后调用PyList_New申请对应的空间，再把元素依次拷过去。

我们看到python在创建PyListObject对象的时候，分了两部分。我们知道python中所有对象底层对应的结构体里面字段都可以分为两部分，一部分是结构体的额外信息，另一部分就是真正用来存储值的。对于PyLongObject来说，它的"另一部分"就是ob_digit，对于这里的PyListObject，它的"另一部分"就是这里的ob_item指向的数组。而对于PyListObject来说，它的这两部分是分开创建的。


内存布局


假设我们创建一个列表l = [1, 2, 2, "xx", "yy", 4]，那么它的内存布局就是这样。



设置元素


我们知道python给对象对应的操作都设置了一个魔法方法，比如列表设置值操作对应__setitem__，那么在底层就对应PyList_SetItem，获取值__getitem__对应PyList_GetItem。有兴趣的话可以看一下底层的api，比较固定。比如我们后面使用C为python编写扩展模块的时候，经常会把python中的对象和C中对象互相转换，如果是C中的对象转换成python中的对象的话就是PyXxx_FromXxx，python中的对象转换成C中的对象就是PyXxx_AsXxx。前面的是python的结构体类型，后面的是C语言类型。


比如python中的int转成C中的double，python中的int底层是PyLongObject，转成double就是PyLong_AsDouble，如果是C中的double转成python中的int，那么就是PyLong_FromDouble。再比如python中的float，float在底层是一个PyFloatObject，那么python中的float转成C中的double就是PyFloat_AsDouble，同理反过来就是PyFloat_FromDouble。再比如python中的str转成C中的宽字符：PyUnicode_AsWideChar，C中的字符串转成python的str：PyUnicode_FromString。可以看到这些api都比较固定，所以不光python的api比较优美，底层的api也是如此。

如果我们对之前的列表执行l[2] = 100这个操作的话，那么内存布局就会如下



插入元素


插入元素的效率是比较低的，因为当前列表是一段连续的存储空间，在索引为i的地方插入一个元素，就意味着索引为i-1后面的所有元素都要依次向后移动一个位置。

我们看到python中list对象的insert做的事情还是比较多的，尤其是索引方面，真的做了好多处理，生怕你出错，底层帮你做了很多的事情，无论指定的位置是哪里，有没有越界都不会报错。事实上python中的很多地方都做了这样的处理，比如：一个对象要想转为整型，内部必须实现__int__方法，如果没有那么会去寻找__index__方法。再比如转化为bool类型，会去寻找内部的__bool__方法，没有的话会去找__len__方法。再比如一个对象要想被for循环，那么首先会去寻找__iter__方法，如果没有那么会退而求其次去寻找__getitem__。所以python就像一个老母亲一样，生怕你有任何闪失(报错)，背后不停地做工作为你保驾护航。而C则是完全相信你，你想做什么都可以我不管，但是自由的同时也要承担所有责任。


删除元素


删除元素，我们可以通过remove，那么底层是如何实现的呢？

既然是删除，那么和insert一样。全局都会进行移动，比如我把第一个元素删了，那么第二个元素要顶在第一个元素的位置，第n个元素要顶在第n-1个元素的位置上。


python中的其它对象


我们不可能把所有的对象都介绍完，因此下面再来挑几个看看它们的结构体定义。


PyFloatObject

Py_False和Py_True

PyComplexObject

PyTupleObject

PyDictObject

PySetObject

我们在python的层面上演示一下

PyGenObject

python中还存在很多对象，比如函数：PyFunctionObject、栈帧：PyFrameObject、模块：PyModuleObject、类里面的一个方法：PyMethodObject。但是我们不可能全部看完，最后再看两个对象：PyLong_Type、PyType_Type。我们到目前为止看的都是相当于python中内建类型的实例对象，那么int、str、dict这些类本身也是一个对象啊，那么它们长什么样子呢？我们知道type创建所有类，它是要看的，至于其它的我们随便挑一个就行，都是类似的，这里选int。

我们看到里面的东西还是很多的，但是很多我们不需要关注，并且我们看到了有的字段是0，这代表它不支持相应的操作，可是有些操作明明是支持的呀，所以这目前创建出来的对象还不是完整的，比如里面tp_dict，这是int的属性字典，只是目前没有，但是虚拟机在初始化的时候，会依次将int支持的操作填进tp_dict中，当然还会通过其它的操作，来使得int这个类变得完整。至于它是怎么做的，这个涉及到了虚拟机的执行流程，我们暂时不扯这么远。而且我们看到里面有一个long_as_number，我们说它指向了一个数组，我们看看这个数组存储了什么？

我们是不是看到了熟悉的东西，这不就是python的魔法方法嘛，long_as_number里面定义了一个整型对象时所支持的操作。


我们再来看看PyType_Type

python中的对象我们就看到这里，哇，扯得真多啊。毕竟编写扩展模块，这些知识还是要有的，而且我们下面还会继续扯python源码方面的知识，毕竟使用C编写python的扩展模块，必须要有python源码方面的知识。