DSAS開発者の部屋

@methane です。

最近 Python の dict をハックしているので、その紹介をしたいと思います。 ですが、まずこの記事では現在 (Python 3.6a2) の dict の実装を詳解します。

データ構造

基本となる構造体は3つです。(Python 3.6a2 のソースより引用)

typedef struct _dictkeysobject PyDictKeysObject;

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

typedef PyDictKeyEntry *(*dict_lookup_func)
(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr);

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    PyDictKeyEntry dk_entries[1];
};

PyDictObject が dict のインスタンスを表すオブジェクトです。 PyObject_HEAD は Python のオブジェクトすべてが持っている共通の管理用データ（参照カウント等）を定義するマクロで、通常ビルドでは3ワード（64bit環境では24バイト）になります。

ma_used がその dict に入っている要素数、 ma_keys が動的に確保されるハッシュテーブルです。 ma_values については後述します。

PyDictKeyEntry はハッシュテーブルの各エントリとなる構造体です。 me_key, me_value が名前のままキーと対応する値となる Python オブジェクトへのポインタで、 me_hash は me_key のハッシュ値です。探索やハッシュテーブルの再構築のときに必要になるので毎回計算するのではなくてエントリーに持ってしまっています。

PyDictKeysObject がハッシュテーブルです。 dk_size がハッシュテーブルのサイズ、 dk_usable があと何要素ハッシュテーブルに入れられるかを示すカウンタです。 dk_usable が 0 のときに挿入しようとするとハッシュテーブルが再構築され、必要に応じて拡張されます。 dk_refcnt については ma_values とともに後で解説します。

dk_lookup は探索関数への関数ポインタです。 dict は例えば関数呼び出しのときに名前から関数を探索したりと、主に文字列をキーとして Python の言語の基本を支えているので、 key の型が文字列の dict に特殊化して高速にした関数を最初に入れておき、文字列以外のキーを挿入した段階で汎用の関数へのポインタに差し替えるなどを行っています。

dk_entries はハッシュテーブルの実態です。構造体の宣言では1要素の配列になっていますが、実際には次のように PyDictKeysEntry をアロケートすることで dk_size の長さを持つ配列になります。

    dk = PyObject_MALLOC(sizeof(PyDictKeysObject) +
                      sizeof(PyDictKeyEntry) * (size-1));

オープンアドレス法

ハッシュテーブルのサイズ (dk_size) は 2^n になっています。また、そのハッシュテーブルに格納できる要素数 (dk_usable の初期値) は (2*dk_size+1)/3 になっています。

dk_size が 2^n なので、ハッシュテーブルに要素を挿入したり、探索する場合は、ハッシュ値 & (dk_size-1) で場所を決めます。 (dk_size が 8 なら2進数で表すと 0b1000 で、 dk_size-1 が 7 = 0b0111 になり、ハッシュ値の下位3bitを利用することになる)

dk_usable が 0 になりハッシュテーブルを再構築する際、（削除操作がなく純粋に追加してきた場合は）dk_sizeが2倍になり、ハッシュテーブルの「密度」は 2/3 から 1/3 になります。なのでハッシュテーブルの密度は下限がだいたい 1/3 、上限が 2/3 になります。

さて、ハッシュ値が綺麗に分散しているとしたら、挿入時に利用されるハッシュ値の下位ビットの衝突率は 1/3 と 2/3 の平均で 1/2 程度になるでしょう。 実際にはハッシュ値は綺麗に分散しているとは限らないので、これより悪くなるはずです。

ハッシュ法で衝突に対処する方法としては、要素をハッシュテーブル外のリストなどに置いてハッシュテーブルにはそこへの参照を格納する方法（オープンハッシュ法）と、ハッシュテーブル内の別の場所に格納する方法（クローズドハッシュ法、またはオープンアドレス法。「オープン」が全く逆のオープンハッシュ法と被るので紛らわしいです）がありますが、 Python はクローズドハッシュ法を採用しています。

クローズドハッシュ法では、「衝突したら次はどこを使うか」というアルゴリズムを決めておいて、挿入も探索も同じ方法を使わなければなりません。 メモリアクセスの効率を考えると衝突した場所の隣の場所を使うのが良いのですが、ハッシュ値が良くなくて衝突が頻発したときや、ハッシュテーブル内に偏りが発生した場合に、次も、その次も、その次も、という感じに衝突する可能性が高くなります。

ハッシュテーブル内を飛び飛びに巡回し、最終的にはテーブル内の全要素を1回ずつ走査する関数が欲しいのですが、その関数として Python は (5*i+1) mod dk_size を採用しています。 例えば dk_size が 8 で ハッシュ値の下位3bitが 3 なら、ハッシュテーブルを 3, 0, 1, 6, 7, 4, 5, 2, 3 という形で、 0~7 を1度ずつ通って最初の 3 に戻ってきます。

しかし、この方法ではハッシュテーブル内の密度の偏りの影響を避けられるものの、ハッシュ値の下位ビットが衝突する key は同じ順番に巡回するので線形探索になってしまい効率が悪いという欠点があります。そこで、先程の関数を改造して、次のようにしています。

    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = i * 5 + perturb + 1;

これで、最初のうちはハッシュ値の上位ビットを使って次の位置を決定していき、ハッシュ値を右シフト仕切ったら先ほどのアルゴリズムで確実に巡回する、というハイブリッド型の巡回アルゴリズムになります。

(ちなみに、このforループには最初の衝突のあとにくるので、 perturb の初期値が hash のままだと、hash 値の下位ビットが衝突する key と1つ目だけでなく2つ目も衝突してしまいますね…)

(なお、 dict よりも最近に改良された set 型では、最初はキャッシュ効率を重視して近くの要素を探すといった改良がされています。)

削除

オープンアドレス法での要素の削除には注意が必要です。というのは、探索や挿入のときの巡回は、同じキーか空きを発見したときに停止するからです。

あるキーAを挿入するときに別のキーBと衝突して別の場所に挿入したのに、その別のキーBが削除されて空きになってしまうと、キーAをまた探索するときに、キーBがあった場所に空きを見つけて、キーAはハッシュテーブルに存在しないと判断してしまいます。

これを避けるために、削除するときはハッシュテーブルを空きに戻すのではなく、ダミー要素に入れ替えます。

また、 popitem() という dict の中の任意の (key, value) を取得しつつ削除するメソッドの実装にも注意が必要です。 ハッシュテーブルを線形探索して、最初に見つけた要素を返し、その場所をダミーに置き換えるのですが、これを繰り返すとハッシュテーブルがダミー要素だらけになっていって、次のようなアルゴリズムの実行時間が O(n**2) になってしまいます。

while d:
    k, v = d.popitem()
    do_something(k, v)

popitem() の平均計算量を O(1) にするために、ハッシュテーブルの先頭に要素があればそれを返し、無かった場合は線形探索した後に、次に線形探索を開始する場所を（空、あるいはダミーkeyが入っている）先頭要素の me_value に格納しておきます。

PEP 412: Key-Sharing Dictionary

次のインタラクティブセッションでは、2つの空の dict のメモリ使用量を表示しています。

>>> d = {}
>>> class A: pass
...
>>> a = A()
>>> ad = a.__dict__  # a の属性を格納している dict のインスタンス
>>> d
{}
>>> ad
{}
>>> type(d), type(ad)
(<class 'dict' at 0x109c735b0>, <class 'dict' at 0x109c735b0>)
>>> import sys
>>> sys.getsizeof(d)
288
>>> sys.getsizeof(ad)
96

両方共確かに dict の空のインスタンスなのですが、サイズは 288 バイトと 96 バイトと、3倍近くの差があります。なぜでしょうか？

ここで、説明を省略していた PyDictKeysObject の dk_refcnt と PyDictObject の ma_values が登場します。

dk_refcnt は参照カウントになっていて、A のインスタンス a を作った際、 a の属性を管理する dict インスタンスを作った後、その PyDictKeysObject の dk_refcnt をインクリメントして、クラス A にポインタをもたせます。

その後、クラスAのインスタンスを作る際は、そのインスタンス用の dict を作るときに PyDictKeysObject を作るのではなく、クラスAが持っているオブジェクトを参照し、参照カウントをインクリメントします。このように、同じクラスの複数のインスタンス間で、 PyDictKeysObject は共有されます。

ハッシュテーブルを共有しているので、 me_value に各 dict が持つはずの値を格納することができません。 PyDictObject の ma_values に、 dk_size と同じ大きさの PyObject* の配列を持たせて、 dk_entries[i].me_value の代わりに ma_values[i] に値を格納します。

dk_entries は各要素がポインタ3つ分の大きさを持っている一方で、 ma_values はポインタ1つ分で済むので、これでかなりのサイズを削減できます。

また、 dk_usable の初期値が (dk_size*2)/3 ではなく (dk_size*2+1)/3 になっていたのにも秘密があります。

通常の dict では dk_size の最小値が 8 なのですが、 key sharing dict では dk_size が 4 になっているのです。 (4*2)/3 は 2 なのに対して、 (4*2+1)/3 は3になるので、この最小の key sharing dict は3つの要素を格納することができるのです。

この結果、属性が3つ以下のインスタンスは 64bit 環境では 96 バイトの dict で属性を管理することができるのです。

この key sharing dict は、 Python 3.4 で導入されました。 (ちなみに 3.4 ではバグでサブクラスで有効にならなかったのが、 3.4.1 で解消されました）

この素敵な新機能が、 dict をハックしていた僕を、単純に実装を複雑にしたり考えないといけないケースを増やすというだけでなく、かなり重い意味で苦しめることになります。

その話は次回の記事で解説します。

@methane