Preventing dict lookups

[eendebakpt]

When profiling my python code I noticed a lot of time is spend in dict access. Can we somehow let the python intepreter eliminate dict lookups? For example convert the collatz below into collatz2 automatically?

def collatz(n):
    while True:
        is_odd =n % 2
        if is_odd:
            if n==1:
                break
            n= 3*n+1
        else:
            n = n >> 1
    
def collatz2(n):
    while True:
        if n % 2:
            if n==1:
                break
            n= 3*n+1
        else:
            n = n >> 1

Some timings (python 3.10):

%timeit collatz(1303)    
8.38 µs ± 233 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit collatz2(1303) 
7.74 µs ± 74.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

I am aware that there are some issues with my proposal (if there in exception, ii will not be available, in the code there might be eval statements). So perhaps this optimization can be made optional? Or the interpreter smart enough to handle these cases.

One more example:

import dis
c="""
x=1
for ii in range(4):
    x=x*2    
"""
print(dis.dis(c))

Output:

  2           0 LOAD_CONST               0 (1)
              2 STORE_NAME               0 (x)

  3           4 LOAD_NAME                1 (range)
              6 LOAD_CONST               1 (4)
              8 CALL_FUNCTION            1
             10 GET_ITER
        >>   12 FOR_ITER                 6 (to 26)
             14 STORE_NAME               2 (ii)

  4          16 LOAD_NAME                0 (x)
             18 LOAD_CONST               2 (2)
             20 BINARY_MULTIPLY
             22 STORE_NAME               0 (x)
             24 JUMP_ABSOLUTE            6 (to 12)

  3     >>   26 LOAD_CONST               3 (None)
             28 RETURN_VALUE
None

In this example it would be ok for me if the line 14 STORE_NAME 2 (ii) is removed from the bytecode.

[da-woods]

is_odd is a local variable so I don't think it goes through a dict lookup. Locals are stored in something much more like tuple (because there's a known fixed number of them)

[Fidget-Spinner]

I think someone tried this before (was it Victor with his FAT Python project?) or at least I've seen this a couple of times on python-ideas or python-dev mailing lists.

This isn't allowed at the compiler level due to language semantics. The variable you removed could be modified externally through the frame object. So Python must lookup every time.

Also @da-woods is completely correct. In your example the local variable uses the LOAD_FAST instruction which loads from a C array. This is quite fast. It doesn't do a dictionary lookup.

Most of the dictionary lookups in Python are done elsewhere (e.g. looking up sys, looking up attributes at the C API level, looking up type methods in C, etc.). Ever since PEP 659, dictionary lookups due to pure Python code are becoming rarer.

[gvanrossum]

This isn't allowed at the compiler level due to language semantics. The variable you removed could be modified externally through the frame object. So Python must lookup every time.

I'm not sure if those semantics are truly part of the language, or just assumed by users of CPython. It only come into play when accessing stack frames, which aren't a stable API. More worrisome would be locals(), but I could argue that locals() cannot introspect what the compiler doesn't generate, and there's no absolute guarantee in this area -- it's merely been unexplored.

It would be different if we were talking about a global or an attribute. Those would be quite visible (e.g. to other threads) and I would object.

Nevetheless the OP seems to assume that local variable accesses are more expensive than they really are.

[FreddieWitherden]

Nevetheless the OP seems to assume that local variable accesses are more expensive than they really are.

Perhaps. But, if the numbers in the post are accurate, then there is almost a 10% difference in run-time between the two code fragments when, really, there should be almost none.

[gvanrossum]

With Python 3.11 the difference seems a little less, but it's still there (about 6.5% faster):

~$ python3.11 -m timeit -s 'from collatz import collatz' 'collatz(1303)'
50000 loops, best of 5: 5.69 usec per loop
~$ python3.11 -m timeit -s 'from collatz import collatz2' 'collatz2(1303)'
50000 loops, best of 5: 5.34 usec per loop

[FreddieWitherden]

I am guessing the overhead comes from an additional store operation? While it is probably legitimate for the compiler to elide an local variables which are consumed once and only once after being set, it is likely quite a niche optimisation on its own and doubt it occurs that frequently. Getting more aggressive would require the compiler to prove any lines between assignment and first use can not possibly access, modify, or change the computed value of the variable to be elided.

With regards to the FAT Python references. My understanding is that FAT Python (if brought to fruition) would have recognized collatz with n being an integer as a pure function and then gone to town on it. Once you know those two facts it is trivial to NOP the entire thing—playing the same party trick as a C compiler from the late 80s.

[Fidget-Spinner]

Yeah it comes from a store in a C array then retrieving that same value again from the same C array. In 3.11 it's a little faster thanks to the STORE_FAST__LOAD_FAST combined instruction. Source code for that instruction here.

>>> dis.dis(collatz, adaptive=True)
  1           0 RESUME_QUICK             0

  2           2 NOP

  3           4 LOAD_FAST__LOAD_CONST     0 (n)
              6 LOAD_CONST               2 (2)
              8 BINARY_OP                6 (%)
             12 STORE_FAST__LOAD_FAST     1 (is_odd)

  4          14 LOAD_FAST                1 (is_odd)
             16 POP_JUMP_FORWARD_IF_FALSE    17 (to 52)

  5          18 LOAD_FAST__LOAD_CONST     0 (n)
             20 LOAD_CONST               3 (1)
             22 COMPARE_OP_INT_JUMP      2 (==)
             28 POP_JUMP_FORWARD_IF_FALSE     2 (to 34)

  6          30 LOAD_CONST               0 (None)
             32 RETURN_VALUE

  7     >>   34 LOAD_CONST__LOAD_FAST     4 (3)
             36 LOAD_FAST                0 (n)
             38 BINARY_OP_MULTIPLY_INT     5 (*)
             42 LOAD_CONST               3 (1)
             44 BINARY_OP_ADD_INT        0 (+)
             48 STORE_FAST               0 (n)
             50 JUMP_FORWARD             5 (to 62)

  9     >>   52 LOAD_FAST__LOAD_CONST     0 (n)
             54 LOAD_CONST               3 (1)
             56 BINARY_OP                9 (>>)
             60 STORE_FAST               0 (n)

  2     >>   62 JUMP_BACKWARD_QUICK     30 (to 4)

[gvanrossum]

With regards to the FAT Python references. My understanding is that FAT Python (if brought to fruition) would have recognized collatz with n being an integer as a pure function and then gone to town on it. Once you know those two facts it is trivial to NOP the entire thing—playing the same party trick as a C compiler from the late 80s.

My understanding is that FAT Python is dead, but the Faster CPython initiative will eventually have the same effect (it will take a few releases but it will be in the main release).