¿Cómo funciona el método append de una lista en CPython?

Vamos a empezar con más preguntas que respuestas.
Como sabéis, las listas de Python son arrays dinámicos. Por otro lado, las tuplas son arrays estáticos.
¿Qué implica que las listas sean arrays dinámicos?
Al ser un array dinámico podemos modificar sus elementos así como extender el array (lista).
¿Cómo funciona lo de extender el array (lista)?
Cada vez que usamos el método append de las listas se crea una copia de la lista original y se añade un elemento a esa copia para luego borrar el array original.
¿Es esto último cierto?
Más o menos.
Todos estaréis conmigo que si cada vez que añadimos un nuevo elemento tenemos que crear una copia y luego eliminar el array original podríamos crear cierto coste/gasto de recursos (en memoria, principalmente, creando copias).
Veamos un poco de código:

En el anterior código hemos creado una lista vacía y le hemos ido añadiendo elementos y hemos obtenido el tamaño de la lista usando la función getsizeof que nos indica el tamaño del objeto en bytes. Luego hemos mostrado en pantalla el número de elementos que tiene la lista y el tamaño que ocupa.
Pero, ¿qué ocurre?, ¿por qué aumentando el número de elementos, a veces, no aumenta el tamaño del objeto?, ¿por qué luego cambia?, ¿por qué a medida que hay más elementos en la lista tarda más en cambiar el tamaño de la misma?
Veamos qué dice el código original de las listas en el repo de Python localizado en Objects/listobject.c.
A partir de la línea 42 del código C podemos leer:

La última línea traducida a Python sería algo así:

En el primer paréntesis tenemos el operador bitwise right shift, similar a la versión en C (no hay que olvidar que CPython está escrito en C) mientras que en el segundo paréntesis tenemos el operador ternario (sin duda, un poco más legible que la versión en C).
¿Qué está pasando aquí?
Los buenos de los core developers de CPython han pensado que si usas un array dinámico será porque quieres hacer ‘perrerías’ con él, como ampliarlo. Y si lo amplías una vez es probable que lo amplíes varias veces. Es por ello que, normalmente, se usa un un tamaño un poco mayor, basado en el tamaño y siquiendo la regla mostrada más arriba, para el array (lista) y, de esta forma, podemos ampliarlo sin necesidad de crear tantas copias.
Veamos esto gráficamente:

Importamos matplotlib para poder crear los gráficos.

Creamos nuestra lista y otra lista que almacenará los tamaños en bytes, sizes.

Y ahora dibujamos los tamaños en función del número de elementos dentro de la lista:

Vemos como los “escalones” en el tamaño de la lista con N elementos va aumentando y el escalón cada vez es más largo a medida que aumenta el tamaño de la lista.

Veamos como es el valor del tamaño dividido por el número de elementos de la lista a medida que va aumentando el mismo (los ejes de la gráfica tienen escala logarítmica):

Curioso, ¿no?

Espero que hayáis aprendido tanto como he aprendido yo elaborando esta entrada.