Speedup method calls

Yury Selivanov wrote a patch to optimize method calls. The patch depends on the “implement per-opcode cache in ceval” patch which requires dictionary versions to invalidate the cache if the globals dictionary or the builtins dictionary has been modified.

The cache also requires that the dictionary version is globally unique. It is possible to define a function in a namespace and call it in a different namespace, using exec() with the globals parameter for example. In this case, the globals dictionary was replaced and the cache must also be invalidated.

Specialized functions using guards

PEP 510 proposes an API to support specialized functions with guards. It allows to implement static optimizers for Python without breaking the Python semantics.

The fatoptimizer of the FAT Python project is an example of a static Python optimizer. It implements many optimizations which require guards on namespaces:

• Call pure builtins: to replace len("abc") with 3, guards on builtins.__dict__['len'] and globals()['len'] are required
• Loop unrolling: to unroll the loop for i in range(...): ..., guards on builtins.__dict__['range'] and globals()['range'] are required
• etc.

Pyjion

According of Brett Cannon, one of the two main developers of Pyjion, Pyjion can benefit from dictionary version to implement optimizations.

Pyjion is a JIT compiler for Python based upon CoreCLR (Microsoft .NET Core runtime).

Cython

Cython can benefit from dictionary version to implement optimizations.

Cython is an optimising static compiler for both the Python programming language and the extended Cython programming language.

Unladen Swallow

Even if dictionary version was not explicitly mentioned, optimizing globals and builtins lookup was part of the Unladen Swallow plan: “Implement one of the several proposed schemes for speeding lookups of globals and builtins.” (source: Unladen Swallow ProjectPlan).

Unladen Swallow is a fork of CPython 2.6.1 adding a JIT compiler implemented with LLVM. The project stopped in 2011: Unladen Swallow Retrospective.

Expose the version at Python level as a read-only __version__ property

The first version of the PEP proposed to expose the dictionary version as a read-only __version__ property at Python level, and also to add the property to collections.UserDict (since this type must mimic the dict API).

There are multiple issues:

• To be consistent and avoid bad surprises, the version must be added to all mapping types. Implementing a new mapping type would require extra work for no benefit, since the version is only required on the dict type in practice.
• All Python implementations would have to implement this new property, it gives more work to other implementations, whereas they may not use the dictionary version at all.
• Exposing the dictionary version at the Python level can lead the false assumption on performances. Checking dict.__version__ at the Python level is not faster than a dictionary lookup. A dictionary lookup in Python has a cost of 48.7 ns and checking the version has a cost of 47.5 ns, the difference is only 1.2 ns (3%):

  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd["33"] == 33'
  10000000 loops, best of 3: 0.0487 usec per loop
  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd.__version__ == 100'
  10000000 loops, best of 3: 0.0475 usec per loop
  

• The __version__ can be wrapped on integer overflow. It is error prone: using dict.__version__ <= guard_version is wrong, dict.__version__ == guard_version must be used instead to reduce the risk of bug on integer overflow (even if the integer overflow is unlikely in practice).

Mandatory bikeshedding on the property name:

• __cache_token__: name proposed by Alyssa Coghlan, name coming from abc.get_cache_token().
• __version__
• __version_tag__
• __timestamp__

Add a version to each dict entry

A single version per dictionary requires to keep a strong reference to the value which can keep the value alive longer than expected. If we add also a version per dictionary entry, the guard can only store the entry version (a simple integer) to avoid the strong reference to the value: only strong references to the dictionary and to the key are needed.

Changes: add a me_version_tag field to the PyDictKeyEntry structure, the field has the C type PY_UINT64_T. When a key is created or modified, the entry version is set to the dictionary version which is incremented at any change (create, modify, delete).

Pseudo-code of a fast guard to check if a dictionary key was modified using hypothetical dict_get_version(dict) and dict_get_entry_version(dict) functions:

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.dict_version = dict_get_version(dict)
        self.entry_version = dict_get_entry_version(dict, key)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        dict_version = dict_get_version(self.dict)
        if dict_version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary to read the entry version
        entry_version = get_dict_key_version(dict, key)
        if entry_version == self.entry_version:
            # another key was modified:
            # cache the new dictionary version
            self.dict_version = dict_version
            self.entry_version = entry_version
            return True

        # the key was modified
        return False

The main drawback of this option is the impact on the memory footprint. It increases the size of each dictionary entry, so the overhead depends on the number of buckets (dictionary entries, used or not used). For example, it increases the size of each dictionary entry by 8 bytes on 64-bit system.

In Python, the memory footprint matters and the trend is to reduce it. Examples:

• PEP 393 – Flexible String Representation
• PEP 412 – Key-Sharing Dictionary

Add a new dict subtype

Add a new verdict type, subtype of dict. When guards are needed, use the verdict for namespaces (module namespace, type namespace, instance namespace, etc.) instead of dict.

Leave the dict type unchanged to not add any overhead (CPU, memory footprint) when guards are not used.

Technical issue: a lot of C code in the wild, including CPython core, expecting the exact dict type. Issues:

• exec() requires a dict for globals and locals. A lot of code use globals={}. It is not possible to cast the dict to a dict subtype because the caller expects the globals parameter to be modified (dict is mutable).
• C functions call directly PyDict_xxx() functions, instead of calling PyObject_xxx() if the object is a dict subtype
• PyDict_CheckExact() check fails on dict subtype, whereas some functions require the exact dict type.
• Python/ceval.c does not completely supports dict subtypes for namespaces

The exec() issue is a blocker issue.

Other issues:

• The garbage collector has a special code to “untrack” dict instances. If a dict subtype is used for namespaces, the garbage collector can be unable to break some reference cycles.
• Some functions have a fast-path for dict which would not be taken for dict subtypes, and so it would make Python a little bit slower.

Method cache and type version tag

In 2007, Armin Rigo wrote a patch to implement a cache of methods. It was merged into Python 2.6. The patch adds a “type attribute cache version tag” (tp_version_tag) and a “valid version tag” flag to types (the PyTypeObject structure).

The type version tag is not exposed at the Python level.

The version tag has the C type unsigned int. The cache is a global hash table of 4096 entries, shared by all types. The cache is global to “make it fast, have a deterministic and low memory footprint, and be easy to invalidate”. Each cache entry has a version tag. A global version tag is used to create the next version tag, it also has the C type unsigned int.

By default, a type has its “valid version tag” flag cleared to indicate that the version tag is invalid. When the first method of the type is cached, the version tag and the “valid version tag” flag are set. When a type is modified, the “valid version tag” flag of the type and its subclasses is cleared. Later, when a cache entry of these types is used, the entry is removed because its version tag is outdated.

On integer overflow, the whole cache is cleared and the global version tag is reset to 0.

See Method cache (issue #1685986) and Armin’s method cache optimization updated for Python 2.6 (issue #1700288).

Globals / builtins cache

In 2010, Antoine Pitrou proposed a Globals / builtins cache (issue #10401) which adds a private ma_version field to the PyDictObject structure (dict type), the field has the C type Py_ssize_t.

The patch adds a “global and builtin cache” to functions and frames, and changes LOAD_GLOBAL and STORE_GLOBAL instructions to use the cache.

The change on the PyDictObject structure is very similar to this PEP.

Cached globals+builtins lookup

In 2006, Andrea Griffini proposed a patch implementing a Cached globals+builtins lookup optimization. The patch adds a private timestamp field to the PyDictObject structure (dict type), the field has the C type size_t.

Thread on python-dev: About dictionary lookup caching (December 2006).

Guard against changing dict during iteration

In 2013, Serhiy Storchaka proposed Guard against changing dict during iteration (issue #19332) which adds a ma_count field to the PyDictObject structure (dict type), the field has the C type size_t. This field is incremented when the dictionary is modified.

PySizer

PySizer: a memory profiler for Python, Google Summer of Code 2005 project by Nick Smallbone.

This project has a patch for CPython 2.4 which adds key_time and value_time fields to dictionary entries. It uses a global process-wide counter for dictionaries, incremented each time that a dictionary is modified. The times are used to decide when child objects first appeared in their parent objects.