Я искал источник sorted_containers и был удивлен, увидев эту строку :
self._load, self._twice, self._half = load, load * 2, load >> 1
Вот load
целое число. Зачем использовать битовый сдвиг в одном месте, а умножение в другом? Представляется разумным, что сдвиг битов может быть быстрее, чем интегральное деление на 2, но почему бы не заменить умножение также на сдвиг? Я сравнил следующие случаи:
- (раз, разделить)
- (сдвиг, смена)
- (раз, смена)
- (сдвиг, деление)
и обнаружил, что # 3 постоянно быстрее, чем другие альтернативы:
# self._load, self._twice, self._half = load, load * 2, load >> 1
import random
import timeit
import pandas as pd
x = random.randint(10 ** 3, 10 ** 6)
def test_naive():
a, b, c = x, 2 * x, x // 2
def test_shift():
a, b, c = x, x << 1, x >> 1
def test_mixed():
a, b, c = x, x * 2, x >> 1
def test_mixed_swapped():
a, b, c = x, x << 1, x // 2
def observe(k):
print(k)
return {
'naive': timeit.timeit(test_naive),
'shift': timeit.timeit(test_shift),
'mixed': timeit.timeit(test_mixed),
'mixed_swapped': timeit.timeit(test_mixed_swapped),
}
def get_observations():
return pd.DataFrame([observe(k) for k in range(100)])
Вопрос:
Мой тест действителен? Если так, почему (умножение, сдвиг) быстрее, чем (сдвиг, сдвиг)?
Я запускаю Python 3.5 на Ubuntu 14.04.
редактировать
Выше оригинальное изложение вопроса. Дэн Гетц дает превосходное объяснение в своем ответе.
Для полноты приведем примеры иллюстраций большего размера, x
когда оптимизации умножения не применяются.
python
python-3.x
performance
bit-shift
integer-arithmetic
hilberts_drinking_problem
источник
источник
x
?x
оно не очень большое, потому что это просто вопрос того, как оно хранится в памяти, верно?Ответы:
Похоже, это связано с тем, что умножение малых чисел оптимизировано в CPython 3.5, а сдвиги влево на маленькие числа - нет. Положительные сдвиги влево всегда создают больший целочисленный объект для хранения результата, как часть вычисления, в то время как для умножений вида, который вы использовали в своем тесте, специальная оптимизация избегает этого и создает целочисленный объект правильного размера. Это можно увидеть в исходном коде целочисленной реализации Python .
Поскольку целые числа в Python имеют произвольную точность, они хранятся в виде массивов целых «цифр» с ограничением на число битов на целую цифру. Таким образом, в общем случае операции с целыми числами не являются отдельными операциями, а вместо этого должны обрабатывать случай нескольких «цифр». В pyport.h этот предел битов определяется как 30 бит на 64-битной платформе или 15 бит в противном случае. (Я просто буду называть это значение 30 для упрощения объяснения. Но учтите, что если бы вы использовали Python, скомпилированный для 32-битной системы, результат вашего теста будет зависеть от того, будет ли он
x
меньше 32 768 или нет.)Когда входы и выходы операции остаются в пределах этого 30-битного предела, операция может обрабатываться оптимизированным способом вместо общего способа. Начало реализации целочисленного умножения выглядит следующим образом:
Таким образом, при умножении двух целых чисел, каждое из которых умещается в 30-битную цифру, это делается как прямое умножение интерпретатором CPython вместо работы с целыми числами как массивами. (
MEDIUM_VALUE()
вызывается для положительного целочисленного объекта просто получает свою первую 30-разрядную цифру.) Если результат помещается в одну 30-разрядную цифру,PyLong_FromLongLong()
заметит это в относительно небольшом количестве операций и создаст однозначный целочисленный объект для хранения Это.Напротив, сдвиги влево таким образом не оптимизируются, и каждый сдвиг влево имеет дело с целым числом, смещаемым в виде массива. В частности, если вы посмотрите на исходный код для
long_lshift()
, в случае небольшого, но положительного сдвига влево, всегда создается двузначный целочисленный объект, если только его длина будет усечена до 1 позже: (мои комментарии в/*** ***/
)Целочисленное деление
Вы не спрашивали о худших показателях целочисленного деления по полу по сравнению с правильными сменами, потому что это соответствовало вашим (и моим) ожиданиям. Но деление небольшого положительного числа на другое небольшое положительное число также не так оптимизировано, как небольшие умножения. Каждый
//
вычисляет как частное, так и остаток, используя функциюlong_divrem()
. Этот остаток вычисляется для небольшого делителя с умножением и сохраняется во вновь выделенном целочисленном объекте , который в этой ситуации немедленно отбрасывается.источник
x
пределами оптимизированного диапазона.