[Python-checkins] CVS: python/dist/src/Misc NEWS,1.178,1.179

[Tim Peters]

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

Modified Files:
	NEWS 
Log Message:
New collision resolution scheme:  no polynomials, simpler, faster, less
code, less memory.  Tests have uncovered no drawbacks.  Christian and
Vladimir are the other two people who have burned many brain cells on the
dict code in recent years, and they like the approach too, so I'm checking
it in without further ado.


Index: NEWS
===================================================================
RCS file: /cvsroot/python/python/dist/src/Misc/NEWS,v
retrieving revision 1.178
retrieving revision 1.179
diff -C2 -r1.178 -r1.179
*** NEWS	2001/05/28 22:30:07	1.178
--- NEWS	2001/06/02 05:27:19	1.179
***************
*** 16,20 ****
    casing of Unicode object return values was dropped (Unicode objects
    were auto-magically converted to string using the default encoding).
!   
    Both methods will now return whatever the codec in charge of the
    requested encoding returns as object, e.g. Unicode codecs will
--- 16,20 ----
    casing of Unicode object return values was dropped (Unicode objects
    were auto-magically converted to string using the default encoding).
! 
    Both methods will now return whatever the codec in charge of the
    requested encoding returns as object, e.g. Unicode codecs will
***************
*** 117,127 ****
    values mutated the dicts.  Making the code bulletproof slowed it down.
  
! - Collisions in dicts now use polynomial division instead of multiplication
!   to generate the probe sequence, following an idea of Christian Tismer's.
!   This allows all bits of the hash code to come into play.  It should have
!   little or no effect on speed in ordinary cases, but can help dramatically
!   in bad cases.  For example, looking up every key in a dict d with
!   d.keys() = [i << 16 for i in range(20000)] is approximately 500x faster
!   now.
  
  Library
--- 117,125 ----
    values mutated the dicts.  Making the code bulletproof slowed it down.
  
! - Collisions in dicts are resolved via a new approach, which can help
!   dramatically in bad cases.  For example, looking up every key in a dict
!   d with d.keys() = [i << 16 for i in range(20000)] is approximately 500x
!   faster now.  Thanks to Christian Tismer for pointing out the cause and
!   the nature of an effective cure (last December! better late than never).
  
  Library