Issue 19332: Guard against changing dict during iteration

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> <head> <title> Issue 19332: Guard against changing dict during iteration - Python tracker </title> <link rel="shortcut icon" href="@@file/favicon.ico" /> <link rel="stylesheet" type="text/css" href="@@file/main.css" /> <link rel="stylesheet" type="text/css" href="@@file/style.css" /> <link rel="search" type="application/opensearchdescription+xml" href="@@file/osd.xml" title="Python bug tracker search" /> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <script nonce="b8be05871c2d1423560239b8895cc5f761c8da237f0c3bbb5a8a3a06a4fe5eb3" type="text/javascript"> submitted = false; function submit_once() { if (submitted) { alert("Your request is being processed.\nPlease be patient."); return false; } submitted = true; return true; } function help_window(helpurl, width, height) { HelpWin = window.open('https://bugs.python.org/' + helpurl, 'RoundupHelpWindow', 'scrollbars=yes,resizable=yes,toolbar=no,height='+height+',width='+width); HelpWin.focus () } </script> <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js"></script> <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jqueryui/1.8.15/jquery-ui.js"></script> <script type="text/javascript" src="@@file/issue.item.js"></script> <link rel="stylesheet" type="text/css" href="https://ajax.googleapis.com/ajax/libs/jqueryui/1.8/themes/smoothness/jquery-ui.css" /> </head> <body>  <h1 id="logoheader"> <a accesskey="1" href="." id="logolink"> <img src="@@file/python-logo.gif" alt="homepage" border="0" id="logo" /></a> </h1> <div id="utility-menu">  <div id="searchbox"> <form name="searchform" method="get" action="issue" id="searchform"> <div id="search"> <input type="hidden" name="@columns" value="id,github,activity,title,creator,assignee,status,type" /> <input type="hidden" name="@sort" value="-activity" /> <input type="hidden" name="@filter" value="status" /> <input type="hidden" name="@action" value="searchid" /> <input type="hidden" name="ignore" value="file:content" /> <input class="input-text" id="search-text" name="@search_text" size="10" /> <input type="submit" id="submit" value="search" name="submit" class="input-button" /> <input type="radio" name="status" id="status_notresolved" value="-1,1,3" /> <label for="status_notresolved">open</label> <input type="radio" name="status" checked="checked" id="status_all" value="-1,1,2,3" /> <label for="status_all">all</label> </div> </form> </div> </div> <div id="left-hand-navigation">  <div id="menu"> <ul class="level-one"> <li><a href="https://www.python.org/" title="Go to the Python homepage">Python Home</a></li> <li><a href="https://www.python.org/about/" title="About The Python Language">About</a></li> <li><a href="https://www.python.org/blogs/" title="">News</a></li> <li><a href="https://www.python.org/doc/" title="">Documentation</a></li> <li><a href="https://www.python.org/downloads/" title="">Downloads</a></li> <li><a href="https://www.python.org/community/" title="">Community</a></li> <li><a href="https://www.python.org/psf/" title="Python Software Foundation">Foundation</a></li> <li><a href="https://devguide.python.org/" title="Python Developer's Guide">Developer's Guide</a></li> <li class="selected"><a href="." class="selected" title="Python Issue Tracker">Issue Tracker</a> <ul class="level-two"> <li> <strong>Issues</strong> <ul class="level-three"> <li><a href="issue?@template=search&status=1">Search</a></li> <li><a href="issue?@action=random">Random Issue</a></li> <li> <form method="post" action="issue19332"> <input type="submit" class="form-small" value="Show issue:" /> <input class="form-small" size="4" type="text" name="@number" /> <input type="hidden" name="@type" value="issue" /> <input type="hidden" name="@action" value="show" /> </form> </li> </ul> </li> <li> <strong>Summaries</strong> <ul class="level-three"> <li> <a href="issue?status=1&@sort=-activity&@columns=id%2Cgithub%2Cactivity%2Ctitle%2Ccreator%2Cstatus&@dispname=Issues%20with%20patch&@startwith=0&@group=priority&keywords=2&@action=search&@filter=&@pagesize=50">Issues with patch</a> </li> <li> <a href="issue?status=1&@sort=-activity&@columns=id%2Cgithub%2Cactivity%2Ctitle%2Ccreator%2Cstatus&@dispname=Easy%20issues&@startwith=0&@group=priority&keywords=6&@action=search&@filter=&@pagesize=50">Easy issues</a> </li> <li> <a href="issue?@template=stats">Stats</a> </li> </ul> </li> <li> <strong>User</strong> <form method="post" action="issue19332"> <ul class="level-three"> <li> Login<br /> <input size="10" name="openid_identifier" style="" /><br /> <input size="10" type="password" name="__login_password" /><br /> <input type="hidden" name="@action" value="Login" /> <input type="checkbox" name="remember" id="remember" /> <label for="remember">Remember me?</label><br /> <input class="form-small" type="submit" value="Login" /><br /> <input type="hidden" name="__came_from" value="https://bugs.python.org/issue19332?"> <input type="hidden" name="@sort" value=""/> <input type="hidden" name="@group" value=""/> <input type="hidden" name="@pagesize" value="50"/> <input type="hidden" name="@startwith" value="0"/> </li> <li> </li> <li><a href="user?@template=forgotten">Lost your login?</a></li> </ul> </form> </li> <li> <strong>Administration</strong> <ul class="level-three"> <li> <a href="user?@sort=username">User List</a></li> <li> <a href="user?iscommitter=1&@action=search&@sort=username&@pagesize=300">Committer List</a></li> </ul> </li> <li> <strong>Help</strong> <ul class="level-three"> <li><a href="http://docs.python.org/devguide/triaging.html"> Tracker Documentation</a></li> <li><a href="http://wiki.python.org/moin/TrackerDevelopment"> Tracker Development</a></li> <li><a href="https://github.com/python/psf-infra-meta/issues"> Report Tracker Problem</a></li> </ul> </li> </ul> </li> </ul> </div>  </div>  <div id="content-body"> <div id="body-main"> <div id="content"> <div id="breadcrumb"> Issue19332 </div> <div id="migration-notice"> <div id="migration-images"> <img width="32" src="@@file/python-logo-small.png" /> ➜ <a href="https://github.com/python/cpython/issues"><img width="32" src="@@file/gh-icon.png" /></a> </div> <p>This issue tracker <b>has been migrated to <a href="https://github.com/python/cpython/issues">GitHub</a></b>, and is currently <b>read-only</b>.<br /> For more information, <a title="GitHub FAQs" href="https://devguide.python.org/gh-faq/"> see the GitHub FAQs in the Python's Developer Guide.</a></p> </div> <div> <form method="post" name="itemSynopsis" onsubmit="return submit_once()" enctype="multipart/form-data" action="issue19332"> <div id="gh-issue-link"> <a href="https://github.com/python/cpython/issues/63531"> <img width="32" src="@@file/gh-icon.png" /> <p> <span>This issue has been migrated to GitHub:</span> https://github.com/python/cpython/issues/63531 </p> </a> </div> <fieldset><legend>classification</legend> <table class="form"> <tr> <th class="required"><a href="http://docs.python.org/devguide/triaging.html#title" target="_blank">Title</a>:</th> <td colspan="3"> <span>Guard against changing dict during iteration</span> <input type="hidden" name="title" value="Guard against changing dict during iteration"> </td> </tr> <tr> <th class="required"><a href="http://docs.python.org/devguide/triaging.html#type" target="_blank">Type</a>:</th> <td>enhancement</td> <th><a href="http://docs.python.org/devguide/triaging.html#stage" target="_blank">Stage</a>:</th> <td>patch review</td> </tr> <tr> <th><a href="http://docs.python.org/devguide/triaging.html#components" target="_blank">Components</a>:</th> <td>Interpreter Core</td> <th><a href="http://docs.python.org/devguide/triaging.html#versions" target="_blank">Versions</a>:</th> <td>Python 3.4</td> </tr> </table> </fieldset> <fieldset><legend>process</legend> <table class="form"> <tr> <th><a href="http://docs.python.org/devguide/triaging.html#status" target="_blank">Status</a>:</th> <td>closed</td> <th><a href="http://docs.python.org/devguide/triaging.html#resolution" target="_blank">Resolution</a>:</th> <td>rejected</td> </tr> <tr> <th> <a href="http://docs.python.org/devguide/triaging.html#dependencies" target="_blank">Dependencies</a>: </th> <td> </td> <th><a href="http://docs.python.org/devguide/triaging.html#superseder" target="_blank">Superseder</a>:</th> <td> </td> </tr> <tr> <th> <a href="http://docs.python.org/devguide/triaging.html#assigned-to" target="_blank">Assigned To</a>: </th> <td> rhettinger </td> <th> <a href="http://docs.python.org/devguide/triaging.html#nosy-list" target="_blank">Nosy List</a>: </th> <td> ethan.furman, pitrou, python-dev, rhettinger, serhiy.storchaka, tim.peters </td> </tr> <tr> <th> <a href="http://docs.python.org/devguide/triaging.html#priority" target="_blank">Priority</a>: </th> <td>normal</td> <th> <a href="http://docs.python.org/devguide/triaging.html#keywords" target="_blank">Keywords</a>: </th> <td>patch</td> </tr> </table> </fieldset> </form> <p>Created on <strong>2013-10-21 14:02</strong> by <strong>serhiy.storchaka</strong>, last changed <strong>2022-04-11 14:57</strong> by <strong>admin</strong>. This issue is now <strong style="color:#00F; background-color:inherit;">closed</strong>.</p> <table class="files"> <tr><th colspan="5" class="header">Files</th></tr> <tr> <th>File name</th> <th>Uploaded</th> <th>Description</th> <th>Edit</th> </tr> <tr> <td> <a href="file32279/dict_mutating_iteration.patch">dict_mutating_iteration.patch</a> </td> <td> <span>serhiy.storchaka</span>, <span>2013-10-21 14:02</span> </td> <td></td> <td> <a href="/review/19332/#ps9649">review</a> </td> </tr> <tr> <td> <a href="file32319/dict_mutating_iteration_2.patch">dict_mutating_iteration_2.patch</a> </td> <td> <span>serhiy.storchaka</span>, <span>2013-10-23 19:46</span> </td> <td></td> <td> <a href="/review/19332/#ps9671">review</a> </td> </tr> </table> <table class="messages"> <tr><th colspan="4" class="header">Messages (9)</th></tr> <tr> <th> <a href="#msg200784" id="msg200784">msg200784</a> - <a href="msg200784">(view)</a></th> <th>Author: Serhiy Storchaka (serhiy.storchaka) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-21 14:02</th> </tr> <tr> <td colspan="4" class="content"> <pre>Currently dict iterating is guarded against changing dict's size. However when dict changed during iteration so that it's size left unchanged, this modification left unnoticed. >>> d = dict.fromkeys('abcd') >>> for i in d: ... print(i) ... d[i + 'x'] = None ... del d[i] ... d a dx dxx ax c b In general iterating over mutating dict considered logical error. It is good detect it as early as possible. The proposed patch introduces a counter which changed every time when added or removed key. If an iterator detects that this counter is changed, it raises runtime error.</pre> </td> </tr> <tr> <th> <a href="#msg200995" id="msg200995">msg200995</a> - <a href="msg200995">(view)</a></th> <th>Author: Raymond Hettinger (rhettinger) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-23 04:20</th> </tr> <tr> <td colspan="4" class="content"> <pre>The decision to not monitor adding or removing keys was intentional. It is just not worth the cost in either time or space.</pre> </td> </tr> <tr> <th> <a href="#msg201062" id="msg201062">msg201062</a> - <a href="msg201062">(view)</a></th> <th>Author: Serhiy Storchaka (serhiy.storchaka) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-23 19:46</th> </tr> <tr> <td colspan="4" class="content"> <pre>In the first patch the counter was placed in the _dictkeysobject structure. In the second place it is placed in the PyDictObject so it now has no memory cost. Access time to new counter for non-modifying operations is same as in current code. The only additional cost is time cost for modifying operations. But modifying operations is usually much rare than non-modifying operations, and the incrementing one field takes only small part of the time needed for all operation. I don't think this will affect total performance of real programs.</pre> </td> </tr> <tr> <th> <a href="#msg201065" id="msg201065">msg201065</a> - <a href="msg201065">(view)</a></th> <th>Author: Antoine Pitrou (pitrou) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-23 20:10</th> </tr> <tr> <td colspan="4" class="content"> <pre>If there's no performance regression, then this sounds like a reasonable idea. The remaining question would be whether it can break existing code. Perhaps you should ask python-dev?</pre> </td> </tr> <tr> <th> <a href="#msg201156" id="msg201156">msg201156</a> - <a href="msg201156">(view)</a></th> <th>Author: Raymond Hettinger (rhettinger) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-24 16:34</th> </tr> <tr> <td colspan="4" class="content"> <pre>I disagree with adding such unimportant code to the critical path.</pre> </td> </tr> <tr> <th> <a href="#msg201780" id="msg201780">msg201780</a> - <a href="msg201780">(view)</a></th> <th>Author: Ethan Furman (ethan.furman) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-10-30 21:47</th> </tr> <tr> <td colspan="4" class="content"> <pre>Raymond, please don't be so concise. Is the code unimportant because the scenario is so rare, or something else?</pre> </td> </tr> <tr> <th> <a href="#msg202262" id="msg202262">msg202262</a> - <a href="msg202262">(view)</a></th> <th>Author: Steven D'Aprano (steven.daprano) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-11-06 12:32</th> </tr> <tr> <td colspan="4" class="content"> <pre>Duplicate of this: <a href="http://bugs.python.org/issue6017">http://bugs.python.org/issue6017</a></pre> </td> </tr> <tr> <th> <a href="#msg202287" id="msg202287">msg202287</a> - <a href="msg202287">(view)</a></th> <th>Author: Raymond Hettinger (rhettinger) <span title="Contributor form received">*</span> <img src="@@file/committer.png" title="Python committer" alt="(Python committer)" /></th> <th>Date: 2013-11-06 20:56</th> </tr> <tr> <td colspan="4" class="content"> <pre>A few thoughts: * No existing, working code will benefit from this patch; however, almost all code will pay a price for it -- bigger size for an empty dict and a runtime cost (possibly very small) on the critical path (every time a value is stored in a dict). * The sole benefit of the patch is provide an earlier warning that someone is doing something weird. For most people, this will never come up (we have 23 years of Python history indicating that there isn't a real problem to that needs to be solved). * The normal rule (not just for Python) is that a data structures have undefined behavior for mutating while iterating, unless there is a specific guarantee (for example, we guarantee that the dicts are allowed to mutate values but not keys during iteration and we guarantee the behavior of list iteration while iterating). * It is not clear that other implementations such as IronPython and Jython would be able to implement this behavior (Jython wraps the Java ConcurrentHashMap). * The current patch second guesses a decision that was made long ago to only detect size changes (because it is cheap, doesn't take extra memory, isn't on the critical path, and handles the common case). * The only case whether we truly need a stronger protection is when it is needed to defend against a segfault. That is why collections.deque() implement a change counter. It has a measureable cost that slows down deque operations (increasing the number of memory accesses per append, pop, or next) but it is needed to prevent the iterator from spilling into freed memory.</pre> </td> </tr> <tr> <th> <a href="#msg257946" id="msg257946">msg257946</a> - <a href="msg257946">(view)</a></th> <th>Author: Roundup Robot (python-dev) <img src="@@file/triager.png" title="Python triager" alt="(Python triager)" /></th> <th>Date: 2016-01-10 23:43</th> </tr> <tr> <td colspan="4" class="content"> <pre>New changeset <a href="https://hg.python.org/lookup/a576199a5350">a576199a5350</a> by Victor Stinner in branch 'default': <a href="https://www.python.org/dev/peps/pep-0509/">PEP 509</a> <a href="https://hg.python.org/peps/rev/a576199a5350">https://hg.python.org/peps/rev/a576199a5350</a></pre> </td> </tr> </table> <table class="history table table-condensed table-striped"><tr><th colspan="4" class="header"> History </th></tr><tr> <th>Date</th> <th>User</th> <th>Action</th> <th>Args</th> </tr> <tr><td>2022-04-11 14:57:52</td><td>admin</td><td>set</td><td>github: 63531</td></tr> <tr><td>2017-02-02 14:38:17</td><td>r.david.murray</td><td>link</td><td><a rel="nofollow" href="issue29420">issue29420 superseder</a></td></tr> <tr><td>2016-01-10 23:43:55</td><td>python-dev</td><td>set</td><td>nosy: + <a rel="nofollow" href="user13902">python-dev</a><br />messages: + <a rel="nofollow" href="msg257946">msg257946</a><br /></td></tr> <tr><td>2013-11-06 20:56:30</td><td>rhettinger</td><td>set</td><td>messages: + <a rel="nofollow" href="msg202287">msg202287</a></td></tr> <tr><td>2013-11-06 12:32:40</td><td>steven.daprano</td><td>set</td><td>nosy: - <a rel="nofollow" href="user9511">steven.daprano</a><br /></td></tr> <tr><td>2013-11-06 12:32:11</td><td>steven.daprano</td><td>set</td><td>nosy: + <a rel="nofollow" href="user9511">steven.daprano</a><br />messages: + <a rel="nofollow" href="msg202262">msg202262</a><br /></td></tr> <tr><td>2013-10-30 21:47:23</td><td>ethan.furman</td><td>set</td><td>nosy: + <a rel="nofollow" href="user12590">ethan.furman</a><br />messages: + <a rel="nofollow" href="msg201780">msg201780</a><br /></td></tr> <tr><td>2013-10-28 06:15:54</td><td>rhettinger</td><td>set</td><td>status: open -> closed<br />resolution: rejected</td></tr> <tr><td>2013-10-24 16:34:30</td><td>rhettinger</td><td>set</td><td>messages: + <a rel="nofollow" href="msg201156">msg201156</a></td></tr> <tr><td>2013-10-23 20:10:35</td><td>pitrou</td><td>set</td><td>messages: + <a rel="nofollow" href="msg201065">msg201065</a></td></tr> <tr><td>2013-10-23 19:58:35</td><td>pitrou</td><td>set</td><td>nosy: + <a rel="nofollow" href="user6">tim.peters</a><br /></td></tr> <tr><td>2013-10-23 19:46:02</td><td>serhiy.storchaka</td><td>set</td><td>files: + <a rel="nofollow" href="file32319">dict_mutating_iteration_2.patch</a><br /><br />messages: + <a rel="nofollow" href="msg201062">msg201062</a></td></tr> <tr><td>2013-10-23 04:20:22</td><td>rhettinger</td><td>set</td><td>assignee: <a rel="nofollow" href="user114">rhettinger</a><br />messages: + <a rel="nofollow" href="msg200995">msg200995</a></td></tr> <tr><td>2013-10-21 14:02:54</td><td>serhiy.storchaka</td><td>create</td><td></td></tr> </table> </div> </div>  <div id="footer"> <div id="credits"> Supported by <a href="https://python.org/psf-landing/" title="The Python Software Foundation">The Python Software Foundation</a>, <br> Powered by <a href="http://roundup.sourceforge.net" title="Powered by the Roundup Issue Tracker">Roundup</a> </div>  Copyright © 1990-2022, <a href="http://python.org/psf">Python Software Foundation</a><br /> <a href="http://python.org/about/legal">Legal Statements</a> </div>  </div>  </div>  </body> </html>

CINXE.COM

Issue 19332: Guard against changing dict during iteration - Python tracker