Python试图删除深度递归对象时会无限挂起。

Question

Python试图删除深度递归对象时会无限挂起。

pythonmemorymemory-managementtreerecursive-datastructures

13

我用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万）。此时所需内存约为80GB，打印第一条语句需要45分钟。我实际使用的版本是用cython编写的，它减少了内存和运行时间，但仍然面临同样的问题。

使用对象的效果与预期相同，即使插入了10亿个字符串。保持对象活动状态（从函数返回它或将其放入全局变量中）将问题推迟到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

- Christian Adam

“无限期”是什么意思（你等了多久）？这个进程是否在消耗CPU周期？ - Tim Peters

我发布的那个版本运行了几个小时，进程从未空闲。而我实际使用的那个版本运行了数天，却从未终止。正如我所说，如果字符串数量稍微少一点，它就会立即退出。 - Christian Adam

1

/tmp/build/80754af9/python_1546061345851/work 看起来像是嵌入到可执行文件中的路径 -- 这是 Python 构建时源代码所在的构建服务器的位置和时间。 - ivan_pozdeev

你实际拥有多少物理内存？如果你正在进行磁盘交换，这个问题可能会加剧。 - Cody Piersall

我正在一台服务器上运行脚本，已经运行了很多次，有时候会分配150GB的内存，所以我认为它从来没有使用过交换空间。如果我没记错的话，作业分配器甚至不允许使用交换空间，如果使用太多内存，它就会杀掉该作业。 - Christian Adam

@ivan_pozdeev 是的，我在服务器上安装了Python，并通过conda进行了安装。我想路径就是conda在安装过程中放置源文件的地方，然后将它们删除了。我刚学会了如何从源代码构建 - 使用那个版本，我可能会被指向实际拥有的文件中的正确行号。(: - Christian Adam

2个回答

4

你可以尝试重新编译Python吗？

在obmalloc.c文件中，有一个称为ARENA_SIZE的宏定义：

#define ARENA_SIZE              (256 << 10)     /* 256KB */

这个默认值并不适用于非常大的内存系统。

你的脚本在按照它里面的空闲池数量进行排序时需要很长时间。如果很多区域具有相同数量的空闲池，则最坏情况下它可以是O(N^2)。

你的脚本以随机顺序释放内存块，这接近于最坏情况。

N 是这里的区域数。当你将 ARENA_SIZE 更改为 (1024 << 10) 时，区域的大小会增加4倍，N 变为1/4，而 N^2 变为1/16。

如果您无法重新编译Python，则可以使用malloc而不是pymalloc。

$ PYTHONMALLOC=malloc python3 yourscript.py

您可以使用 LD_PRELOAD 环境变量来使用 jemalloc 或 tcmalloc 覆盖 malloc。

- methane

我该如何重新编译Python并更改ARENA_SIZE？ - Christian Adam

1

@methane，FYI，在我的情况下（规模小了10倍），这个改变将总的释放时间从大约45秒减少到大约10秒。在python-dev上，我建议采用一种方法来替换“排序”操作，使用常数时间的链表操作（这需要改变很多代码）。 - Tim Peters

2

我可以确认这一点。将ARENA_SIZE更改为（256 << 12）后，解除分配需要13分钟。现在正在运行使用malloc的版本。 - Christian Adam

2

使用PYTHONMALLOC=malloc，插入时间几乎增加了一倍，但释放内存只需2分钟！ - Christian Adam

最后一个观察：对于Cython版本，如果使用malloc，插入时间保持不变，但释放时间会略微超过一分钟。 - Christian Adam

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Peters · Accepted Answer

更新

在错误报告中，对一台巨型机器进行的运行显示，回收树形存储的时间从将近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项目的拉取请求，提议通过彻底移除搜索来“修复”这个问题。它在我的10倍小的测试中运行良好，但我无法访问到具有足够内存运行原始数据的计算机。因此，在合并PR之前，我正在等待能够做到这一点的人(谁知道？这里可能存在一个或多个“大量对象”的设计缺陷)。

（原始回复）

感谢您提供可执行的样例以重现您的问题！但遗憾的是，我无法运行它——需要的内存比我拥有的多得多。如果我将字符串数量减少十倍，就会获得大约1亿个Node实例，需要大约8GB的RAM，并且需要大约45秒才能完成垃圾回收树的拆卸 (Python 3.7.3)。所以我猜你大概有10亿个Node实例。

我认为你没有得到响应，是因为这里没有已知的“普遍问题”，而检测它需要如此庞大的计算机。在python-dev邮件列表中询问或在https://bugs.python.org上打开一个问题可能是个更好的选择。

跑完程序后，非常缓慢的垃圾回收通常的原因是内存已经被交换到磁盘上，然后需要花费数千倍于通常情况下读取对象并拆除它们的随机顺序，这就需要很长时间。我假设这里没有发生这种情况。如果发生了，CPU使用率通常会降至接近0，因为进程大部分时间都在等待磁盘读取。

较少情况下，底层C库的malloc / free实现遇到错误模式。但这在这里似乎也不太可能，因为这些对象足够小，Python只会请求C提供“大块”RAM并自己切割。

所以我不知道。因为无法排除任何情况，您还应提供有关您使用的操作系统以及如何构建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邮件列表上发了一条关于此事的说明，并且迄今为止，只有一个人私下回复：

我使用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

虽然需要大约80 GB的RAM和几个小时的时间，但程序并未卡住。

因此，除非有其他人能够重现这个问题，否则我们可能无法解决它。您至少需要提供更多关于您使用的操作系统以及如何构建Python的详细信息。