[Python-checkins] CVS: python/dist/src/Objects obmalloc.c,2.25,2.26

[Tim Peters]

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv8882/python/Objects

Modified Files:
	obmalloc.c 
Log Message:
Restructured my pool-management overview in terms of the three
possible pool states.  I think it's much clearer now.

Added a new long overdue block-management overview comment block.

I believe the comments are in good shape now.

Added two comments about possible small optimizations (one getting rid
of runtime multiplications at the cost of a new pool_header member; the
other getting rid of runtime divisions and the pool_header capacity
member, at the cost of a static const vector of 32 uints).


Index: obmalloc.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/obmalloc.c,v
retrieving revision 2.25
retrieving revision 2.26
diff -C2 -d -r2.25 -r2.26
*** obmalloc.c	1 Apr 2002 06:04:21 -0000	2.25
--- obmalloc.c	1 Apr 2002 19:23:44 -0000	2.26
***************
*** 269,293 ****
  16, and so on:  index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
  
! The partially used pools for a given index are linked together via their
! pool_header's prevpool and nextpool members.  "Partially used" means at least
! one block in the pool is currently allocated, *and* at least one block in the
! pool is not currently allocated.
  
! When all blocks in a pool are allocated, the pool is unlinked from the list,
! and isn't linked to from anything anymore (you can't find it then from
! anything obmalloc.c knows about); the pool's own prevpool and nextpool
! pointers are set to point to itself.  The comments say the pool "is full" then.
  
- When a small block is returned to pymalloc, there are two cases.  If its pool
- was full, its pool is relinked into the appropriate usedpools[] list, at the
- front (so the next allocation of the same size class will be taken from this
- pool).  Else its pool was not full, the pool is already in a usedpools[]
- list, and isn't moved.  Instead the block is just linked to the front of the
- pool's own freeblock singly-linked list.  However, if that makes the pool
- entirely free of allocated blocks (the comments say the pool "is empty" then),
- the pool is unlinked from usedpools[], and inserted at the front of the
- (file static) singly-linked freepools list, via the pool header's nextpool
- member; prevpool is meaningless in this case.  Pools put on the freepools
- list can be changed to belong to a different size class.
  
  Major obscurity:  While the usedpools vector is declared to have poolp
--- 269,332 ----
  16, and so on:  index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
  
! Pools are carved off the current arena highwater mark (file static arenabase)
! as needed.  Once carved off, a pool is in one of three states forever after:
  
! used == partially used, neither empty nor full
!     At least one block in the pool is currently allocated, and at least one
!     block in the pool is not currently allocated (note this implies a pool
!     has room for at least two blocks).
!     This is a pool's initial state, as a pool is created only when malloc
!     needs space.
!     The pool holds blocks of a fixed size, and is in the circular list headed
!     at usedpools[i] (see above).  It's linked to the other used pools of the
!     same size class via the pool_header's nextpool and prevpool members.
!     If all but one block is currently allocated, a malloc can cause a
!     transition to the full state.  If all but one block is not currently
!     allocated, a free can cause a transition to the empty state.
! 
! full == all the pool's blocks are currently allocated
!     On transition to full, a pool is unlinked from its usedpools[] list.
!     It's not linked to from anything then anymore, and its nextpool and
!     prevpool members are meaningless until it transitions back to used.
!     A free of a block in a full pool puts the pool back in the used state.
!     Then it's linked in at the front of the appropriate usedpools[] list, so
!     that the next allocation for its size class will reuse the freed block.
! 
! empty == all the pool's blocks are currently available for allocation
!     On transition to empty, a pool is unlinked from its usedpools[] list,
!     and linked to the front of the (file static) singly-linked freepools list,
!     via its nextpool member.  The prevpool member has no meaning in this case.
!     Empty pools have no inherent size class:  the next time a malloc finds
!     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).
! 
! 
! Block Management
! 
! Blocks within pools are again carved out as needed.  pool->freeblock points to
! the start of a singly-linked list of free blocks within the pool.  When a
! 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.
  
  
  Major obscurity:  While the usedpools vector is declared to have poolp
***************
*** 511,514 ****
--- 550,554 ----
  #define ADDRESS_IN_RANGE(P, I) \
  	((I) < narenas && (uptr)(P) - arenas[I] < (uptr)ARENA_SIZE)
+ 
  /*==========================================================================*/