Почему копирование перетасованного списка происходит намного медленнее?

Ответ 1

Интересный бит заключается в том, что он зависит от порядка создания целых чисел first. Например, вместо shuffle создайте случайную последовательность с помощью random.randint:

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

Это так же быстро, как копирование вашего list(range(10**6)) (первый и быстрый пример).

Однако, когда вы перетасовываете - тогда ваши целые числа не в порядке, в котором они были впервые созданы, что делает его медленным.

Быстрое intermezzo:

• Все объекты Python находятся в куче, поэтому каждый объект является указателем.
• Копирование списка - это мелкая операция.
• Однако Python использует подсчет ссылок, поэтому, когда объект помещается в новый контейнер, счетчик ссылок должен быть увеличен ( Py_INCREF в list_slice), поэтому Python действительно должен пойти туда, где находится объект. Он не может просто скопировать ссылку.

Поэтому, когда вы копируете свой список, вы получаете каждый элемент этого списка и помещаете его "как есть" в новый список. Когда ваш следующий элемент был создан вскоре после текущего, есть хороший шанс (без гарантии!), Который он сохранил рядом с ним в куче.

Предположим, что всякий раз, когда ваш компьютер загружает элемент в кеш, он также загружает элементы x next-in-memory (локальность кэша). Затем ваш компьютер может выполнить инкремент подсчета ссылок для x+1 элементов в одном кеше!

С перетасованной последовательностью он все еще загружает элементы следующего в памяти, но это не те, что находятся в списке. Таким образом, он не может выполнить инкремент счетчика ссылок, не "действительно" ищет следующий элемент.

TL; DR:. Фактическая скорость зависит от того, что произошло перед копией: в каком порядке были созданы эти элементы и в каком порядке они указаны в списке.

Вы можете проверить это, посмотрев id:

Подробности реализации CPython: это адрес объекта в памяти.

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

Просто, чтобы показать короткий отрывок:

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

Итак, эти объекты действительно "рядом друг с другом в куче". С shuffle это не:

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

Что показывает, что они не находятся рядом друг с другом в памяти:

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

Важное примечание:

Я сам этого не думал. Большинство информации можно найти в блоге за то, что указали это.

Ответ 2

Когда вы перетасовываете элементы списка, у них худшая локальность ссылок, что приводит к ухудшению производительности кеша.

Вы можете подумать, что копирование списка просто копирует ссылки, а не объекты, поэтому их расположение в куче не должно иметь значения. Тем не менее, копирование по-прежнему связано с доступом к каждому объекту для модификации refcount.

Ответ 3

Как объясняется другими, это не просто копирование ссылок, но также увеличивает количество ссылок в объектах и, следовательно, объекты доступны и кеш играет роль.

Здесь я просто хочу добавить больше экспериментов. Не столько о перетасовке и неподготовленности (когда доступ к одному элементу может пропустить кеш, но в кеш-память входят следующие элементы, чтобы они попадали). Но об повторяющихся элементах, где последующие обращения одного и того же элемента могут попасть в кеш, потому что элемент все еще находится в кеше.

Тестирование нормального диапазона:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

Список одного и того же размера, но с одним повторяющимся элементом снова и снова, быстрее, поскольку он все время попадает в кеш:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

И, похоже, не имеет значения, какое это число:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

Интересно, что он становится еще быстрее, когда я вместо этого повторяю те же два или четыре элемента:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

Я думаю, что-то не нравится, что один и тот же счетчик постоянно увеличивается. Возможно, какой-то конвейерный столп, потому что каждое увеличение должно ждать результата предыдущего увеличения, но это дикое предположение.

В любом случае, попробуйте это для еще большего количества повторяющихся элементов:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

Выход (первый столбец - это количество разных элементов, для каждого из которых я тестирую три раза, а затем беру среднее значение):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

Таким образом, примерно с 2,8 секунды для одного (повторного) элемента он опускается до 2,2 секунды для 2, 4, 8, 16,... разных элементов и остается около 2,2 секунды до сотен тысяч. Я думаю, что это использует мой кэш L2 (4 × 256 КБ, у меня есть i7-6700).

Затем в течение нескольких шагов время увеличивается до 3,5 секунд. Я думаю, что это использует смесь моего кэша L2 и моего кеша L3 (8 МБ) до тех пор, пока это не будет исчерпано.

В конце он остается около 3,5 секунд, я думаю, потому что мои кеши больше не помогают с повторяющимися элементами.