Pythonのint入門の入門
はじめにのはじめに
この記事は2020年ISアドベントカレンダーの７日目として書かれました。明日はハードウェア構成法の鬼テストななまる君の記事です。楽しみですね！
はじめに
書いた人
概要
目標と注意
- 目標はintを読むことですが、全体としてあまり筋道立っていない散漫な記事になりました。
流れ
- cpythonについて
- pyobjectたちについて
- intについて
pythonとcpython
pythonはいくつかの処理系を持ちますが、その殆どがcpythonです。
他の処理系も（pypy等）色々あります。下の記事によくまとまっていました。
「pypyはJITコンパイラを持ち、javaっぽくなって速い（？？）」という話がありますが、Cで書かれたモジュールなどとの互換性を考えるとcpythonを使っておくのが丸そうです。
cpythonのデータ構造
では、実際にcpythonの中身を読んでみましょう！実装はここ（https://github.com/python/cpython )にころがっています。 intに行く前に、それの母体となるPyobjectから見ていきましょう。
Pyobject
この中の/include/object.hにすべてのオブジェクトの基となるPyobjectが書かれています。
#define _PyObject_HEAD_EXTRA \
struct _object *_ob_next; \
struct _object *_ob_prev;
...中略
typedef struct _object {
_PyObject_HEAD_EXTRA
Py_ssize_t ob_refcnt;
PyTypeObject *ob_type;
} PyObject;
構造体のメンバ変数を一つずつ見ていきましょう。
_ob_nextと_ob_prev
公式ドキュメントによると、
These fields are only present when the macro Py_TRACE_REFS is defined. Their initialization to NULL is taken care of by the PyObject_HEAD_INIT macro. For statically allocated objects, these fields always remain NULL. For dynamically allocated objects, these two fields are used to link the object into a doubly-linked list of all live objects on the heap. This could be used for various debugging purposes; currently the only use is to print the objects that are still alive at the end of a run when the environment variable PYTHONDUMPREFS is set. https://docs.python.org/3/c-api/typeobj.html
Py_TRACE_REFS が指定されているときかつオブジェクトのサイズが動的に変わる時に使われるということなので、debug時に何か働いてくれてるんでしょう。ちなみに僕はどう使われるか理解してません。ガハハ https://www.oreilly.com/library/view/python-cookbook/0596001673/ch16s09.html
ob_refcnt
参照カウンタ（このobjectが何回参照されているか）。pythonなら普通これが0になれば自動でオブジェクトが破壊されます。
ob_type
型が入っている。「こいつ(ob_type)の型」がPyTypeObjectなので、こいつの説明に入ります。
PyTypeObject
型に対応する関数とかモリモリ
定義
まずは、定義を見ると/include/obejct.hには
/* PyTypeObject structure is defined in cpython/object.h. In Py_LIMITED_API, PyTypeObject is an opaque structure. */ typedef struct _typeobject PyTypeObject;
とある。特にインクルードしてるファイルもないし_typeobjectについて上で書かれているわけでもないのでよく分からなかったが、/Include/cpython/object.hにそれっぽい実装があるのでそれを読むと
struct _typeobject {
PyObject_VAR_HEAD
const char *tp_name; /* For printing, in format "<module>.<name>" */
Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */
/* Methods to implement standard operations */
destructor tp_dealloc;
Py_ssize_t tp_vectorcall_offset;
getattrfunc tp_getattr;
setattrfunc tp_setattr;
PyAsyncMethods *tp_as_async; /* formerly known as tp_compare (Python 2)
or tp_reserved (Python 3) */
reprfunc tp_repr;
/* Method suites for standard classes */
PyNumberMethods *tp_as_number;
PySequenceMethods *tp_as_sequence;
PyMappingMethods *tp_as_mapping;
/* More standard operations (here for binary compatibility) */
hashfunc tp_hash;
ternaryfunc tp_call;
reprfunc tp_str;
getattrofunc tp_getattro;
setattrofunc tp_setattro;
/* Functions to access object as input/output buffer */
PyBufferProcs *tp_as_buffer;
/* Flags to define presence of optional/expanded features */
unsigned long tp_flags;
const char *tp_doc; /* Documentation string */
/* Assigned meaning in release 2.0 */
/* call function for all accessible objects */
traverseproc tp_traverse;
...略
1００行を超えて居たのでこれのすべてを理解をするのは諦めるとして、分かるところだけをさらって分かった風に振る舞います
PyObject_VAR_HEAD
- pyvarobjectに必要なものを固めてるもの
- tp_name
- 型の名前でしょう
- getattrfunc
- get attribute functionの略っぽいので、属性（それに付随するメンバ関数やメンバ変数）をgetできるんでしょう
- ソース https://docs.python.org/ja/3/c-api/typeobj.html#c.getattrfunc
あまり慣習がわかっていなくて、cpython/Include/object.hをcpython/Include/cpython/object.hで使っていそうなのが自分には少し気持ち悪いです。
customな型の実装例
定義は上のような形でしたが、実際にcustomな型の実装例を見るのも良い気がしていて以下から引っ張ってきました。 https://docs.python.org/ja/3/extending/newtypes_tutorial.html#defining-new-types
少しだけ説明を加えます
PyObject_HEADは素のPy_objectである。
PyModule_Createで、引数に従ってモジュールを作ってる。
PyModule_Createのドキュメントも置いておきます。 https://docs.python.org/ja/3/c-api/module.html
#define PY_SSIZE_T_CLEAN
#include <Python.h>
typedef struct {
PyObject_HEAD
/* Type-specific fields go here. */
} CustomObject;
static PyTypeObject CustomType = {
PyVarObject_HEAD_INIT(NULL, 0)
.tp_name = "custom.Custom",
.tp_doc = "Custom objects",
.tp_basicsize = sizeof(CustomObject),
.tp_itemsize = 0,
.tp_flags = Py_TPFLAGS_DEFAULT,
.tp_new = PyType_GenericNew,
};
static PyModuleDef custommodule = {
PyModuleDef_HEAD_INIT,
.m_name = "custom",
.m_doc = "Example module that creates an extension type.",
.m_size = -1,
};
PyMODINIT_FUNC
PyInit_custom(void)
{
PyObject *m;
if (PyType_Ready(&CustomType) < 0)
return NULL;
m = PyModule_Create(&custommodule);
if (m == NULL)
return NULL;
Py_INCREF(&CustomType);
if (PyModule_AddObject(m, "Custom", (PyObject *) &CustomType) < 0) {
Py_DECREF(&CustomType);
Py_DECREF(m);
return NULL;
}
return m;
}
PyVarObject
既に何回か登場しているのですが、PyVarObjectの下位存在的な形でPyVarObjectというものが存在します。これをひな形にしてintやfloatなどが作られています。まずこの定義を見ましょう。
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
PyObjectに一つ変数が追加された形になっています。 変数(variable)の構造体なのにob_size?それもNumber of itemsと言い始めるところが怖いですね。
intの実装
本題に入ります。まずはintのヘッダファイルから見てみましょう。 https://github.com/python/cpython/blob/master/Include/longintrepr.h
定義をみると
typedef uint32_t digit;
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
となっています。 「上から一つの桁に一つの数字が入る」というデータ構造をしている事がわかります。pythonのintは配列なんですね。
満を持してlongintrepr.cをみると、5740行あって泣く。あれ、というかcpythonを読もうとするたび毎回ここでやめていませんか？
アドベントカレンダー書く時ぐらいしか読まないと思うので少しだけ読むと、まずメモリの確保が出てきます。
_PyLong_New(Py_ssize_t size)
{
PyLongObject *result;
/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
sizeof(digit)*size. Previous incarnations of this code used
sizeof(PyVarObject) instead of the offsetof, but this risks being
incorrect in the presence of padding between the PyVarObject header
and the digits. */
if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
PyErr_SetString(PyExc_OverflowError,
"too many digits in integer");
return NULL;
}
result = PyObject_Malloc(offsetof(PyLongObject, ob_digit) +
size*sizeof(digit));
if (!result) {
PyErr_NoMemory();
return NULL;
}
_PyObject_InitVar((PyVarObject*)result, &PyLong_Type, size);
return result;
}
MAX_LONG_DIGITSというのが環境に用意されていて、それでobjectを作るか決めたり、これはmallocで確保して、足りないときは云々...という処理に見える。
次に、longからpythonのlongを作る関数っぽいものがある。
PyLong_FromLong(long ival)
{
PyLongObject *v;
unsigned long abs_ival;
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
int sign;
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
if (ival < 0) {
/* negate: can't write this as abs_ival = -ival since that
invokes undefined behaviour when ival is LONG_MIN */
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
sign = ival == 0 ? 0 : 1;
}
/* Fast path for single-digit ints */
if (!(abs_ival >> PyLong_SHIFT)) {
v = _PyLong_New(1);
if (v) {
Py_SET_SIZE(v, sign);
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival, unsigned long, digit);
}
return (PyObject*)v;
}
#if PyLong_SHIFT==15
/* 2 digits */
if (!(abs_ival >> 2*PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SET_SIZE(v, 2 * sign);
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival & PyLong_MASK, unsigned long, digit);
v->ob_digit[1] = Py_SAFE_DOWNCAST(
abs_ival >> PyLong_SHIFT, unsigned long, digit);
}
return (PyObject*)v;
}
#endif
/* Larger numbers: loop to determine number of digits */
t = abs_ival;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->ob_digit;
Py_SET_SIZE(v, ndigits * sign);
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(
t & PyLong_MASK, unsigned long, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
これがpythonのintの作り方として結構わかりやすそうですね。まず最初にabs_ival >> PyLong_SHIFT というif文でpylong_shift（一般に30桁）に収まるものはそれに収めて返しています。v->ob_digit[0]ということで、０桁目しか使っていないことが見て取れますね。次に、それにおさまらないものを桁数を増やしたりなどして収めて返している事がわかります。
いくつか飛ばして、doubleからpythonのlongを作るものが出て来ました。これは面白そうなので読むと
PyLong_FromDouble(double dval)
{
/* Try to get out cheap if this fits in a long. When a finite value of real
* floating type is converted to an integer type, the value is truncated
* toward zero. If the value of the integral part cannot be represented by
* the integer type, the behavior is undefined. Thus, we must check that
* value is in range (LONG_MIN - 1, LONG_MAX + 1). If a long has more bits
* of precision than a double, casting LONG_MIN - 1 to double may yield an
* approximation, but LONG_MAX + 1 is a power of two and can be represented
* as double exactly (assuming FLT_RADIX is 2 or 16), so for simplicity
* check against [-(LONG_MAX + 1), LONG_MAX + 1).
*/
const double int_max = (unsigned long)LONG_MAX + 1;
if (-int_max < dval && dval < int_max) {
return PyLong_FromLong((long)dval);
}
PyLongObject *v;
double frac;
int i, ndig, expo, neg;
neg = 0;
if (Py_IS_INFINITY(dval)) {
PyErr_SetString(PyExc_OverflowError,
"cannot convert float infinity to integer");
return NULL;
}
if (Py_IS_NAN(dval)) {
PyErr_SetString(PyExc_ValueError,
"cannot convert float NaN to integer");
return NULL;
}
if (dval < 0.0) {
neg = 1;
dval = -dval;
}
frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
assert(expo > 0);
ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
v = _PyLong_New(ndig);
if (v == NULL)
return NULL;
frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
for (i = ndig; --i >= 0; ) {
digit bits = (digit)frac;
v->ob_digit[i] = bits;
frac = frac - (double)bits;
frac = ldexp(frac, PyLong_SHIFT);
}
if (neg) {
Py_SET_SIZE(v, -(Py_SIZE(v)));
}
return (PyObject *)v;
}
値がある程度小さければCのlongに直してから、pythonのlongになおしていますね。 次に無限大の判定等をしていますが、これはC由来ののisinfを使っているようです。（cpython/Include/pymath.h） 計算機システムやパタヘネでやった事が出てきて嬉しいですね。 frexpはC++とかにあるやつと同じで浮動小数点をx * 2**nの形に分解していそうです。 そう考えると、pylong_shift（一桁あたりのbit数）乗で区切って、これをob_digitに一桁ずつ入れていくところが見て取れます。 https://cpprefjp.github.io/reference/cmath/frexp.html#:~:text=frexp%20%E9%96%A2%E6%95%B0%20
PyLong_SHIFT
これは自分が誤解をしているかもしれないのですが、こいつがpythonのintのそれぞれの桁に入りうるbit数を司っていると思って自分は生きています。最初の方のifdefを見ると一般にこれが30であることが推測され、此の時「30bitずつが一桁」になります。
colaboratoryでの実験結果を置いておきます。
floatの実装
typedef struct {
PyObject_HEAD
double ob_fval;
} PyFloatObject;
doubleです。特になし。 https://github.com/python/cpython/blob/ae00a5a88534fd45939f86c12e038da9fa6f9ed6/Include/floatobject.h
終わりに
いかがでしたか？C＋＋もpythonも無知なので、どこか間違っていたらすいません。よく考えたら自分は去年のこれぐらいの時期も同じことをしていました。去年からほんの少ししか理解が進んでい無さそう... 来年も同じことしてるかもしれません。来年の自分さん、来年のadvenr calenderはpythonのlistの実装あたりでどうですか。
