Python リストの作成方法で占有するメモリサイズが異なる その3(終) (original) (raw)
はじめに
masamoriです。
このシリーズ最後です。
今回は、[0 for _ in range(3)]です。コードを追いましょう。
改めて確認
import sys
list = [0 for _ in range(3)]
print("sizeof list: ", sys.getsizeof(list))
[0 for _ in range(3)]の場合、メモリの使用量は上記のようになります。
disモジュールを使って計算ロジックを確認しましょう。
import dis
print("disassemble [0 for _ in range(3)]") dis.dis("[0 for i in range(3)]")
disassemble [0 for _ in range(3)] 0 0 RESUME 0
1 2 PUSH_NULL 4 LOAD_NAME 0 (range) 6 LOAD_CONST 0 (3) 8 CALL 1 16 GET_ITER 18 LOAD_FAST_AND_CLEAR 0 (i) 20 SWAP 2 22 BUILD_LIST 0 24 SWAP 2 >> 26 FOR_ITER 4 (to 38) 30 STORE_FAST 0 (i) 32 LOAD_CONST 1 (0) 34 LIST_APPEND 2 36 JUMP_BACKWARD 6 (to 26) >> 38 END_FOR 40 SWAP 2 42 STORE_FAST 0 (i) 44 RETURN_VALUE >> 46 SWAP 2 48 POP_TOP 50 SWAP 2 52 STORE_FAST 0 (i) 54 RERAISE 0 ExceptionTable: 22 to 38 -> 46 [2]
こうなります。長いですね。
しかし、大事な部分はメモリ割り当ての部分LIST_APPENDです。
CPython
では、該当部分PyList_Appendから見ていきます。
int PyList_Append(PyObject *op, PyObject *newitem) { if (PyList_Check(op) && (newitem != NULL)) { int ret; Py_BEGIN_CRITICAL_SECTION(op); ret = _PyList_AppendTakeRef((PyListObject *)op, Py_NewRef(newitem)); Py_END_CRITICAL_SECTION(); return ret; } PyErr_BadInternalCall(); return
_PyList_AppendTakeRefを確認します。
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem) { assert(self != NULL && newitem != NULL); assert(PyList_Check(self)); Py_ssize_t len = Py_SIZE(self); Py_ssize_t allocated = self->allocated; assert((size_t)len + 1 < PY_SSIZE_T_MAX); if (allocated > len) { #ifdef Py_GIL_DISABLED _Py_atomic_store_ptr_release(&self->ob_item[len], newitem); #else PyList_SET_ITEM(self, len, newitem); #endif Py_SET_SIZE(self, len + 1); return 0; } return _PyList_AppendTakeRefListResize(self, newitem); }
リストに対して十分なメモリが割り当てられている場合はreturn 0で処理を終えます。
しかし、十分なメモリが割り当てられていない場合は_PyList_AppendTakeRefListResizeを呼び出します。
最初の呼び出しではメモリはまだ割り当てられていないはずなので、_PyList_AppendTakeRefListResizeが呼び出されるはずです。
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem) { Py_ssize_t len = Py_SIZE(self); assert(self->allocated == -1 || self->allocated == len); if (list_resize(self, len + 1) < 0) { Py_DECREF(newitem); return -1; } FT_ATOMIC_STORE_PTR_RELEASE(self->ob_item[len], newitem); return 0; }
現在のリストのサイズを取得し、len + 1に拡張します。この時点で割り当てが少ない場合、list_resizeが呼び出されます。
static int list_resize(PyListObject *self, Py_ssize_t newsize) { size_t new_allocated, target_bytes; Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SET_SIZE(self, newsize);
return 0;
}
/* 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().
* Add padding to make the allocated size multiple of 4.
* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
* Note: new_allocated won't overflow because the largest possible value
* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
/* Do not overallocate if the new size is closer to overallocated size
* than to the old size.
*/
if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
if (newsize == 0)
new_allocated = 0;...略
重要なのはコメントの部分です。実はPythonはリストを拡大するたびにメモリを割り当てているわけではありません。ある程度のかたまりでメモリを増やしていきます。* Add padding to make the allocated size multiple of 4. * The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... この部分ですね。
なのでこの関数が最初に呼び出された時、まずは4つ分の長さのメモリが割り当てられます。 メモリの割り当てが終わり、要素が増加する分だけバイトコードLIST_APPENDが呼び出されます。しかし、list_resizeの最初の呼び出しでリストの要素4つ分メモリがすでに割り当てられているので、list_resizeは今回のケースではもう呼び出されません。
というわけで[0 for _ in range(3)]に割り当てられるメモリ量は
56(リストオブジェクトのbyteサイズ) + 4(要素数) * 8(byte) = 88(byte).
ということになるのですね。
確認
ということは、要素の数がひとつ増えたからといって、即座にメモリは再割り当てされないケースもあるということです。コメントから読み取れる情報から推測すると、[0 for _ in range(2)] と [0 for _ in range(3)]、[0 for _ in range(5)] と [0 for _ in range(7)] はメモリのサイズが一緒のはずです。
確認してみましょう。
import sys
list1 = [0 for _ in range(2)] list2 = [0 for _ in range(3)] list3 = [0 for _ in range(5)] list4 = [0 for _ in range(7)]
print("sizeof list1: ", sys.getsizeof(list1)) print("sizeof list2: ", sys.getsizeof(list2)) print("sizeof list3: ", sys.getsizeof(list3)) print("sizeof list4: ", sys.getsizeof(list4))
はい、同じでした。いちいちメモリを再割り当てしていると計算効率が下がってしまうのですのね。ある程度の余裕を持ってあらかじめメモリを割り当てる方が効率が良い、ということなのでしょう。
ちなみに、こちらも元記事とはpython内部の計算のロジックは違いました。(結果は一緒)
元記事はこちら.
Pythonの内部実装を見るって、なかなか面白いです。
また面白そうなネタがあれば書きたいと思います。