[Python-checkins] CVS: python/dist/src/Objects obmalloc.c,2.29,2.30
Tim Peters
tim_one@users.sourceforge.net
Thu, 04 Apr 2002 20:32:31 -0800
- Previous message: [Python-checkins] CVS: python/dist/src/Doc/lib libasyncore.tex,1.11,1.12 libcfgparser.tex,1.21,1.22 libcode.tex,1.13,1.14 libfilecmp.tex,1.6,1.7 libmutex.tex,1.5,1.6 libposixpath.tex,1.22,1.23 librobotparser.tex,1.4,1.5 libtabnanny.tex,1.2,1.3
- Next message: [Python-checkins] CVS: python/dist/src/Objects obmalloc.c,2.30,2.31
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv24020/python/Objects
Modified Files:
obmalloc.c
Log Message:
Widespread, but mostly in _PyMalloc_Malloc: optimize away all expensive
runtime multiplications and divisions, via the scheme developed with
Vladimir Marangozov on Python-Dev. The pool_header struct loses its
capacity member, but gains nextoffset and maxnextoffset members; this
still leaves it at 32 bytes on a 32-bit box (it has to be padded to a
multiple of 8 bytes).
Index: obmalloc.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/obmalloc.c,v
retrieving revision 2.29
retrieving revision 2.30
diff -C2 -d -r2.29 -r2.30
*** obmalloc.c 4 Apr 2002 05:08:31 -0000 2.29
--- obmalloc.c 5 Apr 2002 04:32:29 -0000 2.30
***************
*** 117,120 ****
--- 117,123 ----
#define ALIGNMENT_MASK (ALIGNMENT - 1)
+ /* Return the number of bytes in size class I, as a uint. */
+ #define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
+
/*
* Max size threshold below which malloc requests are considered to be
***************
*** 226,230 ****
typedef uchar block;
! /* Pool for small blocks */
struct pool_header {
union { block *_padding;
--- 229,233 ----
typedef uchar block;
! /* Pool for small blocks. */
struct pool_header {
union { block *_padding;
***************
*** 235,239 ****
uint arenaindex; /* index into arenas of base adr */
uint szidx; /* block size class index */
! uint capacity; /* pool capacity in # of blocks */
};
--- 238,243 ----
uint arenaindex; /* index into arenas of base adr */
uint szidx; /* block size class index */
! uint nextoffset; /* bytes to virgin block */
! uint maxnextoffset; /* largest valid nextoffset */
};
***************
*** 247,252 ****
/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */
! #define POOL_ADDR(P) \
! ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK))
/*==========================================================================*/
--- 251,259 ----
/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */
! #define POOL_ADDR(P) ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK))
!
! /* Return total number of blocks in poolp P, as a uint. */
! #define NUMBLOCKS(P) \
! ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE((P)->szidx))
/*==========================================================================*/
***************
*** 300,311 ****
an empty list in usedpools[], it takes the first pool off of freepools.
If the size class needed happens to be the same as the size class the pool
! last had, some expensive initialization can be skipped (including an
! integer division -- XXX since the value
!
! pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size;
!
! is invariant across all pools of a given size class, it may make more
! sense to compute those at compile-time into a const vector indexed by
! size class, and lose the pool->capacity member and the runtime divisions).
--- 307,311 ----
an empty list in usedpools[], it takes the first pool off of freepools.
If the size class needed happens to be the same as the size class the pool
! last had, some pool initialization can be skipped.
***************
*** 316,331 ****
block is freed, it's inserted at the front of its pool's freeblock list. Note
that the available blocks in a pool are *not* linked all together when a pool
! is initialized. Instead only "the first" (lowest address) block is set up,
! setting pool->freeblock to NULL. This is consistent with that pymalloc
! strives at all levels (arena, pool, and block) never to touch a piece of
! memory until it's actually needed. So long as a pool is in the used state,
! we're certain there *is* a block available for allocating. If pool->freeblock
! is NULL then, that means we simply haven't yet gotten to one of the higher-
! address blocks. The address of "the next" available block can be computed
! then from pool->ref.count (the number of currently allocated blocks). This
! computation can be expensive, because it requires an integer multiply.
! However, so long as the pool's size class doesn't change, it's a one-time cost
! for that block; the computation could be made cheaper via adding a highwater
! pointer to the pool_header, but the tradeoff is murky.
--- 316,333 ----
block is freed, it's inserted at the front of its pool's freeblock list. Note
that the available blocks in a pool are *not* linked all together when a pool
! is initialized. Instead only "the first two" (lowest addresses) blocks are
! set up, returning the first such block, and setting pool->freeblock to a
! one-block list holding the second such block. This is consistent with that
! pymalloc strives at all levels (arena, pool, and block) never to touch a piece
! of memory until it's actually needed.
!
! So long as a pool is in the used state, we're certain there *is* a block
! available for allocating. If pool->freeblock is NULL then, that means we
! simply haven't yet gotten to one of the higher-address blocks. The offset
! from the pool_header to the start of "the next" virgin block is stored in
! the pool_header nextoffset member, and the largest value of nextoffset that
! makes sense is stored in the maxnextoffset member when a pool is initialized.
! All the blocks in a pool have been passed out at least when and only when
! nextoffset > maxnextoffset.
***************
*** 597,609 ****
* Reached the end of the free list, try to extend it
*/
! if (pool->ref.count < pool->capacity) {
/*
* There is room for another block
*/
! size++;
! size <<= ALIGNMENT_SHIFT; /* block size */
! pool->freeblock = (block *)pool + \
! POOL_OVERHEAD + \
! pool->ref.count * size;
*(block **)(pool->freeblock) = NULL;
UNLOCK();
--- 599,609 ----
* Reached the end of the free list, try to extend it
*/
! if (pool->nextoffset <= pool->maxnextoffset) {
/*
* There is room for another block
*/
! pool->freeblock = (block *)pool +
! pool->nextoffset;
! pool->nextoffset += INDEX2SIZE(size);
*(block **)(pool->freeblock) = NULL;
UNLOCK();
***************
*** 651,664 ****
}
/*
! * Initialize the pool header and free list
! * then return the first block.
*/
pool->szidx = size;
! size++;
! size <<= ALIGNMENT_SHIFT; /* block size */
bp = (block *)pool + POOL_OVERHEAD;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL;
- pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size;
UNLOCK();
return (void *)bp;
--- 651,665 ----
}
/*
! * Initialize the pool header, set up the free list to
! * contain just the second block, and return the first
! * block.
*/
pool->szidx = size;
! size = INDEX2SIZE(size);
bp = (block *)pool + POOL_OVERHEAD;
+ pool->nextoffset = POOL_OVERHEAD + (size << 1);
+ pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL;
UNLOCK();
return (void *)bp;
***************
*** 737,741 ****
* and the pool is in a usedpools[] list.
*/
- assert(pool->ref.count < pool->capacity);
if (--pool->ref.count != 0) {
/* pool isn't empty: leave it in usedpools */
--- 738,741 ----
***************
*** 768,772 ****
* blocks of the same size class.
*/
- assert(pool->ref.count == pool->capacity); /* else not full */
--pool->ref.count;
assert(pool->ref.count > 0); /* else the pool is empty */
--- 768,771 ----
***************
*** 807,811 ****
/* We're in charge of this block */
INCMINE;
! size = (pool->szidx + 1) << ALIGNMENT_SHIFT; /* block size */
if (size >= nbytes)
/* Don't bother if a smaller size was requested. */
--- 806,810 ----
/* We're in charge of this block */
INCMINE;
! size = INDEX2SIZE(pool->szidx);
if (size >= nbytes)
/* Don't bother if a smaller size was requested. */
***************
*** 1256,1260 ****
++numpools[p->szidx];
numblocks[p->szidx] += p->ref.count;
! numfreeblocks[p->szidx] += p->capacity - p->ref.count;
}
}
--- 1255,1259 ----
++numpools[p->szidx];
numblocks[p->szidx] += p->ref.count;
! numfreeblocks[p->szidx] += NUMBLOCKS(p) - p->ref.count;
}
}
***************
*** 1272,1276 ****
ulong b = numblocks[i];
ulong f = numfreeblocks[i];
! uint size = (i+1) << ALIGNMENT_SHIFT;
if (p == 0) {
assert(b == 0 && f == 0);
--- 1271,1275 ----
ulong b = numblocks[i];
ulong f = numfreeblocks[i];
! uint size = INDEX2SIZE(i);
if (p == 0) {
assert(b == 0 && f == 0);
- Previous message: [Python-checkins] CVS: python/dist/src/Doc/lib libasyncore.tex,1.11,1.12 libcfgparser.tex,1.21,1.22 libcode.tex,1.13,1.14 libfilecmp.tex,1.6,1.7 libmutex.tex,1.5,1.6 libposixpath.tex,1.22,1.23 librobotparser.tex,1.4,1.5 libtabnanny.tex,1.2,1.3
- Next message: [Python-checkins] CVS: python/dist/src/Objects obmalloc.c,2.30,2.31
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]