[Python-bugs-list] [ python-Bugs-604716 ] faster [None]*n or []*n

[noreply@sourceforge.net]

Bugs item #604716, was opened at 2002-09-04 15:20
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=604716&group_id=5470

Category: Python Interpreter Core
Group: Not a Bug
Status: Open
Resolution: None
Priority: 5
Submitted By: Gregory Smith (gregsmith)
Assigned to: Nobody/Anonymous (nobody)
Summary: faster [None]*n or []*n

Initial Comment:
This is a suggestion to speed up multiplying
a list by an integer, in the case where 
the length of the list is 0 or 1. currently there
is a lot of overhead in the loop for these cases.
The current loop ( in list_repeat, in listobject.c) :

	p = np->ob_item;
	for (i = 0; i < n; i++) {
		for (j = 0; j < a->ob_size; j++) {
			*p = a->ob_item[j];
			Py_INCREF(*p);
			p++;
		}
	}
	return (PyObject *) np;

Suggested  ( where Py_INCREF_N(o,n) bumps
the refcount of  'o' by n): 

	p = np->ob_item;
        if( a->ob_size <= 1 ){
		if( a->ob_size ){  // is 1
			Pyobject *a0 = a->ob_item[0];
			for (i = 0; i < n; i++) {
				*p++ = a0;
			}
		        Py_INCREF_N(a0,n);
		}
        }else{
		for (i = 0; i < n; i++) {
			for (j = 0; j < a->ob_size; j++) {
				*p = a->ob_item[j];
				Py_INCREF(*p);
				p++;
			}
		}
        }
	return (PyObject *) np;


You could also do special cases for len=2, etc
(with *p++ = a0; *p++ =  a1; inside) but len=1
is a common case, with things like [None]*1000
used to create lists.

The best approach in general is to check
if the list being replicated is sufficiently smaller than
the replication count; and if so, use a different set
of loops nested in the other order, so that the
outer loop runs less often. 

 With the inverted loop case, you have 
'a->ob_size' calls to Py_INCREF_N instead of
'a->ob_size*n' calls to Py_INCREF. 


Exact same comments apply to tuplerepeat().

If any interest, I will code this and test it. 



----------------------------------------------------------------------

>Comment By: Raymond Hettinger (rhettinger)
Date: 2002-09-04 20:45

Message:
Logged In: YES 
user_id=80475

Here's  a faster approach that doesn't involve a special 
case:

	for (i = 0; i < n; i++)
		memcpy(p + i*n, p, size);
	for (j = 0; j < a->ob_size; j++){
		Py_INCREF_N(*p, n);
		p++;
	}

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=604716&group_id=5470