Python 3.x 정수의 경우 비트 시프트보다 2배 더 빠릅니까?

Python 3.x 정수의 경우 비트 시프트보다 2배 더 빠릅니까?

sorted_containers의 소스를 보고 있었는데 다음 줄을 보고 놀랐습니다.

self._load, self._twice, self._half = load, load * 2, load >> 1

여기서load는 정수입니다.비트 시프트를 한 곳에서 사용하고 곱셈을 다른 곳에서 사용하는 이유는 무엇입니까?비트 이동이 2만큼 적분 나눗셈보다 빠를 수도 있지만, 곱셈도 이동으로 대체하는 것은 어떨까요?다음과 같은 사례를 벤치마킹했습니다.

1. (시간, 나누기)
2. (시프트, 시프트)
3. (times, shift)
4. (shift, divide)

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

질문:

제 시험이 유효한가요?그렇다면 왜 (배수, 시프트)가 (시프트, 시프트)보다 빠릅니까?

Ubuntu 14.04에서 Python 3.5를 실행합니다.

편집

위는 질문의 원래 문장입니다.댄 게츠는 그의 대답에서 훌륭한 설명을 제공합니다.

완전성을 위해, 여기 더 큰 크기를 위한 샘플 그림이 있습니다.x곱셈 최적화가 적용되지 않는 경우.

이것은 작은 숫자에 의한 왼쪽 이동이 그렇지 않은 방식으로 작은 숫자의 곱셈이 CPython 3.5에서 최적화되기 때문으로 보입니다.양의 왼쪽 이동은 항상 계산의 일부로 결과를 저장하기 위해 더 큰 정수 개체를 생성하는 반면, 검정에 사용한 정렬의 곱셈의 경우 특수 최적화를 통해 이를 방지하고 올바른 크기의 정수 개체를 생성합니다.이는 Python의 정수 구현의 소스 코드에서 확인할 수 있습니다.

파이썬의 정수는 임의의 정밀도이기 때문에 정수 자리당 비트 수에 제한이 있는 정수 "자리" 배열로 저장됩니다.따라서 일반적인 경우 정수를 포함하는 연산은 단일 연산이 아니라 여러 "자리수"의 경우를 처리해야 합니다.pyport.h에서 이 비트 제한은 64비트 플랫폼에서 30비트로 정의되며, 그렇지 않으면 15비트로 정의됩니다.(설명을 간단하게 하기 위해 지금부터 30번만 전화하겠습니다.그러나 32비트용으로 컴파일된 Python을 사용하고 있다면 벤치마크의 결과는 다음과 같은지 여부에 따라 달라집니다.x32,768 미만 또는 그렇지 않음).

작업의 입력 및 출력이 이 30비트 제한 내에 있으면 일반적인 방식 대신 최적화된 방식으로 작업을 처리할 수 있습니다.정수 곱셈 구현의 시작은 다음과 같습니다.

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit digits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

그래서 각각 30비트 숫자에 맞는 두 개의 정수를 곱할 때, 이것은 정수를 배열로 사용하는 대신에 CPython 인터프리터에 의한 직접 곱셈으로 이루어집니다.(MEDIUM_VALUE()양의 정수 객체에서 호출되면 첫 번째 30비트 숫자를 얻을 수 있습니다.결과가 단일 30비트 숫자에 해당하는 경우 에서는 비교적 적은 수의 작업에서 이를 인식하고 이를 저장할 한 자리 정수 개체를 만듭니다.

반대로, 왼쪽 이동은 이러한 방식으로 최적화되지 않으며, 모든 왼쪽 이동은 배열로 이동되는 정수를 처리합니다.특히, 에 대한 소스 코드를 살펴보면, 작지만 양의 왼쪽 이동의 경우, 길이가 나중에 1로 잘리기만 하면 항상 2자리 정수 개체가 생성됩니다. (의 내 설명)

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
    /*** ... ***/

    wordshift = shiftby / PyLong_SHIFT;   /*** zero for small w ***/
    remshift  = shiftby - wordshift * PyLong_SHIFT;   /*** w for small w ***/

    oldsize = Py_ABS(Py_SIZE(a));   /*** 1 for small v > 0 ***/
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;   /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
    z = _PyLong_New(newsize);

    /*** ... ***/
}

---

정수 나눗셈

당신은 우측 교대조에 비해 낮은 정수 바닥 분할 성능에 대해 묻지 않았습니다. 왜냐하면 그것이 당신과 저의 기대에 부합하기 때문입니다.그러나 작은 양수를 다른 작은 양수로 나누는 것도 작은 곱셈만큼 최적화되지 않습니다. 든//함수를 사용하여 몫과 나머지를 모두 계산합니다.이 나머지는 곱셈이 있는 작은 나눗셈에 대해 계산되고 새로 할당된 정수 개체에 저장되며, 이 경우 즉시 삭제됩니다.

아니면 적어도, 이 질문이 처음에 나왔을 때는 그랬습니다.CPython 3.6에서 small int를 위한 빠른 경로//추가되었습니다.//은 금은을 능가합니다.>>작은 의미에서도.

언급URL : https://stackoverflow.com/questions/37053379/times-two-faster-than-bit-shift-for-python-3-x-integers