How to increase the speed of this program?

[Klaas]

Klaas wrote:

> In fact, you can make it about 4x faster by balancing:
>
> [klaas at worbo ~]$ python -m timeit -s "from array import array"
> "array('c','\0'*200)*500"
> 10000 loops, best of 3: 32.4 usec per loop

This is an unclean minimally-tested patch which achieves reasonable
performance (about 10x faster than unpatched python):

$ ./python -m timeit -s "from array import array" "array('c',
'\0')*100000"
10000 loops, best of 3: 71.6 usec per loop

You have my permission to use this code if you want to submit a patch
to sourceforge (it needs, proper benchmarking, testing, and tidying).

-Mike

Index: Modules/arraymodule.c
===================================================================
--- Modules/arraymodule.c       (revision 52849)
+++ Modules/arraymodule.c       (working copy)
@@ -680,10 +680,29 @@
                return NULL;
        p = np->ob_item;
        nbytes = a->ob_size * a->ob_descr->itemsize;
-       for (i = 0; i < n; i++) {
-               memcpy(p, a->ob_item, nbytes);
-               p += nbytes;
-       }
+
+        if (n) {
+          Py_ssize_t chunk_size = nbytes;
+          Py_ssize_t copied = 0;
+          char *src = np->ob_item;
+
+          /* copy first element */
+          memcpy(p, a->ob_item, nbytes);
+          copied += nbytes;
+
+          /* copy exponentially-increasing chunks */
+          while(chunk_size < (size - copied)) {
+            memcpy(p + copied, src, chunk_size);
+            copied += chunk_size;
+            if(chunk_size < size/10)
+              chunk_size *= 2;
+          }
+          /* copy remainder */
+          while (copied < size) {
+            memcpy(p + copied, src, nbytes);
+            copied += nbytes;
+          }          
+        }
        return (PyObject *) np;
 }