./Python String Intern

posted by cli on

Python String Intern

Python2.x 中的String对象的实现让我觉得有点不可思议。Python的设计者为了提高内存利用率,使用了intern的机制来共享相同的字符串,也就是说如果你有两个字符串: s1=’python’ s2=’python’,s1和s2实际上是指向同一个内存块的,他们共享了同一个PyStringObject。Python内部维护了一个dict类型的变量interned来记录所有的共享字符串,这就引出了一个问题。由于共享字符串的维护直接依赖于Python中的dict,对interned查询需要的参数就应该是一个PyObect的‘派生’类型,不管interned中是不是已经存在了需要的字符串对象,Python总是会先建立一个临时的字符串对象,然后再以该临时对象为interned的一个key去查找是否存在一个已缓存的相同的字符串,如果存在的话就丢弃这个临时变量而是用interned中的缓存。这里最大的问题是在建立这个临时的字符串对象时有一个拷贝内存的过程: Py_MEMCPY(op->ob_sval, str, size+1);如果当前要创建的字符串还没有被缓存过,那么这里一切都很好;但是如果这个字符串已经缓存过了,这次所做的内存拷贝就是无用功,而且还是个耗费时间的无用功。如果字符串比较大,这里对效率的影响可想而知。

针对这个问题,最直接的想法是能不能不拷贝字符串而直接去根据参数中传进来的字符串去判断这个字符串有没有被缓存过了,这样做的话也就意味着不能再使用Python的dict来维护这些字符串缓存了,这可能就需要引入专门的代码来操作一个专用的数据结构了。相比较而言,Lua中使用一个stringtable来缓存所有字符串,创建一个新字符串的时候是先根据源字符串计算出一个hash值,再根据这个hash值去stringtable中查找,只有在这找不到时才会真正的创建一个通过拷贝创建一个新字符串。所以Lua中的字符串就没有这个问题。

Python的设计者肯定是意识到这个问题的,这应该也是他们权衡后的决策结果。这里纯粹就是一个概率游戏了,碰到某些极端应用时这个实现的效率可能会让人无法接受。

Update[11/27/2013]: Python只对长度为0和1的字符串做intern,我没写清楚,可能夸大了可能存在的效率问题。