Python 在迭代下替换字典键的行为

Question

我正在看一段 Python 3.6（注意 Python 3.8 会抛出一个错误）代码如下：

x = {0: None}
for i in x:
    del x[i]
    x[i+1] = None
    print(i)

这是在每次迭代时删除键 i 并将键 i + 1 添加到字典中，所以大概它应该永远循环，在每次迭代时打印递增的值？然而，它实际上在打印 i = 4 后停止迭代。我想知道为什么会出现这种行为，这是什么原因造成的？

Answer 1

TL;DR: 是因为当key table 的大小超过PyDict_MINSIZE 时dict 正在调整大小，这使得解释器意识到迭代器已经移动过去它应该停止的点。

继续阅读以了解您是如何自己发现的。

It's not possible to answer such question completely，因此我将尝试解释我的发现，同时，尝试为您提供自行探索所需的工具。

虽然确实归结为 implementation-specific 未定义的行为，但如果您知道如何浏览 CPython 代码，就不难找出发生了什么.以下是基于您的代码的嫌疑人名单：

保存字典迭代器的C结构是dictiterobject
您使用 dictiter_iternextkey()
保存字典的 C 结构是 PyDictObject。
您使用 PyDict_New(), which is actually a wrapper around new_dict()
您 del x[i] 使用 PyDict_DelItem(), a wrapper around _PyDict_DelItem_KnownHash()
使用 PyDict_SetItem(), which is a wrapper around insertdict() 添加密钥。

首先，注意字典迭代器只有在dictiter_iternextkey()中使用goto fail时才会停止。这只有在迭代器位置超过字典键中的条目数 table 时才会发生（di->di_pos >= di->di_dict->ma_keys->dk_nentries，在代码中写为 i >= n）。

让我们使用 GDB 看看实际发生了什么。首先，编译 CPython 3.6.10（有关完整说明，请参阅 the devguide）。运行 GDB 下的 CPython，在 dictiter_iternextkey() 中设置断点，运行你的脚本，并在每次迭代时打印 di_pos 和 dk_nentries：

git clone https://github.com/python/cpython
cd cpython
git checkout v3.6.10
./configure --with-pydebug
make -j 16 -s

# Put your code into weird.py

gdb ./python

(gdb) b Objects/dictobject.c:3480
(gdb) run weird.py

# Iterate these commands until process exits
(gdb) p di->di_pos
(gdb) p di->di_dict->ma_keys->dk_nentries
(gdb) c

您会看到，在循环的每次迭代中，di_pos 和 dk_nentries 都会递增 1，但最后一次除外，其中 dk_nentries重置为 1。

现在，我们只需要找出重置 dk_nentries 计数器的原因。您的代码中还有另外两行可以执行此操作：del x[i] 和 x[i+1] = None。您可以通过阅读代码找出它是哪一个，但让我们使用一个观察点来代替它：

(gdb) b Objects/dictobject.c:3480
(gdb) run weird.py
(gdb) watch -l di->di_dict->ma_keys->dk_nentries
# 'c'-ontinue until the following output appears:

(gdb) c                                                                                       
Continuing.                                                                                   
                                                                                              
Hardware watchpoint 3: -location di->di_dict->ma_keys->dk_nentries                            
                                                                                              
Old value = 5                                                                                 
New value = -2604246222170760229                                                              
__memset_avx2_unaligned_erms () at ../sysdeps/x86_64/multiarch/memset-vec-unaligned-erms.S:204
204     ../sysdeps/x86_64/multiarch/memset-vec-unaligned-erms.S: No such file or directory.

我们现在在内存管理代码中。新值看起来好像旧键 table 已被释放 - 它现在是垃圾。让我们看看回溯，看看是什么代码发出了 free()-ing:

(gdb) bt

...
#5  0x00005555556206e6 in dictresize (mp=0x7ffff72ffaa8, minsize=<optimized out>) at Objects/dictobject.c:1314
#6  0x0000555555620751 in insertion_resize (mp=<optimized out>) at Objects/dictobject.c:1103
#7  0x0000555555620e6d in insertdict (mp=0x7ffff72ffaa8, key=5, hash=5, value=None)
#8  0x0000555555623e4a in PyDict_SetItem (op={}, key=5, value=None) at Objects/dictobject.c:1576
...

添加密钥时会发生这种情况。解释器在调整字典大小时计算出实际有多少条目，并刷新 table，包括它的计数器。但为什么不早点发生呢？

如果您查看调用 insertion_resize() 的代码，您将看到以下分支：

        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(mp) < 0)
                goto Fail;
            find_empty_slot(mp, key, hash, &value_addr, &hashpos);
        }

如您所见，PyDictKeysObject 结构有一个 dk_usable 字段。作为优化，键 table 被初始化多一点 space，这样当添加 2-3 个键时，解释器不必立即调整字典的大小。

开头的“免费 space”数量是 controlled by PyDict_MINSIZE in PyDict_New(). This is actually mentioned in the macro section of the file。找出为什么将它设置为 8 让一个字典最多有 5 个条目留作练习。

自己检查一下：如果您重新编译 CPython 并将 PyDict_MINSIZE 设置为 32 (it must be a power of 2)，它会使您的代码最多迭代 20 次。

Python 在迭代下替换字典键的行为

Python behavior in replacing dictionary keys under iteration

python

dictionary

python-3.6