[Python-ideas] RFC: PEP: Add dict.__version__

[Victor Stinner]

Hi,

2016-01-11 9:07 GMT+01:00 Chris Angelico <rosuav at gmail.com>:
> Yes, but if you're using the ID as the hash and identity as equality,
> then *by definition* the only way to look up that key is with that
> object. That means it doesn't matter to the lookup optimization if the
> object itself has changed:
>
> class Puddle(object): pass
> d = {}
> key, val = Puddle(), Puddle()
> key.foo = "foo"; val.foo = "bar"
> d[key] = val

IMHO the discussion gone too far. See the PEP: the goal is to
implement efficient guards on namespaces. In namespaces, keys are
short immutable strings. Not funny objects. Keys come from the Python
source code, like "x" from "x=1".

Again, if the dict value is mutable (like functions implemented in
pure Python), they are dedicated guards for that, but no PEP is
required to implement these guards ;-) See the PEP 510: to specialize
a function, you have to a pass a *list* of guards. There is not
arbitrary limit on the number of guards :-) (But I expect to have less
than 10 guards for the common case, or more likely just a few ones.)

> There would be very few operations that can be optimized like this. In
> practical terms, the only ones that I can think of are what you might
> call "computed literals" - like (2+3j), they aren't technically
> literals, but the programmer thinks of them that way.

FYI Python 2 peephole optimizer is not able to optimize all operations
like that because of technical issues, it's limited :-/ Python 3
peephole optimizer is better ;-)
http://faster-cpython.readthedocs.org/bytecode.html#cpython-peephole-optimizer

In more general, the optimizer is limited because it works on the
bytecode which is difficult to manipulate. It's difficult to implement
simple optimizations. For example, the peephole optimizer of Python 3
maintains a "stack of constants" to implement constant folding.
Implemeting constant folding on the AST is much easier, you can browse
the subtree of a node with nice Python objects. If you are curious,
you can take a look at the constant folding optimization step of
astoptimizer:
https://hg.python.org/sandbox/fatpython/file/tip/Lib/astoptimizer/const_fold.py

It implements more optimizations than the peephole optimizer:
http://faster-cpython.readthedocs.org/fat_python.html#comparison-with-the-peephole-optimizer

> Things like
> module-level constants (the 'stat' module comes to mind),

In Python, it's rare to manipulate directly constants. But it's common
to access constant coming from a different namespace, like constants
at the module level. To implement constant propagation on these
constants, we also need guards on the namespace to disable the
optimization when a "constant" is modified (which can be done for unit
tests for example).

For example, the base64 module defines:

   _b32alphabet = b'ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'

and later in a function, it uses:

    {v: k for k, v in enumerate(_b32alphabet)}

This "complex" dict-comprehension calling enumerate() can be replaced
with a simpler dict literal: {65: 0, 66: 1, ...} or dict(((65,0),
(66,0), ...)). I don't know if it's the best example, I don't know if
it's really much faster, it's just to explain the general idea.

Another simple example: pickle.py defines many constants like MARK =
b'(' and TUPLE = b(', defined at module-level. Later it uses for
example MARK + TUPLE. Using guards on the global namespace, it's
possible to replace MARK + TUPLE with b'((' to avoid two dict lookups
and a call to byte string concatenation. Again, it's a simple explain
to explain the principle.

Usually, a single optimization alone is not interesting. It's when you
combine optimization that it becomes interesting. For example,
constant propagation + constant folding + simplify iterable + loop
unrolling + elimitation of unused variables really makes the code
simpler (and more efficient).

> a small
> handful of simple transformations, and maybe some text<->bytes
> transformations (eg "abc".encode("ascii") could be replaced at
> compile-time with b"abc"). There won't be very many others, I suspect.

It's possible to optimize some method calls on builtin types without
guards since it's not possible to replace methods of builtin types. My
old AST optimizer implements such optimizations (I didn't reimplement
them in my new AST optimizer yet), but alone they are not really
interesting in term of performance.

Victor