[Python-checkins] python/dist/src/Objects dictnotes.txt,1.1,1.2

[rhettinger@users.sourceforge.net]

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

Modified Files:
	dictnotes.txt 
Log Message:
* Note how dummy entry re-use benefits use cases with interspersed deletes
  and adds.

* Note that dictionary iteration is negatively impacted by additional
  sparseness.



Index: dictnotes.txt
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictnotes.txt,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** dictnotes.txt	2 May 2003 20:11:29 -0000	1.1
--- dictnotes.txt	4 May 2003 21:25:19 -0000	1.2
***************
*** 44,47 ****
--- 44,51 ----
          such as with the % formatting operator.
  
+ Dynamic Mappings
+     Characterized by deletions interspersed with adds and replacments.
+     Performance benefits greatly from the re-use of dummy entries.
+ 
  
  Data Layout (assuming a 32-bit box with 64 bytes per cache line)
***************
*** 92,95 ****
--- 96,105 ----
  others).  Any one test or benchmark is likely to prove misleading.
  
+ While making a dictionary more sparse reduces collisions, it impairs
+ iteration and key listing.  Those methods loop over every potential
+ entry.  Doubling the size of dictionary results in twice as many
+ non-overlapping memory accesses for keys(), items(), values(),
+ __iter__(), iterkeys(), iteritems(), itervalues(), and update().
+ 
  
  Results of Cache Locality Experiments
***************
*** 166,170 ****
     is not at a premium, the user may benefit from setting the maximum load
     ratio at 5% or 10% instead of the usual 66.7%.  This will sharply
!    curtail the number of collisions.
  
  2) Dictionary creation time can be shortened in cases where the ultimate
--- 176,180 ----
     is not at a premium, the user may benefit from setting the maximum load
     ratio at 5% or 10% instead of the usual 66.7%.  This will sharply
!    curtail the number of collisions but will increase iteration time.
  
  2) Dictionary creation time can be shortened in cases where the ultimate