Shell's Home

Jun 17, 2015 - 1 minute read - Comments

list.append的性能分析

在python2.7.5的源码中,list的append操作最终调用的是Python-2.7.5/Objects/listobject.c:266这里的app1(请帮我复核一下,Python的源码有很多隐藏的手脚不容易看见)。

在app1里,使用了list_resize来进行resize,而list_resize间接用到了PyMem_RESIZE。按照我的阅读,这个应该是层层转到realloc上的。

下面就是查glibc源码的事了。我看到的应该是glibc-2.19/malloc/malloc.c:2951这里的__libc_realloc函数。这个函数很长,我大致读了一下。这里分了两个分支。一个是2992行的chunk_is_mmapped。如果我没理解错的话,我们的内存块不可能没有mapped。那么另一个就是2996行的HAVE_MREMAP,这个是编译时宏,我也不知道我的系统上是不是打开的。如果没打开的话,肯定是走alloc,copy,free的流程。

所以我就用strace跟踪了一下,结果确实调用了mremap。

这个函数在linux内核中。我使用的源码是linux-3.2,结果在linux-3.2/mm/mremap.c:535这里。

大致看了一下函数实现。首先试图处理缩小,如果不行的话试图在扩展到最大(vma_to_resize),如果这样还是不行,先试试看能不能追加映射(vma_expandable/vma_adjust)。如果都不行,他还是用的创建并移动的方法。(We weren’t able to just expand or shrink the area, we need to create a new one and move it..)。

所以,总体来说,list.append的复杂度还是O(n)级。但是由于remap的内核实现,因此比直接搬数据应该会快一些。具体表现可能要以测试为准了。

但是这里就有一个疑惑。难道python现在删除了复杂的内存层,将mm管理直接用系统的来支持么?我记忆中python源码解析里讲过python有一个巨复杂无比的内存控制系统。难道全用系统管理了么?对此我查了一下 2.6 / 2.7 的python mm文档。里面倒是明确提到不要同时使用系统api和python api来管理内存。但是并没有明确说明如何处理的实现。但是我在系统里并没有找到第二个实现(debug不算),唯一的实现在Python-2.7.5/Include/pymem.h:76,是直接转到realloc上去的。

貌似在新证据出现前,我得认为python使用的glibc api来处理的mm问题。

携程本次问题分析 一个有趣的python问题

comments powered by Disqus