БЛОГ НА HUSL


Почему одинаковые списки при разных способах создания весят по разному?

Автор вопроса: kristal

Столкнулся я недавно с такой вот задачкой:

sys.getsizeof([0] * 3)  # 80
sys.getsizeof([0, 0, 0])  # 120
sys.getsizeof([0 for i in range(3)])  # 88

Проверено на Python 3.10.4. Важно уточнить что такое поведение свойственно не всем версиям пайтона, а только приблизительно с 3.9.19 до 3.10.14(но это не точно).

Собственно вопрос заключается в том что здесь происходит и почему одинаковые списки весят по разному?

import sys

list_1 = [0] * 3
list_2 = [0, 0, 0]
list_3 = [0 for i in range(3)]

print(list_1)  # > [0, 0, 0]
print(list_2)  # > [0, 0, 0]
print(list_3)  # > [0, 0, 0]

print(list_1 == list_2 and list_2 == list_3 and list_3 == list_1)  # > True

print(sys.getsizeof(list_1))  # > 80
print(sys.getsizeof(list_2))  # > 120
print(sys.getsizeof(list_3))  # > 88

Логично предположить, что первый массив после дублирования хранит три ссылки на один и тот же объект в памяти, и это как-то оптимизируется интерпретатором. Но разве для других массивов не происходит то же самое? Ведь Python кэширует числа от -5 до 256, а значит, и в других списках должны храниться три одинаковые ссылки на кэшированное число 0. Однако тогда возникает вопрос: почему три ссылки на одинаковые числа весят столько же, сколько и три ссылки на разные числа, и при этом меньше, чем в списках 2 и 3?

list_4 = list(range(3))
print(list_4)  # > [0, 1, 2]
print(sys.getsizeof(list_4))  # > 80

Источник

Ответы (1 шт):

Автор решения: Stanislav Volodarskiy

  • [0] * <константа> - строит список точно заказанного размера.

  • [0, 0, 0, ...] - строит список одним вызовом list.extend, который для производительности выделяет место с запасом.

  • [0 for i in range(<константа)] - строит список вызывая list.append в цикле. И снова ради производительности место выделяется с запасом. Но этот запас считается слегка по-другому.

Подробности ниже.

[0] * <константа>

Выражение [0] * <константа> всегда компилируется одинаково и приводит к вызову BINARY_MULTIPLY:

n размер код ассемблер
... ... ... ...
4 88 
[0] * 4
 
  2           0 LOAD_CONST               1 (0)
              2 BUILD_LIST               1
              4 LOAD_CONST               2 (4)
              6 BINARY_MULTIPLY
... ... ... ...

BINARY_MULTIPLY с приключениями приходит в list_repeat, который выделяет список ровно требуемого размера (n) и заполняет его нулями. То есть, размер списка всегда 56 + 8n.

n 0 1 2 3 4 5 6 7 8 9 10
размер 56 64 72 80 88 96 104 112 120 128 136

Литерал [0, 0, 0, ...]

Литералы компилируются по разному в зависимости от числа нулей:

n размер код ассемблер
0 56 
[]
 
  2           0 BUILD_LIST               0
1 64 
[0]
 
  2           0 LOAD_CONST               1 (0)
              2 BUILD_LIST               1
2 72 
[0, 0]
 
  2           0 LOAD_CONST               1 (0)
              2 LOAD_CONST               1 (0)
              4 BUILD_LIST               2
3 120 
[0, 0, 0]
 
  2           0 BUILD_LIST               0
              2 LOAD_CONST               1 ((0, 0, 0))
              4 LIST_EXTEND              1
4 120 
[0, 0, 0, 0]
 
  2           0 BUILD_LIST               0
              2 LOAD_CONST               1 ((0, 0, 0, 0))
              4 LIST_EXTEND              1
5 120 
[0, 0, 0, 0, 0]
 
  2           0 BUILD_LIST               0
              2 LOAD_CONST               1 ((0, 0, 0, 0, 0))
              4 LIST_EXTEND              1
... ... ... ...

[], [0] и [0, 0] обрабатываются вызовом BUILD_LIST, который строит точный список. В остальных случаях компилятор сохраняет кортеж (не список (!)) с нулями и вызывает LIST_EXTEND на пустом списке.

LIST_EXTEND - процедура общего назначения. Она должна работать быстро, если вы вызываете её в цикле и добавляете данные в список небольшими порциями. Можно показать что если она будет выделять место под элементы точно, добавление начнёт тормозить на больших списках. Так что список растёт шагами, примерно пропорциональными его размеру. Путанный код внутри list_resize отвечает за странные скачки. Обратите внимание на 120 после 152:

n 0 1 2 3 4 5 6 7 8 9 10
размер 56 64 72 120 120 120 152 120 120 152 152

[0 for i in range(<константа)]

Компилятор одинаково обрабатывает все константы. Например [0 for i in range(4)]:

  2           0 LOAD_CONST               1 (<code object  at 0x7f71c70b7260, file "", line 2>)
              2 LOAD_CONST               2 ('comprehension_4..')
              4 MAKE_FUNCTION            0
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_CONST               3 (4)
             10 CALL_FUNCTION            1
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 RETURN_VALUE

Disassembly of <code object  at 0x7f71c70b7260, file "", line 2>:
  2           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 4 (to 14)
              6 STORE_FAST               1 (i)
              8 LOAD_CONST               0 (0)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            2 (to 4)
        >>   14

Создаётся пустой список и дополняется нулями (LIST_APPEND). Размер списка заранее не вычисляется, список растёт прямо в процессе. Снова он растёт скачками, иначе будут тормоза. Снова за всё отвечает путанный код в list_resize. Но тут он вызывается для других параметров и приводит к немного другим размерам:

n 0 1 2 3 4 5 6 7 8 9 10
размер 56 88 88 88 88 120 120 120 120 184 184

NB По производительности этот вариант самый худший: множественные перевыделения списка, явный цикл на Питоне. Просто кошмар!

→ Ссылка

licensed under cc by-sa 3.0 with attribution.