Mercurial > cpython-lru_cache-weakref

comparison Modules/arraymodule.c @ 28043:db92c77b05e2 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SF patch #687598, array.append is sloooow This improves speed by about 5.6% for me.
author Neal Norwitz <nnorwitz@gmail.com>
date Mon, 24 Feb 2003 02:08:42 +0000
parents 8d1b272c9e71
children 5c9dcdc7fe8d
comparison
equal deleted inserted replaced
28041:1b6538aa0959 28043:db92c77b05e2
10 #else /* !STDC_HEADERS */ 10 #else /* !STDC_HEADERS */
11 #ifndef DONT_HAVE_SYS_TYPES_H 11 #ifndef DONT_HAVE_SYS_TYPES_H
12 #include <sys/types.h> /* For size_t */ 12 #include <sys/types.h> /* For size_t */
13 #endif /* DONT_HAVE_SYS_TYPES_H */ 13 #endif /* DONT_HAVE_SYS_TYPES_H */
14 #endif /* !STDC_HEADERS */ 14 #endif /* !STDC_HEADERS */
15
16 /* Shamelessy stolen from listobject.c */
17 static int
18 roundupsize(int n)
19 {
20 unsigned int nbits = 0;
21 unsigned int n2 = (unsigned int)n >> 5;
22
23 /* Round up:
24 * If n < 256, to a multiple of 8.
25 * If n < 2048, to a multiple of 64.
26 * If n < 16384, to a multiple of 512.
27 * If n < 131072, to a multiple of 4096.
28 * If n < 1048576, to a multiple of 32768.
29 * If n < 8388608, to a multiple of 262144.
30 * If n < 67108864, to a multiple of 2097152.
31 * If n < 536870912, to a multiple of 16777216.
32 * ...
33 * If n < 2**(5+3*i), to a multiple of 2**(3*i).
34 *
35 * This over-allocates proportional to the list size, making room
36 * for additional growth. The over-allocation is mild, but is
37 * enough to give linear-time amortized behavior over a long
38 * sequence of appends() in the presence of a poorly-performing
39 * system realloc() (which is a reality, e.g., across all flavors
40 * of Windows, with Win9x behavior being particularly bad -- and
41 * we've still got address space fragmentation problems on Win9x
42 * even with this scheme, although it requires much longer lists to
43 * provoke them than it used to).
44 */
45 do {
46 n2 >>= 3;
47 nbits += 3;
48 } while (n2);
49 return ((n >> nbits) + 1) << nbits;
50 }
51
52 #define NRESIZE(var, type, nitems) \
53 do { \
54 size_t _new_size = roundupsize(nitems); \
55 if (_new_size <= ((~(size_t)0) / sizeof(type))) \
56 PyMem_RESIZE(var, type, _new_size); \
57 else \
58 var = NULL; \
59 } while (0)
60 /* END SHAMELESSLY STOLEN CODE */
15 61
16 struct arrayobject; /* Forward */ 62 struct arrayobject; /* Forward */
17 63
18 /* All possible arraydescr values are defined in the vector "descriptors" 64 /* All possible arraydescr values are defined in the vector "descriptors"
19 * below. That's defined later because the appropriate get and set 65 * below. That's defined later because the appropriate get and set
417 return -1; 463 return -1;
418 } 464 }
419 if ((*self->ob_descr->setitem)(self, -1, v) < 0) 465 if ((*self->ob_descr->setitem)(self, -1, v) < 0)
420 return -1; 466 return -1;
421 items = self->ob_item; 467 items = self->ob_item;
422 PyMem_RESIZE(items, char, 468 NRESIZE(items, char, (self->ob_size+1) * self->ob_descr->itemsize);
423 (self->ob_size+1) * self->ob_descr->itemsize);
424 if (items == NULL) { 469 if (items == NULL) {
425 PyErr_NoMemory(); 470 PyErr_NoMemory();
426 return -1; 471 return -1;
427 } 472 }
428 if (where < 0) 473 if (where < 0)