The internals of Python string interning
This article describes how Python string interning works in CPython 2.7.7.
A few days ago, I had to explain to a colleague what the built-in function
intern does. I gave him the following example:
You got the idea but… how does it work internally?
Let’s delve into CPython source code and take a look at
PyStringObject, the C structure representing Python strings located in the file stringobject.h:
According to this comment, the variable
ob_sstate is different from 0 if and only if the string is interned. This variable is never accessed directly but always through the macro
PyString_CHECK_INTERNED defined a few lines below:
Then, let’s open stringobject.c. Line 24 declares a reference to an object where interned strings will be stored:
In fact, this object is a regular Python dictionary and is initialized line 4745:
Finally, all the magic happens line 4732 in the
PyString_InternInPlace function. The implementation is straightforward:
As you can see, keys in the interned dictionary are pointers to string objects and values are the same pointers. Furthermore, string subclasses cannot be interned. Let me set aside error checking and reference counting and rewrite this function in pseudo Python code:
Simple, isn’t it?
What are the benefits of interning strings?
Why would you intern strings? Firstly, “sharing” string objects reduces the amount of memory used. Let’s go back to our first example, initially, the variables
s2 reference two different objects:
After being interned, they both point to the same object. The memory occupied by the second object is saved:
When dealing with large lists with low entropy, interning makes sense. For instance, when tokenizing a corpus, we could benefit from the very heavy-tailed distribution of word frequencies in human languages to intern strings to our advantage. In the following example, we will load the play Hamlet by Shakespeare with NLTK and we will use Heapy to inspect the object heap before and after interning:
As you can see, we drastically reduced the number of allocated string objects from 31 166 to 4 529 and divided by 6.5 the memory occupied by the strings!
Secondly, strings can be compared by a O(1) pointer comparison instead of a O(n) byte-per-byte comparison.
To prove so, I have measured the time required to verify the equality of two strings as a function of their length when they are interned and when they are not. The following should convince you:
Under certain conditions, strings are natively interned. Recall the first example, if I had written
foo instead of
foo!, the strings
s2 would have been interned “automatically”:
Interned or not interned?
Before writing this blog post, I always thought that, under the hood, strings were natively interned according to a rule taking into account their length and the characters composing them. I was not far away from the truth but, unfortunately, when playing with pairs of strings built in very different ways, I could never infer what this rule exactly was. Can you?
After looking at these examples, you have to admit that it is hard to tell on which basis a string is natively interned or not. So let’s read some more CPython code and figure it out!
Fact 1: all length 0 and length 1 strings are interned
Still in stringobject.c, this time we will take a look at these interesting lines placed in both of the following functions
This leaves no ambiguity: all strings of length 0 and 1 are interned.
Fact 2: strings are interned at compile time
The Python code you write is not directly interpreted and goes through a classic compilation chain which generates an intermediate language called bytecode. Python bytecode is a set of instructions executed by a virtual machine: the Python interpreter. The list of these instructions can be found here and you can find out what instructions are run by a particular function or module, by using the
As you know, in Python everything is an object and Code objects are Python objects which represent pieces of bytecode. A Code object carries along with all the information needed to execute: constants, variable names, and so on. It turns out that when building a Code object in CPython, some more strings are interned:
In codeobject.c, the tuple
consts contains the literals defined at compile time: booleans, floating-point numbers, integers, and strings declared in your program. The strings stored in this tuple and not filtered out by the
all_name_chars function are interned.
In the example below,
s1 is declared at compile time. Oppositely,
s2 is produced at runtime:
As a consequence,
s1 will be interned whereas
s2 will not.
all_name_chars rules out strings that are not composed of ascii letters, digits or underscores, i.e. strings looking like identifiers:
With all these explanations in mind, we now understand why
'foo!' is 'foo!' evaluates to
'foo' is 'foo' evaluates to
True. Victory? Not quite yet.
Bytecode optimization produces more string constants
It might sound very counterintuitive, but in the example below, the outcome of the string concatenation is not performed at runtime but at compile time:
This is why the result of
'foo' + 'bar' is also interned and the expression evaluates to
How? The penultimate source code compilation step produces a first version of bytecode. This “raw” bytecode finally goes into a last compilation step called “peephole optimization”.
The goal of this step is to produce more efficient bytecode by replacing some instructions by faster ones.
One of the techniques applied during peephole optimization is called constant folding and consists in simplifying constant expressions in advance. Imagine you are a compiler and you come across this line:
What can you do to simplify this expression and save some clock cycles at runtime? You are going to substitute this expression by the computed value
This is exactly what happens to the
'foo' + 'bar' expression. Let’s define the foobar function and disassemble the corresponding bytecode:
See? No sign of the addition and the two initial constants
'bar'. If CPython bytecode was not optimized, the output would have been the following:
We discovered why the following expression evaluates to True:
Avoiding large .pyc files
So why does
'a' * 21 is 'aaaaaaaaaaaaaaaaaaaaa' not evaluate to
True? Do you remember the .pyc files you encounter in all your packages? Well, Python bytecode is stored in these files. What would happen if someone wrote something like this
['foo!'] * 10**9? The resulting .pyc file would be huge! In order to avoid this phenomena, sequences generated through peephole optimization are discarded if their length is superior to 20.
I know interning
Now, you know all about Python string interning!
I’m amazed at how deep I dug in CPython in order to understand something as anecdotic as string interning. I’m also surprised by the simplicity of the CPython API. Even though, I’m a poor C developer, the code is very readable, very well documented, and I feel like even I could contribute to it.
Oh… one last thing, I forgot to mention one VERY important thing. Interning works because Python strings are immutable. Interning mutable objects would not make sense at all and would cause disastrous side effects.
But wait… We know some other immutable objects. Integers for instance. Well… guess what?
comments powered by Disqus