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

[rhettinger@users.sourceforge.net]

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

Modified Files:
	dictnotes.txt 
Log Message:
Add notes on use cases with paired accesses to the same key.



Index: dictnotes.txt
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictnotes.txt,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** dictnotes.txt	5 May 2003 21:31:51 -0000	1.3
--- dictnotes.txt	28 May 2003 14:10:46 -0000	1.4
***************
*** 29,39 ****
      Repeated writes to a smaller set of keys.
      Single read of each key.
  
      * Removing duplicates from a sequence.
          dict.fromkeys(seqn).keys()
      * Counting elements in a sequence.
!         for e in seqn:  d[e]=d.get(e,0) + 1
!     * Accumulating items in a dictionary of lists.
!         for k, v in itemseqn:  d.setdefault(k, []).append(v)
  
  Membership Testing
--- 29,51 ----
      Repeated writes to a smaller set of keys.
      Single read of each key.
+     Some use cases have two consecutive accesses to the same key.
  
      * Removing duplicates from a sequence.
          dict.fromkeys(seqn).keys()
+ 
      * Counting elements in a sequence.
!         for e in seqn:
!           d[e] = d.get(e,0) + 1
! 
!     * Accumulating references in a dictionary of lists:
! 
!         for pagenumber, page in enumerate(pages):
!           for word in page:
!             d.setdefault(word, []).append(pagenumber)
! 
!     Note, the second example is a use case characterized by a get and set
!     to the same key.  There are similar used cases with a __contains__
!     followed by a get, set, or del to the same key.  Part of the
!     justification for d.setdefault is combining the two lookups into one.
  
  Membership Testing
***************
*** 45,49 ****
  
  Dynamic Mappings
!     Characterized by deletions interspersed with adds and replacments.
      Performance benefits greatly from the re-use of dummy entries.
  
--- 57,61 ----
  
  Dynamic Mappings
!     Characterized by deletions interspersed with adds and replacements.
      Performance benefits greatly from the re-use of dummy entries.
  
***************
*** 142,145 ****
--- 154,160 ----
  in cache.
  
+ * In use cases with paired accesses to the same key, the second access
+ is always in cache and gets no benefit from efforts to further improve
+ cache locality.
  
  Optimizing the Search of Small Dictionaries
***************
*** 185,189 ****
     a more sparse environment than before.  The preconditions for this
     strategy arise whenever a dictionary is created from a key or item
!    sequence of known length.
  
  3) If the key space is large and the access pattern is known to be random,
--- 200,204 ----
     a more sparse environment than before.  The preconditions for this
     strategy arise whenever a dictionary is created from a key or item
!    sequence and the number of unique keys is known.
  
  3) If the key space is large and the access pattern is known to be random,
***************
*** 219,220 ****
--- 234,245 ----
  so that dictionary iteration can proceed in len(d) steps instead of
  (mp->mask + 1) steps.
+ 
+ 
+ Caching Lookups
+ ---------------
+ The idea is to exploit key access patterns by anticipating future lookups
+ based of previous lookups.
+ 
+ The simplest incarnation is to save the most recently accessed entry.
+ This gives optimal performance for use cases where every get is followed
+ by a set or del to the same key.