[Python-Dev] parallel for-loops.
Thomas Wouters
thomas@xs4all.net
Mon, 10 Jul 2000 16:32:33 +0200
--mSxgbZZZvrAyzONB
Content-Type: text/plain; charset=us-ascii
I've attached a patch that adds yet another new feature to Python ;P It's
the 'parallel for loop' thing that's come past here and on python-list a few
times. Guido sent me the suggested Grammar patch and I went from there, so
if I got any of the details wrong, please yell at me, loudly.
Here's how it works:
>>> for x in [1,2,3,4,5]; y in ['a','b','c','d','e','f','g']:
... print x, y
...
1 a
2 b
3 c
4 d
5 e
>>>
The two loops are traversed in parallel, like in
for x, y in map(None, [1,2,3,4,5], ['a','b','c','d','e','f','g'])
*except* that the first IndexError of any of the lists terminates the loop.
The syntax is not limited to two lists in parallel, of course! There is no
specific limit forced by this patch, so the limit is either the available
memory, or the max number of child nodes (32k or so) whichever comes first ;)
The patch works internally by passing a tuple of sequences as argument to
FOR_LOOP, instead of just a single sequence as before. Likewise, the result
of the FOR_LOOP operation is a tuple, which is then unpacked into the proper
variables. This is done for all for loops, even single-list ones, so all
for-loops take a slight performance hit with this patch. (A tuple-build on
entering the loop, and a few iterations, a tuple build and a tuple unpack,
even for the common case. I didn't measure it, though.)
If this is deemed undesirable, it would be trivial to add a new bytcode,
FORMORE_LOOP or such, that handles the multiple-list type of for loop. I
almost went ahead and did that, but decided I'd try for a patch that
*doesn't* add bytecodes for a change ;) Unfortunately, the patch is binary
incompatible, so the bytecode magic does have to be changed.
Don't forget to type 'make' inside 'Grammar' after applying it.
I'll do some more testing on this, write some docs and some tests, and if
noone here has convinced me otherwise, upload it to sourceforge ;) The patch
is really suprisingly small and elegant, thanks to Python's extreme
simplicity!
--
Thomas Wouters <thomas@xs4all.net>
Hi! I'm a .signature virus! copy me into your .signature file to help me spread!
--mSxgbZZZvrAyzONB
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="parallelfor.patch"
Index: Grammar/Grammar
===================================================================
RCS file: /cvsroot/python/python/dist/src/Grammar/Grammar,v
retrieving revision 1.35
diff -c -r1.35 Grammar
*** Grammar/Grammar 2000/03/28 23:49:00 1.35
--- Grammar/Grammar 2000/07/10 14:06:26
***************
*** 54,60 ****
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
while_stmt: 'while' test ':' suite ['else' ':' suite]
! for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite]
try_stmt: ('try' ':' suite (except_clause ':' suite)+ #diagram:break
['else' ':' suite] | 'try' ':' suite 'finally' ':' suite)
# NB compile.c makes sure that the default except clause is last
--- 54,60 ----
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
while_stmt: 'while' test ':' suite ['else' ':' suite]
! for_stmt: 'for' exprlist 'in' testlist (';' exprlist 'in' testlist)* ':' suite ['else' ':' suite]
try_stmt: ('try' ':' suite (except_clause ':' suite)+ #diagram:break
['else' ':' suite] | 'try' ':' suite 'finally' ':' suite)
# NB compile.c makes sure that the default except clause is last
Index: Python/ceval.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Python/ceval.c,v
retrieving revision 2.183
diff -c -r2.183 ceval.c
*** Python/ceval.c 2000/07/09 03:09:56 2.183
--- Python/ceval.c 2000/07/10 14:06:28
***************
*** 1473,1481 ****
continue;
case FOR_LOOP:
! /* for v in s: ...
! On entry: stack contains s, i.
! On exit: stack contains s, i+1, s[i];
but if loop exhausted:
s, i are popped, and we jump */
w = POP(); /* Loop index */
--- 1473,1481 ----
continue;
case FOR_LOOP:
! /* for v1 in s1; v2 in s2: ...
! On entry: stack contains t(s), i.
! On exit: stack contains t(s), i+1, t(s[i]);
but if loop exhausted:
s, i are popped, and we jump */
w = POP(); /* Loop index */
***************
*** 2548,2566 ****
loop_subscript(v, w)
PyObject *v, *w;
{
! PySequenceMethods *sq = v->ob_type->tp_as_sequence;
! int i;
! if (sq == NULL || sq->sq_item == NULL) {
! PyErr_SetString(PyExc_TypeError, "loop over non-sequence");
return NULL;
}
i = PyInt_AsLong(w);
! v = (*sq->sq_item)(v, i);
! if (v)
! return v;
! if (PyErr_ExceptionMatches(PyExc_IndexError))
! PyErr_Clear();
! return NULL;
}
/* Extract a slice index from a PyInt or PyLong, the index is bound to
--- 2548,2585 ----
loop_subscript(v, w)
PyObject *v, *w;
{
! PyObject *res;
! long i;
! int j, len;
!
! if (!PyTuple_Check(v)) {
! PyErr_SetString(PyExc_SystemError, "bad (internal) arg to for loop");
return NULL;
}
+
+ len = PyTuple_Size(v);
+ res = PyTuple_New(len);
i = PyInt_AsLong(w);
!
! for (j = 0; j < len; j++) {
! PyObject *u = PyTuple_GET_ITEM(v, j);
! PySequenceMethods *sq = u->ob_type->tp_as_sequence;
! if (sq == NULL || sq->sq_item == NULL) {
! Py_DECREF(res);
! PyErr_SetString(PyExc_TypeError, "loop over non-sequence");
! return NULL;
! }
! u = (*sq->sq_item)(u, i);
! if (u) {
! PyTuple_SET_ITEM(res, j, u);
! continue;
! }
! if (PyErr_ExceptionMatches(PyExc_IndexError))
! PyErr_Clear();
! Py_DECREF(res);
! return NULL;
! }
! return res;
}
/* Extract a slice index from a PyInt or PyLong, the index is bound to
Index: Python/compile.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Python/compile.c,v
retrieving revision 2.114
diff -c -r2.114 compile.c
*** Python/compile.c 2000/07/09 03:09:56 2.114
--- Python/compile.c 2000/07/10 14:06:29
***************
*** 2433,2443 ****
int break_anchor = 0;
int anchor = 0;
int save_begin = c->c_begin;
REQ(n, for_stmt);
! /* 'for' exprlist 'in' exprlist ':' suite ['else' ':' suite] */
com_addfwref(c, SETUP_LOOP, &break_anchor);
block_push(c, SETUP_LOOP);
! com_node(c, CHILD(n, 3));
v = PyInt_FromLong(0L);
if (v == NULL)
c->c_errors++;
--- 2433,2457 ----
int break_anchor = 0;
int anchor = 0;
int save_begin = c->c_begin;
+ int inum, i;
+
REQ(n, for_stmt);
! /* 'for' exprlist 'in' exprlist (';' exprlist 'in' testlist)*
! ':' suite ['else' ':' suite] */
!
! if (NCH(n) % 2) {
! /* Uneven number of children, so it includes 'else' clause */
! inum = ((NCH(n) - 5) / 4);
! } else {
! /* No 'else' clause */
! inum = ((NCH(n) - 2) / 4);
! }
com_addfwref(c, SETUP_LOOP, &break_anchor);
block_push(c, SETUP_LOOP);
! for (i = 1; i <= inum; i++)
! com_node(c, CHILD(n, i*4 - 1));
! com_addoparg(c, BUILD_TUPLE, inum);
! com_pop(c, inum-1);
v = PyInt_FromLong(0L);
if (v == NULL)
c->c_errors++;
***************
*** 2448,2456 ****
com_addoparg(c, SET_LINENO, n->n_lineno);
com_addfwref(c, FOR_LOOP, &anchor);
com_push(c, 1);
! com_assign(c, CHILD(n, 1), OP_ASSIGN);
c->c_loops++;
! com_node(c, CHILD(n, 5));
c->c_loops--;
com_addoparg(c, JUMP_ABSOLUTE, c->c_begin);
c->c_begin = save_begin;
--- 2462,2473 ----
com_addoparg(c, SET_LINENO, n->n_lineno);
com_addfwref(c, FOR_LOOP, &anchor);
com_push(c, 1);
! com_addoparg(c, UNPACK_TUPLE, inum);
! com_push(c, inum-1);
! for (i = 1; i <= inum; i++)
! com_assign(c, CHILD(n, i*4 - 3), OP_ASSIGN);
c->c_loops++;
! com_node(c, CHILD(n, inum*4 + 1));
c->c_loops--;
com_addoparg(c, JUMP_ABSOLUTE, c->c_begin);
c->c_begin = save_begin;
***************
*** 2458,2465 ****
com_pop(c, 2); /* FOR_LOOP has popped these */
com_addbyte(c, POP_BLOCK);
block_pop(c, SETUP_LOOP);
! if (NCH(n) > 8)
! com_node(c, CHILD(n, 8));
com_backpatch(c, break_anchor);
}
--- 2475,2483 ----
com_pop(c, 2); /* FOR_LOOP has popped these */
com_addbyte(c, POP_BLOCK);
block_pop(c, SETUP_LOOP);
! if (NCH(n) % 2) {
! com_node(c, CHILD(n, inum*4 + 3));
! }
com_backpatch(c, break_anchor);
}
Index: Python/import.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Python/import.c,v
retrieving revision 2.140
diff -c -r2.140 import.c
*** Python/import.c 2000/07/09 03:09:56 2.140
--- Python/import.c 2000/07/10 14:06:31
***************
*** 65,71 ****
/* XXX Perhaps the magic number should be frozen and a version field
added to the .pyc file header? */
/* New way to come up with the magic number: (YEAR-1995), MONTH, DAY */
! #define MAGIC (50428 | ((long)'\r'<<16) | ((long)'\n'<<24))
/* Magic word as global; note that _PyImport_Init() can change the
value of this global to accommodate for alterations of how the
--- 65,71 ----
/* XXX Perhaps the magic number should be frozen and a version field
added to the .pyc file header? */
/* New way to come up with the magic number: (YEAR-1995), MONTH, DAY */
! #define MAGIC (50710 | ((long)'\r'<<16) | ((long)'\n'<<24))
/* Magic word as global; note that _PyImport_Init() can change the
value of this global to accommodate for alterations of how the
--mSxgbZZZvrAyzONB--