[解決済み] メモリ上のリストのサイズ

質問

私はちょうどメモリ内のpythonデータ構造のサイズについて実験していました。私は次のスニペットを書きました。

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

以下の構成でコードをテストしてみました。

• Windows 7 64bit、Python3.1: 出力は以下の通りです。 52 40 で、lst1 が 52 バイトで、lst2 が 40 バイトです。
• Ubuntu 11.4 32bit、Python3.2：出力は以下の通りです。 48 32
• Ubuntu 11.4 32bit Python2.7です。 48 36

どちらも1を含むリストであるにもかかわらず、なぜ2つのサイズが異なるのか、どなたか説明してください。

getizeof関数のpythonドキュメントで、私は次のことを見つけました。 ...adds an additional garbage collector overhead if the object is managed by the garbage collector. これは私の小さな例のケースでしょうか？

どのように解決するのですか？

何が起こっているのかを説明するのに役立つ、より充実したインタラクティブなセッションです (Python 2.6 on Windows XP 32-bit, but it doesn't matter really)。

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

空のリストは [1] が入っているものよりも少し小さいことに注意してください。しかし、要素が追加されると、それはずっと大きくなります。

この理由は、実装の詳細が Objects/listobject.c にある、CPythonのソースにあります。

空のリスト

空のリストがある場合 [] が作成されると、要素のためのスペースは確保されません。 PyList_New . 36バイトは32ビットマシンでのリストデータ構造自体に必要な容量です。

1つの要素を持つリスト

要素が1つのリストの場合 [1] が作成されると、リストデータ構造自体が必要とするメモリに加えて、1つの要素のためのスペースが割り当てられます。この場合も PyList_New . 与えられた size を引数として与えると、計算します。

nbytes = size * sizeof(PyObject *);

そして、持っている。

if (size <= 0)
    op->ob_item = NULL;
else {
    op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
    if (op->ob_item == NULL) {
        Py_DECREF(op);
        return PyErr_NoMemory();
    }
    memset(op->ob_item, 0, nbytes);
}
Py_SIZE(op) = size;
op->allocated = size;

ということで size = 1 で、1つのポインタのためのスペースが確保されます。4バイト（私の32ビットボックス上）。

空のリストへの追加

を呼び出す場合 append を空のリストで呼び出すと、次のようになります。

• PyList_Append コール app1
• app1 リストのサイズを問い合わせる（そして答えとして0を得る）
• app1 そして list_resize で size+1 (この例では1)
• list_resize には興味深い割り当て戦略があり、そのソースからのこのコメントで要約されています。

ここにあります。

/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

計算をしてみよう

冒頭のセッションで引用した数字が、どのように到達するのかを見てみましょう。

つまり、36バイトは32ビットでのリストデータ構造自体が必要とするサイズです。要素が1つの場合、ポインタ1つ分のスペースが確保されるので、4バイト余分になり、合計40バイトになります。ここまではOKです。

いつ app1 が空のリストで呼ばれた場合、それは list_resize と共に size=1 . のオーバーアロケーションアルゴリズムによれば list_resize の過剰割り当てアルゴリズムによると、1の次に大きな利用可能なサイズは4なので、4つのポインタのための場所が割り当てられます。4 * 4 = 16 バイトで、36 + 16 = 52 となります。

確かに、すべてが理にかなっています :-)