[Python-checkins] CVS: python/dist/src/Objects dictobject.c,2.87,2.88

[Tim Peters]

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

Modified Files:
	dictobject.c 
Log Message:
Aggressive reordering of dict comparisons.  In case of collision, it stands
to reason that me_key is much more likely to match the key we're looking
for than to match dummy, and if the key is absent me_key is much more
likely to be NULL than dummy:  most dicts don't even have a dummy entry.
Running instrumented dict code over the test suite and some apps confirmed
that matching dummy was 200-300x less frequent than matching key in
practice.  So this reorders the tests to try the common case first.
It can lose if a large dict with many collisions is mostly deleted, not
resized, and then frequently searched, but that's hardly a case we
should be favoring.


Index: dictobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v
retrieving revision 2.87
retrieving revision 2.88
diff -C2 -r2.87 -r2.88
*** dictobject.c	2001/05/13 00:19:31	2.87
--- dictobject.c	2001/05/13 06:43:53	2.88
***************
*** 220,223 ****
--- 220,225 ----
  	if (!incr)
  		incr = mask;
+ 	/* In the loop, me_key == dummy is by far (factor of 100s) the
+ 	   least likely outcome, so test for that last. */
  	for (;;) {
  		ep = &ep0[(i+incr)&mask];
***************
*** 225,243 ****
  			if (restore_error)
  				PyErr_Restore(err_type, err_value, err_tb);
! 			if (freeslot != NULL)
! 				return freeslot;
! 			else
! 				return ep;
! 		}
! 		if (ep->me_key == dummy) {
! 			if (freeslot == NULL)
! 				freeslot = ep;
  		}
! 		else if (ep->me_key == key) {
  			if (restore_error)
  				PyErr_Restore(err_type, err_value, err_tb);
  			return ep;
  		}
! 		else if (ep->me_hash == hash) {
  			if (!checked_error) {
  				checked_error = 1;
--- 227,238 ----
  			if (restore_error)
  				PyErr_Restore(err_type, err_value, err_tb);
! 			return freeslot == NULL ? ep : freeslot;
  		}
! 		if (ep->me_key == key) {
  			if (restore_error)
  				PyErr_Restore(err_type, err_value, err_tb);
  			return ep;
  		}
! 		else if (ep->me_hash == hash && ep->me_key != dummy) {
  			if (!checked_error) {
  				checked_error = 1;
***************
*** 258,266 ****
  				PyErr_Clear();
  		}
  		/* Cycle through GF(2^n)-{0} */
! 		incr = incr << 1;
  		if (incr > mask)
! 			incr ^= mp->ma_poly; /* This will implicitly clear
! 						the highest bit */
  	}
  }
--- 253,262 ----
  				PyErr_Clear();
  		}
+ 		else if (ep->me_key == dummy && freeslot == NULL)
+ 			freeslot = ep;
  		/* Cycle through GF(2^n)-{0} */
! 		incr <<= 1;
  		if (incr > mask)
! 			incr ^= mp->ma_poly; /* clears the highest bit */
  	}
  }
***************
*** 315,340 ****
  	if (!incr)
  		incr = mask;
  	for (;;) {
  		ep = &ep0[(i+incr)&mask];
! 		if (ep->me_key == NULL) {
! 			if (freeslot != NULL)
! 				return freeslot;
! 			else
! 				return ep;
! 		}
! 		if (ep->me_key == dummy) {
! 			if (freeslot == NULL)
! 				freeslot = ep;
! 		}
! 		else if (ep->me_key == key
! 			 || (ep->me_hash == hash
! 			     && compare(ep->me_key, key) == 0)) {
  			return ep;
! 		}
  		/* Cycle through GF(2^n)-{0} */
! 		incr = incr << 1;
  		if (incr > mask)
! 			incr ^= mp->ma_poly; /* This will implicitly clear
! 						the highest bit */
  	}
  }
--- 311,331 ----
  	if (!incr)
  		incr = mask;
+ 	/* In the loop, me_key == dummy is by far (factor of 100s) the
+ 	   least likely outcome, so test for that last. */
  	for (;;) {
  		ep = &ep0[(i+incr)&mask];
! 		if (ep->me_key == NULL)
! 			return freeslot == NULL ? ep : freeslot;
! 		if (ep->me_key == key
! 		    || (ep->me_hash == hash
! 		        && ep->me_key != dummy
! 			&& compare(ep->me_key, key) == 0))
  			return ep;
! 		else if (ep->me_key == dummy && freeslot == NULL)
! 			freeslot = ep;
  		/* Cycle through GF(2^n)-{0} */
! 		incr <<= 1;
  		if (incr > mask)
! 			incr ^= mp->ma_poly; /* clears the highest bit */
  	}
  }