Почему Python3 работает быстрее, если он отрицает XOR? - PullRequest
Новая
       4

Почему Python3 работает быстрее, если он отрицает XOR?

6 голосов
/ 04 марта 2020

Я думал, что отрицание слова или XOR слова с 1 оба должны занимать 1 тактовый такт процессора, но если используется Python3, следующий код для подсчета четности слова: 

def parity(x: int) -> int:
    p = 0
    while x:
        p = ~p
        x = x & (x-1)
    return p & 1

при выполнении 10000 тестовых случаев сообщит 4μs среднее время выполнения последовательно, но если оно равно: 

def parity(x: int) -> int:
    p = 0
    while x:
        p = p ^ 1
        x = x & (x-1)
    return p

, то оно постоянно 5μs. На самом деле в конце операции на одну операцию меньше & 1.

Даже 

def parity(x: int) -> int:
    p = 0
    while x:
        p += 1
        x = x & (x-1)
    return p % 2

постоянно работает для 4μs. Чтобы проверить приращение против сложения, я изменил p += 1 на p += 7, и он снова последовательно 4μs. В чем причина отрицания, увеличения или добавления быстрее, чем XOR при использовании Python3? (это на Ма c, если это имеет какое-либо значение).

1 Ответ

4 голосов
/ 04 марта 2020

Как выясняется, в Python не все операторы созданы одинаково.

Вы упоминаете "тактовый цикл" в своем вопросе. Это правда, что типичный ЦП может выполнять многие из этих задач за один цикл, однако выполнение кода Python (в CPython) определяется скомпилированным байт-кодом. Это список операций (кодов операций), которые отображаются на код C во время выполнения CPython.

Время выполнения этих частей кода C, очевидно, может отличаться. Фактически, вы обнаружите, что ни одна из них не ассоциируется с операцией «1 цикла», а скорее с несколькими вызовами функций и операторами ветвления.

Если вы разберете две заданные вами функции, dis.dis(parity), вы в соответствующем разделе вы увидите, как отличаются их коды операций.

От первой функции (отрицание) 

10 LOAD_FAST                1 (p)
12 UNARY_INVERT
14 STORE_FAST               1 (p)

От второй функции (XOR): 

10 LOAD_FAST                1 (p)
12 LOAD_CONST               2 (1)
14 BINARY_XOR
16 STORE_FAST               1 (p)

В частности, UNARY_INVERT изменяется на BINARY_XOR. Проверьте мастер switch (opcode) { ... } в Python / ceval. c, чтобы увидеть, как эти операционные коды и соответствующий им код отличаются.

Вот небольшая тестовая программа для сравнения времени некоторых различных операторов в Python. 

import timeit

print('binary operators')

ops = ['+', '-', '^', '&', '|']
for op in ops:
    t = timeit.timeit(f'a = a {op} b', 'a = 1; b = 2')
    print(op, t)

print('unary operators')

ops = ['-', '~', 'not']
for op in ops:
    t = timeit.timeit(f'a = {op} a', 'a = 1')
    print(op, t)

Вот мои результаты в CPython 3.7.2 64 бит (Windows) 

binary operators
+ 0.038782999999999956
- 0.03799190000000002
^ 0.05287609999999998
& 0.03716779999999997
| 0.0518267
unary operators
- 0.020763399999999987
~ 0.020213900000000007
not 0.01701140000000001

Из этих результаты, кажется, ^ или BINARY_XOR на самом деле самый медленный оператор (из протестированных)

...