CINXE.COM

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta name="color-scheme" content="light dark"> <title>PEP 509 – Add a private version to dict | peps.python.org</title> <link rel="shortcut icon" href="../_static/py.png"> <link rel="canonical" href="https://peps.python.org/pep-0509/"> <link rel="stylesheet" href="../_static/style.css" type="text/css"> <link rel="stylesheet" href="../_static/mq.css" type="text/css"> <link rel="stylesheet" href="../_static/pygments.css" type="text/css" media="(prefers-color-scheme: light)" id="pyg-light"> <link rel="stylesheet" href="../_static/pygments_dark.css" type="text/css" media="(prefers-color-scheme: dark)" id="pyg-dark"> <link rel="alternate" type="application/rss+xml" title="Latest PEPs" href="https://peps.python.org/peps.rss"> <meta property="og:title" content='PEP 509 – Add a private version to dict | peps.python.org'> <meta property="og:description" content="Add a new private version to the builtin dict type, incremented at each dictionary creation and at each dictionary change, to implement fast guards on namespaces."> <meta property="og:type" content="website"> <meta property="og:url" content="https://peps.python.org/pep-0509/"> <meta property="og:site_name" content="Python Enhancement Proposals (PEPs)"> <meta property="og:image" content="https://peps.python.org/_static/og-image.png"> <meta property="og:image:alt" content="Python PEPs"> <meta property="og:image:width" content="200"> <meta property="og:image:height" content="200"> <meta name="description" content="Add a new private version to the builtin dict type, incremented at each dictionary creation and at each dictionary change, to implement fast guards on namespaces."> <meta name="theme-color" content="#3776ab"> </head> <body> <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <symbol id="svg-sun-half" viewBox="0 0 24 24" pointer-events="all"> <title>Following system colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <circle cx="12" cy="12" r="9"></circle> <path d="M12 3v18m0-12l4.65-4.65M12 14.3l7.37-7.37M12 19.6l8.85-8.85"></path> </svg> </symbol> <symbol id="svg-moon" viewBox="0 0 24 24" pointer-events="all"> <title>Selected dark colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <path stroke="none" d="M0 0h24v24H0z" fill="none"></path> <path d="M12 3c.132 0 .263 0 .393 0a7.5 7.5 0 0 0 7.92 12.446a9 9 0 1 1 -8.313 -12.454z"></path> </svg> </symbol> <symbol id="svg-sun" viewBox="0 0 24 24" pointer-events="all"> <title>Selected light colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <circle cx="12" cy="12" r="5"></circle> <line x1="12" y1="1" x2="12" y2="3"></line> <line x1="12" y1="21" x2="12" y2="23"></line> <line x1="4.22" y1="4.22" x2="5.64" y2="5.64"></line> <line x1="18.36" y1="18.36" x2="19.78" y2="19.78"></line> <line x1="1" y1="12" x2="3" y2="12"></line> <line x1="21" y1="12" x2="23" y2="12"></line> <line x1="4.22" y1="19.78" x2="5.64" y2="18.36"></line> <line x1="18.36" y1="5.64" x2="19.78" y2="4.22"></line> </svg> </symbol> </svg> <script> document.documentElement.dataset.colour_scheme = localStorage.getItem("colour_scheme") || "auto" </script> <section id="pep-page-section"> <header> <h1>Python Enhancement Proposals</h1> <ul class="breadcrumbs"> <li><a href="https://www.python.org/" title="The Python Programming Language">Python</a> » </li> <li><a href="../pep-0000/">PEP Index</a> » </li> <li>PEP 509</li> </ul> <button id="colour-scheme-cycler" onClick="setColourScheme(nextColourScheme())"> <svg aria-hidden="true" class="colour-scheme-icon-when-auto"><use href="#svg-sun-half"></use></svg> <svg aria-hidden="true" class="colour-scheme-icon-when-dark"><use href="#svg-moon"></use></svg> <svg aria-hidden="true" class="colour-scheme-icon-when-light"><use href="#svg-sun"></use></svg> Toggle light / dark / auto colour theme </button> </header> <article> <section id="pep-content"> <h1 class="page-title">PEP 509 – Add a private version to dict</h1> <dl class="rfc2822 field-list simple"> <dt class="field-odd">Author:</dt> <dd class="field-odd">Victor Stinner <vstinner at python.org></dd> <dt class="field-even">Status:</dt> <dd class="field-even"><abbr title="Replaced by another succeeding PEP">Superseded</abbr></dd> <dt class="field-odd">Type:</dt> <dd class="field-odd"><abbr title="Normative PEP with a new feature for Python, implementation change for CPython or interoperability standard for the ecosystem">Standards Track</abbr></dd> <dt class="field-even">Created:</dt> <dd class="field-even">04-Jan-2016</dd> <dt class="field-odd">Python-Version:</dt> <dd class="field-odd">3.6</dd> <dt class="field-even">Post-History:</dt> <dd class="field-even"><a class="reference external" href="https://mail.python.org/archives/list/python-ideas@python.org/thread/FPB7MLWMRSCYQVOUYN2SUV4NR47TPPG3/" title="Python-Ideas thread">08-Jan-2016</a>, <a class="reference external" href="https://mail.python.org/archives/list/python-dev@python.org/thread/AY42HER5DFKA7DJV25AL7YX5DQPF6RMV/" title="Python-Dev thread">11-Jan-2016</a>, <a class="reference external" href="https://mail.python.org/archives/list/python-dev@python.org/thread/UXEQIDSTVLAHJVDQJMJPCU2QZGYMBV2H/" title="Python-Dev thread">14-Apr-2016</a>, <a class="reference external" href="https://mail.python.org/archives/list/python-dev@python.org/thread/2S562SVRK5S2QKP3SFONG357Z72I6KLE/" title="Python-Dev thread">19-Apr-2016</a></dd> <dt class="field-odd">Superseded-By:</dt> <dd class="field-odd"><a class="reference external" href="../pep-0699/">699</a></dd> <dt class="field-even">Resolution:</dt> <dd class="field-even"><a class="reference external" href="https://mail.python.org/archives/list/python-dev@python.org/message/QFVJV6YQOUSWIYY4FBORY647YCBSCIMQ/">Python-Dev message</a></dd> </dl> <hr class="docutils" /> <section id="contents"> <details><summary>Table of Contents</summary><ul class="simple"> <li><a class="reference internal" href="#abstract">Abstract</a></li> <li><a class="reference internal" href="#rationale">Rationale</a></li> <li><a class="reference internal" href="#guard-example">Guard example</a></li> <li><a class="reference internal" href="#usage-of-the-dict-version">Usage of the dict version</a><ul> <li><a class="reference internal" href="#speedup-method-calls">Speedup method calls</a></li> <li><a class="reference internal" href="#specialized-functions-using-guards">Specialized functions using guards</a></li> <li><a class="reference internal" href="#pyjion">Pyjion</a></li> <li><a class="reference internal" href="#cython">Cython</a></li> <li><a class="reference internal" href="#unladen-swallow">Unladen Swallow</a></li> </ul> </li> <li><a class="reference internal" href="#changes">Changes</a></li> <li><a class="reference internal" href="#backwards-compatibility">Backwards Compatibility</a></li> <li><a class="reference internal" href="#implementation-and-performance">Implementation and Performance</a></li> <li><a class="reference internal" href="#integer-overflow">Integer overflow</a></li> <li><a class="reference internal" href="#alternatives">Alternatives</a><ul> <li><a class="reference internal" href="#expose-the-version-at-python-level-as-a-read-only-version-property">Expose the version at Python level as a read-only __version__ property</a></li> <li><a class="reference internal" href="#add-a-version-to-each-dict-entry">Add a version to each dict entry</a></li> <li><a class="reference internal" href="#add-a-new-dict-subtype">Add a new dict subtype</a></li> </ul> </li> <li><a class="reference internal" href="#prior-art">Prior Art</a><ul> <li><a class="reference internal" href="#method-cache-and-type-version-tag">Method cache and type version tag</a></li> <li><a class="reference internal" href="#globals-builtins-cache">Globals / builtins cache</a></li> <li><a class="reference internal" href="#cached-globals-builtins-lookup">Cached globals+builtins lookup</a></li> <li><a class="reference internal" href="#guard-against-changing-dict-during-iteration">Guard against changing dict during iteration</a></li> <li><a class="reference internal" href="#pysizer">PySizer</a></li> </ul> </li> <li><a class="reference internal" href="#discussion">Discussion</a></li> <li><a class="reference internal" href="#acceptance">Acceptance</a></li> <li><a class="reference internal" href="#copyright">Copyright</a></li> </ul> </details></section> <section id="abstract"> <h2><a class="toc-backref" href="#abstract" role="doc-backlink">Abstract</a></h2> Add a new private version to the builtin <code class="docutils literal notranslate">dict</code> type, incremented at each dictionary creation and at each dictionary change, to implement fast guards on namespaces. </section> <section id="rationale"> <h2><a class="toc-backref" href="#rationale" role="doc-backlink">Rationale</a></h2> In Python, the builtin <code class="docutils literal notranslate">dict</code> type is used by many instructions. For example, the <code class="docutils literal notranslate">LOAD_GLOBAL</code> instruction looks up a variable in the global namespace, or in the builtins namespace (two dict lookups). Python uses <code class="docutils literal notranslate">dict</code> for the builtins namespace, globals namespace, type namespaces, instance namespaces, etc. The local namespace (function namespace) is usually optimized to an array, but it can be a dict too. Python is hard to optimize because almost everything is mutable: builtin functions, function code, global variables, local variables, … can be modified at runtime. Implementing optimizations respecting the Python semantics requires to detect when “something changes”: we will call these checks “guards”. The speedup of optimizations depends on the speed of guard checks. This PEP proposes to add a private version to dictionaries to implement fast guards on namespaces. Dictionary lookups can be skipped if the version does not change, which is the common case for most namespaces. The version is globally unique, so checking the version is also enough to verify that the namespace dictionary was not replaced with a new dictionary. When the dictionary version does not change, the performance of a guard does not depend on the number of watched dictionary entries: the complexity is O(1). Example of optimization: copy the value of a global variable to function constants. This optimization requires a guard on the global variable to check if it was modified after it was copied. If the global variable is not modified, the function uses the cached copy. If the global variable is modified, the function uses a regular lookup, and maybe also deoptimizes the function (to remove the overhead of the guard check for next function calls). See the <a class="pep reference internal" href="../pep-0510/" title="PEP 510 – Specialize functions with guards">510 – Specialized functions with guards</a> for concrete usage of guards to specialize functions and for a more general rationale on Python static optimizers. </section> <section id="guard-example"> <h2><a class="toc-backref" href="#guard-example" role="doc-backlink">Guard example</a></h2> Pseudo-code of a fast guard to check if a dictionary entry was modified (created, updated or deleted) using a hypothetical <code class="docutils literal notranslate">dict_get_version(dict)</code> function: <div class="highlight-default notranslate"><div class="highlight"><pre>UNSET = object() class GuardDictKey: def __init__(self, dict, key): self.dict = dict self.key = key self.value = dict.get(key, UNSET) self.version = dict_get_version(dict) def check(self): """Return True if the dictionary entry did not change and the dictionary was not replaced.""" # read the version of the dictionary version = dict_get_version(self.dict) if version == self.version: # Fast-path: dictionary lookup avoided return True # lookup in the dictionary value = self.dict.get(self.key, UNSET) if value is self.value: # another key was modified: # cache the new dictionary version self.version = version return True # the key was modified return False </pre></div> </div> </section> <section id="usage-of-the-dict-version"> <h2><a class="toc-backref" href="#usage-of-the-dict-version" role="doc-backlink">Usage of the dict version</a></h2> <section id="speedup-method-calls"> <h3><a class="toc-backref" href="#speedup-method-calls" role="doc-backlink">Speedup method calls</a></h3> Yury Selivanov wrote a <a class="reference external" href="https://bugs.python.org/issue26110">patch to optimize method calls</a>. The patch depends on the <a class="reference external" href="https://bugs.python.org/issue26219">“implement per-opcode cache in ceval”</a> 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 <code class="docutils literal notranslate">exec()</code> with the globals parameter for example. In this case, the globals dictionary was replaced and the cache must also be invalidated. </section> <section id="specialized-functions-using-guards"> <h3><a class="toc-backref" href="#specialized-functions-using-guards" role="doc-backlink">Specialized functions using guards</a></h3> <a class="pep reference internal" href="../pep-0510/" title="PEP 510 – Specialize functions with guards">PEP 510</a> proposes an API to support specialized functions with guards. It allows to implement static optimizers for Python without breaking the Python semantics. The <a class="reference external" href="http://fatoptimizer.readthedocs.org/">fatoptimizer</a> of the <a class="reference external" href="http://faster-cpython.readthedocs.org/fat_python.html">FAT Python</a> project is an example of a static Python optimizer. It implements many optimizations which require guards on namespaces: <ul class="simple"> <li>Call pure builtins: to replace <code class="docutils literal notranslate">len("abc")</code> with <code class="docutils literal notranslate">3</code>, guards on <code class="docutils literal notranslate">builtins.__dict__['len']</code> and <code class="docutils literal notranslate">globals()['len']</code> are required</li> <li>Loop unrolling: to unroll the loop <code class="docutils literal notranslate">for i in range(...): ...</code>, guards on <code class="docutils literal notranslate">builtins.__dict__['range']</code> and <code class="docutils literal notranslate">globals()['range']</code> are required</li> <li>etc.</li> </ul> </section> <section id="pyjion"> <h3><a class="toc-backref" href="#pyjion" role="doc-backlink">Pyjion</a></h3> According of Brett Cannon, one of the two main developers of Pyjion, Pyjion can benefit from dictionary version to implement optimizations. <a class="reference external" href="https://github.com/Microsoft/Pyjion">Pyjion</a> is a JIT compiler for Python based upon CoreCLR (Microsoft .NET Core runtime). </section> <section id="cython"> <h3><a class="toc-backref" href="#cython" role="doc-backlink">Cython</a></h3> Cython can benefit from dictionary version to implement optimizations. <a class="reference external" href="http://cython.org/">Cython</a> is an optimising static compiler for both the Python programming language and the extended Cython programming language. </section> <section id="unladen-swallow"> <h3><a class="toc-backref" href="#unladen-swallow" role="doc-backlink">Unladen Swallow</a></h3> 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: <a class="reference external" href="https://code.google.com/p/unladen-swallow/wiki/ProjectPlan">Unladen Swallow ProjectPlan</a>). Unladen Swallow is a fork of CPython 2.6.1 adding a JIT compiler implemented with LLVM. The project stopped in 2011: <a class="reference external" href="http://qinsb.blogspot.com.au/2011/03/unladen-swallow-retrospective.html">Unladen Swallow Retrospective</a>. </section> </section> <section id="changes"> <h2><a class="toc-backref" href="#changes" role="doc-backlink">Changes</a></h2> Add a <code class="docutils literal notranslate">ma_version_tag</code> field to the <code class="docutils literal notranslate">PyDictObject</code> structure with the C type <code class="docutils literal notranslate">PY_UINT64_T</code>, 64-bit unsigned integer. Add also a global dictionary version. Each time a dictionary is created, the global version is incremented and the dictionary version is initialized to the global version. Each time the dictionary content is modified, the global version must be incremented and copied to the dictionary version. Dictionary methods which can modify its content: <ul class="simple"> <li><code class="docutils literal notranslate">clear()</code></li> <li><code class="docutils literal notranslate">pop(key)</code></li> <li><code class="docutils literal notranslate">popitem()</code></li> <li><code class="docutils literal notranslate">setdefault(key, value)</code></li> <li><code class="docutils literal notranslate">__delitem__(key)</code></li> <li><code class="docutils literal notranslate">__setitem__(key, value)</code></li> <li><code class="docutils literal notranslate">update(...)</code></li> </ul> The choice of increasing or not the version when a dictionary method does not change its content is left to the Python implementation. A Python implementation can decide to not increase the version to avoid dictionary lookups in guards. Examples of cases when dictionary methods don’t modify its content: <ul class="simple"> <li><code class="docutils literal notranslate">clear()</code> if the dict is already empty</li> <li><code class="docutils literal notranslate">pop(key)</code> if the key does not exist</li> <li><code class="docutils literal notranslate">popitem()</code> if the dict is empty</li> <li><code class="docutils literal notranslate">setdefault(key, value)</code> if the key already exists</li> <li><code class="docutils literal notranslate">__delitem__(key)</code> if the key does not exist</li> <li><code class="docutils literal notranslate">__setitem__(key, value)</code> if the new value is identical to the current value</li> <li><code class="docutils literal notranslate">update()</code> if called without argument or if new values are identical to current values</li> </ul> Setting a key to a new value equals to the old value is also considered as an operation modifying the dictionary content. Two different empty dictionaries must have a different version to be able to identify a dictionary just by its version. It allows to verify in a guard that a namespace was not replaced without storing a strong reference to the dictionary. Using a borrowed reference does not work: if the old dictionary is destroyed, it is possible that a new dictionary is allocated at the same memory address. By the way, dictionaries don’t support weak references. The version increase must be atomic. In CPython, the Global Interpreter Lock (GIL) already protects <code class="docutils literal notranslate">dict</code> methods to make changes atomic. Example using a hypothetical <code class="docutils literal notranslate">dict_get_version(dict)</code> function: <div class="highlight-default notranslate"><div class="highlight"><pre>>>> d = {} >>> dict_get_version(d) 100 >>> d['key'] = 'value' >>> dict_get_version(d) 101 >>> d['key'] = 'new value' >>> dict_get_version(d) 102 >>> del d['key'] >>> dict_get_version(d) 103 </pre></div> </div> The field is called <code class="docutils literal notranslate">ma_version_tag</code>, rather than <code class="docutils literal notranslate">ma_version</code>, to suggest to compare it using <code class="docutils literal notranslate">version_tag == old_version_tag</code>, rather than <code class="docutils literal notranslate">version <= old_version</code> which becomes wrong after an integer overflow. </section> <section id="backwards-compatibility"> <h2><a class="toc-backref" href="#backwards-compatibility" role="doc-backlink">Backwards Compatibility</a></h2> Since the <code class="docutils literal notranslate">PyDictObject</code> structure is not part of the stable ABI and the new dictionary version not exposed at the Python scope, changes are backward compatible. </section> <section id="implementation-and-performance"> <h2><a class="toc-backref" href="#implementation-and-performance" role="doc-backlink">Implementation and Performance</a></h2> The <a class="reference external" href="https://bugs.python.org/issue26058">issue #26058: PEP 509: Add ma_version_tag to PyDictObject</a> contains a patch implementing this PEP. On pybench and timeit microbenchmarks, the patch does not seem to add any overhead on dictionary operations. For example, the following timeit micro-benchmarks takes 318 nanoseconds before and after the change: <div class="highlight-default notranslate"><div class="highlight"><pre>python3.6 -m timeit 'd={1: 0}; d[2]=0; d[3]=0; d[4]=0; del d[1]; del d[2]; d.clear()' </pre></div> </div> When the version does not change, <code class="docutils literal notranslate">PyDict_GetItem()</code> takes 14.8 ns for a dictionary lookup, whereas a guard check only takes 3.8 ns. Moreover, a guard can watch for multiple keys. For example, for an optimization using 10 global variables in a function, 10 dictionary lookups costs 148 ns, whereas the guard still only costs 3.8 ns when the version does not change (39x as fast). The <a class="reference external" href="http://fatoptimizer.readthedocs.org/en/latest/fat.html">fat module</a> implements such guards: <code class="docutils literal notranslate">fat.GuardDict</code> is based on the dictionary version. </section> <section id="integer-overflow"> <h2><a class="toc-backref" href="#integer-overflow" role="doc-backlink">Integer overflow</a></h2> The implementation uses the C type <code class="docutils literal notranslate">PY_UINT64_T</code> to store the version: a 64 bits unsigned integer. The C code uses <code class="docutils literal notranslate">version++</code>. On integer overflow, the version is wrapped to <code class="docutils literal notranslate">0</code> (and then continues to be incremented) according to the C standard. After an integer overflow, a guard can succeed whereas the watched dictionary key was modified. The bug only occurs at a guard check if there are exactly <code class="docutils literal notranslate">2 ** 64</code> dictionary creations or modifications since the previous guard check. If a dictionary is modified every nanosecond, <code class="docutils literal notranslate">2 ** 64</code> modifications takes longer than 584 years. Using a 32-bit version, it only takes 4 seconds. That’s why a 64-bit unsigned type is also used on 32-bit systems. A dictionary lookup at the C level takes 14.8 ns. A risk of a bug every 584 years is acceptable. </section> <section id="alternatives"> <h2><a class="toc-backref" href="#alternatives" role="doc-backlink">Alternatives</a></h2> <section id="expose-the-version-at-python-level-as-a-read-only-version-property"> <h3><a class="toc-backref" href="#expose-the-version-at-python-level-as-a-read-only-version-property" role="doc-backlink">Expose the version at Python level as a read-only __version__ property</a></h3> The first version of the PEP proposed to expose the dictionary version as a read-only <code class="docutils literal notranslate">__version__</code> property at Python level, and also to add the property to <code class="docutils literal notranslate">collections.UserDict</code> (since this type must mimic the <code class="docutils literal notranslate">dict</code> API). There are multiple issues: <ul> <li>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 <code class="docutils literal notranslate">dict</code> type in practice.</li> <li>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.</li> <li>Exposing the dictionary version at the Python level can lead the false assumption on performances. Checking <code class="docutils literal notranslate">dict.__version__</code> 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%):<div class="highlight-default notranslate"><div class="highlight"><pre>$ 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 </pre></div> </div> </li> <li>The <code class="docutils literal notranslate">__version__</code> can be wrapped on integer overflow. It is error prone: using <code class="docutils literal notranslate">dict.__version__ <= guard_version</code> is wrong, <code class="docutils literal notranslate">dict.__version__ == guard_version</code> must be used instead to reduce the risk of bug on integer overflow (even if the integer overflow is unlikely in practice).</li> </ul> Mandatory bikeshedding on the property name: <ul class="simple"> <li><code class="docutils literal notranslate">__cache_token__</code>: name proposed by Alyssa Coghlan, name coming from <a class="reference external" href="https://docs.python.org/3/library/abc.html#abc.get_cache_token">abc.get_cache_token()</a>.</li> <li><code class="docutils literal notranslate">__version__</code></li> <li><code class="docutils literal notranslate">__version_tag__</code></li> <li><code class="docutils literal notranslate">__timestamp__</code></li> </ul> </section> <section id="add-a-version-to-each-dict-entry"> <h3><a class="toc-backref" href="#add-a-version-to-each-dict-entry" role="doc-backlink">Add a version to each dict entry</a></h3> 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 <code class="docutils literal notranslate">me_version_tag</code> field to the <code class="docutils literal notranslate">PyDictKeyEntry</code> structure, the field has the C type <code class="docutils literal notranslate">PY_UINT64_T</code>. 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 <code class="docutils literal notranslate">dict_get_version(dict)</code> and <code class="docutils literal notranslate">dict_get_entry_version(dict)</code> functions: <div class="highlight-default notranslate"><div class="highlight"><pre>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 </pre></div> </div> 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: <ul class="simple"> <li><a class="pep reference internal" href="../pep-0393/" title="PEP 393 – Flexible String Representation">PEP 393</a> – Flexible String Representation</li> <li><a class="pep reference internal" href="../pep-0412/" title="PEP 412 – Key-Sharing Dictionary">PEP 412</a> – Key-Sharing Dictionary</li> </ul> </section> <section id="add-a-new-dict-subtype"> <h3><a class="toc-backref" href="#add-a-new-dict-subtype" role="doc-backlink">Add a new dict subtype</a></h3> Add a new <code class="docutils literal notranslate">verdict</code> type, subtype of <code class="docutils literal notranslate">dict</code>. When guards are needed, use the <code class="docutils literal notranslate">verdict</code> for namespaces (module namespace, type namespace, instance namespace, etc.) instead of <code class="docutils literal notranslate">dict</code>. Leave the <code class="docutils literal notranslate">dict</code> 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 <code class="docutils literal notranslate">dict</code> type. Issues: <ul class="simple"> <li><code class="docutils literal notranslate">exec()</code> requires a <code class="docutils literal notranslate">dict</code> for globals and locals. A lot of code use <code class="docutils literal notranslate">globals={}</code>. It is not possible to cast the <code class="docutils literal notranslate">dict</code> to a <code class="docutils literal notranslate">dict</code> subtype because the caller expects the <code class="docutils literal notranslate">globals</code> parameter to be modified (<code class="docutils literal notranslate">dict</code> is mutable).</li> <li>C functions call directly <code class="docutils literal notranslate">PyDict_xxx()</code> functions, instead of calling <code class="docutils literal notranslate">PyObject_xxx()</code> if the object is a <code class="docutils literal notranslate">dict</code> subtype</li> <li><code class="docutils literal notranslate">PyDict_CheckExact()</code> check fails on <code class="docutils literal notranslate">dict</code> subtype, whereas some functions require the exact <code class="docutils literal notranslate">dict</code> type.</li> <li><code class="docutils literal notranslate">Python/ceval.c</code> does not completely supports dict subtypes for namespaces</li> </ul> The <code class="docutils literal notranslate">exec()</code> issue is a blocker issue. Other issues: <ul class="simple"> <li>The garbage collector has a special code to “untrack” <code class="docutils literal notranslate">dict</code> instances. If a <code class="docutils literal notranslate">dict</code> subtype is used for namespaces, the garbage collector can be unable to break some reference cycles.</li> <li>Some functions have a fast-path for <code class="docutils literal notranslate">dict</code> which would not be taken for <code class="docutils literal notranslate">dict</code> subtypes, and so it would make Python a little bit slower.</li> </ul> </section> </section> <section id="prior-art"> <h2><a class="toc-backref" href="#prior-art" role="doc-backlink">Prior Art</a></h2> <section id="method-cache-and-type-version-tag"> <h3><a class="toc-backref" href="#method-cache-and-type-version-tag" role="doc-backlink">Method cache and type version tag</a></h3> 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” (<code class="docutils literal notranslate">tp_version_tag</code>) and a “valid version tag” flag to types (the <code class="docutils literal notranslate">PyTypeObject</code> structure). The type version tag is not exposed at the Python level. The version tag has the C type <code class="docutils literal notranslate">unsigned int</code>. 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 <code class="docutils literal notranslate">unsigned int</code>. 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 <code class="docutils literal notranslate">0</code>. See <a class="reference external" href="https://bugs.python.org/issue1685986">Method cache (issue #1685986)</a> and <a class="reference external" href="https://bugs.python.org/issue1700288">Armin’s method cache optimization updated for Python 2.6 (issue #1700288)</a>. </section> <section id="globals-builtins-cache"> <h3><a class="toc-backref" href="#globals-builtins-cache" role="doc-backlink">Globals / builtins cache</a></h3> In 2010, Antoine Pitrou proposed a <a class="reference external" href="http://bugs.python.org/issue10401">Globals / builtins cache (issue #10401)</a> which adds a private <code class="docutils literal notranslate">ma_version</code> field to the <code class="docutils literal notranslate">PyDictObject</code> structure (<code class="docutils literal notranslate">dict</code> type), the field has the C type <code class="docutils literal notranslate">Py_ssize_t</code>. The patch adds a “global and builtin cache” to functions and frames, and changes <code class="docutils literal notranslate">LOAD_GLOBAL</code> and <code class="docutils literal notranslate">STORE_GLOBAL</code> instructions to use the cache. The change on the <code class="docutils literal notranslate">PyDictObject</code> structure is very similar to this PEP. </section> <section id="cached-globals-builtins-lookup"> <h3><a class="toc-backref" href="#cached-globals-builtins-lookup" role="doc-backlink">Cached globals+builtins lookup</a></h3> In 2006, Andrea Griffini proposed a patch implementing a <a class="reference external" href="https://bugs.python.org/issue1616125">Cached globals+builtins lookup optimization</a>. The patch adds a private <code class="docutils literal notranslate">timestamp</code> field to the <code class="docutils literal notranslate">PyDictObject</code> structure (<code class="docutils literal notranslate">dict</code> type), the field has the C type <code class="docutils literal notranslate">size_t</code>. Thread on python-dev: <a class="reference external" href="https://mail.python.org/pipermail/python-dev/2006-December/070348.html">About dictionary lookup caching</a> (December 2006). </section> <section id="guard-against-changing-dict-during-iteration"> <h3><a class="toc-backref" href="#guard-against-changing-dict-during-iteration" role="doc-backlink">Guard against changing dict during iteration</a></h3> In 2013, Serhiy Storchaka proposed <a class="reference external" href="https://bugs.python.org/issue19332">Guard against changing dict during iteration (issue #19332)</a> which adds a <code class="docutils literal notranslate">ma_count</code> field to the <code class="docutils literal notranslate">PyDictObject</code> structure (<code class="docutils literal notranslate">dict</code> type), the field has the C type <code class="docutils literal notranslate">size_t</code>. This field is incremented when the dictionary is modified. </section> <section id="pysizer"> <h3><a class="toc-backref" href="#pysizer" role="doc-backlink">PySizer</a></h3> <a class="reference external" href="http://pysizer.8325.org/">PySizer</a>: 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 <code class="docutils literal notranslate">key_time</code> and <code class="docutils literal notranslate">value_time</code> 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. </section> </section> <section id="discussion"> <h2><a class="toc-backref" href="#discussion" role="doc-backlink">Discussion</a></h2> Thread on the mailing lists: <ul class="simple"> <li>python-dev: <a class="reference external" href="https://mail.python.org/pipermail/python-dev/2016-April/144250.html">Updated PEP 509</a></li> <li>python-dev: <a class="reference external" href="https://mail.python.org/pipermail/python-dev/2016-April/144137.html">RFC: PEP 509: Add a private version to dict</a></li> <li>python-dev: <a class="reference external" href="https://mail.python.org/pipermail/python-dev/2016-January/142685.html">PEP 509: Add a private version to dict</a> (January 2016)</li> <li>python-ideas: <a class="reference external" href="https://mail.python.org/pipermail/python-ideas/2016-January/037702.html">RFC: PEP: Add dict.__version__</a> (January 2016)</li> </ul> </section> <section id="acceptance"> <h2><a class="toc-backref" href="#acceptance" role="doc-backlink">Acceptance</a></h2> The PEP was <a class="reference external" href="https://mail.python.org/pipermail/python-dev/2016-September/146298.html">accepted on 2016-09-07 by Guido van Rossum</a>. The PEP implementation has since been committed to the repository. </section> <section id="copyright"> <h2><a class="toc-backref" href="#copyright" role="doc-backlink">Copyright</a></h2> This document has been placed in the public domain. </section> </section> <hr class="docutils" /> Source: <a class="reference external" href="https://github.com/python/peps/blob/main/peps/pep-0509.rst">https://github.com/python/peps/blob/main/peps/pep-0509.rst</a> Last modified: <a class="reference external" href="https://github.com/python/peps/commits/main/peps/pep-0509.rst">2025-02-01 08:55:40 GMT</a> </article> <nav id="pep-sidebar"> <h2>Contents</h2> <ul> <li><a class="reference internal" href="#abstract">Abstract</a></li> <li><a class="reference internal" href="#rationale">Rationale</a></li> <li><a class="reference internal" href="#guard-example">Guard example</a></li> <li><a class="reference internal" href="#usage-of-the-dict-version">Usage of the dict version</a><ul> <li><a class="reference internal" href="#speedup-method-calls">Speedup method calls</a></li> <li><a class="reference internal" href="#specialized-functions-using-guards">Specialized functions using guards</a></li> <li><a class="reference internal" href="#pyjion">Pyjion</a></li> <li><a class="reference internal" href="#cython">Cython</a></li> <li><a class="reference internal" href="#unladen-swallow">Unladen Swallow</a></li> </ul> </li> <li><a class="reference internal" href="#changes">Changes</a></li> <li><a class="reference internal" href="#backwards-compatibility">Backwards Compatibility</a></li> <li><a class="reference internal" href="#implementation-and-performance">Implementation and Performance</a></li> <li><a class="reference internal" href="#integer-overflow">Integer overflow</a></li> <li><a class="reference internal" href="#alternatives">Alternatives</a><ul> <li><a class="reference internal" href="#expose-the-version-at-python-level-as-a-read-only-version-property">Expose the version at Python level as a read-only __version__ property</a></li> <li><a class="reference internal" href="#add-a-version-to-each-dict-entry">Add a version to each dict entry</a></li> <li><a class="reference internal" href="#add-a-new-dict-subtype">Add a new dict subtype</a></li> </ul> </li> <li><a class="reference internal" href="#prior-art">Prior Art</a><ul> <li><a class="reference internal" href="#method-cache-and-type-version-tag">Method cache and type version tag</a></li> <li><a class="reference internal" href="#globals-builtins-cache">Globals / builtins cache</a></li> <li><a class="reference internal" href="#cached-globals-builtins-lookup">Cached globals+builtins lookup</a></li> <li><a class="reference internal" href="#guard-against-changing-dict-during-iteration">Guard against changing dict during iteration</a></li> <li><a class="reference internal" href="#pysizer">PySizer</a></li> </ul> </li> <li><a class="reference internal" href="#discussion">Discussion</a></li> <li><a class="reference internal" href="#acceptance">Acceptance</a></li> <li><a class="reference internal" href="#copyright">Copyright</a></li> </ul> <a id="source" href="https://github.com/python/peps/blob/main/peps/pep-0509.rst">Page Source (GitHub)</a> </nav> </section> <script src="../_static/colour_scheme.js"></script> <script src="../_static/wrap_tables.js"></script> <script src="../_static/sticky_banner.js"></script> </body> </html>