Хэш-функция для функции в Python
Опубликовано 12 September 2017 в Python
Пару недель назад один из моих коллег задал вопрос: можно ли использовать функцию в качестве ключей словаря? Да, можно. У каждой функции в Питоне есть хеш. Но как он считается? На основе имени функции? На основе байт-кода? В действительности, хэш считается трансформацией над указателем на объект функции. Тем не менее, не так-то легко отыскать эти расчеты в коде CPython.
Навигация по C-коду довольно интересный опыт, хотя делать это совсем не просто: все эти макросы делают простой поиск нужных переходов довольно сложным. Конечно, я уверен, что вы сможете с этим справиться и найти все вызываемые функции при запросе хеша для объекта функции.
Но давайте поступим немного по-другому. Мы пройдем всего пару вызовов, что бы понять как CPython работает, а затем поговорим об устройстве CPython, что бы не нужно было искать потерянные вызовы в куче макросов.
Я буду использовать master-ветку официального репозитория CPython. Вы можете его клонировать или исследовать в браузере. Объект функции описан в файле funcobject.c. Наиболее интересная нам часть вот эта:
PyTypeObject PyFunction_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"function",
sizeof(PyFunctionObject),
0,
(destructor)func_dealloc, /* tp_dealloc */
0, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_reserved */
(reprfunc)func_repr, /* tp_repr */
0, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
0, /* tp_hash */
function_call, /* tp_call */
0, /* tp_str */
0, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
func_new__doc__, /* tp_doc */
(traverseproc)func_traverse, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
offsetof(PyFunctionObject, func_weakreflist), /* tp_weaklistoffset */
0, /* tp_iter */
0, /* tp_iternext */
0, /* tp_methods */
func_memberlist, /* tp_members */
func_getsetlist, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
func_descr_get, /* tp_descr_get */
0, /* tp_descr_set */
offsetof(PyFunctionObject, func_dict), /* tp_dictoffset */
0, /* tp_init */
0, /* tp_alloc */
func_new, /* tp_new */
};
Это декларация типа функции. Каждая строка помеченная комментарием tp_something
- указатель на C функцию, которая делает что-либо специфичное для заданного типа. При этом, если указан 0, то это значит, что будет вызываться унаследованная функция. В нашем случае для tp_hash
указан именно 0.
Найти эту функцию, которая будет вызываться по умолчанию, не просто. В файле есть всего одно место где используется структура PyFunction_Type
: она фигурирует в качестве параметра вызова макроса PyObject_GC_New
внутри PyFunction_NewWithQualName
.
Хотя, как я уже говорил, походить по сишному коду может быть интересным занятием, мы воспользуемся коротким путем. Если просмотреть документ "CPython’s PyTypeObject", то становится более или менее понятно как организован и как работает PyTypeObject. В этом же документе можно узнать, что функцию по умолчанию для tp_hash
нужно искать в PyBaseObject_Type.tp_hash
и что значение по умолчанию равно _Py_HashPointer
.
Теперь мы легко найдем нужную нам функцию:
Py_hash_t
_Py_HashPointer(void *p)
{
Py_hash_t x;
size_t y = (size_t)p;
/* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
excessive hash collisions for dicts and sets */
y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
x = (Py_hash_t)y;
if (x == -1)
x = -2;
return x;
}
Как видно, никакого полного имени функции не используется. Хэш функции - это всего лишь значение зависящее от значения указателя на объект функции.
Это было довольно интересное погружение в CPython. Конечно, я использовал "короткий путь". Тем не менее даже он требует некоторых знаний того, как устроен интерпретатор изнутри. Пожалуй лучший способ разобраться с этим посмотреть видео CPython Internals.
Возник вопрос? Мне всегда можно написать в Twitter: avkorablev