Почему вложенный l oop работает намного быстрее, чем сплющенный?

Question

ОБНОВЛЕНИЕ

Извините, ребята, но предыдущее число НЕТОЧНО. Когда я тестировал предыдущий код, я использовал tqdm, чтобы увидеть ожидаемое время, и функция снизит производительность, если итерируемый объект очень длинный. Таким образом, я получаю 18,22 с, что в 9 раз больше, чем 2,43 с.

ОДНАКО, вывод СОГЛАСОВАН: вложенный l oop намного БЫСТРЕЕ. При времени итерации 100 ^ 5 разница значительна: 321,49 против 210,05. Между ними разница примерно в 1,53 раза. Как правило, мы не сталкиваемся с такой длинной итерацией, мне просто интересно узнать причину аномальной ситуации c.

Моя python версия - 3.7.3. Я использую 13-дюймовый MacBookPro2019 с процессором Intel Core i5 2,4 ГГц. Операционная система - macOS Mojave 10.14.6

---

Я обнаружил странную ситуацию в python следующим образом:

import time

start = time.time()
# flattened loop
for i in range(100**4):
    pass
print(time.time() - start) # 18.22(Wrong! Should be 3.09)

# nested loop
start = time.time()
for i in range(100):
    for j in range(100):
        for k in range(100):
            for l in range(100):
                pass
print(time.time() - start) # 2.43

Два вида циклов, указанных выше, имеют одинаковое время итерации. Однако вложенный l oop (2,43 с) работает намного быстрее, чем сплющенный (18,22 с). Разница тем больше, чем больше время итерации. Мотыги такое бывает?

Answer 1

Во-первых, это ненадежный способ измерения выполнения кода. Давайте вместо этого рассмотрим этот код (который будет запускаться в I Python), который не включает расчет мощности в l oop, и имеет некоторые вычисления, чтобы убедиться, что он не может быть «оптимизирован» до «пожалуйста, сделайте» ничего ".

def flattened_loop(n):
    x = 0
    for i in range(n):
        x += 1
    return x


def nested4_loop(n):
    x = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                for l in range(n):
                    x += 1
    return x


print(f'{"n":>4s}  {"n ** 4":>16s}  {"flattened":>18s}  {"nested4":>18s}')
for n in range(10, 120, 10):
    t1 = %timeit -q -o flattened_loop(n)
    t2 = %timeit -q -o nested4_loop(n)
    print(f'{n:4}  {n**4:16}  {t1.best * 1e3:15.3f} ms  {t2.best * 1e3:15.3f} ms')

   n            n ** 4           flattened             nested4
  10             10000            0.526 ms            0.653 ms
  20            160000            8.561 ms            8.459 ms
  30            810000           43.077 ms           39.417 ms
  40           2560000          136.709 ms          121.422 ms
  50           6250000          331.748 ms          291.132 ms
  60          12960000          698.014 ms          599.228 ms
  70          24010000         1280.681 ms         1081.062 ms
  80          40960000         2187.500 ms         1826.629 ms
  90          65610000         3500.463 ms         2942.909 ms
 100         100000000         5349.721 ms         4437.965 ms
 110         146410000         7835.733 ms         6474.588 ms

, что показывает, что разница существует, и она больше для больших n.

Выполняется ли у первого больше байт-кода? Нет. Мы можем ясно увидеть это через dis:

• flattened_loop()

import dis


dis.dis(flattened_loop)

  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (x)

  3           4 SETUP_LOOP              24 (to 30)
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_FAST                0 (n)
             10 CALL_FUNCTION            1
             12 GET_ITER
        >>   14 FOR_ITER                12 (to 28)
             16 STORE_FAST               2 (i)

  4          18 LOAD_FAST                1 (x)
             20 LOAD_CONST               2 (1)
             22 INPLACE_ADD
             24 STORE_FAST               1 (x)
             26 JUMP_ABSOLUTE           14
        >>   28 POP_BLOCK

  5     >>   30 LOAD_FAST                1 (x)
             32 RETURN_VALUE

• nested4_loop()

dis.dis(nested4_loop)

  9           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (x)

 10           4 SETUP_LOOP              78 (to 84)
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_FAST                0 (n)
             10 CALL_FUNCTION            1
             12 GET_ITER
        >>   14 FOR_ITER                66 (to 82)
             16 STORE_FAST               2 (i)

 11          18 SETUP_LOOP              60 (to 80)
             20 LOAD_GLOBAL              0 (range)
             22 LOAD_FAST                0 (n)
             24 CALL_FUNCTION            1
             26 GET_ITER
        >>   28 FOR_ITER                48 (to 78)
             30 STORE_FAST               3 (j)

 12          32 SETUP_LOOP              42 (to 76)
             34 LOAD_GLOBAL              0 (range)
             36 LOAD_FAST                0 (n)
             38 CALL_FUNCTION            1
             40 GET_ITER
        >>   42 FOR_ITER                30 (to 74)
             44 STORE_FAST               4 (k)

 13          46 SETUP_LOOP              24 (to 72)
             48 LOAD_GLOBAL              0 (range)
             50 LOAD_FAST                0 (n)
             52 CALL_FUNCTION            1
             54 GET_ITER
        >>   56 FOR_ITER                12 (to 70)
             58 STORE_FAST               5 (l)

 14          60 LOAD_FAST                1 (x)
             62 LOAD_CONST               2 (1)
             64 INPLACE_ADD
             66 STORE_FAST               1 (x)
             68 JUMP_ABSOLUTE           56
        >>   70 POP_BLOCK
        >>   72 JUMP_ABSOLUTE           42
        >>   74 POP_BLOCK
        >>   76 JUMP_ABSOLUTE           28
        >>   78 POP_BLOCK
        >>   80 JUMP_ABSOLUTE           14
        >>   82 POP_BLOCK

 15     >>   84 LOAD_FAST                1 (x)
             86 RETURN_VALUE

---

Не слишком ли большие числа в одинарных петлях? Нет.

import sys


print([(n, sys.getsizeof(n), n ** 4, sys.getsizeof(n ** 4)) for n in (10, 110)])
# [(10, 28, 10000, 28), (110, 28, 146410000, 28)]

Объясняет ли операция питания (не рассчитанная в моем коде, а в вашем) разницу во времени (рассчитанная только один раз, потому что вычисления констант кэшируются в Python)? Нет.

%timeit -r1 -n1 100 ** 4
# loop, best of 1: 708 ns per loop

---

Итак, что происходит?

На данный момент это всего лишь предположение, но, учитывая, что мы исключили по крайней мере некоторых из потенциальных кандидатов, Я считаю, что это связано с каким-то механизмом кеширования, который имеет место во вложенной версии. Такое кэширование, вероятно, используется для ускорения заведомо сравнительно медленного явного цикла. чтобы обеспечить его динамизм), мы действительно получаем:

import numba as nb


@nb.jit
def flattened_loop_nb(n):
    x = 0
    for i in range(n):
        x += 1
    return x


@nb.jit
def nested4_loop_nb(n):
    x = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                for l in range(n):
                    x += 1
    return x


flattened_loop_nb(100)  # trigger compilation
nested4_loop_nb(100)  # trigger compilation


print(f'{"n":>4s}  {"n ** 4":>16s}  {"flattened":>18s}  {"nested4":>18s}')
for n in range(10, 120, 10):
    m = n ** 4
    t1 = %timeit -q -o flattened_loop_nb(m)
    t2 = %timeit -q -o nested4_loop_nb(n)
    print(f'{n:4}  {n**4:16}  {t1.best * 1e6:15.3f} µs  {t2.best * 1e6:15.3f} µs')

   n            n ** 4           flattened             nested4
  10             10000            0.195 µs            0.199 µs
  20            160000            0.196 µs            0.201 µs
  30            810000            0.196 µs            0.200 µs
  40           2560000            0.195 µs            0.197 µs
  50           6250000            0.193 µs            0.199 µs
  60          12960000            0.195 µs            0.199 µs
  70          24010000            0.197 µs            0.200 µs
  80          40960000            0.195 µs            0.199 µs
  90          65610000            0.194 µs            0.197 µs
 100         100000000            0.195 µs            0.199 µs
 110         146410000            0.194 µs            0.199 µs

Немного более медленную (но в значительной степени не зависящую от n) скорость выполнения вложенных циклов (как и ожидалось).

Answer 2

Я запускал сценарий, который вы предоставили с python 2.x и 3.x несколько раз. Меня тоже удивило, что вложенный l oop постоянно завершается быстрее. Вот что думает, что вызывает эту проблему:

Когда вы запускаете свою python скрипт, операционная система, в которой вы работаете, назначит ему PID. Он может быть прерван системными вызовами, и его приоритет может быть изменилось со временем. Но система вряд ли заберет ресурсы у процесса, когда вы измените адреса или значения памяти. Когда вы запускаете плоский для l oop, он присваивает (также я пробовал их операторы присваивания, у них гораздо более близкие результаты!) Гораздо меньше переменных, чем вложенные l oop. Таким образом, мы можем сказать, что вложенный l oop использует ресурсы больше, чем плоский l oop, если они доступны . Если это не так (попробуйте их в ограниченных контейнерах docker), плоский l oop будет быстрее.

Answer 3

2,43 с, конечно, многовато по сравнению с 18,22 с. Удивительно, но вложенный l oop все время кажется немного быстрее на моей машине. Причина может быть в том, что это зависит от машины.

Другой возможной причиной может быть то, что в первом l oop переменной итерации должны быть присвоены очень большие числа, а во втором l oop они все просто в пределах 100. Данные два цикла выполняются на моей машине на 4,2 и 3,9 с; и увеличение нуля до 1e9, потребуется 43,3 и 39,2 секунды соответственно.