bugfix> python > 投稿

Pythonで3項検索ツリーを作成しましたが、ツリーが非常に深くなり、削除しようとすると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()

これは「これは印刷されます」を出力しますが、「これは印刷されません」は出力しません。オブジェクトを手動で削除しようとすると、同じ効果があります。挿入される文字列の数を2,700万から2,500万に減らすと、すべてが問題ありません。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の3行をループします-GDBは1796-98行で言っていますが、数字はオフになっていて、ファイルはトレースバック(/ tmp /にあります) )は存在しません。

これはPython 3.7.3と3.6の両方で発生しますが、ハングアップを引き起こすのに必要な文字列の数は異なります(両方のバージョンで発生した場所は2,700万でした)。その時点で必要なメモリは約80ギガバイトであり、最初のステートメントが出力されるまで45分かかります。私が実際に使用するバージョンはcythonで書かれており、メモリとランタイムを削減しますが、同じ問題に直面しています。

10億個の文字列が挿入されても、オブジェクトの使用は意図したとおりに機能します。オブジェクトを存続させる(関数から返すか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

回答 2 件
  • 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を再コンパイルできない場合は、pymallocの代わりにmallocを使用できます。

    $ PYTHONMALLOC=malloc python3 yourscript.py
    
    

    LD_PRELOAD を使用して、mallocをjemallocまたはtcmallocでオーバーライドできます。  環境変数。

  • 更新

    バグレポートで、巨大なマシンでの実行により、ツリーストレージを回収する時間が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倍小さいテストケースでは問題なく動作しますが、元のファイルを実行するのに十分なRAMに近いマシンにアクセスできません。ですから、PRをマージする前に誰かがいるのを待っています(知っている人はいますか?ここに複数の「オブジェクトの巨大な」設計上の欠陥があるかもしれません)。

    元の返信

    問題を再現する実行可能サンプルを提供してくれてありがとう。残念ながら、私はそれを実行することはできません-私が持っているよりもはるかに多くのメモリが必要です。文字列の数を10分の1に削減すると、約100,000,000 Node になります  インスタンスは約8GBのRAMにあり、ガベージコレクションがツリーを破棄するのに約45秒かかります(Python 3.7.3)。だから私はあなたが約10億 Node を持っていると推測しています  インスタンス。

    ここでは「一般的な問題」は知られていないため、応答が得られないことを期待します。また、試してみるのに非常に大きなマシンが必要です。ザ・ python-dev  メーリングリストは、https://bugs.python.orgで質問するか、問題を開くのに適した場所です。

    実行の終了時にガベージコレクションが非常に遅くなる通常の原因は、メモリがディスクにスワップアウトされ、「ランダム」な順序でRAMにオブジェクトを読み込むために「通常」よりも数千倍長くかかることです、それらを破壊する。しかし、私はここで起こっていないことを仮定しています。その場合、プロセスがディスク読み取りを待機する時間のほとんどを費やすため、CPU使用率は通常0近くに低下します。

    あまり頻繁ではありませんが、基礎となるCライブラリのmalloc/free実装で何らかの悪いパターンがヒットします。しかし、これらのオブジェクトは十分に小さいため、PythonはCに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() への呼び出しを置き換えます  with:

    killed = 0
    main()
    print(killed, "killed")
    
    

    興味深いものを明らかにする場合もしない場合もあります。

    他の人がハングしませんでした

    これについてのメモをpython-devメーリングリストに投稿しましたが、これまで一人が非公開で返信しました:

    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の構築方法に関する正確な情報を提供する必要があります。

あなたの答え