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.
diff --git a/Objects/abstract.c b/Objects/abstract.c
index 377f359..b981001 100644
--- a/Objects/abstract.c
+++ b/Objects/abstract.c
@@ -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;