537 lines
42 KiB
HTML
537 lines
42 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:description" content="A persistent data structure is defined as a data structure that preserves the previous version of the data when the data is modified. Such data structures are effectively immutable, as operations on them do not update the structure in-place, but instead...">
|
||
<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="A persistent data structure is defined as a data structure that preserves the previous version of the data when the data is modified. Such data structures are effectively immutable, as operations on them do not update the structure in-place, but instead...">
|
||
<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> |