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 _______________________________________________ Patches mailing list Patches@python.org http://mail.python.org/mailman/listinfo/patches
