diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index aeaf845..79a5d55 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -59,6 +59,15 @@
 }
 #endif
 
+static inline void
+tuple_gc_track(PyTupleObject *op)
+{
+#ifdef SHOW_TRACK_COUNT
+    count_tracked++;
+#endif
+    _PyObject_GC_TRACK(op);
+}
+
 /* Print summary info about the state of the optimized allocator */
 void
 _PyTuple_DebugMallocStats(FILE *out)
@@ -76,25 +85,25 @@
 #endif
 }
 
-PyObject *
-PyTuple_New(Py_ssize_t size)
+/* Allocate an uninitialized tuple object. Before making it public following
+   steps must be done:
+   - initialize its items
+   - call tuple_gc_track() on it
+   Because the empty tuple is always reused and it's already tracked by GC,
+   this function must not be called with size == 0 (unless from PyTuple_New()
+   which wraps this function).
+*/
+static PyTupleObject *
+tuple_alloc(Py_ssize_t size)
 {
     PyTupleObject *op;
-    Py_ssize_t i;
     if (size < 0) {
         PyErr_BadInternalCall();
         return NULL;
     }
 #if PyTuple_MAXSAVESIZE > 0
-    if (size == 0 && free_list[0]) {
-        op = free_list[0];
-        Py_INCREF(op);
-#ifdef COUNT_ALLOCS
-        _Py_tuple_zero_allocs++;
-#endif
-        return (PyObject *) op;
-    }
     if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
+        assert(size != 0);
         free_list[size] = (PyTupleObject *) op->ob_item[0];
         numfree[size]--;
 #ifdef COUNT_ALLOCS
@@ -113,14 +122,33 @@
         /* Check for overflow */
         if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
                     sizeof(PyObject *)) / sizeof(PyObject *)) {
-            return PyErr_NoMemory();
+            return (PyTupleObject *)PyErr_NoMemory();
         }
         op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
         if (op == NULL)
             return NULL;
     }
-    for (i=0; i < size; i++)
+    return op;
+}
+
+PyObject *
+PyTuple_New(Py_ssize_t size)
+{
+    PyTupleObject *op;
+#if PyTuple_MAXSAVESIZE > 0
+    if (size == 0 && free_list[0]) {
+        op = free_list[0];
+        Py_INCREF(op);
+#ifdef COUNT_ALLOCS
+        _Py_tuple_zero_allocs++;
+#endif
+        return (PyObject *) op;
+    }
+#endif
+    op = tuple_alloc(size);
+    for (Py_ssize_t i = 0; i < size; i++) {
         op->ob_item[i] = NULL;
+    }
 #if PyTuple_MAXSAVESIZE > 0
     if (size == 0) {
         free_list[0] = op;
@@ -128,10 +156,7 @@
         Py_INCREF(op);          /* extra INCREF so that this is never freed */
     }
 #endif
-#ifdef SHOW_TRACK_COUNT
-    count_tracked++;
-#endif
-    _PyObject_GC_TRACK(op);
+    tuple_gc_track(op);
     return (PyObject *) op;
 }
 
@@ -211,24 +236,28 @@
 {
     Py_ssize_t i;
     PyObject *o;
-    PyObject *result;
     PyObject **items;
     va_list vargs;
 
+    if (n == 0) {
+        return PyTuple_New(0);
+    }
+
     va_start(vargs, n);
-    result = PyTuple_New(n);
+    PyTupleObject *result = tuple_alloc(n);
     if (result == NULL) {
         va_end(vargs);
         return NULL;
     }
-    items = ((PyTupleObject *)result)->ob_item;
+    items = result->ob_item;
     for (i = 0; i < n; i++) {
         o = va_arg(vargs, PyObject *);
         Py_INCREF(o);
         items[i] = o;
     }
     va_end(vargs);
-    return result;
+    tuple_gc_track(result);
+    return (PyObject *)result;
 }
 
 
@@ -421,7 +450,11 @@
 PyObject *
 _PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
 {
-    PyTupleObject *tuple = (PyTupleObject *)PyTuple_New(n);
+    if (n == 0) {
+        return PyTuple_New(0);
+    }
+
+    PyTupleObject *tuple = tuple_alloc(n);
     if (tuple == NULL) {
         return NULL;
     }
@@ -431,6 +464,7 @@
         Py_INCREF(item);
         dst[i] = item;
     }
+    tuple_gc_track(tuple);
     return (PyObject *)tuple;
 }
 
@@ -486,7 +520,11 @@
     if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
         return PyErr_NoMemory();
     size = Py_SIZE(a) + Py_SIZE(b);
-    np = (PyTupleObject *) PyTuple_New(size);
+    if (size == 0) {
+        return PyTuple_New(0);
+    }
+
+    np = tuple_alloc(size);
     if (np == NULL) {
         return NULL;
     }
@@ -504,6 +542,7 @@
         Py_INCREF(v);
         dest[i] = v;
     }
+    tuple_gc_track(np);
     return (PyObject *)np;
 #undef b
 }
@@ -515,8 +554,6 @@
     Py_ssize_t size;
     PyTupleObject *np;
     PyObject **p, **items;
-    if (n < 0)
-        n = 0;
     if (Py_SIZE(a) == 0 || n == 1) {
         if (PyTuple_CheckExact(a)) {
             /* Since tuples are immutable, we can return a shared
@@ -524,13 +561,14 @@
             Py_INCREF(a);
             return (PyObject *)a;
         }
-        if (Py_SIZE(a) == 0)
-            return PyTuple_New(0);
+    }
+    if (Py_SIZE(a) == 0 || n <= 0) {
+        return PyTuple_New(0);
     }
     if (n > PY_SSIZE_T_MAX / Py_SIZE(a))
         return PyErr_NoMemory();
     size = Py_SIZE(a) * n;
-    np = (PyTupleObject *) PyTuple_New(size);
+    np = tuple_alloc(size);
     if (np == NULL)
         return NULL;
     p = np->ob_item;
@@ -542,6 +580,7 @@
             p++;
         }
     }
+    tuple_gc_track(np);
     return (PyObject *) np;
 }
 
@@ -754,7 +793,6 @@
     else if (PySlice_Check(item)) {
         Py_ssize_t start, stop, step, slicelength, i;
         size_t cur;
-        PyObject* result;
         PyObject* it;
         PyObject **src, **dest;
 
@@ -774,11 +812,11 @@
             return (PyObject *)self;
         }
         else {
-            result = PyTuple_New(slicelength);
+            PyTupleObject* result = tuple_alloc(slicelength);
             if (!result) return NULL;
 
             src = self->ob_item;
-            dest = ((PyTupleObject *)result)->ob_item;
+            dest = result->ob_item;
             for (cur = start, i = 0; i < slicelength;
                  cur += step, i++) {
                 it = src[cur];
@@ -786,7 +824,8 @@
                 dest[i] = it;
             }
 
-            return result;
+            tuple_gc_track(result);
+            return (PyObject *)result;
         }
     }
     else {