[Python-checkins] python/dist/src/Objects abstract.c,2.132,2.133

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv30187

Modified Files:
	abstract.c 
Log Message:
SF bug #1085744:  Performance issues with PySequence_Tuple()

* Added missing error checks.
* Fixed O(n**2) growth pattern.  Modeled after lists to achieve linear
  amortized resizing.  Improves construction of "tuple(it)" when "it" is
  large and does not have a __len__ method.  Other cases are unaffected.



Index: abstract.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/abstract.c,v
retrieving revision 2.132
retrieving revision 2.133
diff -u -d -r2.132 -r2.133
--- abstract.c	19 Sep 2004 06:00:15 -0000	2.132
+++ abstract.c	16 Dec 2004 10:38:38 -0000	2.133
@@ -1427,10 +1427,20 @@
 			break;
 		}
 		if (j >= n) {
-			if (n < 500)
-				n += 10;
-			else
-				n += 100;
+			int oldn = n;
+			/* The over-allocation strategy can grow a bit faster
+			   than for lists because unlike lists the 
+			   over-allocation isn't permanent -- we reclaim
+			   the excess before the end of this routine.
+			   So, grow by ten and then add 25%.
+			*/
+			n += 10;
+			n += n >> 2;
+			if (n < oldn) {
+				/* Check for overflow */
+				PyErr_NoMemory();
+				goto Fail; 
+			}
 			if (_PyTuple_Resize(&result, n) != 0) {
 				Py_DECREF(item);
 				goto Fail;