こんにちは、AI ShiftのAIチームの干飯(@hosimesi11_)です。
この記事はAI Shift Advent Calendar 14日目の記事になります。
本記事では、CPython(※ 以下Python)のメモリ管理・GCについて執筆を行います。
はじめに
機械学習分野ではPythonが重宝します。C言語などと違い、Pythonでは自身でメモリ管理を意識することはありません。また、Pythonではハードウェアの制約はあるにせよすべての整数を持つことができます。
C言語では具体的にメモリ領域をmallocで確保し、freeで解放します。これらに当たる処理をPythonではGC(Garbage Collection)が管理してくれています。この辺りは、通常のPythonでのアプリケーション実装では考える機会は少ないですが、高速化のためにC言語で書かれたコードをCythonインターフェイスから呼び出す際などに必要になります。また、Pythonがどのように書かれているかを知ることで、より良い効率的なコードを書くことができる可能性があります。
本記事では、Pythonでのメモリ管理、GCがどのように行われているのかについてコードリーディングしていきたいと思います。
※ 本記事の対象はPython3.11です。3.12でも変更が入りそうです。
メモリ管理
メモリ管理と一口に言っても、範囲が広く単体で議論するのは困難です。なので、今回は組み込みオブジェクトである整数オブジェクト、リストオブジェクトを見ていきます。
整数オブジェクト
C言語などではint型などの範囲は決まっています。エンジニアは値の取りうる値を判断し、int、longなどで変数を初期化します。一方で、Pythonではハードウェアの制約はありますが、どんな大きい値も持つことができます。
これらはどのように実現されているのでしょうか。コードを見ていきたいと思います。
Pythonでは全てのオブジェクトの基礎になるものをPyObjectとして定義しています。
typedef struct _object {
_PyObject_HEAD_EXTRA
Py_ssize_t ob_refcnt;
PyTypeObject *ob_type;
} PyObject;そして、Pythonの整数型は以下のように定義されています。
// https://github.com/python/cpython/blob/3.11/Include/cpython/longintrepr.h
struct _longobject {
PyObject_VAR_HEAD;
digit ob_digit[1];
};ユーザ定義の構造体やマクロを展開し、もう少し詳しく見ます。
#define PyObject_VAR_HEAD PyVarObject ob_base;
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
struct _longobject {
_PyObject_HEAD_EXTRA;
ssize_t ob_refcnt;
PyTypeObject *ob_type;
ssize_t ob_size; /* Number of items in variable part */
uint32_t ob_digit[1];
};ここで、_PyObject_HEAD_EXTRAは双方向の連結リストになっており、前後のオブジェクトのポインタを保持しています。ob_refcntはGCのための参照数を扱うための(signedな)整数型になります。ob_typeは型情報であり、今回の場合は整数型の情報になります。
そして、整数型の実体は以下の二つの情報が表現します。
- ob_size
- ob_digit[1]
ob_sizeは整数型を表現する配列の長さと、符号を持ちます。そして、ob_digitが実際の値を持ちます。Pythonは任意の大きさの整数を表現できるため、その値は単一の数値として表現することはできず、配列を用いています。そのため、ob_digitを用いて数値を「桁」ごとに分割し、それぞれを配列の要素として格納します。基数(2進数のようなもの)を用いて各桁ごとに配列に入っているイメージです。ob_sizeは配列の長さが入りますが、ob_sizeの符号で整数型の正負を表現しています。
|-------------|-----------------------|
| ob_size | ob_digit |
|-------------|-----------------------|
| -2 | 1332433 | 1149 |
|-------------|-----------------------|つまり、どのようなサイズであれ、ob_sizeを増やし、ob_digitの長さを伸ばすことで任意の大きさの整数を持つことができます。
また、-5から256までの値に対して、事前にPyLongオブジェクトを事前に生成して、キャッシュしています。正の整数に関してはforなどの効率が上がり、負の整数は配列の最後の要素などによく使われるからだと思います。
#define _PY_NSMALLPOSINTS 257
#define _PY_NSMALLNEGINTS 5
#define IS_SMALL_INT(ival) (-_PY_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)
static PyObject *
get_small_int(sdigit ival)
{
assert(IS_SMALL_INT(ival));
PyObject *v = (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + ival];
Py_INCREF(v);
return v;
}Appendix
具体的にどういうレイアウト？
PythonオブジェクトはPyObject_HEAD と、実体のオブジェクトに分かれています。
|-------------|------------|---------------
| ob_refcnt | *ob_type | objectの実体 ・・・
|-------------|------------|---------------GCのためにさらに情報を追加します。
|-------------|-------------|-------------|------------|-------------|--
| *_gc_next | *_gc_prev | ob_refcnt | *ob_type | objectの実体 ・・・
|-------------|-------------|-------------|------------|-------------|--新しいPyGC_Head は双方向の連結リストになっており、一つ前のオブジェクトのポインタと1つ後ろのオブジェクトのポインタを持ちます。その後、オブジェクトの実体と続いています。
ヒープ領域を制限したい？
Pythonは上記でも分かるように、デフォルトで制限なくヒープ領域を確保しようとします。しかし、Python上で使用するヒープ領域に上限をかけることでリソースの管理が可能になります。
pythonにはresourceモジュールがあり、setrlimitで上限を設定できます。
memory_bytes = os.sysconf("SC_PAGE_SIZE") * os.sysconf("SC_PHYS_PAGES")
resource.setrlimit(resource.RLIMIT_DATA, (memory_bytes, -1))リストオブジェクト
C言語などの配列ではあらかじめサイズを指定し、メモリを確保します。一方で、Pythonでは動的にメモリを確保し、基本的にどんなサイズのリストも持つことができます。
また、配列に要素を追加する(append)場合と、リスト内包表記をした場合で実行速度が異なるといった挙動があります。
これらはどのように実現されているのでしょうか。
リストのメモリ確保
a = [1]このようにlistを初期化した際、Pythonでは以下のような関数が呼ばれます。これを見る限りでは、通常のC言語などと同様に要素分のサイズの配列を確保します。
static PyObject *
list_new_prealloc(Py_ssize_t size)
{
assert(size > 0);
PyListObject *op = (PyListObject *) PyList_New(0);
if (op == NULL) {
return NULL;
}
assert(op->ob_item == NULL);
op->ob_item = PyMem_New(PyObject *, size);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
op->allocated = size;
return (PyObject *) op;
}では、このリストに要素を追加する場合はどうなるのでしょうか。今のままでは追加できる領域は存在し得ないはずです。
要素の追加時は以下の関数が呼ばれ、リサイズされます。(呼び出し元は別ですが、重要な部分を抜粋しています。)
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SET_SIZE(self, newsize);
return 0;
}
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
// 省略
}- 今の配列(allocated)が新しいもの(newsize)より小さいかつ、半分以上の場合、メモリの再確保はせず、新しいサイズにリサイズします。
- 新しいサイズに対して1/8を加え、さらに6を加えてから、最下位2ビットを0にします。少し多めにメモリを確保することによって、連続した要素の追加にも効率が良くなります。
newsize >> 3
- それ以外は新しくメモリを確保します。(チェックなどを省略しているので、詳しくは実装を見てください。)
このようにすることで、動的にメモリを確保し、どんなサイズのリストも持てるようになっています。
appendと内包表記
上記のようにlistのappendでは、メモリの再確保などが発生しうります。また、for文で回すため命令が増えます。
内包表記の場合、listのサイズがあらかじめ把握でき、追加処理のバイトコードを直接参照できます。それぞれの処理を確認してみます。
append
from dis import dis
def list_append():
loop_list = []
for i in range(10):
loop_list.append(i)
return loop_list
print(dis(list_append))
コードの行番号 命令オフセット 命令 オペランド 付加情報
6 0 BUILD_LIST 0
2 STORE_FAST 0 (loop_list)
7 4 LOAD_GLOBAL 0 (range)
6 LOAD_CONST 1 (10)
8 CALL_FUNCTION 1
10 GET_ITER
>> 12 FOR_ITER 14 (to 28)
14 STORE_FAST 1 (i)
8 16 LOAD_FAST 0 (loop_list)
18 LOAD_METHOD 1 (append)
20 LOAD_FAST 1 (i)
22 CALL_METHOD 1
24 POP_TOP
26 JUMP_ABSOLUTE 12
9 >> 28 LOAD_FAST 0 (loop_list)
30 RETURN_VALUE内包表記
from dis import dis
def list_comprehension():
return [i for i in range(10)]
print(dis(list_comprehension))15 0 BUILD_LIST 0
2 LOAD_FAST 0 (.0)
>> 4 FOR_ITER 8 (to 14)
6 STORE_FAST 1 (i)
8 LOAD_FAST 1 (i)
10 LIST_APPEND 2
12 JUMP_ABSOLUTE 4
>> 14 RETURN_VALUEこれらのバイトコードを見ると以下の違いが見受けられます。
// append
LOAD_METHOD
CALL_METHOD
POP_TOP
// 内包表記
LIST_APPEND つまり、命令数の少なさと重い処理(LOAD_METHOD、CALL_METHOD、POP_TOPのいずれかは未確認です。)がないことが内包表記の高速化につながっています。また、内包表記では、直接LIST_APPENDを呼び出せることによるメリットもあります。
GC
PythonでGCを扱う上で一般的なのはgcモジュールがあります。PythonではGCの手法として大きく2つ準備しています。
- 参照カウントによるGC
- 循環参照のオブジェクトのGC
Pythonでは基本的に参照カウントと呼ばれる方法でオブジェクトを管理します。参照カウントによるメモリ管理とは、オブジェクトへの参照が0になった際に、どの部分からもアクセスされていないと認識し、メモリを解放するといったものです。
参照カウントはsysモジュールのgetrefcountを使って確認することができます。
import sys
sample = []
print(sys.getrefcount(sample))
// 2ここで参照カウントが2になっているのは、getrefcountで参照している分が含まれているからです。参照カウントが0になった時、イメージとしては以下のdelのようなデストラクタが呼び出されます。
class A:
# 省略
def __del__(self):
free()Cレベルでは、Py_DECREFが呼び出され、デストラクタである_Py_Deallocが一般的に呼び出されます。
void
_Py_Dealloc(PyObject *op)
{
PyTypeObject *type = Py_TYPE(op);
destructor dealloc = type->tp_dealloc;
// 省略
}参照カウントによるGCには問題点もあります。参照カウントによるGCでは循環参照を処理できません。循環参照とは以下のようなオブジェクトのことを言います。
obj = []
obj.append(obj)
print(sys.getrefcount(obj))
// 3ここでobjは自身への参照も持っているため、今のままだと、参照カウントが0になることはありません。Pythonではこれらの循環参照のオブジェクトのために別途GCの仕組みを用意しています。
定期的にgc.collect()をして、ルートオブジェクトから到達可能か確認し、到達不能なオブジェクトに関してはメモリ解放しています。
実際gc.collect()を実行するとPyGC_Collectが呼び出されます。PyGC_CollectはGILの影響でスレッドの情報などを取得して処理をしていますが、重要な部分は以下の関数です。
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
// 対象となる世代とそれより若い世代のオブジェクトをマージ
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
}
young = GEN_HEAD(gcstate, generation);
// 到達不能なオブジェクトを特定
deduce_unreachable(young, &unreachable);
// final_unreachableセット内のオブジェクトに対してtp_clearを呼び出し、参照参照を解放。
delete_garbage(tstate, gcstate, &final_unreachable, old);
}上記からもわかるように、PythonのGCは世代的なアプローチを採用しており、GCが実行される度に残ったオブジェクトの世代が1つ増やされます(3世代まであります)。高い世代のオブジェクトは少ない頻度でGCの対象となるため、GCのオーバーヘッドを抑えることができる工夫もされています。
Appendix
定期的にgcの走査をしていると言うが具体的にはいつ？
最後に検出を行ってから生成・削除したオブジェクトの数をカウントしており、この数によって検出を開始します。オブジェクトの生成数 - 削除数が0世代の閾値より大きくなると、検出を開始します。最初は第0世代のオブジェクトのみを走査し、第1世代の走査が 第1世代の閾値回実行されると、 第1世代のオブジェクトの検査を行います。同様に、 第1世代が第2世代の閾値回検査されると、 第2世代の検査を行います。
gcモジュールからも具体的に設定可能となっており、以下のように設定できます。
import gc
gc.set_threshold(700, 10, 10)たとえば、0世代の閾値が700である場合、700個の新たなオブジェクトが割り当てられると0世代のGCが実行されます。同様に、1世代の閾値が10である場合、0世代のGCが10回実行されると1世代のGCが実行されます。
おわりに
今回は、Pythonの数種類のオブジェクトのメモリ確保や、GCの挙動について確認しました。
CPythonでは毎年50%の高速化を行い、4年間で5倍の高速化を目標とするfaster-cpython が進んでいます。GILの除去などで高速化をより進めるということなので、これからも定期的にコードリーディングしていきたいと思います。
個人的にはPython3.11からのトレースバック時に詳細なエラーの場所を提示してくれる機能が便利です！
AI Shiftではエンジニアの採用に力を入れています！この分野に少しでも興味を持っていただけましたら、カジュアル面談でお話しませんか？（オンライン・19時以降の面談も可能です！）
明日のAdvent Calendar 15日目の記事は、AIチームの邊土名による 対話システムシンポジウム参加報告 の記事の予定です。こちらもよろしくお願いいたします。
