Python 无限期挂起试图删除深度递归对象
Python hangs indefinitely trying to delete deeply recursive object
我在 Python 中写了一个三元搜索树，我注意到当树变得很深时，试图删除它会导致 Python 无限期挂起。这是产生此行为的代码的精简版本：
import random
import sys
from collections import deque
class Node():
__slots__ = ("char", "count", "lo", "eq", "hi")
def __init__(self, char):
self.char = char
self.count = 0
self.lo = None
self.eq = None
self.hi = None
class TernarySearchTree():
"""Ternary search tree that stores counts for n-grams
and their subsequences.
"""
def __init__(self, splitchar=None):
self.root = None
self.splitchar = splitchar
def insert(self, string):
self.root = self._insert(string, self.root)
def _insert(self, string, node):
"""Insert string at a given node.
"""
if not string:
return node
char, *rest = string
if node is None:
node = Node(char)
if char == node.char:
if not rest:
node.count += 1
return node
else:
if rest[0] == self.splitchar:
node.count += 1
node.eq = self._insert(rest, node.eq)
elif char < node.char:
node.lo = self._insert(string, node.lo)
else:
node.hi = self._insert(string, node.hi)
return node
def random_strings(num_strings):
random.seed(2)
symbols = "abcdefghijklmnopqrstuvwxyz"
for i in range(num_strings):
length = random.randint(5, 15)
yield "".join(random.choices(symbols, k=length))
def train():
tree = TernarySearchTree("#")
grams = deque(maxlen=4)
for token in random_strings(27_000_000):
grams.append(token)
tree.insert("#".join(grams))
sys.stdout.write("This gets printed!\n")
sys.stdout.flush()
def main():
train()
sys.stdout.write("This doesn't get printed\n")
sys.stdout.flush()
if __name__ == "__main__":
main()
这会打印出 "This gets printed"，但不会打印出 "This doesn't get printed"。尝试手动删除该对象具有相同的效果。如果我将插入的字符串数量从 2700 万减少到 2500 万，一切都很好 - Python 打印出两个语句，然后立即退出。我尝试 运行 GDB，这是我得到的回溯：
#0 pymalloc_free.isra.0 (p=0x2ab537a4d580) at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1797
#1 _PyObject_Free (ctx=<optimized out>, p=0x2ab537a4d580)
at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1834
#2 0x0000555555701c18 in subtype_dealloc ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/typeobject.c:1256
#3 0x0000555555738ce6 in _PyTrash_thread_destroy_chain ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/object.c:2212
#4 0x00005555556cd24f in frame_dealloc (f=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/frameobject.c:492
#5 function_code_fastcall (globals=<optimized out>, nargs=<optimized out>, args=<optimized out>, co=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:291
#6 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#7 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#8 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#9 0x00005555556ccecb in function_code_fastcall (globals=<optimized out>, nargs=0, args=<optimized out>,
co=<optimized out>) at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:283
#10 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#11 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#12 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#13 0x00005555556690d9 in _PyEval_EvalCodeWithName ()
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3930
#14 0x0000555555669fa4 in PyEval_EvalCodeEx () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3959
#15 0x0000555555669fcc in PyEval_EvalCode (co=co@entry=0x2aaaaac08300, globals=globals@entry=0x2aaaaaba8168,
locals=locals@entry=0x2aaaaaba8168) at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:524
#16 0x0000555555783664 in run_mod () at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:1035
#17 0x000055555578d881 in PyRun_FileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:988
#18 0x000055555578da73 in PyRun_SimpleFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:429
#19 0x000055555578db3d in PyRun_AnyFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:84
#20 0x000055555578eb2f in pymain_run_file (p_cf=0x7fffffffd240, filename=0x5555558c5440 L"minimal.py",
fp=0x5555559059a0) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:427
#21 pymain_run_filename (cf=0x7fffffffd240, pymain=0x7fffffffd350)
at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:1627
#22 pymain_run_python (pymain=0x7fffffffd350) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:2876
#23 pymain_main () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3037
#24 0x000055555578ec4c in _Py_UnixMain () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3072
#25 0x00002aaaaaf0d3d5 in __libc_start_main () from /lib64/libc.so.6
#26 0x0000555555733982 in _start () at ../sysdeps/x86_64/elf/start.S:103
如果我尝试从那一点开始单步执行，执行将循环通过 obmalloc.c 中的三行 - GDB 在第 1796-98 行表示，但数字似乎已关闭，回溯中的文件（在 /tmp/) 不存在。
这发生在 Python 3.7.3 和 3.6 上，尽管导致挂断所需的字符串数量不同（两个版本都发生了 2700 万）。此时所需的内存约为 80 GB，打印出第一条语句需要 45 分钟。我实际使用的版本是用cython写的，减少了内存和运行时间，但面临同样的问题。
即使插入了十亿个字符串，使用该对象也能按预期工作。使对象保持活动状态（从函数返回它或将其放入 globals()）将问题推迟到 Python 退出 - 所以至少我可以确保所有工作都在那时完成，但我真的很想知道这里出了什么问题。
编辑： 我通过 conda (4.6.2) 安装了 python，我在 linux 服务器节点上：
> uname -a
Linux computingnodeX 3.10.0-862.14.4.el7.x86_64 #1 SMP Wed Sep 26 15:12:11 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
更新
在错误报告中，巨型机器上的 运行 显示回收树存储的时间从将近 5 小时下降到大约 70 秒：
master:
build time 0:48:53.664428
teardown time 4:58:20.132930
patched:
build time 0:48:08.485639
teardown time 0:01:10.46670
（建议修复）
这是一个针对 CPython 项目的 pull request，该项目提议 "fix this" 完全删除搜索。它适用于我小 10 倍的测试用例，但我无法访问内存足够接近 运行 原始内存的机器。所以我在等待有人在合并 PR 之前这样做（谁知道呢？这里 可能 不止一个 "huge number of objects" 设计缺陷）。
原回复
感谢您出色地提供了可重现您的问题的可执行样本！唉，我做不到 运行 - 需要比我多得多的内存。如果我将字符串的数量减少十倍，我最终会在大约 8GB 的 RAM 中得到大约 100,000,000 Node 个实例，并且垃圾收集需要大约 45 秒才能拆除树（Python 3.7.3)。所以我猜你有大约十亿个 Node 个实例。
我希望您不会收到回复，因为这里没有 "general problem" 已知的内容，而且它需要如此庞大的机器才能尝试。 python-dev 邮件列表可能是提问或在 https://bugs.python.org 上提出问题的更好地方。
在 运行 结束时垃圾收集速度非常慢的通常原因是内存被换出到磁盘，然后需要数千倍的时间 "than normal" 将对象读回RAM，按 "random" 顺序，将它们拆除。不过，我 假设 这不会发生在这里。如果是，CPU 使用率通常会下降到接近 0，因为该进程大部分时间都在等待磁盘读取。
在底层 C 库的 malloc/free 实现中，很少会遇到一些错误模式。但这在这里似乎也不太可能，因为这些对象足够小，以至于 Python 只向 C 请求 "big chunks" RAM 并自行分割它们。
所以我不知道。因为不能排除任何可能性，所以您还应该提供有关您正在使用的 OS 以及 Python 是如何构建的详细信息。
只是为了好玩，你可以试试这个来了解事情在停滞之前能走多远。先把这个方法加到Node:
def delete(self):
global killed
if self.lo:
self.lo.delete()
self.lo = None
if self.eq:
self.eq.delete()
self.eq = None
if self.hi:
self.hi.delete()
self.hi = None
killed += 1
if killed % 100000 == 0:
print(f"{killed:,} deleted")
在train()的末尾添加：
tree.root.delete()
并将对 main() 的调用替换为：
killed = 0
main()
print(killed, "killed")
这可能会或可能不会揭示一些有趣的东西。
不是为别人挂的
我在 python-dev mailing list 上发布了一条关于此事的评论，目前有一个人私下回复：
I started this using Python 3.7.3 | packaged by conda-forge | (default, Mar 27 2019, 23:01:00)
[GCC 7.3.0] :: Anaconda, Inc. on linux
$ python fooz.py
This gets printed!
This doesn't get printed
It did take ~80 GB of RAM and several hours, but did not get stuck.
因此，除非突然出现其他人 可以 复制它，否则我们在这里可能不走运。您至少需要提供更多关于您正在使用的 OS 以及 Python 是如何构建的信息。
您可以尝试重新编译 Python 吗？
在obmalloc.c中，有ARENA_SIZE宏定义为：
#define ARENA_SIZE (256 << 10) /* 256KB */
此默认值未针对超大内存系统进行优化。
您的脚本需要很长时间才能根据其中的空闲池数对竞技场进行排序。
在最坏的情况下，它可能是 O(N^2)，当许多竞技场具有相同数量的空闲池时。
您的脚本以随机顺序释放内存块，这接近于最坏的情况。
N 是这里的竞技场数量。当您将 ARENA_SIZE 更改为 (1024 << 10) 时，
竞技场大小为4x，N变为1/4，N^2变为1/16.
如果无法重新编译Python，可以使用malloc代替pymalloc。
$ PYTHONMALLOC=malloc python3 yourscript.py
您可以使用 LD_PRELOAD 环境变量用 jemalloc 或 tcmalloc 覆盖 malloc。
我在 Python 中写了一个三元搜索树，我注意到当树变得很深时，试图删除它会导致 Python 无限期挂起。这是产生此行为的代码的精简版本：
import random
import sys
from collections import deque
class Node():
__slots__ = ("char", "count", "lo", "eq", "hi")
def __init__(self, char):
self.char = char
self.count = 0
self.lo = None
self.eq = None
self.hi = None
class TernarySearchTree():
"""Ternary search tree that stores counts for n-grams
and their subsequences.
"""
def __init__(self, splitchar=None):
self.root = None
self.splitchar = splitchar
def insert(self, string):
self.root = self._insert(string, self.root)
def _insert(self, string, node):
"""Insert string at a given node.
"""
if not string:
return node
char, *rest = string
if node is None:
node = Node(char)
if char == node.char:
if not rest:
node.count += 1
return node
else:
if rest[0] == self.splitchar:
node.count += 1
node.eq = self._insert(rest, node.eq)
elif char < node.char:
node.lo = self._insert(string, node.lo)
else:
node.hi = self._insert(string, node.hi)
return node
def random_strings(num_strings):
random.seed(2)
symbols = "abcdefghijklmnopqrstuvwxyz"
for i in range(num_strings):
length = random.randint(5, 15)
yield "".join(random.choices(symbols, k=length))
def train():
tree = TernarySearchTree("#")
grams = deque(maxlen=4)
for token in random_strings(27_000_000):
grams.append(token)
tree.insert("#".join(grams))
sys.stdout.write("This gets printed!\n")
sys.stdout.flush()
def main():
train()
sys.stdout.write("This doesn't get printed\n")
sys.stdout.flush()
if __name__ == "__main__":
main()
这会打印出 "This gets printed"，但不会打印出 "This doesn't get printed"。尝试手动删除该对象具有相同的效果。如果我将插入的字符串数量从 2700 万减少到 2500 万，一切都很好 - Python 打印出两个语句，然后立即退出。我尝试 运行 GDB，这是我得到的回溯：
#0 pymalloc_free.isra.0 (p=0x2ab537a4d580) at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1797
#1 _PyObject_Free (ctx=<optimized out>, p=0x2ab537a4d580)
at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1834
#2 0x0000555555701c18 in subtype_dealloc ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/typeobject.c:1256
#3 0x0000555555738ce6 in _PyTrash_thread_destroy_chain ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/object.c:2212
#4 0x00005555556cd24f in frame_dealloc (f=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/frameobject.c:492
#5 function_code_fastcall (globals=<optimized out>, nargs=<optimized out>, args=<optimized out>, co=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:291
#6 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#7 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#8 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#9 0x00005555556ccecb in function_code_fastcall (globals=<optimized out>, nargs=0, args=<optimized out>,
co=<optimized out>) at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:283
#10 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#11 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#12 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#13 0x00005555556690d9 in _PyEval_EvalCodeWithName ()
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3930
#14 0x0000555555669fa4 in PyEval_EvalCodeEx () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3959
#15 0x0000555555669fcc in PyEval_EvalCode (co=co@entry=0x2aaaaac08300, globals=globals@entry=0x2aaaaaba8168,
locals=locals@entry=0x2aaaaaba8168) at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:524
#16 0x0000555555783664 in run_mod () at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:1035
#17 0x000055555578d881 in PyRun_FileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:988
#18 0x000055555578da73 in PyRun_SimpleFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:429
#19 0x000055555578db3d in PyRun_AnyFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:84
#20 0x000055555578eb2f in pymain_run_file (p_cf=0x7fffffffd240, filename=0x5555558c5440 L"minimal.py",
fp=0x5555559059a0) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:427
#21 pymain_run_filename (cf=0x7fffffffd240, pymain=0x7fffffffd350)
at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:1627
#22 pymain_run_python (pymain=0x7fffffffd350) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:2876
#23 pymain_main () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3037
#24 0x000055555578ec4c in _Py_UnixMain () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3072
#25 0x00002aaaaaf0d3d5 in __libc_start_main () from /lib64/libc.so.6
#26 0x0000555555733982 in _start () at ../sysdeps/x86_64/elf/start.S:103
如果我尝试从那一点开始单步执行，执行将循环通过 obmalloc.c 中的三行 - GDB 在第 1796-98 行表示，但数字似乎已关闭，回溯中的文件（在 /tmp/) 不存在。
这发生在 Python 3.7.3 和 3.6 上，尽管导致挂断所需的字符串数量不同（两个版本都发生了 2700 万）。此时所需的内存约为 80 GB，打印出第一条语句需要 45 分钟。我实际使用的版本是用cython写的，减少了内存和运行时间，但面临同样的问题。
即使插入了十亿个字符串，使用该对象也能按预期工作。使对象保持活动状态（从函数返回它或将其放入 globals()）将问题推迟到 Python 退出 - 所以至少我可以确保所有工作都在那时完成，但我真的很想知道这里出了什么问题。
编辑： 我通过 conda (4.6.2) 安装了 python，我在 linux 服务器节点上：
> uname -a
Linux computingnodeX 3.10.0-862.14.4.el7.x86_64 #1 SMP Wed Sep 26 15:12:11 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
更新
在错误报告中，巨型机器上的 运行 显示回收树存储的时间从将近 5 小时下降到大约 70 秒：
master:
build time 0:48:53.664428
teardown time 4:58:20.132930
patched:
build time 0:48:08.485639
teardown time 0:01:10.46670
（建议修复）
这是一个针对 CPython 项目的 pull request，该项目提议 "fix this" 完全删除搜索。它适用于我小 10 倍的测试用例，但我无法访问内存足够接近 运行 原始内存的机器。所以我在等待有人在合并 PR 之前这样做（谁知道呢？这里 可能 不止一个 "huge number of objects" 设计缺陷）。
原回复
感谢您出色地提供了可重现您的问题的可执行样本！唉，我做不到 运行 - 需要比我多得多的内存。如果我将字符串的数量减少十倍，我最终会在大约 8GB 的 RAM 中得到大约 100,000,000 Node 个实例，并且垃圾收集需要大约 45 秒才能拆除树（Python 3.7.3)。所以我猜你有大约十亿个 Node 个实例。
我希望您不会收到回复，因为这里没有 "general problem" 已知的内容，而且它需要如此庞大的机器才能尝试。 python-dev 邮件列表可能是提问或在 https://bugs.python.org 上提出问题的更好地方。
在 运行 结束时垃圾收集速度非常慢的通常原因是内存被换出到磁盘，然后需要数千倍的时间 "than normal" 将对象读回RAM，按 "random" 顺序，将它们拆除。不过，我 假设 这不会发生在这里。如果是，CPU 使用率通常会下降到接近 0，因为该进程大部分时间都在等待磁盘读取。
在底层 C 库的 malloc/free 实现中，很少会遇到一些错误模式。但这在这里似乎也不太可能，因为这些对象足够小，以至于 Python 只向 C 请求 "big chunks" RAM 并自行分割它们。
所以我不知道。因为不能排除任何可能性，所以您还应该提供有关您正在使用的 OS 以及 Python 是如何构建的详细信息。
只是为了好玩，你可以试试这个来了解事情在停滞之前能走多远。先把这个方法加到Node:
def delete(self):
global killed
if self.lo:
self.lo.delete()
self.lo = None
if self.eq:
self.eq.delete()
self.eq = None
if self.hi:
self.hi.delete()
self.hi = None
killed += 1
if killed % 100000 == 0:
print(f"{killed:,} deleted")
在train()的末尾添加：
tree.root.delete()
并将对 main() 的调用替换为：
killed = 0
main()
print(killed, "killed")
这可能会或可能不会揭示一些有趣的东西。
不是为别人挂的
我在 python-dev mailing list 上发布了一条关于此事的评论，目前有一个人私下回复：
I started this using Python 3.7.3 | packaged by conda-forge | (default, Mar 27 2019, 23:01:00) [GCC 7.3.0] :: Anaconda, Inc. on linux
$ python fooz.py
This gets printed!
This doesn't get printed
It did take ~80 GB of RAM and several hours, but did not get stuck.
因此，除非突然出现其他人 可以 复制它，否则我们在这里可能不走运。您至少需要提供更多关于您正在使用的 OS 以及 Python 是如何构建的信息。
您可以尝试重新编译 Python 吗？
在obmalloc.c中，有ARENA_SIZE宏定义为：
#define ARENA_SIZE (256 << 10) /* 256KB */
此默认值未针对超大内存系统进行优化。
您的脚本需要很长时间才能根据其中的空闲池数对竞技场进行排序。 在最坏的情况下，它可能是 O(N^2)，当许多竞技场具有相同数量的空闲池时。
您的脚本以随机顺序释放内存块，这接近于最坏的情况。
N 是这里的竞技场数量。当您将 ARENA_SIZE 更改为 (1024 << 10) 时，
竞技场大小为4x，N变为1/4，N^2变为1/16.
如果无法重新编译Python，可以使用malloc代替pymalloc。
$ PYTHONMALLOC=malloc python3 yourscript.py
您可以使用 LD_PRELOAD 环境变量用 jemalloc 或 tcmalloc 覆盖 malloc。