python のリストの実装方法を調べてみた

python のリストの実装方法を調べたメモ。

・要素へのアクセスは以下の様に配列へのアクセスになっている。（listobject.h）
　※内部ではいわゆるリストではなく、配列で実装されている。

     #define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
     #define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])

・要素追加時に空き領域がないと、以下の様にサイズを拡張している。（listobject.c）
　※newsize: リストのサイズ, new_allocated: 空き領域を含めたサイズ

     The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

・拡張時にはリストのコピーが行われる。（listobject.c, pymem.h）

  #define PyMem_RESIZE(p, type, n) \
    ( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL :        \
          (type *) PyMem_REALLOC((p), (n) * sizeof(type)) )

  if (new_allocated <= (SIZE_MAX / sizeof(PyObject *)))
     PyMem_RESIZE(items, PyObject *, new_allocated);