टाइम्स दो बिट शिफ्ट से तेज है?

Question

मैं sorted_containers का स्रोत देख रही है और this line देख कर हैरान था:

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

यहाँ load एक पूर्णांक है। एक जगह में बिट शिफ्ट का उपयोग क्यों करें, और दूसरे में गुणा करें? ऐसा लगता है कि बिट स्थानांतरण 2 से अभिन्न विभाजन से तेज हो सकता है, लेकिन गुणा को प्रतिस्थापित करके क्यों नहीं बदला जा सकता है?

1. (बार, विभाजन)
2. (पाली, पाली)
3. (बार, पाली)
4. (पाली, विभाजन)

और पाया: मैं निम्नलिखित मामलों बेंचमार्क कि # 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_swaped(): 
    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_swaped), 
    } 


def get_observations(): 
    return pd.DataFrame([observe(k) for k in range(100)]) 

प्रश्न:

अपने परीक्षण मान्य है? यदि हां, तो क्यों (गुणा, शिफ्ट) (शिफ्ट, शिफ्ट) से तेज है?

मैं उबंटू 14.04 पर पायथन 3.5 चलाता हूं।

संपादित

से ऊपर प्रश्न के मूल बयान है। दान गेटज़ अपने जवाब में एक उत्कृष्ट स्पष्टीकरण प्रदान करता है।

पूर्णता के लिए, यहां बड़े x के लिए नमूना चित्रण हैं जब गुणा ऑप्टिमाइज़ेशन लागू नहीं होते हैं।

Answer 1

इसका कारण यह है कम संख्या के गुणन एक तरीका है कि कम संख्या से बदलाव छोड़ दिया में CPython 3.5 में अनुकूलित है, हो रहा है नहीं कर रहे हैं। सकारात्मक बाएं बदलाव हमेशा गणना के हिस्से के रूप में परिणाम को संग्रहीत करने के लिए एक बड़ा पूर्णांक ऑब्जेक्ट बनाते हैं, जबकि आपके परीक्षण में उपयोग किए जाने वाले सॉर्ट के गुणा के लिए, एक विशेष अनुकूलन इससे बचाता है और सही आकार का पूर्णांक वस्तु बनाता है। इसे the source code of Python's integer implementation में देखा जा सकता है।

क्योंकि पाइथन में पूर्णांक मनमानी-परिशुद्धता हैं, इसलिए उन्हें पूर्णांक अंकों के बिट्स की संख्या पर सीमा के साथ पूर्णांक "अंक" के सरणी के रूप में संग्रहीत किया जाता है। तो सामान्य मामले में, पूर्णांक से जुड़े संचालन एकल संचालन नहीं होते हैं, बल्कि इसके बजाय कई "अंकों" के मामले को संभालने की आवश्यकता होती है। pyport.h में, यह बिट सीमा is defined as 64-बिट प्लेटफॉर्म पर 30 बिट्स या अन्यथा 15 बिट्स। (मैं स्पष्टीकरण को सरल रखने के लिए यहां से केवल 30 को कॉल करूंगा। लेकिन ध्यान दें कि यदि आप 32-बिट के लिए संकलित पायथन का उपयोग कर रहे थे, तो आपका बेंचमार्क का परिणाम इस बात पर निर्भर करेगा कि x 32,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 दुभाषिया द्वारा एक सीधा गुणा के रूप में किया जाता है गुणा, बजाय के रूप में पूर्णांक के साथ काम: integer multiplication implementation की शुरुआत इस प्रकार है सरणियों। (MEDIUM_VALUE() को एक सकारात्मक पूर्णांक ऑब्जेक्ट पर बुलाया जाता है, यह केवल 30-बिट अंक प्राप्त करता है।) यदि परिणाम 30-बिट अंकों में फिट बैठता है, तो PyLong_FromLongLong() इसे अपेक्षाकृत कम संख्या में संचालन में देखेगा, और एकल-अंक पूर्णांक ऑब्जेक्ट बनायेगा इसे स्टोर करने के लिए।

इसके विपरीत, बाएं बदलाव इस तरह से अनुकूलित नहीं किए जाते हैं, और प्रत्येक बाएं शिफ्ट को पूर्णांक के साथ एक सरणी के रूप में स्थानांतरित किया जाता है। विशेष रूप से, यदि आप long_lshift() के लिए स्रोत कोड देखते हैं, तो एक छोटी लेकिन सकारात्मक बाएं शिफ्ट के मामले में, 2-अंकीय पूर्णांक ऑब्जेक्ट हमेशा बनाया जाता है, अगर केवल इसकी लम्बाई 1 बाद में हो जाती है: (मेरी टिप्पणियां /*** ***/)

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

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

---

पूर्णांक विभाजन

क्योंकि है कि आपके (और मेरी) अपेक्षाओं के अनुरूप आप सही बदलाव की तुलना में पूर्णांक मंजिल डिवीजन के खराब प्रदर्शन के बारे में नहीं पूछा। लेकिन एक छोटे से सकारात्मक संख्या को एक छोटे से सकारात्मक संख्या से विभाजित करना छोटे गुणा के रूप में अनुकूलित नहीं है, या तो। प्रत्येक // फ़ंक्शन long_divrem() फ़ंक्शन का उपयोग करके शेष और दोनों को गणना करता है। यह शेष a multiplication, और is stored in a newly-allocated integer object के साथ एक छोटे से विभाजक के लिए गणना की जाती है, जो इस स्थिति में तुरंत त्याग दिया जाता है।