[Python-checkins] python/dist/src/Objects listobject.c,2.126,2.127

tim_one@users.sourceforge.net tim_one@users.sourceforge.net
Fri, 19 Jul 2002 00:05:46 -0700


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

Modified Files:
	listobject.c 
Log Message:
More sort cleanup:  Moved the special cases from samplesortslice into
listsort.  If the former calls itself recursively, they're a waste of
time, since it's called on a random permutation of a random subset of
elements.  OTOH, for exactly the same reason, they're an immeasurably
small waste of time (the odds of finding exploitable order in a random
permutation are ~= 0, so the special-case loops looking for order give
up quickly).  The point is more for conceptual clarity.
Also changed some "assert comments" into real asserts; when this code
was first written, Python.h didn't supply assert.h.


Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.126
retrieving revision 2.127
diff -C2 -d -r2.126 -r2.127
*** listobject.c	19 Jul 2002 06:12:32 -0000	2.126
--- listobject.c	19 Jul 2002 07:05:44 -0000	2.127
***************
*** 1006,1046 ****
  	struct SamplesortStackNode stack[STACKSIZE];
  
! 	/* assert lo <= hi */
  	n = hi - lo;
! 
! 	/* ----------------------------------------------------------
! 	 * Special cases
! 	 * --------------------------------------------------------*/
! 	if (n < 2)
! 		return 0;
! 
! 	/* Set r to the largest value such that [lo,r) is sorted.
! 	   This catches the already-sorted case, the all-the-same
! 	   case, and the appended-a-few-elements-to-a-sorted-list case.
! 	   If the array is unsorted, we're very likely to get out of
! 	   the loop fast, so the test is cheap if it doesn't pay off.
! 	*/
! 	/* assert lo < hi */
! 	for (r = lo+1; r < hi; ++r) {
! 		IFLT(*r, *(r-1))
! 			break;
! 	}
! 	/* [lo,r) is sorted, [r,hi) unknown.  Get out cheap if there are
! 	   few unknowns, or few elements in total. */
! 	if (hi - r <= MAXMERGE || n < MINSIZE)
! 		return binarysort(lo, hi, r, compare);
! 
! 	/* Check for the array already being reverse-sorted.  Typical
! 	   benchmark-driven silliness <wink>. */
! 	/* assert lo < hi */
! 	for (r = lo+1; r < hi; ++r) {
! 		IFLT(*(r-1), *r)
! 			break;
! 	}
! 	if (hi - r <= MAXMERGE) {
! 		/* Reverse the reversed prefix, then insert the tail */
! 		reverse_slice(lo, r);
! 		return binarysort(lo, hi, r, compare);
! 	}
  
  	/* ----------------------------------------------------------
--- 1006,1013 ----
  	struct SamplesortStackNode stack[STACKSIZE];
  
! 	assert(lo <= hi);
  	n = hi - lo;
! 	if (n < MINSIZE)
! 		return binarysort(lo, hi, lo, compare);
  
  	/* ----------------------------------------------------------
***************
*** 1094,1098 ****
  	 * --------------------------------------------------------*/
  	for (;;) {
! 		/* assert lo <= hi, so n >= 0 */
  		n = hi - lo;
  
--- 1061,1065 ----
  	 * --------------------------------------------------------*/
  	for (;;) {
! 		assert(lo <= hi);
  		n = hi - lo;
  
***************
*** 1104,1109 ****
  		if (n < MINPARTITIONSIZE || extra == 0) {
  			if (n >= MINSIZE) {
! 				/* assert extra == 0
! 				   This is rare, since the average size
  				   of a final block is only about
  				   ln(original n). */
--- 1071,1076 ----
  		if (n < MINPARTITIONSIZE || extra == 0) {
  			if (n >= MINSIZE) {
! 				assert(extra == 0);
! 				/* This is rare, since the average size
  				   of a final block is only about
  				   ln(original n). */
***************
*** 1185,1189 ****
  		l = lo + 1;
  		r = hi - 1;
! 		/* assert lo < l < r < hi (small n weeded out above) */
  
  		do {
--- 1152,1156 ----
  		l = lo + 1;
  		r = hi - 1;
! 		assert(lo < l && l < r && r < hi);
  
  		do {
***************
*** 1209,1215 ****
  		} while (l < r);
  
! 		/* assert lo < r <= l < hi
! 		   assert r == l or r+1 == l
! 		   everything to the left of l is < pivot, and
  		   everything to the right of r is >= pivot */
  
--- 1176,1181 ----
  		} while (l < r);
  
! 		assert(lo < r && r <= l && l < hi);
! 		/* everything to the left of l is < pivot, and
  		   everything to the right of r is >= pivot */
  
***************
*** 1220,1230 ****
  				--r;
  		}
! 		/* assert lo <= r and r+1 == l and l <= hi
! 		   assert r == lo or a[r] < pivot
! 		   assert a[lo] is pivot
! 		   assert l == hi or a[l] >= pivot
! 		   Swap the pivot into "the middle", so we can henceforth
! 		   ignore it.
! 		*/
  		*lo = *r;
  		*r = pivot;
--- 1186,1195 ----
  				--r;
  		}
! 		assert(lo <= r && r+1 == l && l <= hi);
! 		/* assert r == lo or a[r] < pivot */
! 		assert(*lo == pivot);
! 		/* assert l == hi or a[l] >= pivot */
! 		/* Swap the pivot into "the middle", so we can henceforth
! 		   ignore it. */
  		*lo = *r;
  		*r = pivot;
***************
*** 1251,1261 ****
  		}
  
! 		/* assert lo <= r < l <= hi
! 		   Partitions are [lo, r) and [l, hi) */
! 
! 		/* push fattest first; remember we still have extra PPs
  		   to the left of the left chunk and to the right of
  		   the right chunk! */
! 		/* assert top < STACKSIZE */
  		if (r - lo <= hi - l) {
  			/* second is bigger */
--- 1216,1225 ----
  		}
  
! 		assert(lo <= r && r < l && l <= hi);
! 		/* Partitions are [lo, r) and [l, hi)
! 		   :ush fattest first; remember we still have extra PPs
  		   to the left of the left chunk and to the right of
  		   the right chunk! */
! 		assert(top < STACKSIZE);
  		if (r - lo <= hi - l) {
  			/* second is bigger */
***************
*** 1284,1289 ****
  }
  
- #undef IFLT
- 
  static PyTypeObject immutable_list_type;
  
--- 1248,1251 ----
***************
*** 1291,1296 ****
  listsort(PyListObject *self, PyObject *args)
  {
! 	int err;
  	PyObject *compare = NULL;
  	PyTypeObject *savetype;
  
--- 1253,1259 ----
  listsort(PyListObject *self, PyObject *args)
  {
! 	int k;
  	PyObject *compare = NULL;
+ 	PyObject **hi, **p;
  	PyTypeObject *savetype;
  
***************
*** 1299,1313 ****
  			return NULL;
  	}
  	savetype = self->ob_type;
  	self->ob_type = &immutable_list_type;
! 	err = samplesortslice(self->ob_item,
! 			      self->ob_item + self->ob_size,
! 			      compare);
! 	self->ob_type = savetype;
! 	if (err < 0)
  		return NULL;
- 	Py_INCREF(Py_None);
- 	return Py_None;
  }
  
  int
--- 1262,1321 ----
  			return NULL;
  	}
+ 
  	savetype = self->ob_type;
+ 	if (self->ob_size < 2) {
+ 		k = 0;
+ 		goto done;
+ 	}
+ 
  	self->ob_type = &immutable_list_type;
! 	hi = self->ob_item + self->ob_size;
! 
! 	/* Set p to the largest value such that [lo, p) is sorted.
! 	   This catches the already-sorted case, the all-the-same
! 	   case, and the appended-a-few-elements-to-a-sorted-list case.
! 	   If the array is unsorted, we're very likely to get out of
! 	   the loop fast, so the test is cheap if it doesn't pay off.
! 	*/
! 	for (p = self->ob_item + 1; p < hi; ++p) {
! 		IFLT(*p, *(p-1))
! 			break;
! 	}
! 	/* [lo, p) is sorted, [p, hi) unknown.  Get out cheap if there are
! 	   few unknowns, or few elements in total. */
! 	if (hi - p <= MAXMERGE || self->ob_size < MINSIZE) {
! 		k = binarysort(self->ob_item, hi, p, compare);
! 		goto done;
! 	}
! 
! 	/* Check for the array already being reverse-sorted, or that with
! 	   a few elements tacked on to the end. */
! 	for (p = self->ob_item + 1; p < hi; ++p) {
! 		IFLT(*(p-1), *p)
! 			break;
! 	}
! 	/* [lo, p) is reverse-sorted, [p, hi) unknown. */
! 	if (hi - p <= MAXMERGE) {
! 		/* Reverse the reversed prefix, then insert the tail */
! 		reverse_slice(self->ob_item, p);
! 		k = binarysort(self->ob_item, hi, p, compare);
! 		goto done;
! 	}
! 
! 	/* A large array without obvious pattern. */
! 	k = samplesortslice(self->ob_item, hi, compare);
! 
! done: /* The IFLT macro requires a label named "fail". */;
! fail:
!  	self->ob_type = savetype;
! 	if (k >= 0) {
! 		Py_INCREF(Py_None);
! 		return Py_None;
! 	}
! 	else
  		return NULL;
  }
+ 
+ #undef IFLT
  
  int