python - कुछ फ्लोट<पूर्णांक तुलना दूसरों की तुलना में चार गुना धीमी क्यों हैं?




performance floating-point (2)

फ्लोट ऑब्जेक्ट्स के लिए पायथन स्रोत कोड में एक टिप्पणी स्वीकार करती है कि:

तुलना बहुत बुरा सपना है

फ्लोट की तुलना पूर्णांक से करते समय यह विशेष रूप से सच है, क्योंकि, फ्लोट के विपरीत, पायथन में पूर्णांक मनमाने ढंग से बड़े हो सकते हैं और हमेशा सटीक होते हैं। पूर्णांक को फ़्लोट में डालने की कोशिश करने से सटीकता खो सकती है और तुलना गलत हो सकती है। फ्लोट को एक पूर्णांक में डालने की कोशिश करना या तो काम करने वाला नहीं है क्योंकि कोई भी आंशिक हिस्सा खो जाएगा।

इस समस्या को हल करने के लिए, पायथन चेक की एक श्रृंखला करता है, यदि चेक में से कोई एक सफल होता है, तो परिणाम लौटाता है। यह दो मानों के संकेतों की तुलना करता है, फिर क्या पूर्णांक "बहुत बड़ा" है जो फ्लोट के रूप में है, फिर फ्लोट के घातांक की तुलना पूर्णांक से करता है। यदि ये सभी चेक विफल हो जाते हैं, तो परिणाम प्राप्त करने के लिए तुलना करने के लिए दो नए पायथन ऑब्जेक्ट्स का निर्माण करना आवश्यक है।

जब एक फ्लोट v तुलना किसी पूर्णांक / लंबे w , तो सबसे खराब स्थिति यह होती है:

  • v और w का एक ही चिन्ह है (सकारात्मक या नकारात्मक दोनों),
  • पूर्णांक w पास कुछ पर्याप्त बिट्स हैं जो इसे size_t प्रकार (आमतौर पर 32 या 64 बिट्स) में आयोजित किया जा सकता है।
  • पूर्णांक w में कम से कम 49 बिट्स हैं,
  • फ्लोट v का प्रतिपादक w में बिट्स की संख्या के समान है।

और यह वही है जो हमारे पास प्रश्न में मूल्यों के लिए है:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

हम देखते हैं कि पूर्णांक में फ्लोट और बिट्स की संख्या दोनों का 49 है। दोनों संख्याएं सकारात्मक हैं और इसलिए उपरोक्त चार मानदंड पूरे किए गए हैं।

मूल्यों में से एक को बड़ा (या छोटा) चुनना पूर्णांक की बिट्स की संख्या, या घातांक के मूल्य को बदल सकता है, और इसलिए पायथन महंगी अंतिम जांच किए बिना तुलना के परिणाम को निर्धारित करने में सक्षम है।

यह भाषा के CPython कार्यान्वयन के लिए विशिष्ट है।

अधिक विस्तार से तुलना

float_richcompare फ़ंक्शन दो मानों v और w बीच तुलना को संभालता है।

नीचे फ़ंक्शन द्वारा किए गए चेक का चरण-दर-चरण वर्णन है। पायथन स्रोत में टिप्पणियां वास्तव में बहुत उपयोगी होती हैं जब यह समझने की कोशिश की जाती है कि फ़ंक्शन क्या करता है, इसलिए मैंने उन्हें जहां प्रासंगिक में छोड़ दिया है। मैंने उत्तर के चरणों में एक सूची में इन चेकों को संक्षेप में प्रस्तुत किया है।

मुख्य विचार पायथन ऑब्जेक्ट्स को v और w को दो उपयुक्त सी डबल्स, i और j मैप करना है, जो तब सही परिणाम देने के लिए आसानी से तुलना की जा सकती है। पाइथन 2 और पाइथन 3 दोनों ही ऐसा करने के लिए समान विचारों का उपयोग करते हैं (पूर्व सिर्फ अलग-अलग और long प्रकारों को संभालता है)।

सबसे पहली बात यह है कि v निश्चित रूप से पायथन फ्लोट है और इसे सी डबल i मैप करता है। अगला फ़ंक्शन यह देखता है कि क्या w भी फ्लोट है और इसे सी डबल j पर मैप करता है। यह फ़ंक्शन के लिए सबसे अच्छा मामला है क्योंकि अन्य सभी चेक को छोड़ दिया जा सकता है। फ़ंक्शन यह देखने के लिए भी जांचता है कि क्या v inf या nan :

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;
    assert(PyFloat_Check(v));       
    i = PyFloat_AS_DOUBLE(v);       

    if (PyFloat_Check(w))           
        j = PyFloat_AS_DOUBLE(w);   

    else if (!Py_IS_FINITE(i)) {
        if (PyLong_Check(w))
            j = 0.0;
        else
            goto Unimplemented;
    }

अब हम जानते हैं कि यदि इन चेकों को w विफल कर दिया, तो यह पायथन फ्लोट नहीं है। अब फ़ंक्शन जाँचता है कि क्या यह पायथन पूर्णांक है। यदि यह मामला है, तो सबसे आसान परीक्षण v का चिह्न और w का चिन्ह निकालना है (वापसी 0 यदि शून्य, -1 यदि ऋणात्मक, तो 1 सकारात्मक)। यदि संकेत भिन्न हैं, तो तुलना के परिणाम को वापस करने के लिए आवश्यक सभी जानकारी है:

    else if (PyLong_Check(w)) {
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        if (vsign != wsign) {
            /* Magnitudes are irrelevant -- the signs alone
             * determine the outcome.
             */
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
    }   

यदि यह जाँच विफल हो गई, तो v और w का चिन्ह समान है।

अगला चेक पूर्णांक w में बिट्स की संख्या को गिनता है। यदि इसमें बहुत अधिक बिट्स हैं तो इसे संभवतः फ्लोट के रूप में नहीं रखा जा सकता है और इसलिए फ्लोट v तुलना में परिमाण में बड़ा होना चाहिए:

    nbits = _PyLong_NumBits(w);
    if (nbits == (size_t)-1 && PyErr_Occurred()) {
        /* This long is so large that size_t isn't big enough
         * to hold the # of bits.  Replace with little doubles
         * that give the same outcome -- w is so large that
         * its magnitude must exceed the magnitude of any
         * finite float.
         */
        PyErr_Clear();
        i = (double)vsign;
        assert(wsign != 0);
        j = wsign * 2.0;
        goto Compare;
    }

दूसरी ओर, यदि पूर्णांक w में 48 या उससे कम बिट्स हैं, तो यह सुरक्षित रूप से C डबल j और तुलना में बदल सकता है:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

इस बिंदु से, हम जानते हैं कि w में 49 या अधिक बिट्स हैं। w को एक सकारात्मक पूर्णांक के रूप में व्यवहार करना सुविधाजनक होगा, इसलिए संकेत और तुलना ऑपरेटर को आवश्यक रूप से बदलें:

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

अब फ़ंक्शन फ्लोट के घातांक को देखता है। याद रखें कि एक फ्लोट लिखा जा सकता है (संकेत को अनदेखा करते हुए) महत्व के रूप में * 2 घातांक और यह कि महत्व 0.5 / 1 के बीच एक संख्या का प्रतिनिधित्व करता है:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

यह दो चीजों की जाँच करता है। यदि प्रतिपादक 0 से कम है तो फ्लोट 1 से छोटा है (और किसी भी पूर्णांक की तुलना में परिमाण में छोटा है)। या, यदि घातांक w में बिट की संख्या से कम है तो हमारे पास वह v < |w| चूंकि महत्व * 2 घातांक 2 nbit से कम है।

इन दो जांचों को विफल करते हुए, फ़ंक्शन यह देखता है कि घातांक बिट में w की संख्या से अधिक है या नहीं। इससे पता चलता है कि महत्व * 2 प्रतिपादक 2 nbit से अधिक है और इसलिए v > |w| :

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

यदि यह जांच सफल नहीं हुई तो हम जानते हैं कि फ्लोट v का घातांक पूर्णांक w में बिट्स की संख्या के समान है।

एकमात्र तरीका यह है कि दो मूल्यों की तुलना अब v और w से दो नए पायथन पूर्णांक बनाने के लिए की जा सकती है। विचार यह है कि v के भिन्नात्मक भाग को छोड़ दें, पूर्णांक भाग को दोगुना करें, और फिर एक जोड़ें। w को भी दोगुना किया गया है और इन दो नए पायथन ऑब्जेक्ट्स की तुलना सही रिटर्न वैल्यू देने के लिए की जा सकती है। छोटे मूल्यों के साथ एक उदाहरण का उपयोग करते हुए, 4.65 < 4 तुलना (2*4)+1 == 9 < 8 == (2*4) (झूठे लौटे (2*4)+1 == 9 < 8 == (2*4) द्वारा निर्धारित किया जाएगा।

    {
        double fracpart;
        double intpart;
        PyObject *result = NULL;
        PyObject *one = NULL;
        PyObject *vv = NULL;
        PyObject *ww = w;

        // snip

        fracpart = modf(i, &intpart); // split i (the double that v mapped to)
        vv = PyLong_FromDouble(intpart);

        // snip

        if (fracpart != 0.0) {
            /* Shift left, and or a 1 bit into vv
             * to represent the lost fraction.
             */
            PyObject *temp;

            one = PyLong_FromLong(1);

            temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
            ww = temp;

            temp = PyNumber_Lshift(vv, one);
            vv = temp;

            temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
            vv = temp;
        }
        // snip
    }
}

संक्षिप्तता के लिए मैंने अतिरिक्त त्रुटि-जाँच और कचरा-ट्रैकिंग पायथन को छोड़ दिया है, जब यह इन नई वस्तुओं को बनाता है। कहने की जरूरत नहीं है, यह अतिरिक्त उपरि जोड़ता है और बताता है कि प्रश्न में हाइलाइट किए गए मान दूसरों की तुलना में काफी धीमा क्यों हैं।

यहां उन चेकों का सारांश दिया गया है जो तुलनात्मक फ़ंक्शन द्वारा किए जाते हैं।

आज्ञा देना एक नाव हो और यह एक सी डबल के रूप में डाली। अब, अगर w भी एक नाव है:

  • जाँचें कि क्या w nan या inf । यदि हां, तो w के प्रकार के आधार पर इस विशेष मामले को अलग से संभालें।

  • यदि नहीं, तो सी के रूप में उनके अभ्यावेदन द्वारा सीधे v और w तुलना करें।

यदि w एक पूर्णांक है:

  • v और w के चिह्न निकालें। यदि वे भिन्न हैं तो हम जानते हैं कि v और w भिन्न हैं और जिनका मूल्य अधिक है।

  • ( संकेत समान हैं। ) जांचें कि क्या w में बहुत सारे बिट्स एक फ्लोट ( size_t से अधिक) हैं। यदि हां, तो v से अधिक परिमाण है।

  • जांचें कि w में 48 या उससे कम बिट्स हैं। यदि हां, तो इसकी शुद्धता खोए बिना और v साथ तुलना में इसे सी डबल में सुरक्षित रूप से डाला जा सकता है।

  • ( w में 48 से अधिक बिट्स हैं। हम अब w को एक सकारात्मक पूर्णांक के रूप में मानेंगे, जिसकी तुलना में ऑप्स को उपयुक्त रूप से बदल दिया जाएगा।

  • फ्लोट v के प्रतिपादक पर विचार करें। यदि घातांक नकारात्मक है, तो v 1 से कम है और इसलिए किसी भी सकारात्मक पूर्णांक से कम है। और, यदि घातांक w में बिट्स की संख्या से कम है तो यह w से कम होना चाहिए।

  • यदि v का प्रतिपादक w में बिट की संख्या से अधिक है तो v , w से अधिक है।

  • ( प्रतिपादक w में बिट्स की संख्या के समान है। )

  • अंतिम जाँच। अपने पूर्णांक और भिन्नात्मक भागों में v को विभाजित करें। पूर्णांक भाग को दोगुना करें और आंशिक भाग की भरपाई के लिए 1 जोड़ें। अब पूर्णांक w डबल करें। परिणाम प्राप्त करने के बजाय इन दो नए पूर्णांकों की तुलना करें।

जब फ्लोटर्स की तुलना पूर्णांक से करते हैं, तो कुछ जोड़े मानों का मूल्यांकन एक समान परिमाण के अन्य मूल्यों की तुलना में अधिक समय तक होता है।

उदाहरण के लिए:

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

लेकिन अगर फ्लोट या पूर्णांक एक निश्चित राशि से छोटा या बड़ा किया जाता है, तो तुलना बहुत अधिक तेजी से चलती है:

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

तुलना ऑपरेटर को बदलना (जैसे == या > का उपयोग करके) किसी भी ध्यान देने योग्य तरीके से समय को प्रभावित नहीं करता है।

यह पूरी तरह से परिमाण से संबंधित नहीं है क्योंकि बड़े या छोटे मूल्यों को चुनने से परिणाम तेजी से हो सकते हैं, इसलिए मुझे संदेह है कि यह कुछ दुर्भाग्यपूर्ण तरीके से बिट्स अप लाइन है।

स्पष्ट रूप से, इन मूल्यों की तुलना सबसे अधिक उपयोग के मामलों के लिए पर्याप्त तेजी से अधिक है। मैं बस इस बात के लिए उत्सुक हूं कि क्यों पायथन दूसरों के साथ मूल्यों के कुछ जोड़े के साथ अधिक संघर्ष करता है।


मनमाने ढंग से सटीक झांकियों और पूर्णांक के साथ gmpy2 का उपयोग करना अधिक समान तुलना प्रदर्शन प्राप्त करना संभव है:

~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec  7 2015, 11:16:01) 
Type "copyright", "credits" or "license" for more information.

IPython 4.1.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import gmpy2

In [2]: from gmpy2 import mpfr

In [3]: from gmpy2 import mpz

In [4]: gmpy2.get_context().precision=200

In [5]: i1=562949953421000

In [6]: i2=562949953422000

In [7]: f=562949953420000.7

In [8]: i11=mpz('562949953421000')

In [9]: i12=mpz('562949953422000')

In [10]: f1=mpfr('562949953420000.7')

In [11]: f<i1
Out[11]: True

In [12]: f<i2
Out[12]: True

In [13]: f1<i11
Out[13]: True

In [14]: f1<i12
Out[14]: True

In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop

In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop

In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop

In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop

In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop

In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop

In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop




python-internals