[Cython] Cython syntax to pre-allocate lists for performance

[Nikita Nemkin]

On Thu, 07 Mar 2013 17:16:10 +0600, Yury V. Zaytsev <yury at shurup.com>  
wrote:

> Hi,
>
> Is there any syntax that I can use to do something like this in Cython:
>
>     py_object_ = PyList_New(123); ?
>
> If not, do you think that this can be added in one way or another?
>
> Unfortunately, I can't think of a non-disruptive way of doing it. For
> instance, if this
>
>     [None] * N
>
> is given a completely new meaning, like make an empty list (of NULLs),
> instead of making a real list of Nones, it will certainly break Python
> code. Besides, it would probably be still faster than no pre-allocation,
> but slower than an empty list with pre-allocation...
>
> Maybe
>
>     [NULL] * N ?
>
> Any ideas?
>

I really like the "[NULL] * N" thing.

Efficient empty list allocation and filling is something I stumble upon
quite often, especially in binding code.

I doubt Cython will be able to automatically use PyList_SET_ITEM
for assignment to such NULL list (it would require induction variable
analysis), but eliminating one extra pass over the list is already helpful.

Implementation note (if this gets implemented):
Cython's optimized list assignment routine uses Py_DECREF, this will
have to be changed to Py_XDECREF, otherwise NULL list items won't be
directly assignable from Cython.
(PyList_SetItem always uses Py_XDECREF on the old element).


> What do you need it for?
>
> Won't list comprehensions work for you? They could potentially be adapted
> to presize the list.

List comprehensions do not preallocate the list.
If they did, the need for the above would be somewhat diminished.

> And why won't [None]*N help you out? It should be pretty cheap.

[None] * N makes