Как работает bytearray в Python? Смотрим реализую на C
Привет! Меня зовут Никита Соболев, я core-разработчик языка программирования CPython, а так же автор серии видео про его устройство.
Сегодня я хочу рассказать, как bytearray устроен внутри.
Под катом будет про: интересные оптимизации, разные аллокаторы в CPython, C pointer math, детали устройства данной структуры данных.
Если вам такое интересно или целиком незнакомо — добро пожаловать!
Начнем с видео, а далее в текстовом формате опишем основные моменты.
Как выглядит bytearray в исходниках CPython?
Сама структура, которая используется питоном выглядит вот так:
typedef struct {
PyObject_VAR_HEAD
Py_ssize_t ob_alloc; /* How many bytes allocated in ob_bytes */
char *ob_bytes; /* Physical backing buffer */
char *ob_start; /* Logical start inside ob_bytes */
Py_ssize_t ob_exports; /* How many buffer exports */
} PyByteArrayObject;Что здесь есть интересного?
PyObject_VAR_HEAD — макрос, который разворачивается в
PyVarObject ob_base;Данный код указывает: во-первых, базовый класс (objectв нашем случае), и что размеры каждого инстанса будут отличаться. Сравнимbytearray()с размером 0 иbytearray(b'abc')с размером 4 байтаPy_ssize_t ob_allocотвечает за хранение размера структуры, дальше рассмотрим волшебный метод__alloc__char *ob_bytes— указатель на буфер с реальными даннымиchar *ob_start— оптимизация, указатель на логическое начало данных средиob_bytes, далее мы рассмотрим, зачем оно нужноPy_ssize_t ob_exports— количество раз, когда мы делали «export» объекта черезBufferпротокол и метод__buffer__
Создание bytearray
Создать bytearray можно разными способами, документацию мы тут пересказывать не будем. А посмотрим мы на C-API функцию PyByteArray_FromStringAndSize (имеется в виду, конечно не питоновский str, а сишное представление), которая широко используется для создания bytearray объектов в коде. Например, при использовании bytearray.copy. Для нас она — отличный пример, потому что очень наглядная:
PyObject *
PyByteArray_FromStringAndSize(const char *bytes, Py_ssize_t size)
{
Py_ssize_t alloc;
/* Код упрощен для целей демонстрации. */
PyByteArrayObject *new = PyObject_New(PyByteArrayObject, &PyByteArray_Type);
if (size == 0) {
new->ob_bytes = NULL;
alloc = 0;
}
else {
alloc = size + 1;
new->ob_bytes = PyMem_Malloc(alloc);
if (new->ob_bytes == NULL) {
Py_DECREF(new);
return PyErr_NoMemory();
}
if (bytes != NULL && size > 0)
memcpy(new->ob_bytes, bytes, size);
new->ob_bytes[size] = '\0'; /* Trailing null byte */
}
Py_SET_SIZE(new, size);
new->ob_alloc = alloc;
new->ob_start = new->ob_bytes;
new->ob_exports = 0;
return (PyObject *)new;
}Что нас здесь может заинтересовать?
Создание объекта с длинной 0, имеет быстрый путь, ничего дополнительного мы не делаем
Если у нас есть не нулевой размер «строки», которую нам передали, то мы выделяем участок памяти на 1 байт больше, чем нам нужно, используем PyMem_Malloc. По сути мы получим просто указатель на неинициализированный кусок памяти нужного нам размера. Простой и понятный аллокатор
Далее, мы используем memcpy для копирования
bytesвnew->ob_bytesс размеромsize(на 1 меньше выделенного участка памяти)Последним шагом мы добавляем
\0(null-byte) в последнюю незанятую позицию в->ob_bytesИнициализируем все нужные поля структуры
Посмотрим, что нам выдается правильный размер через магический метод __alloc__:
PyDoc_STRVAR(alloc_doc,
"B.__alloc__() -> int\n\
\n\
Return the number of bytes actually allocated.");
static PyObject *
bytearray_alloc(PyByteArrayObject *self, PyObject *Py_UNUSED(ignored))
{
return PyLong_FromSsize_t(self->ob_alloc);
}И проверим:
>>> b = bytearray(b'abc')
>>> b.__alloc__()
4Все верно, ответ 4 — потому что у нас есть еще один дополнительный байт — \0!
Удаляем байты из начала
Следующая интересная тема — оптимизация с ob_start. Когда мы работаем с набором байт, нам часто нужно удалить какие-то байты в начале последовательности. Например, заголовок какой-нибудь в известное количество байт. То есть, мы будем делать del b[:4] для удаления первых четырех байт.
Как оно будет работать? Посмотрим на bytearray_setslice_linear, который вызывается из bytearray_setslice:
static int
bytearray_setslice_linear(PyByteArrayObject *self,
Py_ssize_t lo, Py_ssize_t hi,
char *bytes, Py_ssize_t bytes_len)
{
Py_ssize_t avail = hi - lo;
char *buf = PyByteArray_AS_STRING(self);
Py_ssize_t growth = bytes_len - avail;
int res = 0;
assert(avail >= 0);
if (growth < 0) {
if (!_canresize(self))
return -1;
if (lo == 0) {
/* Shrink the buffer by advancing its logical start */
self->ob_start -= growth;
/*
0 lo hi old_size
| |<----avail----->|<-----tail------>|
| |<-bytes_len->|<-----tail------>|
0 new_lo new_hi new_size
*/
}
else {
/*
0 lo hi old_size
| |<----avail----->|<-----tomove------>|
| |<-bytes_len->|<-----tomove------>|
0 lo new_hi new_size
*/
memmove(buf + lo + bytes_len, buf + hi,
Py_SIZE(self) - hi);
}
// ...
}
// ...
}Давайте посмотрим на такой питон код, который вызовет код выше:
>>> b = bytearray(b'abc')
>>> del b[0]
>>> b
bytearray(b'bc')
>>> b.__alloc__()
4Смотрите: мы удаляем нулевой объект в bytearray, но почему-то не происходит изменения размера в self->ob_alloc. Ответ в коде выше на C. Что там происходит?
Если мы сталкиваемся с «отрицательным ростом» размера объекта, то мы смотрим, откуда начинается изменение: с нуля или нет
Если мы удаем, скажем
del b[2:4], то нам приходится идти по сложному пути и двигать память при помощиmemmoveЕсли мы удаляем объекты с нуля, то мы просто перемещаем указатель
ob_startна нужное количество байт
Тут нужно сделать оговорку про self->ob_start -= growth; Тут немного нужно разобраться, что такое C pointer math. Потому что тут мы отнимаем число от указателя (точнее прибавляем, потому что growth отрицательный)! На самом деле мы делаем что-то вроде: self->ob_start -= (growth * sizeof(char)) . То есть, мы прибавляем размер данных внутри указателя, что позволяет нам, например, переходить по значениям внутри массива. Пример (отсюда):
#include
int main() {
int int_arr[] = {12, 23, 45};
int *ptrArr = int_arr;
printf("Value at ptrArr: %d\n", *ptrArr); // 12
// Добавляем 2 к указателю:
ptrArr = ptrArr + 2; // ptrArr + (2 * sizeof(int))
// Мы с 12 перевели на 2 значения вперед: до 45
printf("Value at ptrArr after adding 2: %d\n", *ptrArr); // 45
return 0;
} Следовательно, когда мы делаем self->ob_start -= growth при growth = -1, бы добавляем: self->ob_start = self.ob_start - (-1 * sizeof(char)), где sizeof(char) является 1. И мы просто сдвигаем указатель в случае del b[0] на один байт. Смотрите:
static inline char* PyByteArray_AS_STRING(PyObject *op)
{
PyByteArrayObject *self = _PyByteArray_CAST(op);
if (Py_SIZE(self)) {
return self->ob_start;
}
return _PyByteArray_empty_string;
}Почти везде в bytearray мы далее используем self->ob_start через PyByteArray_AS_STRING. И потому такая оптимизация дает нам O (1) удаление с начала последовательности!
Добавляем новые значения через .append ()
Сам по себе bytearray.append очень простой. Но, в нем есть самая интересная часть:
if (PyByteArray_Resize((PyObject *)self, n + 1) < 0)
return NULL;
PyByteArray_AS_STRING(self)[n] = item;Давайте разбираться с ней. Как происходит увеличение bytearray? Сначала мы выбираем стратегию увеличения размера: будем ли мы делать пере-аллокацию? Или добавим только нужное количество байт?
int
PyByteArray_Resize(PyObject *self, Py_ssize_t requested_size)
{
void *sval;
PyByteArrayObject *obj = ((PyByteArrayObject *)self);
/* All computations are done unsigned to avoid integer overflows
(see issue #22335). */
size_t alloc = (size_t) obj->ob_alloc;
size_t logical_offset = (size_t) (obj->ob_start - obj->ob_bytes);
size_t size = (size_t) requested_size;
if (size + logical_offset + 1 <= alloc) {
/* Current buffer is large enough to host the requested size,
decide on a strategy. */
if (size < alloc / 2) {
/* Major downsize; resize down to exact size */
alloc = size + 1;
}
else {
/* Minor downsize; quick exit */
Py_SET_SIZE(self, size);
PyByteArray_AS_STRING(self)[size] = '\0'; /* Trailing null */
return 0;
}
}
else {
/* Need growing, decide on a strategy */
if (size <= alloc * 1.125) {
/* Moderate upsize; overallocate similar to list_resize() */
alloc = size + (size >> 3) + (size < 9 ? 3 : 6);
}
else {
/* Major upsize; resize up to exact size */
alloc = size + 1;
}
}
// ...
}Что мы видим?
Если объект уменьшается, то мы можем пойти по долгому пути (в случае если запрашиваемый размер в два раза меньше текущего), чтобы сохранить память, или просто сделать быструю замену размера и установить
\0в конец. Так быстрее, но требует больше «лишней» памятиЕсли объект увеличивается, то мы можем выделить дополнительную память, которая пока не очень нужна (в случае если запрашиваемый размер в
1.125раза больше текущего), или просто добавить требуемое количество памяти
Далее, нам нужно выполнить саму аллокацию / реаллокацию памяти и установить нужные поля в объекте. Тут мы будем смотреть на наличие ob_start в logical_offset:
// ...
if (logical_offset > 0) {
sval = PyMem_Malloc(alloc);
if (sval == NULL) {
PyErr_NoMemory();
return -1;
}
memcpy(sval, PyByteArray_AS_STRING(self),
Py_MIN((size_t)requested_size, (size_t)Py_SIZE(self)));
PyMem_Free(obj->ob_bytes);
}
else {
sval = PyMem_Realloc(obj->ob_bytes, alloc);
if (sval == NULL) {
PyErr_NoMemory();
return -1;
}
}
obj->ob_bytes = obj->ob_start = sval;
Py_SET_SIZE(self, size);
obj->ob_alloc = alloc;
obj->ob_bytes[size] = '\0'; /* Trailing null byte */
return 0;
}Если
ob_startбольшеob_bytes, то мы имеем дело с «оптимизированным» случаем из примера в прошлой главе. Тогда нам нужно создать полностью новый участок памяти нового размера при помощи PyMem_Malloc. И скопировать память в новое место изPyByteArray_AS_STRING(self)(self->ob_start) правильного размера. То есть, не потребуются уже отрошенные куски памяти. Такая операция, очевидно, долгаяВ противном случае (если мы не оптимизировали ничего и оба указателя совпадают), то мы используем PyMem_Realloc для добавления нужного количества байт к
self->ob_bytes, что значительно быстрее
Итого, данное объяснение позволяет нам ответить на вопрос: какой код быстрее?
b1 = bytearray(b'abc')
b1.append(ord(b'd'))
del b1[0]
b2 = bytearray(b'abc')
del b2[0]
b2.append(ord(b'd'))Да, правильно. Первый код быстрее. Замеры:
» pyperf timeit -s 'b = bytearray(b"abc"); c = ord(b"d")' '
b.append(c); del b[0]'
.....................
Mean +- std dev: 33.1 ns +- 0.1 ns
» pyperf timeit -s 'b = bytearray(b"abc"); c = ord(b"d")' '
del b[0]; b.append(ord(b"d"))'
.....................
Mean +- std dev: 41.3 ns +- 0.4 nsВыводы
Мы обсудили много интересного. Но много всего осталось за кадром. Почему, например, код вида
>>> b = bytearray(b'1234')
>>> del b[:4:2]
>>> b
bytearray(b'24')
>>> b.__alloc__()
5работает так, как он работает? Ответ прячется в bytearray_ass_subscript.
Если нравится такой контект, забегайте ко мне в телеграм канал. Там мы регулярно обсуждаем устройство технологий. С любовью и глубоким погружением. В том числе и пример выше.
А что-то (как, например, место bytearray среди интерфейсов питона и ob_exports) я более подробно объяснил в приложенном видео.
Ну, а вывод от текущего только один — если вы понимаете, как работает ваш код, то вы можете писать более оптимальные и быстрые программы! :)
