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

Question

Копирование перетасовал range(10**6) лист в десять раз у меня уходит около 0,18 секунд: (эти пять трасс)

0.175597017661 
0.173731403198 
0.178601711594 
0.180330912952 
0.180811964451 

Копирование в unshuffled список десять раз у меня уходит около 0,05 секунд:

0.058402235973 
0.0505464636856 
0.0509734306934 
0.0526022752744 
0.0513324916184 

Вот мое тестирование код:

from timeit import timeit 
import random 

a = range(10**6) 
random.shuffle(a) # Remove this for the second test. 
a = list(a)   # Just an attempt to "normalize" the list. 
for _ in range(5): 
    print timeit(lambda: list(a), number=10) 

Я также попытался скопировать с a[:], результаты были сходными (то есть, большая Шпее d)

Почему большая разница в скорости? Я знаю и понимаю разницу скоростей в знаменитом примере Why is it faster to process a sorted array than an unsorted array?, но здесь моя обработка не имеет решений. Это просто слепо копирование ссылок внутри списка, нет?

Я использую Python 2.7.12 на Windows, 10.

Edit: Пробовал Python 3.5.2, а сейчас, результаты были почти такими же (перемешиваются последовательно около 0,17 секунд, unshuffled последовательно около 0,05 секунд). Вот код, который:

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

Answer 1

Интересный бит, что это зависит от того, в котором целые числа являются первого создан. Например, вместо 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)) (первый и быстрый пример).

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

Быстрый интермеццо:

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

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

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

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

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

---

Вы можете убедиться в этом, посмотрев на 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 

---

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

Я не подумал об этом сам. Большая часть информации содержится в blogpost of Ricky Stewart.

Этот ответ основан на «официальной реализации CPython для Python». Детали в других реализациях (Jython, PyPy, IronPython, ...) могут отличаться. Спасибо @ JörgWMittag for pointing this out.

Answer 2

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

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

Answer 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] 

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

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

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 секунд, я думаю, потому что мои кеши больше не помогают с повторяющимися элементами.