[Python-checkins] python/dist/src/Modules arraymodule.c,2.93,2.94
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Sat Mar 13 23:37:52 EST 2004
Update of /cvsroot/python/python/dist/src/Modules
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv8264/Modules
Modified Files:
arraymodule.c
Log Message:
Update the array overallocation scheme to match the approach used for
lists. Speeds append() operations and reduces memory requirements
(because of more conservative overallocation).
Paves the way for the feature request for array.extend() to support
arbitrary iterable arguments.
Index: arraymodule.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Modules/arraymodule.c,v
retrieving revision 2.93
retrieving revision 2.94
diff -C2 -d -r2.93 -r2.94
*** arraymodule.c 13 Mar 2004 18:18:51 -0000 2.93
--- arraymodule.c 14 Mar 2004 04:37:50 -0000 2.94
***************
*** 14,63 ****
#endif /* !STDC_HEADERS */
- /* Shamelessy stolen from listobject.c */
- static int
- roundupsize(int n)
- {
- unsigned int nbits = 0;
- unsigned int n2 = (unsigned int)n >> 5;
-
- /* Round up:
- * If n < 256, to a multiple of 8.
- * If n < 2048, to a multiple of 64.
- * If n < 16384, to a multiple of 512.
- * If n < 131072, to a multiple of 4096.
- * If n < 1048576, to a multiple of 32768.
- * If n < 8388608, to a multiple of 262144.
- * If n < 67108864, to a multiple of 2097152.
- * If n < 536870912, to a multiple of 16777216.
- * ...
- * If n < 2**(5+3*i), to a multiple of 2**(3*i).
- *
- * This over-allocates proportional to the list size, making room
- * for additional growth. The over-allocation is mild, but is
- * enough to give linear-time amortized behavior over a long
- * sequence of appends() in the presence of a poorly-performing
- * system realloc() (which is a reality, e.g., across all flavors
- * of Windows, with Win9x behavior being particularly bad -- and
- * we've still got address space fragmentation problems on Win9x
- * even with this scheme, although it requires much longer lists to
- * provoke them than it used to).
- */
- do {
- n2 >>= 3;
- nbits += 3;
- } while (n2);
- return ((n >> nbits) + 1) << nbits;
- }
-
- #define NRESIZE(var, type, nitems) \
- do { \
- size_t _new_size = roundupsize(nitems); \
- if (_new_size <= ((~(size_t)0) / sizeof(type))) \
- PyMem_RESIZE(var, type, _new_size); \
- else \
- var = NULL; \
- } while (0)
- /* END SHAMELESSLY STOLEN CODE */
-
struct arrayobject; /* Forward */
--- 14,17 ----
***************
*** 77,80 ****
--- 31,35 ----
int ob_size;
char *ob_item;
+ int allocated;
struct arraydescr *ob_descr;
} arrayobject;
***************
*** 85,88 ****
--- 40,91 ----
#define array_CheckExact(op) ((op)->ob_type == &Arraytype)
+ static int
+ array_resize(arrayobject *self, int newsize)
+ {
+ char *items;
+ size_t _new_size;
+
+ /* Bypass realloc() when a previous overallocation is large enough
+ to accommodate the newsize. If the newsize is 16 smaller than the
+ current size, then proceed with the realloc() to shrink the list.
+ */
+
+ if (self->allocated >= newsize &&
+ self->ob_size < newsize + 16 &&
+ self->ob_item != NULL) {
+ self->ob_size = newsize;
+ return 0;
+ }
+
+ /* This over-allocates proportional to the array size, making room
+ * for additional growth. The over-allocation is mild, but is
+ * enough to give linear-time amortized behavior over a long
+ * sequence of appends() in the presence of a poorly-performing
+ * system realloc().
+ * The growth pattern is: 0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
+ * Note, the pattern starts out the same as for lists but then
+ * grows at a smaller rate so that larger arrays only overallocate
+ * by about 1/16th -- this is done because arrays are presumed to be more
+ * memory critical.
+ */
+
+ _new_size = (newsize >> 4) + (self->ob_size < 8 ? 3 : 7) + newsize;
+ items = self->ob_item;
+ /* XXX The following multiplication and division does not optimize away
+ like it does for lists since the size is not known at compile time */
+ if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
+ PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
+ else
+ items = NULL;
+ if (items == NULL) {
+ PyErr_NoMemory();
+ return -1;
+ }
+ self->ob_item = items;
+ self->ob_size = newsize;
+ self->allocated = _new_size;
+ return 0;
+ }
+
/****************************************************************************
Get and Set functions for each type.
***************
*** 439,442 ****
--- 442,446 ----
}
op->ob_descr = descr;
+ op->allocated = size;
return (PyObject *) op;
}
***************
*** 456,459 ****
--- 460,464 ----
{
char *items;
+ int n = self->ob_size;
if (v == NULL) {
PyErr_BadInternalCall();
***************
*** 462,483 ****
if ((*self->ob_descr->setitem)(self, -1, v) < 0)
return -1;
! items = self->ob_item;
! NRESIZE(items, char, (self->ob_size+1) * self->ob_descr->itemsize);
! if (items == NULL) {
! PyErr_NoMemory();
return -1;
! }
if (where < 0) {
! where += self->ob_size;
if (where < 0)
where = 0;
}
! if (where > self->ob_size)
! where = self->ob_size;
! memmove(items + (where+1)*self->ob_descr->itemsize,
! items + where*self->ob_descr->itemsize,
! (self->ob_size-where)*self->ob_descr->itemsize);
! self->ob_item = items;
! self->ob_size++;
return (*self->ob_descr->setitem)(self, where, v);
}
--- 467,486 ----
if ((*self->ob_descr->setitem)(self, -1, v) < 0)
return -1;
!
! if (array_resize(self, n+1) == -1)
return -1;
! items = self->ob_item;
if (where < 0) {
! where += n;
if (where < 0)
where = 0;
}
! if (where > n)
! where = n;
! /* appends don't need to call memmove() */
! if (where != n)
! memmove(items + (where+1)*self->ob_descr->itemsize,
! items + where*self->ob_descr->itemsize,
! (n-where)*self->ob_descr->itemsize);
return (*self->ob_descr->setitem)(self, where, v);
}
***************
*** 729,732 ****
--- 732,736 ----
/* Can't fail */
a->ob_item = item;
+ a->allocated = a->ob_size;
}
else if (d > 0) { /* Insert d items */
***************
*** 742,745 ****
--- 746,750 ----
a->ob_item = item;
a->ob_size += d;
+ a->allocated = a->ob_size;
}
if (n > 0)
***************
*** 796,800 ****
memcpy(self->ob_item + self->ob_size*self->ob_descr->itemsize,
b->ob_item, b->ob_size*b->ob_descr->itemsize);
! self->ob_size = size;
return 0;
--- 801,806 ----
memcpy(self->ob_item + self->ob_size*self->ob_descr->itemsize,
b->ob_item, b->ob_size*b->ob_descr->itemsize);
! self->ob_size = size;
! self->allocated = size;
return 0;
***************
*** 826,829 ****
--- 832,836 ----
self->ob_item = NULL;
self->ob_size = 0;
+ self->allocated = 0;
}
else {
***************
*** 838,841 ****
--- 845,849 ----
self->ob_item = items;
self->ob_size *= n;
+ self->allocated = self->ob_size;
}
}
***************
*** 1159,1162 ****
--- 1167,1171 ----
self->ob_item = item;
self->ob_size += n;
+ self->allocated = self->ob_size;
nread = fread(item + (self->ob_size - n) * itemsize,
itemsize, n, fp);
***************
*** 1165,1168 ****
--- 1174,1178 ----
PyMem_RESIZE(item, char, self->ob_size*itemsize);
self->ob_item = item;
+ self->allocated = self->ob_size;
PyErr_SetString(PyExc_EOFError,
"not enough items in file");
***************
*** 1231,1234 ****
--- 1241,1245 ----
self->ob_item = item;
self->ob_size += n;
+ self->allocated = self->ob_size;
for (i = 0; i < n; i++) {
PyObject *v = PyList_GetItem(list, i);
***************
*** 1239,1242 ****
--- 1250,1254 ----
self->ob_size * itemsize);
self->ob_item = item;
+ self->allocated = self->ob_size;
return NULL;
}
***************
*** 1301,1304 ****
--- 1313,1317 ----
self->ob_item = item;
self->ob_size += n;
+ self->allocated = self->ob_size;
memcpy(item + (self->ob_size - n) * itemsize,
str, itemsize*n);
***************
*** 1354,1357 ****
--- 1367,1371 ----
self->ob_item = (char *) item;
self->ob_size += n;
+ self->allocated = self->ob_size;
memcpy(item + self->ob_size - n,
ustr, n * sizeof(Py_UNICODE));
***************
*** 1612,1616 ****
self->ob_size -= slicelength;
self->ob_item = PyMem_REALLOC(self->ob_item, itemsize*self->ob_size);
!
return 0;
--- 1626,1630 ----
self->ob_size -= slicelength;
self->ob_item = PyMem_REALLOC(self->ob_item, itemsize*self->ob_size);
! self->allocated = self->ob_size;
return 0;
***************
*** 1812,1815 ****
--- 1826,1830 ----
self->ob_size = n / sizeof(Py_UNICODE);
memcpy(item, PyUnicode_AS_DATA(initial), n);
+ self->allocated = self->ob_size;
}
#endif
More information about the Python-checkins
mailing list