Python の set のリサイズ戦略とメモリ断片化

Python の set は要素数に応じてテーブルサイズを動的に変更する。このリサイズ戦略とメモリへの影響を詳しく見ていく。

リサイズのトリガー

CPython では、テーブルの使用率が約 66% を超えるとリサイズが発生する。

/* setobject.c からの抜粋 */
#define USABLE_FRACTION(n) (((n) << 1) / 3)

/* fill が USABLE_FRACTION を超えたらリサイズ */
if (so->fill * 3 >= (so->mask + 1) * 2) {
    /* リサイズ実行 */
}

fill * 3 >= (mask + 1) * 2 は fill >= 2/3 * size と同等だ。

なぜ 66% なのか

オープンアドレス法では、使用率が高いと衝突が増える。66% は探索効率とメモリ効率のバランスポイント。

fill を使う理由

deleted（ダミー）も含めて計算することで、削除が多い状況での性能劣化を防ぐ。

成長戦略

リサイズ時のテーブルサイズ決定ロジックを見る。

/* 新しいサイズを決定 */
Py_ssize_t minused = so->used * 2;  /* 最低でも used の 2 倍 */

Py_ssize_t newsize = PySet_MINSIZE;
while (newsize <= minused) {
    newsize <<= 2;  /* 4 倍ずつ増やす */
}

テーブルは 4 倍ずつ成長する。これはリサイズ頻度を減らすためだ。

# 成長パターンの観察
import sys

s = set()
prev_size = sys.getsizeof(s)
print(f"  0 elements: {prev_size} bytes")

for i in range(1, 1000):
    s.add(i)
    size = sys.getsizeof(s)
    if size != prev_size:
        print(f"{i:3d} elements: {size} bytes")
        prev_size = size

典型的な出力:

#   0 elements: 216 bytes
#   5 elements: 728 bytes
#  21 elements: 2264 bytes
#  85 elements: 8408 bytes
# 341 elements: 32984 bytes

要素数 5, 21, 85, 341… でリサイズが発生している。

縮小は自動では行われない

要素を削除してもテーブルは自動的に縮小しない。

import sys

s = set(range(1000))
print(f"After adding 1000: {sys.getsizeof(s)} bytes")

for i in range(999):
    s.remove(i)
print(f"After removing 999: {sys.getsizeof(s)} bytes")

大きなテーブルが残り続ける。メモリを解放したい場合は、新しい set を作り直す必要がある。

s = set(range(1000))
for i in range(999):
    s.remove(i)

# メモリを解放するには再作成
s = set(s)
print(f"After recreation: {sys.getsizeof(s)} bytes")

rehash の過程

リサイズ時には全要素を新しいテーブルに再配置する。

static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{
    setentry *oldtable = so->table;
    Py_ssize_t oldmask = so->mask;
    
    /* 新しいテーブルを確保 */
    setentry *newtable = PyMem_New(setentry, newsize);
    
    /* 全エントリを再挿入 */
    for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
        if (entry->key != NULL && entry->key != dummy) {
            /* 新しい位置を計算して挿入 */
            set_insert_key(so, entry->key, entry->hash);
        }
    }
    
    /* 古いテーブルを解放 */
    if (oldtable != so->smalltable)
        PyMem_Free(oldtable);
}

この再配置は O(n) の操作だが、償却計算量では O(1) に収まる。

償却計算量の分析

n 回の挿入での総リサイズコストを考える。

# リサイズは 8 → 32 → 128 → 512 → 2048 ...
# 各リサイズでのコピー数: 5, 21, 85, 341, ...

# 総コピー数 ≈ n + n/4 + n/16 + n/64 + ...
#            = n * (1 + 1/4 + 1/16 + ...)
#            = n * 4/3
#            ≈ 1.33n

# n 回の挿入で 1.33n のコピー → 1 回あたり O(1)

幾何級数の和により、平均コストは定数になる。

ダミーエントリとリサイズ

削除が多いと、ダミーエントリが蓄積してリサイズが必要になる。

s = set(range(100))
print(f"Initial: {sys.getsizeof(s)} bytes")

# 大量に削除
for i in range(80):
    s.remove(i)
# テーブルサイズは変わらないが、fill は 100 のまま

# 新しい要素を追加すると...
for i in range(100, 200):
    s.add(i)
print(f"After operations: {sys.getsizeof(s)} bytes")

この場合、ダミーエントリが多いため fill が閾値を超え、リサイズが発生する。リサイズ時にダミーは除去されるため、テーブルはクリーンになる。

メモリ断片化

頻繁なリサイズはメモリ断片化を引き起こす可能性がある。

断片化の発生

テーブル確保→解放→より大きいテーブル確保を繰り返すと、メモリ空間に「穴」ができる。

glibc のアロケータ

小さいブロックは再利用されるが、大きいブロックは mmap/munmap で管理され、断片化しにくい。

Python の場合、CPython のメモリアロケータが介在するため、OS レベルの断片化は限定的だ。

smalltable の効果

8 要素以下の set は、オブジェクト内の smalltable を使う。

import sys

for n in range(10):
    s = set(range(n))
    print(f"{n} elements: {sys.getsizeof(s)} bytes")

出力:

# 0 elements: 216 bytes
# 1 elements: 216 bytes
# ...
# 4 elements: 216 bytes
# 5 elements: 728 bytes  ← ここでリサイズ

4 要素までは追加のメモリ確保が発生しない。これにより、小さい set の作成・破棄が高速になる。

メモリプロファイリング

tracemalloc を使ってメモリ使用を追跡できる。

import tracemalloc

tracemalloc.start()

sets = []
for i in range(1000):
    s = set(range(i))
    sets.append(s)

current, peak = tracemalloc.get_traced_memory()
print(f"Current: {current / 1024 / 1024:.2f} MB")
print(f"Peak: {peak / 1024 / 1024:.2f} MB")

tracemalloc.stop()

ピークメモリがカレントより大きい場合、リサイズ時の一時的なメモリ増加が原因だ。

事前サイズ確保

残念ながら、Python の set には reserve() のような事前確保の仕組みがない。

# C++ なら
# std::unordered_set<int> s;
# s.reserve(10000);

# Python ではできない
s = set()
# s.reserve(10000)  # そんなメソッドはない

ただし、既知のデータから初期化すれば、適切なサイズで作成される。

# 初期データがあれば一度にサイズが決まる
s = set(range(10000))  # リサイズは 1 回で済む

# 逐次追加だと複数回リサイズ
s = set()
for i in range(10000):
    s.add(i)  # 複数回リサイズが発生

大量のデータを扱う場合は、リスト内包表記などで一度に作成するほうが効率的だ。

長期稼働プロセスでの注意

削除と追加を繰り返す長期稼働プロセスでは、set のメモリ効率が低下することがある。

import sys

s = set()

# 追加と削除を繰り返す
for cycle in range(10):
    for i in range(10000):
        s.add(i)
    for i in range(9000):
        s.remove(i)
    print(f"Cycle {cycle}: len={len(s)}, size={sys.getsizeof(s)} bytes")

テーブルが大きいまま維持される。定期的に s = set(s) で再構築するか、アプリケーションのリスタートを検討すべきだ。

# 定期的なメンテナンス
def compact_set(s):
    """set を再構築してメモリを最適化"""
    return set(s)

このリサイズ戦略を理解することで、大規模データを扱う際のメモリ管理が適切に行える。