[python] python 元组的实现和探析

typedef struct {
  PyObject_VAR_HEAD
  /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
  PyObject **ob_item;
  /* ob_item contains space for 'allocated' elements.  The number
   * currently in use is ob_size.
   * Invariants:
   *   0 <= ob_size <= allocated
   *   len(list) == ob_size
   *   ob_item == NULL implies ob_size == allocated == 0
   * list.sort() temporarily sets allocated to -1 to detect mutations.
   *
   * Items must normally not be NULL, except during construction when
   * the list is not yet visible outside the function that builds it.
   */
  Py_ssize_t allocated;
} PyListObject;

typedef struct {
  PyObject_VAR_HEAD
  PyObject *ob_item[1];
  /* ob_item contains space for 'ob_size' elements.
   * Items must normally not be NULL, except during construction when
   * the tuple is not yet visible outside the function that builds it.
   */
} PyTupleObject;

• free_list[0] 用于存储长度为 0 的 tuple 对象，整个解释器的生命周期里面只有一个长度为 0 的 tuple 对象实例
  
• free_list[1] 用于存储长度为 1 的 tuple 对象，可以通过 tuple 对象的 ob_item[0] 指针遍历到下一个长度为 1 的 tuple 对象
  
• free_list[2] 用于存储长度为 2 的 tuple 对象，上图画的 free_list[2] 中只有一个对象
  
• free_list 每一格最多能存储 PyTuple_MAXFREELIST个 tuple 链表长度，这里定义的是 2000
  

/* Objects/tupleobject.c 79 - 136 行 */
 
PyObject *
PyTuple_New(Py_ssize_t size)
{
  PyTupleObject *op;
  Py_ssize_t i;
  if (size < 0) {
    PyErr_BadInternalCall();
    return NULL;
  }
/* 如果启动了 free_list 存储 */
#if PyTuple_MAXSAVESIZE > 0
  if (size == 0 && free_list[0]) {
    /* 如果 size 为 0, 则返回 free_list 的第一个元素 */
    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) {
    /* 如果 size 在 free_list 范围内，并且 free_list[size] 存有之前回收过的对应size的tuple 对象 
    把 free_list[size] 指向 op 的下一个链表地址
    */
    free_list[size] = (PyTupleObject *) op->ob_item[0];
    numfree[size]--;
#ifdef COUNT_ALLOCS
    _Py_fast_tuple_allocs++;
#endif
    /* Inline PyObject_InitVar */
#ifdef Py_TRACE_REFS
    Py_SIZE(op) = size;
    Py_TYPE(op) = &PyTuple_Type;
#endif
    _Py_NewReference((PyObject *)op);
  }
  else
#endif
  {
    /* free_list 未找到对应大小的 tuple 并且 size 不为 0，向操作系统分配 */
    /* Check for overflow */
    if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
          sizeof(PyObject *)) / sizeof(PyObject *)) {
      return PyErr_NoMemory();
    }
    op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
    if (op == NULL)
      return NULL;
  }
  /* 把 tuple 里面的元素设置为空指针 */
  for (i=0; i < size; i++)
    op->ob_item[i] = NULL;
#if PyTuple_MAXSAVESIZE > 0
  if (size == 0) {
    free_list[0] = op;
    ++numfree[0];
    Py_INCREF(op);      /* extra INCREF so that this is never freed */
  }
#endif
#ifdef SHOW_TRACK_COUNT
  count_tracked++;
#endif
  _PyObject_GC_TRACK(op);
  return (PyObject *) op;
}

>>> t = ([1,2,3,4],[5,4,5,6,4])
>>> t
([1, 2, 3, 4], [5, 4, 5, 6, 4])
>>> t[1].append("hello yerik")
>>> t
([1, 2, 3, 4], [5, 4, 5, 6, 4, 'hello yerik'])
>>> t[1].pop()
'hello yerik'
>>> t[1].pop(2)
5
>>> t
([1, 2, 3, 4], [5, 4, 6, 4])