Terms Privacy

© Rollpie

MathPython
24 Dec 2025

Python の set のメモリレイアウトとオブジェクト構造（PySetObject の解剖）

CPython の set は Objects/setobject.c で実装されている。内部構造を理解することで、パフォーマンス特性や制約の理由が明確になる。

PySetObject の構造

CPython 3.x における set オブジェクトは以下の構造体で定義されている。

typedef struct {
    PyObject_HEAD
    Py_ssize_t fill;            /* アクティブ + ダミーエントリ数 */
    Py_ssize_t used;            /* アクティブエントリ数 */
    Py_ssize_t mask;            /* テーブルサイズ - 1（2^n - 1）*/
    setentry *table;            /* ハッシュテーブル */
    Py_hash_t hash;             /* frozenset のみ使用 */
    Py_ssize_t finger;          /* pop() 用のインデックス */
    setentry smalltable[PySet_MINSIZE];  /* 小さいセット用の埋め込みテーブル */
    PyObject *weakreflist;      /* 弱参照リスト */
} PySetObject;

重要なフィールドを順に見ていく。

fill と used の違い

fill と used の区別は、削除されたエントリの扱いに関係する。

used

実際に格納されている要素数。len(s) で返る値。

fill

アクティブなエントリ + ダミーエントリ（削除済みマーカー）の合計。

要素を削除しても fill は減らない。これはオープンアドレス法の探索を正しく動作させるためだ。

s = {1, 2, 3, 4, 5}
# used=5, fill=5

s.remove(3)
# used=4, fill=5（3 の位置にダミーマーカー）

fill が閾値を超えるとリサイズが発生し、ダミーエントリも整理される。

setentry の構造

各エントリは以下の構造を持つ。

typedef struct {
    PyObject *key;      /* 格納されている要素（またはNULL/ダミー）*/
    Py_hash_t hash;     /* 要素のハッシュ値（キャッシュ）*/
} setentry;

ハッシュ値をキャッシュしているのは、探索時に毎回 __hash__ を呼ばないためだ。リサイズ時にも再計算せずに済む。

smalltable の最適化

小さい set のために、オブジェクト内に固定サイズのテーブルを持っている。

#define PySet_MINSIZE 8

setentry smalltable[PySet_MINSIZE];

8 要素以下の set は、追加のメモリ確保なしで動作する。これにより、小さい set の作成が高速になる。

import sys

# 空の set でもメモリは確保済み
s = set()
print(sys.getsizeof(s))  # 216 bytes（smalltable を含む）

要素数が 8 を超えると、table ポインタが別のメモリ領域を指すようになる。

mask とインデックス計算

mask はテーブルサイズから 1 を引いた値で、常に 2^n - 1 の形になる。

# インデックス計算
index = hash_value & mask

# これは以下と同等だが高速
# index = hash_value % (mask + 1)

ビット AND 演算は除算より高速なため、この最適化は重要だ。テーブルサイズが 2 の累乗でなければならない理由がここにある。

テーブルサイズの進行

テーブルは 2 の累乗サイズで拡張される。

# 実際のサイズ変化を観察
import sys

s = set()
prev_size = sys.getsizeof(s)
sizes = [(0, prev_size)]

for i in range(100):
    s.add(i)
    size = sys.getsizeof(s)
    if size != prev_size:
        sizes.append((len(s), size))
        prev_size = size

for count, size in sizes:
    print(f"{count} elements: {size} bytes")

出力例として、要素数 0→5→21→85 あたりでサイズが増加する。これはテーブルサイズが 8→32→128→512 と 4 倍ずつ成長していることを示す。

finger フィールド

finger は pop() の最適化に使われる。

Py_ssize_t finger;  /* pop() 用のインデックス */

pop() はランダムな要素を返すが、毎回テーブルの先頭から探索すると効率が悪い。finger は前回の位置を記憶し、そこから探索を再開する。

s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
while s:
    print(s.pop(), end=' ')
# 出力順序はハッシュテーブルの配置に依存

hash フィールド（frozenset 専用）

frozenset はイミュータブルなので、ハッシュ値を一度計算したらキャッシュできる。

Py_hash_t hash;  /* frozenset のみ使用 */

set はミュータブルなのでこのフィールドは使われない（ハッシュ不可能なため）。

fs = frozenset([1, 2, 3])
print(hash(fs))  # 計算済みの値を返す（2回目以降は即座に返る）

メモリレイアウトの可視化

set オブジェクトのメモリ配置を概念的に示す。

# 概念的なメモリ配置
#
# PySetObject:
# +------------------+
# | PyObject_HEAD    |  (ob_refcnt, ob_type)
# +------------------+
# | fill             |  5
# +------------------+
# | used             |  4
# +------------------+
# | mask             |  7 (テーブルサイズ8の場合)
# +------------------+
# | table            |  → smalltable または外部テーブルへのポインタ
# +------------------+
# | hash             |  (frozenset のみ)
# +------------------+
# | finger           |  pop() 用
# +------------------+
# | smalltable[0]    |  (key, hash)
# | smalltable[1]    |  (key, hash)
# | ...              |
# | smalltable[7]    |  (key, hash)
# +------------------+
# | weakreflist      |
# +------------------+

空スロットとダミーの判別

テーブルのスロットには 3 つの状態がある。

状態key の値意味
空NULL一度も使われていない
アクティブ有効なポインタ要素が格納されている
ダミー_PySet_Dummy削除された（探索は継続）

ダミーマーカーがあることで、衝突チェーンが途切れない。

#define EMPTY_TO_MINSIZE(so) do {                       \
    memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
    (so)->used = (so)->fill = 0;                        \
    (so)->table = (so)->smalltable;                     \
    (so)->mask = PySet_MINSIZE - 1;                     \
} while(0)

GC との連携

set は他のオブジェクトを参照するため、ガベージコレクタの追跡対象になる。

PyObject_GC_Track(so);  /* GC に登録 */

循環参照を検出するために、GC は set 内の全要素を走査できる必要がある。tp_traverse コールバックがこれを実現している。

import gc

# 循環参照の例
a = set()
b = [a]
a.add(tuple(b))  # 間接的な循環

# GC が検出して解放できる
gc.collect()

この内部構造を理解することで、set の挙動やパフォーマンス特性の理由が明確になる。

8 views