Speed-up in array_repeat()

[lskovlund]

BPO	1569291
Nosy	@birkenfeld, @rhettinger, @josiahcarlson, @abalkin, @larryhastings
Files	arraymodule.diff: Patch against current SVN issue1569291.diff: Patch against revision 61850

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/birkenfeld'
closed_at = <Date 2010-12-04.11:02:31.868>
created_at = <Date 2006-10-02.13:30:28.000>
labels = ['extension-modules', 'easy', 'performance']
title = 'Speed-up in array_repeat()'
updated_at = <Date 2010-12-04.11:02:31.866>
user = 'https://bugs.python.org/lskovlund'

bugs.python.org fields:

activity = <Date 2010-12-04.11:02:31.866>
actor = 'georg.brandl'
assignee = 'georg.brandl'
closed = True
closed_date = <Date 2010-12-04.11:02:31.868>
closer = 'georg.brandl'
components = ['Extension Modules']
creation = <Date 2006-10-02.13:30:28.000>
creator = 'lskovlund'
dependencies = []
files = ['7558', '9841']
hgrepos = []
issue_num = 1569291
keywords = ['patch', 'easy']
message_count = 15.0
messages = ['51182', '51183', '51184', '51185', '51186', '51187', '51188', '64405', '64429', '64433', '64435', '68096', '110500', '110501', '123334']
nosy_count = 8.0
nosy_names = ['georg.brandl', 'rhettinger', 'josiahcarlson', 'belopolsky', 'larry', 'lskovlund', 'stutzbach', 'BreamoreBoy']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue1569291'
versions = ['Python 3.1', 'Python 2.7', 'Python 3.2']

[lskovlund]

Use iterative doubling when extending the old array.
This results in O(log n) calls to memcpy() instead of O(n).

[josiahcarlson]

Logged In: YES
user_id=341410

Have you benchmarked this for repeats found "in the wild" to
establish *observable* speedup for code that already exists?

[lskovlund]

Logged In: YES
user_id=263372

I wrote this code for a university project I'm doing myself,
which involves initializing a *very* large array (it's a
remote memory system). It does help there, certainly; for
medium-sized arrays, the improvement would be negligable,
and for small ones it might even be worse.

If you mean, have I benchmarked it with other people's code,
no. I just thought I'd offer it to the community, since it
has certainly helped me.

[rhettinger]

Logged In: YES
user_id=80475

This patch is basically fine. Will neaten it up to match
our source coding conventions and apply it when I get a
chance. Py2.6 won't be out for a good while, so there is
no hurry.

[larryhastings]

Logged In: YES
user_id=364875

I'd assumed Python *didn't* double the size when resizing an array because of how much memory that wastes. May I suggest trying it with a multiplier of 1.5x, and comparing both CPU time and memory consumption? I find for these things that 1.5x is nearly as fast and wastes far less memory.

[josiahcarlson]

Logged In: YES
user_id=341410

This patch has nothing to do with array resizing. It has to
do with array initialization.

[rhettinger]

This proposal is basically fine. The patch should be re-worked to model as closely as possible the code for string_repeat in Objects/stringobject.c (revisions 30616 and 30368 provide the details). That code is known to work and to have provided a meaningful speed-up.

[rhettinger]

This one is easy if someone wants to take a crack at it.

[abalkin]

Looking at stringobject.c:1034:

i = 0;  
if (i < size) {  
        Py_MEMCPY(op->ob_sval, a->ob_sval, Py_SIZE(a));  
        i = Py_SIZE(a);  
}  
while (i < size) {  
        j = (i <= size-i)  ?  i  :  size-i;  
        Py_MEMCPY(op->ob_sval+i, op->ob_sval, j);  
        i += j;  
}  
return (PyObject *) op;

Do I miss something or the first condition "if (i < size)" is
a fancy way to check for size > 0?

Wouldn't it be clearer to write

if (size == 0)
return (PyObject *) op;
Py_MEMCPY(op->ob_sval, a->ob_sval, Py_SIZE(a));
i = Py_SIZE(a);
..

[abalkin]

Attached patch (bpo-1569291.diff) reimplements the optimization by
following Objects/stringobject.c logic as Raymond suggested.

I see two remaining issues which in my view should be addressed separately:

1. There is no check for overflow after the multiplication computing the
   size of the resulting array. Note that while newarrayobject checks that
   size*itemsize does not overflow internally, there is no such check for
   Py_SIZE(a) * n. A decision needs to be made whether Overflow or NoMemory
   error should be raised because currently string_repeat and
   newarrayobject treat overflow differently.

2. See msg64429 above. I think both string and (patched) array codes
   can be simplified.

[abalkin]

I forgot to mention that I added a unit test to cover the special case
of repeating a single-byte array.

[rhettinger]

Georg, do you want to take it from here.

[BreamoreBoy]

There are lots of positive comments on this issue, please can core developers take a bit of time to have a look and say yes or no.

[birkenfeld]

Uh, this slipped under my radar. Let's see if I get the chance to look at it at the core sprint next week.

[birkenfeld]

I changed the patch to look more like unicode_repeat (which addresses Alex' point #2) and committed in r87022.