// Python-3.10.6/Objects/listobject.c
//
// algorithm about how list resize, include expansion and shrink

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{

	...
	
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overallocated size
     * than to the old size.
     */
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = new_allocated;
    return 0;
}

// Python-3.10.6/Objects/listobject.c
//

static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{

	...
	
    PyObject *recycle_on_stack[8];
    PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
    PyObject **item;
    PyObject **vitem = NULL;
    PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
    Py_ssize_t n; /* # of elements in replacement list */
    Py_ssize_t norig; /* # of elements in list getting replaced */
    Py_ssize_t d; /* Change in size */
    Py_ssize_t k;
    size_t s;
    int result = -1;            /* guilty until proved innocent */
#define b ((PyListObject *)v)
    if (v == NULL)
        n = 0;
    else {
        if (a == b) {
            /* Special case "a[i:j] = a" -- copy b first */
            v = list_slice(b, 0, Py_SIZE(b));
            if (v == NULL)
                return result;
            result = list_ass_slice(a, ilow, ihigh, v);
            Py_DECREF(v);
            return result;
        }
        v_as_SF = PySequence_Fast(v, "can only assign an iterable");
        if(v_as_SF == NULL)
            goto Error;
        n = PySequence_Fast_GET_SIZE(v_as_SF);
        vitem = PySequence_Fast_ITEMS(v_as_SF);
    }
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);

    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);

    norig = ihigh - ilow;
    assert(norig >= 0);
    d = n - norig;

    if (Py_SIZE(a) + d == 0) {
        Py_XDECREF(v_as_SF);
        return _list_clear(a);
    }
    item = a->ob_item;
    /* recycle the items that we are about to remove */
    s = norig * sizeof(PyObject *);
    /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
    if (s) {
        if (s > sizeof(recycle_on_stack)) {
            recycle = (PyObject **)PyMem_Malloc(s);
            if (recycle == NULL) {
                PyErr_NoMemory();
                goto Error;
            }
        }
        memcpy(recycle, &item[ilow], s);
    }

    if (d < 0) { /* Delete -d items */
        Py_ssize_t tail;
        tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
        memmove(&item[ihigh+d], &item[ihigh], tail);
        if (list_resize(a, Py_SIZE(a) + d) < 0) {
            memmove(&item[ihigh], &item[ihigh+d], tail);
            memcpy(&item[ilow], recycle, s);
            goto Error;
        }
        item = a->ob_item;
    }
    else if (d > 0) { /* Insert d items */
        k = Py_SIZE(a);
        if (list_resize(a, k+d) < 0)
            goto Error;
        item = a->ob_item;
        memmove(&item[ihigh+d], &item[ihigh],
            (k - ihigh)*sizeof(PyObject *));
    }
    for (k = 0; k < n; k++, ilow++) {
        PyObject *w = vitem[k];
        Py_XINCREF(w);
        item[ilow] = w;
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]);
    result = 0;
 Error:
    if (recycle != recycle_on_stack)
        PyMem_Free(recycle);
    Py_XDECREF(v_as_SF);
    return result;
#undef b
}

>>>
>>> # shrinking list by deleting elements
>>>
>>> l = [1]
>>> l.append(2)
>>> sys.getsizeof(l)
120
>>> l.pop(len(l)-1)
2
>>> sys.getsizeof(l)
88
>>>
>>> # comparing with creating new one
>>>
>>> l = l[:len(l)]
>>> sys.getsizeof(l)
64
>>>

// Python-3.10.6/Objects/listobject.c

static int
list_preallocate_exact(PyListObject *self, Py_ssize_t size)
{
    assert(self->ob_item == NULL);
    assert(size > 0);

    /* Since the Python memory allocator has granularity of 16 bytes on 64-bit
     * platforms (8 on 32-bit), there is no benefit of allocating space for
     * the odd number of items, and there is no drawback of rounding the
     * allocated size up to the nearest even number.
     */
    size = (size + 1) & ~(size_t)1;
    PyObject **items = PyMem_New(PyObject*, size);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    self->allocated = size;
    return 0;
}

// Python-3.10.6/Objects/listobject.c

static PyObject *
list_new_prealloc(Py_ssize_t size)
{
    assert(size > 0);
    PyListObject *op = (PyListObject *) PyList_New(0);
    if (op == NULL) {
        return NULL;
    }
    assert(op->ob_item == NULL);
    op->ob_item = PyMem_New(PyObject *, size);
    if (op->ob_item == NULL) {
        Py_DECREF(op);
        return PyErr_NoMemory();
    }
    op->allocated = size;
    return (PyObject *) op;
}

>>> # list_preallocate_exact
>>> l = []
>>> l.extend([1,2,3])
>>> sys.getsizeof(l)
88
>>> l.__sizeof__()
72
>>> l = l[:len(l)]
>>> l.__sizeof__()
64
>>> sys.getsizeof(l)
80
>>>
>>> # list_new_prealloc
>>> l = [1,2,3]
>>> sys.getsizeof(l)
88
>>> l.__sizeof__()
72
>>> l = l[:len(l)]
>>> sys.getsizeof(l)
80
>>> 
>>> 
>>> # only diff when the length of list is odd
>>> 
>>> # list_preallocate_exact
>>> l = []
>>> l.extend([1,2,3,4,5,6])
>>> sys.getsizeof(l)
104
>>> l.__sizeof__()
88
>>> l = l[:len(l)]
>>> sys.getsizeof(l)
104
>>> l.__sizeof__()
88
>>>
>>> # list_new_prealloc
>>> l = [1,2,3,4,5,6]
>>> sys.getsizeof(l)
104
>>> l.__sizeof__()
88
>>> l = l[:len(l)]
>>> sys.getsizeof(l)
104
>>> l.__sizeof__()
88
>>>

nums = [1,2,3,4,5,6]
i = 0
for j in range(len(nums)): # all of done by memmove
    if nums[j] != 4:
        nums[i] = nums[j]
        i = i + 1
    nums = nums[:i]

# P. IndexError: list index out of range
nums = [1,2,3,4,5,6]
for i in range(len(nums)):
    if nums[i] == 9:
        nums.pop(i)


# P. skip check some element
nums = [1,2,3,4,4,5,6]
# output: [1,2,3,4,5,6]
for v in nums:
    if v == 4:
        nums.remove(v)

# remove element in range safely
nums = [1,2,3,4,5,6]
i = 0
while i < len(nums):
    if nums[i] == 4:
        nums.pop(i)
    else:
        i = i + 1

# best way to remove element in range
nums = [1,2,3,4,5,6]
for i in range(len(nums) - 1, -1, -1):
    if nums[i] == 4:
        nums.pop(i)

# P. too many Load / Store ops cause bad performance (> 0.5x slower)
nums = [1,2,3,4,5,6]
i = 0
for j in range(len(nums)):
    if nums[j] != 4:
        nums[i] = nums[j]
        i = i + 1
    # result is nums[:i]