[Patches] [ python-Patches-1569291 ] Speed-up in array_repeat()

SourceForge.net noreply at sourceforge.net
Tue Apr 3 04:50:12 CEST 2007


Patches item #1569291, was opened at 2006-10-02 08:30
Message generated for change (Comment added) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1569291&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Modules
Group: Python 2.6
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Lars Skovlund (lskovlund)
Assigned to: Raymond Hettinger (rhettinger)
Summary: Speed-up in array_repeat()

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

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

>Comment By: Raymond Hettinger (rhettinger)
Date: 2007-04-02 21:50

Message:
Logged In: YES 
user_id=80475
Originator: NO

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.


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

Comment By: Josiah Carlson (josiahcarlson)
Date: 2006-10-13 10:26

Message:
Logged In: YES 
user_id=341410

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

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

Comment By: Larry Hastings (lhastings)
Date: 2006-10-13 03:17

Message:
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.

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

Comment By: Raymond Hettinger (rhettinger)
Date: 2006-10-07 19:59

Message:
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.

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

Comment By: Lars Skovlund (lskovlund)
Date: 2006-10-07 17:12

Message:
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.

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

Comment By: Josiah Carlson (josiahcarlson)
Date: 2006-10-07 11:39

Message:
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?

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

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


More information about the Patches mailing list