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

[rhettinger@users.sourceforge.net]

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

Modified Files:
	dictnotes.txt 
Log Message:
Add notes from python-dev about readonly dictionaries.

Index: dictnotes.txt
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictnotes.txt,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** dictnotes.txt	4 May 2003 21:25:19 -0000	1.2
--- dictnotes.txt	5 May 2003 21:31:51 -0000	1.3
***************
*** 198,199 ****
--- 198,220 ----
     the need to test for dummy entries on each probe.  The preconditions
     for this strategy arise in symbol tables and in the builtin dictionary.
+ 
+ 
+ Readonly Dictionaries
+ ---------------------
+ Some dictionary use cases pass through a build stage and then move to a
+ more heavily exercised lookup stage with no further changes to the
+ dictionary.
+ 
+ An idea that emerged on python-dev is to be able to convert a dictionary
+ to a read-only state.  This can help prevent programming errors and also
+ provide knowledge that can be exploited for lookup optimization.
+ 
+ The dictionary can be immediately rebuilt (eliminating dummy entries),
+ resized (to an appropriate level of sparseness), and the keys can be
+ jostled (to minimize collisions).  The lookdict() routine can then
+ eliminate the test for dummy entries (saving about 1/4 of the time
+ spend in the collision resolution loop).
+ 
+ An additional possibility is to insert links into the empty spaces
+ so that dictionary iteration can proceed in len(d) steps instead of
+ (mp->mask + 1) steps.