Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's with the integer cache maintained by the interpreter?

After dive into Python's source code, I find out that it maintains an array of PyInt_Objects ranging from int(-5) to int(256) (@src/Objects/intobject.c)

A little experiment proves it:

>>> a = 1 >>> b = 1 >>> a is b True >>> a = 257 >>> b = 257 >>> a is b False 

But if I run those code together in a py file (or join them with semi-colons), the result is different:

>>> a = 257; b = 257; a is b True 

I'm curious why they are still the same object, so I digg deeper into the syntax tree and compiler, I came up with a calling hierarchy listed below:

PyRun_FileExFlags()      mod = PyParser_ASTFromFile()          node *n = PyParser_ParseFileFlagsEx() //source to cst             parsetoke()                  ps = PyParser_New()                  for (;;)                     PyTokenizer_Get()                      PyParser_AddToken(ps, ...)         mod = PyAST_FromNode(n, ...)  //cst to ast     run_mod(mod, ...)         co = PyAST_Compile(mod, ...) //ast to CFG             PyFuture_FromAST()             PySymtable_Build()             co = compiler_mod()         PyEval_EvalCode(co, ...)             PyEval_EvalCodeEx() 

Then I added some debug code in PyInt_FromLong and before/after PyAST_FromNode, and executed a test.py:

a = 257 b = 257 print "id(a) = %d, id(b) = %d" % (id(a), id(b)) 

the output looks like:

DEBUG: before PyAST_FromNode name = a ival = 257, id = 176046536 name = b ival = 257, id = 176046752 name = a name = b DEBUG: after PyAST_FromNode run_mod PyAST_Compile ok id(a) = 176046536, id(b) = 176046536 Eval ok 

It means that during the cst to ast transform, two different PyInt_Objects are created (actually it's performed in the ast_for_atom() function), but they are later merged.

I find it hard to comprehend the source in PyAST_Compile and PyEval_EvalCode, so I'm here to ask for help, I'll be appreciative if some one gives a hint?

like image 799
felix021 Avatar asked Mar 02 '13 06:03

felix021


People also ask

What is integer caching in Python?

Python caches small integers, which are integers between -5 and 256. These numbers are used so frequently that it's better for performance to already have these objects available. So these integers will be assigned at startup. Then, each time you refer to one, you'll be referring to an object that already exists.

What is integer cache in Java?

Java Integer Cache Implementation:Integer objects are cached internally and reused via the same referenced objects. This is applicable for Integer values in the range between –128 to +127. This Integer caching works only on auto-boxing. Integer objects will not be cached when they are built using the constructor.

What does cache do in Python?

Caching is an optimization technique that you can use in your applications to keep recent or often-used data in memory locations that are faster or computationally cheaper to access than their source.

Does Python have cache?

Python offers built-in possibilities for caching, from a simple dictionary to a more complete data structure such as functools. lru_cache . The latter can cache any item using a Least-Recently Used algorithm to limit the cache size. Those data structures are, however, by definition local to your Python process.


1 Answers

Python caches integers in the range [-5, 256], so integers in that range are usually but not always identical.

What you see for 257 is the Python compiler optimizing identical literals when compiled in the same code object.

When typing in the Python shell each line is a completely different statement, parsed and compiled separately, thus:

>>> a = 257 >>> b = 257 >>> a is b False 

But if you put the same code into a file:

$ echo 'a = 257 > b = 257 > print a is b' > testing.py $ python testing.py True 

This happens whenever the compiler has a chance to analyze the literals together, for example when defining a function in the interactive interpreter:

>>> def test(): ...     a = 257 ...     b = 257 ...     print a is b ...  >>> dis.dis(test)   2           0 LOAD_CONST               1 (257)               3 STORE_FAST               0 (a)    3           6 LOAD_CONST               1 (257)               9 STORE_FAST               1 (b)    4          12 LOAD_FAST                0 (a)              15 LOAD_FAST                1 (b)              18 COMPARE_OP               8 (is)              21 PRINT_ITEM                        22 PRINT_NEWLINE                     23 LOAD_CONST               0 (None)              26 RETURN_VALUE         >>> test() True >>> test.func_code.co_consts (None, 257) 

Note how the compiled code contains a single constant for the 257.

In conclusion, the Python bytecode compiler is not able to perform massive optimizations (like statically typed languages), but it does more than you think. One of these things is to analyze usage of literals and avoid duplicating them.

Note that this does not have to do with the cache, because it works also for floats, which do not have a cache:

>>> a = 5.0 >>> b = 5.0 >>> a is b False >>> a = 5.0; b = 5.0 >>> a is b True 

For more complex literals, like tuples, it "doesn't work":

>>> a = (1,2) >>> b = (1,2) >>> a is b False >>> a = (1,2); b = (1,2) >>> a is b False 

But the literals inside the tuple are shared:

>>> a = (257, 258) >>> b = (257, 258) >>> a[0] is b[0] False >>> a[1] is b[1] False >>> a = (257, 258); b = (257, 258) >>> a[0] is b[0] True >>> a[1] is b[1] True 

(Note that constant folding and the peephole optimizer can change behaviour even between bugfix versions, so which examples return True or False is basically arbitrary and will change in the future).


Regarding why you see that two PyInt_Object are created, I'd guess that this is done to avoid literal comparison. for example, the number 257 can be expressed by multiple literals:

>>> 257 257 >>> 0x101 257 >>> 0b100000001 257 >>> 0o401 257 

The parser has two choices:

  • Convert the literals to some common base before creating the integer, and see if the literals are equivalent. then create a single integer object.
  • Create the integer objects and see if they are equal. If yes, keep only a single value and assign it to all the literals, otherwise, you already have the integers to assign.

Probably the Python parser uses the second approach, which avoids rewriting the conversion code and also it's easier to extend (for example it works with floats as well).


Reading the Python/ast.c file, the function that parses all numbers is parsenumber, which calls PyOS_strtoul to obtain the integer value (for intgers) and eventually calls PyLong_FromString:

    x = (long) PyOS_strtoul((char *)s, (char **)&end, 0);     if (x < 0 && errno == 0) {         return PyLong_FromString((char *)s,                                  (char **)0,                                  0);     } 

As you can see here the parser does not check whether it already found an integer with the given value and so this explains why you see that two int objects are created, and this also means that my guess was correct: the parser first creates the constants and only afterward optimizes the bytecode to use the same object for equal constants.

The code that does this check must be somewhere in Python/compile.c or Python/peephole.c, since these are the files that transform the AST into bytecode.

In particular, the compiler_add_o function seems the one that does it. There is this comment in compiler_lambda:

/* Make None the first constant, so the lambda can't have a    docstring. */ if (compiler_add_o(c, c->u->u_consts, Py_None) < 0)     return 0; 

So it seems like compiler_add_o is used to insert constants for functions/lambdas etc. The compiler_add_o function stores the constants into a dict object, and from this immediately follows that equal constants will fall in the same slot, resulting in a single constant in the final bytecode.

like image 175
Bakuriu Avatar answered Sep 19 '22 19:09

Bakuriu