[Python-checkins] python/dist/src/Misc NEWS,1.931,1.932

Fri Feb 13 06:36:41 EST 2004

Update of /cvsroot/python/python/dist/src/Misc
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv8586/Misc
Modified Files:
	NEWS 
Log Message:
* Optimized list appends and pops by making fewer calls the underlying system
 realloc(). This is achieved by tracking the overallocation size in a new
 field and using that information to skip calls to realloc() whenever
 possible.
* Simplified and tightened the amount of overallocation. For larger lists,
 this overallocates by 1/8th (compared to the previous scheme which ranged
 between 1/4th to 1/32nd over-allocation). For smaller lists (n<6), the
 maximum overallocation is one byte (formerly it could be upto eight bytes).
 This saves memory in applications with large numbers of small lists.
* Eliminated the NRESIZE macro in favor of a new, static list_resize function
 that encapsulates the resizing logic. Coverting this back to macro would
 give a small (under 1%) speed-up. This was too small to warrant the loss
 of readability, maintainability, and de-coupling.
* Some functions using NRESIZE had grown unnecessarily complex in their
 efforts to bend to the macro's calling pattern. With the new list_resize
 function in place, those other functions could be simplified. That is
 being saved for a separate patch.
* The ob_item==NULL check could be eliminated from the new list_resize
 function. This would entail finding each piece of code that sets ob_item
 to NULL and adding a new line to invalidate the overallocation tracking
 field. Rather than impose a new requirement on other pieces of list code,
 it was preferred to leave the NULL check in place and retain the benefits
 of decoupling, maintainability and information hiding (only PyList_New()
 and list_sort() need to know about the new field). This approach also
 reduces the odds of breaking an extension module.
(Collaborative effort by Raymond Hettinger, Hye-Shik Chang, Tim Peters, 
 and Armin Rigo.)
Index: NEWS
===================================================================
RCS file: /cvsroot/python/python/dist/src/Misc/NEWS,v
retrieving revision 1.931
retrieving revision 1.932
diff -C2 -d -r1.931 -r1.932
*** NEWS	12 Feb 2004 15:28:27 -0000	1.931
--- NEWS	13 Feb 2004 11:36:39 -0000	1.932
***************
*** 13,16 ****
--- 13,27 ----
 -----------------
 
+ - Optimized list resize operations to make fewer calls to the system
+ realloc(). Significantly speeds up list appends, list pops,
+ list comprehensions, and the list contructor (when the input iterable
+ length is not known).
+ 
+ - Changed the internal list over-allocation scheme. For larger lists,
+ overallocation ranged between 3% and 25%. Now, it is a constant 12%.
+ For smaller lists (n<=5), overallocation was upto eight bytes. Now,
+ the overallocation is no more than one byte -- this improves space
+ utilization for applications that have large numbers of small lists.
+ 
 - Support for arbitrary objects supporting the read-only buffer
 interface as the co_code field of code objects (something that was