generate tuples from sequence

Peter Otten __peter__ at web.de
Thu Jan 18 13:51:20 CET 2007


Duncan Booth wrote:

> Peter Otten <__peter__ at web.de> wrote:
>> But still, to help my lack of fantasy -- what would a sane zip()
>> implementation look like that does not guarantee the above output?
>> 
> Hypothetically?
> 
> The code in zip which builds the result tuples looks (ignoring error
> handling) like:
> 
> // inside a loop building each result element...
>     PyObject *next = PyTuple_New(itemsize);
> 
>     for (j = 0; j < itemsize; j++) {
>         PyObject *it = PyTuple_GET_ITEM(itlist, j);
>         PyObject *item = PyIter_Next(it);
>         PyTuple_SET_ITEM(next, j, item);
>     }
> 
> For fixed size tuples you can create them using PyTuple_Pack. So imagine
> some world where the following code works faster for small tuples:
> 
>    // Outside the loop building the result list:
>    PyObject *a, *b, *c;
>    if (itemsize >= 1 && itemsize <= 3) a = PyTuple_GET_ITEM(...);
>    if (itemsize >= 2 && itemsize <= 3) b = PyTuple_GET_ITEM(...);
>    if (itemsize == 3) c = PyTuple_GET_ITEM(...);
>    ...
> 
>    // inside the result list loop:
>    PyObject *next;
>    if (itemsize==1) {
>        next = PyTuple_Pack(1,
>                 PyIter_Next(a));
>    } else if (itemsize==2) {
>        next = PyTuple_Pack(2,
>                 PyIter_Next(a),
>                 PyIter_Next(b));
>    } else if (itemsize==2) {
>        next = PyTuple_Pack(3,
>                 PyIter_Next(a),
>                 PyIter_Next(b),
>                 PyIter_Next(c));
>    } else {
>        next = PyTuple_New(itemsize);
> 
>        for (j = 0; j < itemsize; j++) {
>            PyObject *it = PyTuple_GET_ITEM(itlist, j);
>            PyObject *item = PyIter_Next(it);
>            PyTuple_SET_ITEM(next, j, item);
>        }
>    }
> 
> If compiled on a system where the stack grows downwards (as it often does)
> the C compiler is very likely to evaluate function arguments in reverse
> order.
> 
> (BTW, this also assumes that it's an implementation which uses exceptions
> or something for error handling otherwise you probably can't get it right,
> but maybe something like IronPython could end up with code like this.)
> 
> Or maybe if someone added PyTuple_Pack1, PyTuple_Pack2, PyTuple_Pack3
> functions which grab their memory off a separate free list for each tuple
> length. That might speed up the time to create the tuples as you might be
> able to just reset the content not rebuild the object each time. Again
> that could make code like the above run more quickly.

Special-casing small tuples meets my sanity criterion :-)

Let's see if I understand the above: In C a call

f(g(), g())

may result in machine code equivalent to either

x = g()
y = g()
f(x, y)

or

y = g()
x = g()
f(x, y)

Is that it?

Peter




More information about the Python-list mailing list