グローバルとmain()関数内で処理する場合のメモリ使用量の差

Question

DFS(深さ優先探索)のコードを書いていて、main()関数内で処理する場合、グローバル名前空間で処理するよりもメモリ使用量が増えていることに気づきました。
競技プログラミングのあるテストケースでメモリ制限が256MBのとき、main()のものだとMLE(>256MB)だったのが括弧を外すと215MBとなりました。
関数内でローカルに処理するほうが実行時間が早くなるのは知っていたのですが、メモリに関しては調べても良い文献が出てきません。
どなたか理由をご存知ありませんか?

提出 #7024392 - AtCoder Typical Contest 001 (MLE)

# ATC001A - DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    def dfs(h: int, w: int) -> None:
        if (h, w) == goal:
            print("Yes")
            exit()
        for dx, dy in dxy:
            x, y = h + dx, w + dy
            if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
                F[x][y] = "#"
                dfs(x, y)

    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(*start)
    print("No")


if __name__ == "__main__":
    main()

提出 #7024438 - AtCoder Typical Contest 001 (AC)

# ATC001A - DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(h: int, w: int) -> None:
    if (h, w) == goal:
        print("Yes")
        exit()
    for dx, dy in dxy:
        x, y = h + dx, w + dy
        if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
            F[x][y] = "#"
            dfs(x, y)

H, W = tuple(map(int, input().rstrip().split()))
F = list(list(input().rstrip()) for _ in range(H))
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
flg = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "s":
            start = i, j
            flg += 1
        elif F[i][j] == "g":
            goal = i, j
            flg += 1
        if flg == 2:
            break
dfs(*start)
print("No")

追記

提出結果のスクリーンショットですが、軽いものを除けばほとんどのケースでグローバル空間に直接書いたほうがメモリ使用量が少なくなっています。
MLEになったものを含め、偶然の結果ではないと思うのですが...
(左がmain(), 右がグローバルのものです)

Answer 1

注意：ここに書いてあることはすべて推測・憶測・個人的な感覚に基づく情報です

まず、main()ありとmain()なしの以下の2つのコードでは、速度に2倍近くの差が出ます。また一般論ですが、速度を出したいときには高速な記憶域をじゃぶじゃぶ使う、記憶域を節約したいときにはCPUをぶんぶん振り回す、というセオリーがコンピュータプログラムにはあると思います。

---

環境：Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)]

# main()あり：速い
from time import perf_counter

def main():
    a = 0
    t = perf_counter()
    for _ in range(10 ** 8):
        a += 1
    print("%.03f sec" % (perf_counter() - t))

main()

# main()なし：遅い
from time import perf_counter

a = 0
t = perf_counter()
for _ in range(10 ** 8):
    a += 1
print("%.03f sec" % (perf_counter() - t))

---

そして記憶域という観点から考えた上記の2つのコードの違いは、main()の名前空間です。main()の名前空間分、記憶域を多く使うことによってmain()ありのコードは速度が出るようになったと考えることができます。

さて、これらの前提を踏まえた上で質問のmain()ありのdfs関数を見てみると、dfs関数はmain関数の内部関数、かつ再起しながら関数の外側の変数を参照するという、うまく言えないですが名前空間的なじゃぶじゃぶ感が否めません。dfs関数が再起していくなかで「たぶん」名前空間が膨れ上がっているんじゃなかろうかと思います。

（駄目だ、時間を掛けたのに上手く論理を展開できない。。。力不足です。）

Answer 2

推測でしかありませんが、上の方は関数内関数になっているため、普通の関数が実行される時に必要な（ローカル変数用の）メモリの他に、もう1つ"外の関数"への（あるいは"外の関数"のローカル変数の辞書への?）参照が保持されるのが、地味に効いているのではないでしょうか?

傍証として、グローバル変数への参照を一切持たないトップレベル関数として実装するとMLEがでませんが、

# これは通る
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(h: int, w: int, goal, dxy, H, W, F) -> None:
    if (h, w) == goal:
        print("Yes")
        sys.exit()
    for dx, dy in dxy:
        x, y = h + dx, w + dy
        if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
            F[x][y] = "#"
            dfs(x, y, goal, dxy, H, W, F)


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(start[0], start[1], goal, dxy, H, W, F)
    print("No")


if __name__ == "__main__":
    main()

これを関数内関数にするとそれだけで（つまり、"外の関数"の変数を一切参照していないのでクロージャではないただの関数内関数であるにも関わらず）MLEになります。

# これはMLE
import sys

sys.setrecursionlimit(10 ** 6)


def main():
    def dfs(h: int, w: int, goal, dxy, H, W, F) -> None:
        if (h, w) == goal:
            print("Yes")
            sys.exit()
        for dx, dy in dxy:
            x, y = h + dx, w + dy
            if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
                F[x][y] = "#"
                dfs(x, y, goal, dxy, H, W, F)

    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(start[0], start[1], goal, dxy, H, W, F)
    print("No")


if __name__ == "__main__":
    main()

Comments

[退会済みユーザー]

ありがとうございます。
quiquiさんの予想が最も頷けるものだったので、ベストアンサーにしました。

Answer 3

元々がギリギリすぎるというだけでは？

あまり細かく検証していませんが、GCが走るタイミング次第では下のコードでも215MBでは走らなくてエラーになるとか、そんなパターンな気がします。

Comments

[退会済みユーザー]

確かにメモリ制限が厳しいのは事実なのですが、追記の画像の通り、処理が重めのケースでは軒並みメモリ使用量に差が出ています。
今後のためにも、その理由が知りたいです。
よろしくお願いします

[hayataka2049]

理屈の上では、そんな大きな差は生じないはずです。単純に私が見落としている可能性もありますが（わかった方は回答していただけると幸いです）。
処理系内部のメモリ管理の最適化の話とかになってしまうと、正直お手上げなので、わからないかもしれません。

[hayataka2049]

あと、関係ないとは思うけど、exitはプログラム中では呼ぶべきではないとされます。
グローバルで書いた方はsys.exitする、mainで書いた方はreturnとかでいいでしょう。
exitする瞬間に送出された例外がスタックフレームを膨れ上がらせるみたいな妄想もしたけど、さすがにないか。