A question about fill_free_list(void) function

[Pedram]

Hello community,
I'm reading the CPython interpreter source code,
first, if you have something that I should know for better reading
this source code, I would much appreciate that
second, in intobject.c file, I read the following code in
fill_free_list function that I couldn't understand:
<code>while (--q > p)
Py_TYPE(q) = (struct _typeobject *)(q-1);
Py_TYPE(q) = NULL;
</code>
What does it mean?

Thanks.

 

[Pedram]

Oh... I got it!
I found this line in ctypes.h:
#define Py_TYPE(q) = ((PyObject *)(q))->ob_next;
So those lines are trying to set the blocks type from rear to front.

But I still don't know why after the while (when q is equal to p), the
Py_TYPE(q) set to NULL!

 

[Pedram]

The code is abusing the ob_type member to store a single linked, NULL
terminated list of free integer objects. It's a tricky optimization you
don't have to understand in order to understand the rest of the code.

And no, the code in ctypes.h is totally unrelated to the free list in
intobject.c.

Christian

Thanks for reply.
I totally understood the fill_free_list() function. Thanks.
But I have problems in understanding the PyInt_FromLong(). Here's the
code:

PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
#ifdef COUNT_ALLOCS
if (ival >= 0)
quick_int_allocs++;
else
quick_neg_int_allocs++;
#endif
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}

v = free_list; // <-- No problem till here
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}

I understood that small numbers (between -5 and 256) are referenced to
small_ints list. Others have to store in PyIntBlock, am I right? OK,
no problem till 'v = free_list;' but can't understand the line
'free_list = (PyIntObject *)Py_TYPE(v);' . Where free_list
referenced to? Don't this correct that free_list have to be referenced
to another free block so next time the function called v store in this
location?
Sorry for my bad English. I hope you could understand me

 

[Peter Otten]

The code is abusing the ob_type member to store a single linked, NULL
terminated list of free integer objects. It's a tricky optimization you
don't have to understand in order to understand the rest of the code.

And no, the code in ctypes.h is totally unrelated to the free list in
intobject.c.

Christian

Thanks for reply.
I totally understood the fill_free_list() function. Thanks.
But I have problems in understanding the PyInt_FromLong(). Here's the
code:

PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
#ifdef COUNT_ALLOCS
if (ival >= 0)
quick_int_allocs++;
else
quick_neg_int_allocs++;
#endif
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}

v = free_list; // <-- No problem till here
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}

I understood that small numbers (between -5 and 256) are referenced to
small_ints list. Others have to store in PyIntBlock, am I right? OK,
no problem till 'v = free_list;' but can't understand the line
'free_list = (PyIntObject *)Py_TYPE(v);' . Where free_list
referenced to? Don't this correct that free_list have to be referenced
to another free block so next time the function called v store in this
location?
Sorry for my bad English. I hope you could understand me

Well, if I understand fill_free_list() correctly, you haven't It only
makes sense together with the allocation code in PyInt_FromLong().

Py_TYPE(v) translates to v->ob_type, and in fill_free_list() that field was
abused(*) to hold a pointer to the previous item in the array of free
integers, thereby temporarily turning it into a linked list.

Assuming that free_list pointed to block->objects[10] in the current
PyIntBlock it will now point to block->objects[9].

When block->objects[0] is reached free_list will be set to NULL as block-

objects[0]->ob_type was initialized with NULL by the line

Py_TYPE(q) = NULL; /* in fill_free_list() */

The next call of PyInt_FromLong() will then trigger the allocation of a new
block.

Peter

(*) It may help if you think of the objects array as a

union linked {
linked *next;
PyInt_Object obj;
};

 

[Pedram]

Thanks for reply.
I totally understood the fill_free_list() function. Thanks.
But I have problems in understanding the PyInt_FromLong(). Here's the
code:

PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
#ifdef COUNT_ALLOCS
if (ival >= 0)
quick_int_allocs++;
else
quick_neg_int_allocs++;
#endif
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}

v = free_list; // <-- No problem till here
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}

I understood that small numbers (between -5 and 256) are referenced to
small_ints list. Others have to store in PyIntBlock, am I right? OK,
no problem till 'v = free_list;' but can't understand the line
'free_list = (PyIntObject *)Py_TYPE(v);' . Where free_list
referenced to? Don't this correct that free_list have to be referenced
to another free block so next time the function called v store in this
location?
Sorry for my bad English. I hope you could understand me

Well, if I understand fill_free_list() correctly, you haven't It only
makes sense together with the allocation code in PyInt_FromLong().

Py_TYPE(v) translates to v->ob_type, and in fill_free_list() that field was
abused(*) to hold a pointer to the previous item in the array of free
integers, thereby temporarily turning it into a linked list.

Assuming that free_list pointed to block->objects[10] in the current
PyIntBlock it will now point to block->objects[9].

When block->objects[0] is reached free_list will be set to NULL as block-

objects[0]->ob_type was initialized with NULL by the line

Py_TYPE(q) = NULL; /* in fill_free_list() */

The next call of PyInt_FromLong() will then trigger the allocation of a new
block.

Peter

(*) It may help if you think of the objects array as a

union linked {
    linked *next;
    PyInt_Object obj;





};

Oh, I got it! What a wonderful implementation!
Thanks so much Peter. You made my day I didn't read the code
carefully.

 

[Gabriel Genellina]

[snip explanation of strange pointer manipulations in the C code of the
integer type]

Oh, I got it! What a wonderful implementation!

Well, I would not say it's "wonderful"...
The wonderful part is that all those nasty tricks are only there, hidden
from us poor mortals, so we can focus on writing nice and elegant Python
code instead