1. Циклы в CPython

Базовая структура циклов

# Цикл for преобразуется в итерационный протокол
for item in sequence:
    process(item)

# Эквивалентно:
iterator = iter(sequence)
while True:
    try:
        item = next(iterator)
        process(item)
    except StopIteration:
        break

Байткод для циклов

# Пример цикла for
  0 LOAD_FAST                0 (iterable)
  2 GET_ITER
>> 4 FOR_ITER                12 (to 18)
  6 STORE_FAST               1 (x)
  8 LOAD_FAST                1 (x)
 10 PRINT_ITEM
 12 PRINT_NEWLINE
 14 JUMP_ABSOLUTE            4
>> 18 LOAD_CONST             0 (None)
 20 RETURN_VALUE

Оптимизации

• Вложенные циклы: нет специальной оптимизации, каждый цикл независим
• range(): в Python 3.x range создает легковесный объект, а не список
• Unrolling: CPython не делает автоматическую развертку циклов
• Локальные переменные: доступ к LOAD_FAST быстрее, чем к LOAD_GLOBAL

2. Списки (list) - внутреннее устройство

Структура PyListObject

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;  // массив указателей
    Py_ssize_t allocated; // выделенная память
} PyListObject;

Ключевые особенности:

1. Динамический массив указателей

   • Хранит указатели на PyObject, а не сами объекты
   • O(1) доступ по индексу

2. Over-allocation (авансовое выделение)

   # При добавлении элементов
   new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
   # Формула: newsize + newsize//8 + константа
   

3. Рост размера: ~12.5% от текущего размера

Операции и их сложность

# O(1)
lst[i]                # доступ
lst.append(x)         # добавление в конец (амортизированное O(1))
len(lst)

# O(n)
lst.insert(i, x)      # вставка (сдвиг элементов)
lst.pop(i)            # удаление по индексу
lst.remove(x)         # удаление по значению
x in lst              # поиск

Реализация common operations

// Пример: list.append()
static PyObject *
list_append(PyListObject *self, PyObject *object)
{
    if (app1(self, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self);
    
    // Проверка необходимости расширения
    if (n == self->allocated) {
        if (list_resize(self, n+1) < 0)
            return -1;
    }
    
    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    Py_SIZE(self)++;
    return 0;
}

3. Работа с памятью

Управление памятью списков

1. Сборка мусора (Reference Counting)

   # Каждый PyObject имеет счетчик ссылок
   typedef struct _object {
       Py_ssize_t ob_refcnt;  // счетчик ссылок
       PyTypeObject *ob_type;
   } PyObject;
   

2. Memory Allocator

   • Использует pymalloc для небольших объектов (< 512 bytes)
   • Для больших объектов вызывает malloc() напрямую

3. List Resize Strategy

   # При создании списка
   []              # allocated = 0
   
   # При добавлении
   lst = []
   lst.append(1)   # allocated = 4 (over-allocation)
   lst.append(2)   # используем существующую память
   lst.append(3)   # используем существующую память
   lst.append(4)   # используем существующую память
   lst.append(5)   # realloc: allocated = 8
   

Оптимизации

1. Free Lists

   // CPython кэширует освобожденные list объекты
   #define PyList_MAXFREELIST 80
   static PyListObject *free_list[PyList_MAXFREELIST];
   static int numfree = 0;
   

2. Memory Reuse

   # При удалении элементов память не сразу освобождается
   lst = [1, 2, 3, 4, 5]
   del lst[2:]      # Память сохраняется для будущего использования
   lst.append(6)    # Используется существующая выделенная память
   

4. Особенности итерации

Итерационный протокол

# Для списков используется отдельный итератор
class list_iterator {
    Py_ssize_t it_index;
    PyListObject *it_seq;
}

Байткод итерации

# Генерация байткода для разных случаев
for x in lst:        # CREATE_ITERATOR
for i in range(n):   # SPECIALIZED_ITERATOR
for k in dict:       # DICT_ITERATOR

5. Примеры и рекомендации

Эффективная работа со списками

# Плохо: O(n²)
result = []
for item in data:
    result = result + [process(item)]  # Создание нового списка каждый раз

# Хорошо: O(n)
result = []
for item in data:
    result.append(process(item))       # Амортизированное O(1)

# Еще лучше: list comprehension (оптимизированный байткод)
result = [process(item) for item in data]

Особенности list comprehension

# LC создает список более эффективно:
# 1. Предварительно вычисляет размер
# 2. Выделяет память одним блоком
# 3. Заполняет ячейки напрямую

# Байткод list comprehension короче и быстрее
[expr(x) for x in iterable]
# vs
result = []
for x in iterable:
    result.append(expr(x))

Работа с памятью

# Срезы создают новые списки
lst = [1, 2, 3, 4, 5]
slice = lst[1:4]          # Копирование элементов

# Для больших данных лучше использовать:
from itertools import islice
for item in islice(huge_list, start, stop):
    process(item)

6. Внутренние оптимизации CPython

1. Method Caching: часто используемые методы кэшируются
2. Inline Caching: для атрибутов и вызовов методов
3. Specialized Instructions: разные инструкции для разных типов
4. Eval Breaks: периодическая проверка прерываний в длинных циклах

Это общая картина работы CPython с циклами и списками. Реальная реализация содержит больше деталей и оптимизаций для конкретных случаев использования.