mirror of https://github.com/python/peps
534 lines
41 KiB
HTML
534 lines
41 KiB
HTML
|
||
<!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 603 – Adding a frozenmap type to collections | peps.python.org</title>
|
||
<link rel="shortcut icon" href="../_static/py.png">
|
||
<link rel="canonical" href="https://peps.python.org/pep-0603/">
|
||
<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 603 – Adding a frozenmap type to collections | peps.python.org'>
|
||
<meta property="og:type" content="website">
|
||
<meta property="og:url" content="https://peps.python.org/pep-0603/">
|
||
<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="Python Enhancement Proposals (PEPs)">
|
||
<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 603</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>
|
||
<span class="visually-hidden">Toggle light / dark / auto colour theme</span>
|
||
</button>
|
||
</header>
|
||
<article>
|
||
<section id="pep-content">
|
||
<h1 class="page-title">PEP 603 – Adding a frozenmap type to collections</h1>
|
||
<dl class="rfc2822 field-list simple">
|
||
<dt class="field-odd">Author<span class="colon">:</span></dt>
|
||
<dd class="field-odd">Yury Selivanov <yury at edgedb.com></dd>
|
||
<dt class="field-even">Discussions-To<span class="colon">:</span></dt>
|
||
<dd class="field-even"><a class="reference external" href="https://discuss.python.org/t/pep-603-adding-a-frozenmap-type-to-collections/2318/">Discourse thread</a></dd>
|
||
<dt class="field-odd">Status<span class="colon">:</span></dt>
|
||
<dd class="field-odd"><abbr title="Proposal under active discussion and revision">Draft</abbr></dd>
|
||
<dt class="field-even">Type<span class="colon">:</span></dt>
|
||
<dd class="field-even"><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-odd">Created<span class="colon">:</span></dt>
|
||
<dd class="field-odd">12-Sep-2019</dd>
|
||
<dt class="field-even">Post-History<span class="colon">:</span></dt>
|
||
<dd class="field-even">12-Sep-2019</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="#specification">Specification</a><ul>
|
||
<li><a class="reference internal" href="#construction">Construction</a></li>
|
||
<li><a class="reference internal" href="#data-access">Data Access</a></li>
|
||
<li><a class="reference internal" href="#mutation">Mutation</a><ul>
|
||
<li><a class="reference internal" href="#frozenmap-including-key-value">frozenmap.including(key, value)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-excluding-key">frozenmap.excluding(key)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-union-mapping-none-kw">frozenmap.union(mapping=None, **kw)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-mutating">frozenmap.mutating()</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#iteration">Iteration</a></li>
|
||
<li><a class="reference internal" href="#hashing">Hashing</a></li>
|
||
<li><a class="reference internal" href="#typing">Typing</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#implementation">Implementation</a><ul>
|
||
<li><a class="reference internal" href="#hamt">HAMT</a></li>
|
||
<li><a class="reference internal" href="#performance">Performance</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#design-considerations">Design Considerations</a><ul>
|
||
<li><a class="reference internal" href="#why-frozenmap-and-not-frozenmap">Why “frozenmap” and not “FrozenMap”</a></li>
|
||
<li><a class="reference internal" href="#why-frozenmap-and-not-frozendict">Why “frozenmap” and not “frozendict”</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#id9">Implementation</a></li>
|
||
<li><a class="reference internal" href="#references">References</a></li>
|
||
<li><a class="reference internal" href="#acknowledgments">Acknowledgments</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>
|
||
<p>A <em>persistent data structure</em> is defined as a data structure that
|
||
preserves the previous version of the data when the data is modified.
|
||
Such data structures are effectively <em>immutable</em>, as operations on
|
||
them do not update the structure in-place, but instead always yield
|
||
a new updated structure (see <a class="footnote-reference brackets" href="#id12" id="id1">[0]</a> for more details.)</p>
|
||
<p>This PEP proposes to add a new fully persistent and immutable mapping
|
||
type called <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> to the <code class="docutils literal notranslate"><span class="pre">collections</span></code> module.</p>
|
||
<p>The bulk of <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code>’s reference implementation is already
|
||
used in CPython to implement the <code class="docutils literal notranslate"><span class="pre">contextvars</span></code> module.</p>
|
||
</section>
|
||
<section id="rationale">
|
||
<h2><a class="toc-backref" href="#rationale" role="doc-backlink">Rationale</a></h2>
|
||
<p>Python has two immutable collection types: <code class="docutils literal notranslate"><span class="pre">tuple</span></code> and
|
||
<code class="docutils literal notranslate"><span class="pre">frozenset</span></code>. These types can be used to represent immutable lists
|
||
and sets. However, a way to represent immutable <em>mappings</em> does not yet
|
||
exist, and this PEP proposes a <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> to implement an
|
||
immutable <em>mapping</em>.</p>
|
||
<p>The proposed <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> type:</p>
|
||
<ul class="simple">
|
||
<li>implements the <code class="docutils literal notranslate"><span class="pre">collections.abc.Mapping</span></code> protocol,</li>
|
||
<li>supports pickling, and</li>
|
||
<li>provides an API for efficient creation of “modified” versions.</li>
|
||
</ul>
|
||
<p>The following use cases illustrate why an immutable mapping is
|
||
desirable:</p>
|
||
<ul>
|
||
<li>Immutable mappings are hashable which allows their use
|
||
as dictionary keys or set elements.<p>This hashable property permits functions decorated with
|
||
<code class="docutils literal notranslate"><span class="pre">@functools.lru_cache()</span></code> to accept immutable mappings as
|
||
arguments. Unlike an immutable mapping, passing a plain <code class="docutils literal notranslate"><span class="pre">dict</span></code>
|
||
to such a function results in error.</p>
|
||
</li>
|
||
<li>Immutable mappings can hold complex state. Since immutable mappings
|
||
can be copied by reference, transactional mutation of state can be
|
||
efficiently implemented.</li>
|
||
<li>Immutable mappings can be used to safely share dictionaries across
|
||
thread and asynchronous task boundaries. The immutability makes it
|
||
easier to reason about threads and asynchronous tasks.</li>
|
||
</ul>
|
||
<p>Lastly, CPython <a class="footnote-reference brackets" href="#id13" id="id2">[1]</a> already contains the main portion of the C code
|
||
required for the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> implementation. The C code already
|
||
exists to implement the <code class="docutils literal notranslate"><span class="pre">contextvars</span></code> module (see <a class="pep reference internal" href="../pep-0567/" title="PEP 567 – Context Variables">PEP 567</a> for
|
||
more details.) Exposing this C code via a public collection type
|
||
drastically increases the number of users of the code. This leads to
|
||
increased code quality by discovering bugs and improving performance
|
||
which without a <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> collection would be very challenging
|
||
because most programs use the <code class="docutils literal notranslate"><span class="pre">contextvars</span></code> module indirectly.</p>
|
||
</section>
|
||
<section id="specification">
|
||
<h2><a class="toc-backref" href="#specification" role="doc-backlink">Specification</a></h2>
|
||
<p>A new public immutable type <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> is added to the
|
||
<code class="docutils literal notranslate"><span class="pre">collections</span></code> module.</p>
|
||
<section id="construction">
|
||
<h3><a class="toc-backref" href="#construction" role="doc-backlink">Construction</a></h3>
|
||
<p><code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> implements a <code class="docutils literal notranslate"><span class="pre">dict</span></code>-like construction API:</p>
|
||
<ul class="simple">
|
||
<li><code class="docutils literal notranslate"><span class="pre">frozenmap()</span></code> creates a new empty immutable mapping;</li>
|
||
<li><code class="docutils literal notranslate"><span class="pre">frozenmap(**kwargs)</span></code> creates a mapping from <code class="docutils literal notranslate"><span class="pre">**kwargs</span></code>, e.g.
|
||
<code class="docutils literal notranslate"><span class="pre">frozenmap(x=10,</span> <span class="pre">y=0,</span> <span class="pre">z=-1)</span></code></li>
|
||
<li><code class="docutils literal notranslate"><span class="pre">frozenmap(collection)</span></code> creates a mapping from the passed
|
||
<code class="docutils literal notranslate"><span class="pre">collection</span></code> object. The passed <code class="docutils literal notranslate"><span class="pre">collection</span></code> object can be:<ul>
|
||
<li>a <code class="docutils literal notranslate"><span class="pre">dict</span></code>,</li>
|
||
<li>another <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code>,</li>
|
||
<li>an object with an <code class="docutils literal notranslate"><span class="pre">items()</span></code> method that is expected to return
|
||
a series of key/value tuples, or</li>
|
||
<li>an iterable of key/value tuples.</li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
</section>
|
||
<section id="data-access">
|
||
<h3><a class="toc-backref" href="#data-access" role="doc-backlink">Data Access</a></h3>
|
||
<p><code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> implements the <code class="docutils literal notranslate"><span class="pre">collection.abc.Mapping</span></code> protocol.
|
||
Therefore, getters, membership checks, and iteration work the same
|
||
way that they would for a <code class="docutils literal notranslate"><span class="pre">dict</span></code>:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">m</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="s1">'bar'</span><span class="p">)</span>
|
||
|
||
<span class="k">assert</span> <span class="n">m</span><span class="p">[</span><span class="s1">'foo'</span><span class="p">]</span> <span class="o">==</span> <span class="s1">'bar'</span>
|
||
<span class="k">assert</span> <span class="n">m</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s1">'foo'</span><span class="p">)</span> <span class="o">==</span> <span class="s1">'bar'</span>
|
||
<span class="k">assert</span> <span class="s1">'foo'</span> <span class="ow">in</span> <span class="n">m</span>
|
||
|
||
<span class="k">assert</span> <span class="s1">'baz'</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">m</span>
|
||
<span class="k">assert</span> <span class="n">m</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s1">'baz'</span><span class="p">,</span> <span class="s1">'missing'</span><span class="p">)</span> <span class="o">==</span> <span class="s1">'missing'</span>
|
||
|
||
<span class="k">assert</span> <span class="n">m</span> <span class="o">==</span> <span class="n">m</span>
|
||
<span class="k">assert</span> <span class="n">m</span> <span class="o">!=</span> <span class="n">frozenmap</span><span class="p">()</span> <span class="c1"># m is not equal to an empty frozenmap</span>
|
||
|
||
<span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span>
|
||
|
||
<span class="c1"># etc.</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
<section id="mutation">
|
||
<h3><a class="toc-backref" href="#mutation" role="doc-backlink">Mutation</a></h3>
|
||
<p><code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> instances are immutable. That said, it is possible
|
||
to efficiently produce mutated <em>copies</em> of the immutable instance.</p>
|
||
<p>The complexity of mutation operations is O(log N) and the resulting
|
||
<code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> copies often consume very little additional memory due
|
||
to the use of structural sharing (read <a class="footnote-reference brackets" href="#id18" id="id3">[6]</a> for more details.)</p>
|
||
<section id="frozenmap-including-key-value">
|
||
<h4><a class="toc-backref" href="#frozenmap-including-key-value" role="doc-backlink">frozenmap.including(key, value)</a></h4>
|
||
<p>The method creates a new <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> copy with a new <em>key</em> / <em>value</em>
|
||
pair:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">m</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span>
|
||
<span class="n">m2</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">including</span><span class="p">(</span><span class="s1">'bar'</span><span class="p">,</span> <span class="mi">100</span><span class="p">)</span>
|
||
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 1})</span>
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m2</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 1, 'bar': 100})</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
<section id="frozenmap-excluding-key">
|
||
<h4><a class="toc-backref" href="#frozenmap-excluding-key" role="doc-backlink">frozenmap.excluding(key)</a></h4>
|
||
<p>The method produces a copy of the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> which does not
|
||
include a deleted <em>key</em>:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">m</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">bar</span><span class="o">=</span><span class="mi">100</span><span class="p">)</span>
|
||
|
||
<span class="n">m2</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">excluding</span><span class="p">(</span><span class="s1">'foo'</span><span class="p">)</span>
|
||
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 1, 'bar': 100})</span>
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m2</span><span class="p">)</span> <span class="c1"># will print frozenmap({'bar': 1})</span>
|
||
|
||
<span class="n">m3</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">excluding</span><span class="p">(</span><span class="s1">'spam'</span><span class="p">)</span> <span class="c1"># will throw a KeyError('spam')</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
<section id="frozenmap-union-mapping-none-kw">
|
||
<h4><a class="toc-backref" href="#frozenmap-union-mapping-none-kw" role="doc-backlink">frozenmap.union(mapping=None, **kw)</a></h4>
|
||
<p>The method produces a copy of the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> and adds or modifies
|
||
multiple key/values for the created copy. The signature of
|
||
the method matches the signature of the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> constructor:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">m</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span>
|
||
|
||
<span class="n">m2</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">union</span><span class="p">({</span><span class="s1">'spam'</span><span class="p">:</span> <span class="s1">'ham'</span><span class="p">})</span>
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m2</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 1, 'spam': 'ham'})</span>
|
||
|
||
<span class="n">m3</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">union</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="mi">100</span><span class="p">,</span> <span class="n">y</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m3</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 100, 'y': 2})</span>
|
||
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="c1"># will print frozenmap({'foo': 1})</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>Calling the <code class="docutils literal notranslate"><span class="pre">union()</span></code> method to add/replace N keys is more efficient
|
||
than calling the <code class="docutils literal notranslate"><span class="pre">including()</span></code> method N times.</p>
|
||
</section>
|
||
<section id="frozenmap-mutating">
|
||
<h4><a class="toc-backref" href="#frozenmap-mutating" role="doc-backlink">frozenmap.mutating()</a></h4>
|
||
<p>The method allows efficient copying of a <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> instance with
|
||
multiple modifications applied. This method is especially useful
|
||
when the frozenmap in question contains thousands of key/value pairs
|
||
and there’s a need to update many of them in a performance-critical
|
||
section of the code.</p>
|
||
<p>The <code class="docutils literal notranslate"><span class="pre">frozenmap.mutating()</span></code> method returns a mutable dict-like
|
||
copy of the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> object: an instance of
|
||
<code class="docutils literal notranslate"><span class="pre">collections.FrozenMapCopy</span></code>.</p>
|
||
<p>The <code class="docutils literal notranslate"><span class="pre">FrozenMapCopy</span></code> objects:</p>
|
||
<ul class="simple">
|
||
<li>are copy-on-write views of the data of <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> instances
|
||
they were created from;</li>
|
||
<li>are mutable, although any mutations on them do not affect the
|
||
<code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> instances they were created from;</li>
|
||
<li>can be passed to the <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> constructor; creating a
|
||
frozenmap from a <code class="docutils literal notranslate"><span class="pre">FrozenMapCopy</span></code> object is an O(1)
|
||
operation;</li>
|
||
<li>have O(log N) complexity for get/set operations; creating
|
||
them is an O(1) operation;</li>
|
||
<li>have a <code class="docutils literal notranslate"><span class="pre">FrozenMapCopy.close()</span></code> method that prevents any
|
||
further access/mutation of the data;</li>
|
||
<li>can be used as a context manager.</li>
|
||
</ul>
|
||
<p>The below example illustrates how <code class="docutils literal notranslate"><span class="pre">mutating()</span></code> can be used with
|
||
a context manager:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">numbers</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">((</span><span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">**</span> <span class="mi">2</span><span class="p">)</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">1_000_000</span><span class="p">))</span>
|
||
|
||
<span class="k">with</span> <span class="n">numbers</span><span class="o">.</span><span class="n">mutating</span><span class="p">()</span> <span class="k">as</span> <span class="n">copy</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">numbers</span><span class="p">:</span>
|
||
<span class="k">if</span> <span class="ow">not</span> <span class="p">(</span><span class="n">numbers</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">%</span> <span class="mi">997</span><span class="p">):</span>
|
||
<span class="k">del</span> <span class="n">copy</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
|
||
|
||
<span class="n">numbers_without_997_multiples</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">copy</span><span class="p">)</span>
|
||
|
||
<span class="c1"># at this point, *numbers* still has 1_000_000 key/values, and</span>
|
||
<span class="c1"># *numbers_without_997_multiples* is a copy of *numbers* without</span>
|
||
<span class="c1"># values that are multiples of 997.</span>
|
||
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">numbers</span><span class="p">:</span>
|
||
<span class="k">if</span> <span class="ow">not</span> <span class="p">(</span><span class="n">numbers</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">%</span> <span class="mi">593</span><span class="p">):</span>
|
||
<span class="k">del</span> <span class="n">copy</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
|
||
|
||
<span class="n">numbers_without_593_multiples</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">(</span><span class="n">copy</span><span class="p">)</span>
|
||
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">copy</span><span class="p">[</span><span class="mi">10</span><span class="p">])</span> <span class="c1"># will print 100.</span>
|
||
|
||
<span class="nb">print</span><span class="p">(</span><span class="n">copy</span><span class="p">[</span><span class="mi">10</span><span class="p">])</span> <span class="c1"># This will throw a ValueError as *copy*</span>
|
||
<span class="c1"># has been closed when the "with" block</span>
|
||
<span class="c1"># was executed.</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
</section>
|
||
<section id="iteration">
|
||
<h3><a class="toc-backref" href="#iteration" role="doc-backlink">Iteration</a></h3>
|
||
<p>As <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> implements the standard <code class="docutils literal notranslate"><span class="pre">collections.abc.Mapping</span></code>
|
||
protocol, so all expected methods of iteration are supported:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">assert</span> <span class="nb">list</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">==</span> <span class="p">[</span><span class="s1">'foo'</span><span class="p">]</span>
|
||
<span class="k">assert</span> <span class="nb">list</span><span class="p">(</span><span class="n">m</span><span class="o">.</span><span class="n">items</span><span class="p">())</span> <span class="o">==</span> <span class="p">[(</span><span class="s1">'foo'</span><span class="p">,</span> <span class="s1">'bar'</span><span class="p">)]</span>
|
||
<span class="k">assert</span> <span class="nb">list</span><span class="p">(</span><span class="n">m</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> <span class="o">==</span> <span class="p">[</span><span class="s1">'foo'</span><span class="p">]</span>
|
||
<span class="k">assert</span> <span class="nb">list</span><span class="p">(</span><span class="n">m</span><span class="o">.</span><span class="n">values</span><span class="p">())</span> <span class="o">==</span> <span class="p">[</span><span class="s1">'bar'</span><span class="p">]</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>Iteration in <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code>, unlike in <code class="docutils literal notranslate"><span class="pre">dict</span></code>, does not preserve the
|
||
insertion order.</p>
|
||
</section>
|
||
<section id="hashing">
|
||
<h3><a class="toc-backref" href="#hashing" role="doc-backlink">Hashing</a></h3>
|
||
<p><code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> instances can be hashable just like <code class="docutils literal notranslate"><span class="pre">tuple</span></code> objects:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nb">hash</span><span class="p">(</span><span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="s1">'bar'</span><span class="p">))</span> <span class="c1"># works</span>
|
||
<span class="nb">hash</span><span class="p">(</span><span class="n">frozenmap</span><span class="p">(</span><span class="n">foo</span><span class="o">=</span><span class="p">[]))</span> <span class="c1"># will throw an error</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
<section id="typing">
|
||
<h3><a class="toc-backref" href="#typing" role="doc-backlink">Typing</a></h3>
|
||
<p>It is possible to use the standard typing notation for frozenmaps:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">m</span><span class="p">:</span> <span class="n">frozenmap</span><span class="p">[</span><span class="nb">str</span><span class="p">,</span> <span class="nb">int</span><span class="p">]</span> <span class="o">=</span> <span class="n">frozenmap</span><span class="p">()</span>
|
||
</pre></div>
|
||
</div>
|
||
</section>
|
||
</section>
|
||
<section id="implementation">
|
||
<h2><a class="toc-backref" href="#implementation" role="doc-backlink">Implementation</a></h2>
|
||
<p>The proposed <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> immutable type uses a Hash Array Mapped
|
||
Trie (HAMT) data structure. Functional programming languages,
|
||
like Clojure, use HAMT to efficiently implement immutable hash tables,
|
||
vectors, and sets.</p>
|
||
<section id="hamt">
|
||
<h3><a class="toc-backref" href="#hamt" role="doc-backlink">HAMT</a></h3>
|
||
<p>The key design contract of HAMT is the guarantee of a predictable
|
||
<em>value</em> when given the hash of a <em>key</em>. For a pair of <em>key</em> and <em>value</em>,
|
||
the hash of the <em>key</em> can be used to determine the location of
|
||
<em>value</em> in the hash map tree.</p>
|
||
<p>Immutable mappings implemented with HAMT have O(log N) performance
|
||
for <code class="docutils literal notranslate"><span class="pre">set()</span></code> and <code class="docutils literal notranslate"><span class="pre">get()</span></code> operations. This efficiency is possible
|
||
because mutation operations only affect one branch of the tree,
|
||
making it possible to reuse non-mutated branches, and, therefore,
|
||
avoiding copying of unmodified data.</p>
|
||
<p>Read more about HAMT in <a class="footnote-reference brackets" href="#id17" id="id4">[5]</a>. The CPython implementation <a class="footnote-reference brackets" href="#id13" id="id5">[1]</a> has a
|
||
fairly detailed description of the algorithm as well.</p>
|
||
</section>
|
||
<section id="performance">
|
||
<h3><a class="toc-backref" href="#performance" role="doc-backlink">Performance</a></h3>
|
||
<figure class="align-center" id="id19">
|
||
<a class="invert-in-dark-mode reference internal image-reference" href="../_images/pep-0603-hamt_vs_dict.png"><img alt="../_images/pep-0603-hamt_vs_dict.png" class="invert-in-dark-mode" src="../_images/pep-0603-hamt_vs_dict.png" style="width: 100%;" /></a>
|
||
<figcaption>
|
||
<p><span class="caption-text">Figure 1. Benchmark code can be found here: <a class="footnote-reference brackets" href="#id15" id="id6">[3]</a>.</span></p>
|
||
</figcaption>
|
||
</figure>
|
||
<p>The above chart demonstrates that:</p>
|
||
<ul class="simple">
|
||
<li><code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> implemented with HAMT displays near O(1) performance
|
||
for all benchmarked dictionary sizes.</li>
|
||
<li><code class="docutils literal notranslate"><span class="pre">dict.copy()</span></code> becomes less efficient when using around
|
||
100-200 items.</li>
|
||
</ul>
|
||
<figure class="align-center" id="id20">
|
||
<a class="invert-in-dark-mode reference internal image-reference" href="../_images/pep-0603-lookup_hamt.png"><img alt="../_images/pep-0603-lookup_hamt.png" class="invert-in-dark-mode" src="../_images/pep-0603-lookup_hamt.png" style="width: 100%;" /></a>
|
||
<figcaption>
|
||
<p><span class="caption-text">Figure 2. Benchmark code can be found here: <a class="footnote-reference brackets" href="#id16" id="id7">[4]</a>.</span></p>
|
||
</figcaption>
|
||
</figure>
|
||
<p>Figure 2 compares the lookup costs of <code class="docutils literal notranslate"><span class="pre">dict</span></code> versus a HAMT-based
|
||
immutable mapping. HAMT lookup time is ~30% slower than Python dict
|
||
lookups on average. This performance difference exists since traversing
|
||
a shallow tree is less efficient than lookup in a flat continuous array.</p>
|
||
<p>Further to that, quoting <a class="footnote-reference brackets" href="#id18" id="id8">[6]</a>: “[using HAMT] means that in practice
|
||
while insertions, deletions, and lookups into a persistent hash array
|
||
mapped trie have a computational complexity of O(log n), for most
|
||
applications they are effectively constant time, as it would require
|
||
an extremely large number of entries to make any operation take more
|
||
than a dozen steps.”</p>
|
||
</section>
|
||
</section>
|
||
<section id="design-considerations">
|
||
<h2><a class="toc-backref" href="#design-considerations" role="doc-backlink">Design Considerations</a></h2>
|
||
<section id="why-frozenmap-and-not-frozenmap">
|
||
<h3><a class="toc-backref" href="#why-frozenmap-and-not-frozenmap" role="doc-backlink">Why “frozenmap” and not “FrozenMap”</a></h3>
|
||
<p>The lower-case “frozenmap” resonates well with the <code class="docutils literal notranslate"><span class="pre">frozenset</span></code>
|
||
built-in as well as with types like <code class="docutils literal notranslate"><span class="pre">collections.defaultdict</span></code>.</p>
|
||
</section>
|
||
<section id="why-frozenmap-and-not-frozendict">
|
||
<h3><a class="toc-backref" href="#why-frozenmap-and-not-frozendict" role="doc-backlink">Why “frozenmap” and not “frozendict”</a></h3>
|
||
<p>“Dict” has a very specific meaning in Python:</p>
|
||
<ul class="simple">
|
||
<li>a dict is a concrete implementation of <code class="docutils literal notranslate"><span class="pre">abc.MutableMapping</span></code> with
|
||
O(1) get and set operations (<code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> has O(log N) complexity);</li>
|
||
<li>Python dicts preserve insertion order.</li>
|
||
</ul>
|
||
<p>The proposed <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> does not have these mentioned
|
||
properties. Instead, <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> has an O(log N) cost of set/get
|
||
operations, and it only implements the <code class="docutils literal notranslate"><span class="pre">abc.Mapping</span></code> protocol.</p>
|
||
</section>
|
||
</section>
|
||
<section id="id9">
|
||
<h2><a class="toc-backref" href="#id9" role="doc-backlink">Implementation</a></h2>
|
||
<p>The full implementation of the proposed <code class="docutils literal notranslate"><span class="pre">frozenmap</span></code> type is
|
||
available at <a class="footnote-reference brackets" href="#id14" id="id10">[2]</a>. The package includes C and pure Python
|
||
implementations of the type.</p>
|
||
<p>See also the HAMT collection implementation as part of the
|
||
CPython project tree here: <a class="footnote-reference brackets" href="#id13" id="id11">[1]</a>.</p>
|
||
</section>
|
||
<section id="references">
|
||
<h2><a class="toc-backref" href="#references" role="doc-backlink">References</a></h2>
|
||
<aside class="footnote-list brackets">
|
||
<aside class="footnote brackets" id="id12" role="doc-footnote">
|
||
<dt class="label" id="id12">[<a href="#id1">0</a>]</dt>
|
||
<dd><a class="reference external" href="https://en.wikipedia.org/wiki/Persistent_data_structure">https://en.wikipedia.org/wiki/Persistent_data_structure</a></aside>
|
||
<aside class="footnote brackets" id="id13" role="doc-footnote">
|
||
<dt class="label" id="id13">[1]<em> (<a href='#id2'>1</a>, <a href='#id5'>2</a>, <a href='#id11'>3</a>) </em></dt>
|
||
<dd><a class="reference external" href="https://github.com/python/cpython/blob/3.8/Python/hamt.c">https://github.com/python/cpython/blob/3.8/Python/hamt.c</a></aside>
|
||
<aside class="footnote brackets" id="id14" role="doc-footnote">
|
||
<dt class="label" id="id14">[<a href="#id10">2</a>]</dt>
|
||
<dd><a class="reference external" href="https://github.com/MagicStack/immutables">https://github.com/MagicStack/immutables</a></aside>
|
||
<aside class="footnote brackets" id="id15" role="doc-footnote">
|
||
<dt class="label" id="id15">[<a href="#id6">3</a>]</dt>
|
||
<dd><a class="reference external" href="https://gist.github.com/1st1/be5a1c10aceb0775d0406e879cf87344">https://gist.github.com/1st1/be5a1c10aceb0775d0406e879cf87344</a></aside>
|
||
<aside class="footnote brackets" id="id16" role="doc-footnote">
|
||
<dt class="label" id="id16">[<a href="#id7">4</a>]</dt>
|
||
<dd><a class="reference external" href="https://gist.github.com/1st1/dbe27f2e14c30cce6f0b5fddfc8c437e">https://gist.github.com/1st1/dbe27f2e14c30cce6f0b5fddfc8c437e</a></aside>
|
||
<aside class="footnote brackets" id="id17" role="doc-footnote">
|
||
<dt class="label" id="id17">[<a href="#id4">5</a>]</dt>
|
||
<dd><a class="reference external" href="https://en.wikipedia.org/wiki/Hash_array_mapped_trie#cite_note-bagwell-1">https://en.wikipedia.org/wiki/Hash_array_mapped_trie#cite_note-bagwell-1</a></aside>
|
||
<aside class="footnote brackets" id="id18" role="doc-footnote">
|
||
<dt class="label" id="id18">[6]<em> (<a href='#id3'>1</a>, <a href='#id8'>2</a>) </em></dt>
|
||
<dd><a class="reference external" href="https://en.wikipedia.org/wiki/Persistent_data_structure#Trees">https://en.wikipedia.org/wiki/Persistent_data_structure#Trees</a></aside>
|
||
</aside>
|
||
</section>
|
||
<section id="acknowledgments">
|
||
<h2><a class="toc-backref" href="#acknowledgments" role="doc-backlink">Acknowledgments</a></h2>
|
||
<p>I thank Carol Willing, Łukasz Langa, Larry Hastings, and
|
||
Guido van Rossum for their feedback, ideas, edits, and discussions
|
||
around this PEP.</p>
|
||
</section>
|
||
<section id="copyright">
|
||
<h2><a class="toc-backref" href="#copyright" role="doc-backlink">Copyright</a></h2>
|
||
<p>This document is placed in the public domain or under the
|
||
CC0-1.0-Universal license, whichever is more permissive.</p>
|
||
</section>
|
||
</section>
|
||
<hr class="docutils" />
|
||
<p>Source: <a class="reference external" href="https://github.com/python/peps/blob/main/peps/pep-0603.rst">https://github.com/python/peps/blob/main/peps/pep-0603.rst</a></p>
|
||
<p>Last modified: <a class="reference external" href="https://github.com/python/peps/commits/main/peps/pep-0603.rst">2023-09-09 17:39:29 GMT</a></p>
|
||
|
||
</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="#specification">Specification</a><ul>
|
||
<li><a class="reference internal" href="#construction">Construction</a></li>
|
||
<li><a class="reference internal" href="#data-access">Data Access</a></li>
|
||
<li><a class="reference internal" href="#mutation">Mutation</a><ul>
|
||
<li><a class="reference internal" href="#frozenmap-including-key-value">frozenmap.including(key, value)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-excluding-key">frozenmap.excluding(key)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-union-mapping-none-kw">frozenmap.union(mapping=None, **kw)</a></li>
|
||
<li><a class="reference internal" href="#frozenmap-mutating">frozenmap.mutating()</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#iteration">Iteration</a></li>
|
||
<li><a class="reference internal" href="#hashing">Hashing</a></li>
|
||
<li><a class="reference internal" href="#typing">Typing</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#implementation">Implementation</a><ul>
|
||
<li><a class="reference internal" href="#hamt">HAMT</a></li>
|
||
<li><a class="reference internal" href="#performance">Performance</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#design-considerations">Design Considerations</a><ul>
|
||
<li><a class="reference internal" href="#why-frozenmap-and-not-frozenmap">Why “frozenmap” and not “FrozenMap”</a></li>
|
||
<li><a class="reference internal" href="#why-frozenmap-and-not-frozendict">Why “frozenmap” and not “frozendict”</a></li>
|
||
</ul>
|
||
</li>
|
||
<li><a class="reference internal" href="#id9">Implementation</a></li>
|
||
<li><a class="reference internal" href="#references">References</a></li>
|
||
<li><a class="reference internal" href="#acknowledgments">Acknowledgments</a></li>
|
||
<li><a class="reference internal" href="#copyright">Copyright</a></li>
|
||
</ul>
|
||
|
||
<br>
|
||
<a id="source" href="https://github.com/python/peps/blob/main/peps/pep-0603.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> |