<
No Thanks ×

Literally Literals and Other Number Oddities In Python

This post requires an intermediate knowledge of Python and some experience with C (or at least being able to read some C),  and the willingness to deal with bytecode. It originated as a series of emails between the Python developers at EveryMundo about a quiz at an expo booth at PyCon 2017. I was also very much inspired by David Wolever’s talk this year about exploring Python’s internals.

Contents

The Python Problem

It started off with a quiz at PyCon that relied on one of those silly programming trick questions. One particularly tricky one was basically about the fact Python treats “small” numbers differently. Well, how small is small?

   
    x = 256
    print(x is 256)  # prints True

    y = 257
    print(y is 257)  # prints False
   

256 is the threshold. But why? And what? Integers inside this range, and integers out of this range won’t always behave exactly the same.

However, this is such a small edge case in the real world, that most people I’ve met have never even heard of it or encountered it. (In fact, I only know of it because of this amazing StackExchange question: “Write a program that makes 2 + 2 = 5”).

The short answer, and easy end to the blog post is “Never use `is` for comparing primitives in Python.”

    
    x = 256
    print(x == 256)  # prints True

    y = 257
    print(y == 257)  # prints True
  

And all your problems go away!

But that wasn’t a choice on the PyCon quiz, so we need to dig into why (instead of, y’know, just abandoning the quiz like a sane person).

This is because in Python, ‘is’ checks to see if two objects are actually the same object. Not just that they’re equal in every way, but they have to be literally the same object. And since everything is an object in Python — even numbers, that means numbers can have the same value but can have different identities. In the above example, there are two numbers with the value “257”. One is assigned to ‘y’ and one isn’t assigned to any name, it’s just used as a “literal” after the ‘is’. So, they both have the same value but different identities.

Like having a clone: virtually identical, and yet not.

Futurama GIF - Fry and Professor

“Look, Professor, I may be identical to you in every possible way but that doesn’t mean I’m anything like you.”

Alright, but that doesn’t answer anything about why 256 is so special.

Why 257 is Not 257

We could try asking Python itself to see what’s going on. There’s the dis module with the disassemble utility! Let’s just open up a Python shell (CPython 3.6 to be specific, yes it actually matters here) and dive in!

First, we’ll disassemble the comparison to 256 and see what’s happening. And then disassemble the 257 version, and they should be different.


    >>> dis.dis('x = 256; x is 256')
      1           0 LOAD_CONST               0 (256)
                  2 STORE_NAME               0 (x)
                  4 LOAD_NAME                0 (x)
                  6 LOAD_CONST               0 (256)
                  8 COMPARE_OP               8 (is)
                 10 POP_TOP
                 12 LOAD_CONST               1 (None)
                 14 RETURN_VALUE
    >>> 
    >>> dis.dis('x = 257; x is 257')
      1           0 LOAD_CONST               0 (257)
                  2 STORE_NAME               0 (x)
                  4 LOAD_NAME                0 (x)
                  6 LOAD_CONST               0 (257)
                  8 COMPARE_OP               8 (is)
                 10 POP_TOP
                 12 LOAD_CONST               1 (None)
                 14 RETURN_VALUE
  

Uh, what? They’re the same?! Let’s try typing it into our console again to make sure they give different answers.


    >>> x = 256; x is 256
    True
    >>> x = 257; x is 257
    True
    >>> x = 257
    >>> x is 257
    False

    >>> print('Wat.')
    Wat.

So, it’s not just 256 that’s special. How else can we break all our assumptions?

It turns out a lot of ways.

By putting the numbers on a different line. By putting them inside a function. By putting them outside a function. Whether the name is bound to an outer scope. Oh, and of course using any other Python Interpreter can give different results (more on that at the end), we’re beginning to get into the nitty-gritty implementation details of CPython (the main Python interpreter).


    >>> x = 500
    >>> x is 500
    False

    >>> x = 500; x is 500
    True

    >>> def wat():
    ...   x = 500
    ...   return x is 500
    >>> wat()
    True

    >>> x = 500
    >>> def outer_wat():
    ...   return x is 500
    >>> outer_wat()
    False
    
    >>> x = 500
    >>> def global_wat():
    >>>   global x
    >>>   x = 600
    >>>   return x is 600
    >>> global_wat()
    True
  

I have to admit, most of these were pretty surprising to me. global_wat() is the only one where the output was what I expected, seeing as it’s basically the same as wat() but using a global name.

So, if the last 2 lines are the same, and the output is the same, surely the disassembly of wat() will be equal to the disassembly at the end of global_wat() , and outer_wat()‘s disassembly will be totally different. …Right?

   
    >>> dis.disassemble(wat.__code__)
    2           0 LOAD_CONST               1 (500)
                3 STORE_FAST               0 (x)

    3           6 LOAD_FAST                0 (x)
                9 LOAD_CONST               1 (500)
                12 COMPARE_OP               8 (is)
                15 RETURN_VALUE

    >>> dis.disassemble(outer_wat.__code__)
    2           0 LOAD_GLOBAL              0 (x)
                3 LOAD_CONST               1 (500)
                6 COMPARE_OP               8 (is)
                9 RETURN_VALUE

    >>> dis.disassemble(global_wat.__code__)
    3           0 LOAD_CONST               1 (600)
                2 STORE_GLOBAL             0 (x)
  
    4           4 LOAD_GLOBAL              0 (x)
                6 LOAD_CONST               1 (600)
                8 COMPARE_OP               8 (is)
               10 RETURN_VALUE
    

I couldn’t believe it! After the instructions, to LOAD_CONST and STORE_GLOBALglobal_wat is identical to outer_wat. Even though one returns ‘True’ and one returns ‘False’.

Our First Clue

But there are some patterns here we can look into. The first thing I noticed is that any time this returns True, the bytecode includes two LOAD_CONST operations to the same address.

So, maybe that’s why sometimes 500 is 500 and sometimes it isn’t. It’s re-using the literal from the constants. To see if this is true, can we make more scenarios without two LOAD_CONST operations to the same address, and see them return “False”? Can we make any return “True”?

For starters, what if we don’t reuse the same literal number? 256 + 1 and 257 should be the same, but are they really?

    
    >>> x = 257; x is 257
    True
    >>> x = 256 + 1; x is 257
    False
    >>> dis.dis('x = 256 + 1; x is 257')
      1           0 LOAD_CONST               4 (257)
                  2 STORE_NAME               0 (x)
                  4 LOAD_NAME                0 (x)
                  6 LOAD_CONST               2 (257)
                  8 COMPARE_OP               8 (is)
                 10 POP_TOP
                 12 LOAD_CONST               3 (None)
                 14 RETURN_VALUE
  

Aha! We’re onto something! Two LOAD_CONST operations for the same value, but to different addresses. And what if we use 256 instead of 257 as our final result?

    
    >>> x = 256; x is 256
    True
    >>> x = 255 + 1; x is 256
    True
    >>> dis.dis('x = 255 + 1; x is 256')
      1           0 LOAD_CONST               4 (256)
                  2 STORE_NAME               0 (x)
                  4 LOAD_NAME                0 (x)
                  6 LOAD_CONST               2 (256)
                  8 COMPARE_OP               8 (is)
                 10 POP_TOP
                 12 LOAD_CONST               3 (None)
                 14 RETURN_VALUE
  

Ugh, nothing wants to do what you expect, does it? The bytecode is even exactly the same except for 256 instead of 257! But thanks to our earlier research we know 256 and below is a special case, so let’s not get discouraged, and come back to this later. Our above fact holds true for any number above 256: if not using the exact same literal number, they’re not identical.

What About Precision Errors?

What if we play around with precision “errors”?

    
    >>> 0.300000000000000000005
    >>> 0.3
    >>> 0.300000000000000000005 is 0.300000000000000000004
    True
    >>> dis.dis('0.300000000000000000005 is 0.300000000000000000004')
    1           0 LOAD_CONST               0 (0.3)
                2 LOAD_CONST               0 (0.3)
                4 COMPARE_OP               8 (is)
                6 RETURN_VALUE
  

That kind of makes sense. It’s reducing them to 0.3 in the bytecode, before the script is even actually run. It then loads the constant twice from the same address.

    
    >>> def closure_wat():
    ...   x = 500
    ...   def nested_wat():
    ...     return x is 500
    ...   return nested_wat
    ...
    >>> closure_wat()()
    False
    >>> dis.dis(closure_wat)
    2           0 LOAD_CONST               1 (500)
                2 STORE_DEREF              0 (x)
    
    3           4 LOAD_CLOSURE             0 (x)
                6 BUILD_TUPLE              1
                8 LOAD_CONST               2 (<code object nested_wat at 0x01F7F548, file "<stdin>", line 3>)
               10 LOAD_CONST               3 ('global_wat.<locals>.nested_wat')
               12 MAKE_FUNCTION            8
               14 STORE_FAST               0 (nested_wat)
    
    5          16 LOAD_FAST                0 (nested_wat)
               18 RETURN_VALUE
    >>> dis.dis(closure_wat())
    3           0 LOAD_DEREF               0 (x)
                2 LOAD_CONST               1 (500)
                4 COMPARE_OP               8 (is)
                6 RETURN_VALUE
  

Oh no! We have two identical LOAD_CONST operations to address 1 to fetch 500, and yet it returns “False”!

But maybe addresses aren’t shared between a frame and this is just a coincidence? That would make more sense than this returning “False” from loading the same constant twice.

Let’s try something and see if we can’t rearrange those addresses.

    
    >>> def closure_wat():
    ...   def nested_wat():
    ...     return x is 500
    ...   x = 500
    ...   return nested_wat
    ...
    >>> closure_wat()()
    False
    >>>
    >>> dis.dis(closure_wat)
      2           0 LOAD_CLOSURE             0 (x)
                  2 BUILD_TUPLE              1
                  4 LOAD_CONST               1 (<code object nested_wat at 0x01F7F6A8, file "<stdin>", line 2>)
                  6 LOAD_CONST               2 ('closure_wat.<locals>.nested_wat')
                  8 MAKE_FUNCTION            8
                 10 STORE_FAST               0 (nested_wat)
    
      4          12 LOAD_CONST               3 (500)
                 14 STORE_DEREF              0 (x)
    
      5          16 LOAD_FAST                0 (nested_wat)
                 18 RETURN_VALUE
    >>> dis.dis(closure_wat())
      3           0 LOAD_DEREF               0 (x)
                  2 LOAD_CONST               1 (500)
                  4 COMPARE_OP               8 (is)
                  6 RETURN_VALUE
  

Aha! Our nested_wat function is still loading 500 from address 1, but the closure_wat loads it from address 3. So, these aren’t the same address space, and it was just a coincidence before.

I feel pretty comfortable now in saying that when a literal is found within a given scope in Python, it is stored in the constants table, which can cause them to have the same identity. When it cannot be loaded from a constant, a new object is created, even though it has an equal value.

But that’s a long sidetrack that didn’t answer the original question at all. And it turns out, we can’t answer it entirely within Python.

We’ll need to jump into the source code to see what’s up.

Why 256 is 256

So back to our original question.

It may seem like everything earlier was unrelated, but we now know that exactly identical bytecode can have different behavior for “small” integers. And because of that, we need to go deeper than the bytecode to see what’s happening.

If we read the Python documentation (we all do that, right…?), we know that:  “The ‘is‘ operator compares the identity of two objects; the id() function returns an integer representing its identity.”

This is our first hint so, let’s look at the source for the builtin id function. We’ll need to pick an actual version of Python to look at now and answers can be different for different interpreters and versions. We’ll be looking at CPython 3.6.1, though this should be very similar for all versions of CPython.

The search function on github found this much more easily than I expected. Now how impossible is the CPython source code going to be to read?

 

Oh, it’s only a single line of code calling another function. Easy so far… Let’s follow that:

And this function only calls one of two other functions, depending on the pointer size of the platform. (I would guess 32bit / 64bit, but honestly didn’t do enough digging to know).

Let’s look at the biggest case, PyLong_FromUnsignedLongLong (the other implementation seems to be same, just casting to Long instead of LongLong)

Aha! Here’s where the actual meat is!

The first thing I noticed is the pointer address is cast as a LongLong here. Specifically, any number can be passed here, not just an address.

When can that happen and why? No idea. But there are special cases in the code to handle it.

If the number is less than PyLong_BASE (either 2^30 or 2^15 depending on platform, 2^30 in the case we’re following) it immediately calls and returns PyLong_FromLong on the object.

Because we only want to learn about cases below 256, and 256 is definitely less than 2^30 or 2^15, we can assume it follows this route on any platform.

Fun Fact: This 2^15 / 2^30 is called a “digit” in CPython.

Following that function, it first does the CHECK_SMALL_INT macro. Sounds like we’re getting close!

The do {…} while (0) seemed really weird to me. Apparently that’s just a C idiom to get around weirdness with multi-line macro definitions with if’s.

This macro references NSMALLNEGINTS and NSMALLPOSINTS, which are easy to find earlier in the file.

NSMALLNEGINTS is 5 and NSMALLPOSINTS is 257.

Plug those into the if statement within CHECK_SMALL_INT, and we find the range [-5, 256]. If the address is in the range [-5, 256] It calls and returns get_small_int()

Then returns that cached PyObject* pointer from the small_ints array. Because it’s a macro, this will also return out of the PyLong_FromUnsignedLongLong function.

And that’s that. id is returned to builtin_id which returns to Python.

We can also see at the end of the file where the small_ints array is initialized, in _PyLong_Init and again we see the range [-5, 256].

I think we figured it out! There is a static array defined in longobject.c that stores “already made” PyLong objects for integers -5 to 256 (which is adjustable at compile time). And any function that converts a C-style Long (or other integer-like type) to a PyLong first calls the CHECK_SMALL_INT macro, which should serve small integers from the cache.

Let’s test this out. Do the tricks that work for 256 also work for -5?

    
    >>> x = -4 - 1; x is -5
    True
    >>> x = -5 - 1; x is -6
    False
  

Woo! Well that’s enough magic for now (even though it was actually very easy to read). And I hope you’ve learned your lesson:

“Never use `is` for comparing primitives in Python”

P.S.

And what about the other Python interpreters? I’ll leave that as an exercise for the reader. But I will tell you, this whole issue would have been avoided in PyPy:
“Object identity of primitive values works by value equality, not by identity of the wrapper. This means that x + 1 is x + 1 is always true, for arbitrary integers x”

 


Thoughts? Add a Comment

Protected with IP Blacklist CloudIP Blacklist Cloud

Comments

%d bloggers like this: