पाइथन में ctypes के साथ मैटिक्स गुणा तेजी से numpy के साथ क्यों है?

Question

मैं सबसे तेज़ तरीका आव्यूह गुणन करने के लिए पता लगाने की कोशिश और 3 अलग अलग तरीकों की कोशिश की गई थी:

• शुद्ध अजगर कार्यान्वयन: यहाँ कोई आश्चर्य।
• Numpy कार्यान्वयन numpy.dot(a, b)
• अजगर में ctypes मॉड्यूल का उपयोग कर सेल्सियस के साथ Interfacing का उपयोग कर।

  #include <stdio.h> 
  #include <stdlib.h> 
  
  void matmult(float* a, float* b, float* c, int n) { 
      int i = 0; 
      int j = 0; 
      int k = 0; 
  
      /*float* c = malloc(nay * sizeof(float));*/ 
  
      for (i = 0; i < n; i++) { 
       for (j = 0; j < n; j++) { 
        int sub = 0; 
        for (k = 0; k < n; k++) { 
         sub = sub + a[i * n + k] * b[k * n + j]; 
        } 
        c[i * n + j] = sub; 
       } 
      } 
      return ; 
  } 
  

  और अजगर कोड है कि यह कॉल:

इस सी कोड है कि एक शेयर की गई लाइब्रेरी में तब्दील हो जाता है

def C_mat_mult(a, b): 
    libmatmult = ctypes.CDLL("./matmult.so") 

    dima = len(a) * len(a) 
    dimb = len(b) * len(b) 

    array_a = ctypes.c_float * dima 
    array_b = ctypes.c_float * dimb 
    array_c = ctypes.c_float * dima 

    suma = array_a() 
    sumb = array_b() 
    sumc = array_c() 

    inda = 0 
    for i in range(0, len(a)): 
     for j in range(0, len(a[i])): 
      suma[inda] = a[i][j] 
      inda = inda + 1 
     indb = 0 
    for i in range(0, len(b)): 
     for j in range(0, len(b[i])): 
      sumb[indb] = b[i][j] 
      indb = indb + 1 

    libmatmult.matmult(ctypes.byref(suma), ctypes.byref(sumb), ctypes.byref(sumc), 2); 

    res = numpy.zeros([len(a), len(a)]) 
    indc = 0 
    for i in range(0, len(sumc)): 
     res[indc][i % len(a)] = sumc[i] 
     if i % len(a) == len(a) - 1: 
      indc = indc + 1 

    return res 

मैं शर्त है कि सी का उपयोग कर संस्करण के लिए होता है तेजी से होता ... और मैं हार गया होता! नीचे मेरी बेंचमार्क जो कि मैं या तो इसे गलत तरीके से किया था दिखाने के लिए लगता है, या कि numpy मूर्खता से तेज है:

मुझे समझ में क्यों numpy संस्करण ctypes संस्करण की तुलना में तेजी से होता है करना चाहते हैं, मैं मैं शुद्ध पायथन कार्यान्वयन के बारे में भी बात नहीं कर रहा हूं क्योंकि यह स्पष्ट है।

Answer 1

मैं नम्पी से बहुत परिचित नहीं हूं, लेकिन स्रोत गीथूब पर है। डॉट उत्पादों का हिस्सा https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/arraytypes.c.src में लागू किया गया है, जो मुझे लगता है कि प्रत्येक डेटाटाइप के लिए विशिष्ट सी कार्यान्वयन में अनुवाद किया गया है। उदाहरण के लिए:

/**begin repeat 
* 
* #name = BYTE, UBYTE, SHORT, USHORT, INT, UINT, 
* LONG, ULONG, LONGLONG, ULONGLONG, 
* FLOAT, DOUBLE, LONGDOUBLE, 
* DATETIME, TIMEDELTA# 
* #type = npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int, npy_uint, 
* npy_long, npy_ulong, npy_longlong, npy_ulonglong, 
* npy_float, npy_double, npy_longdouble, 
* npy_datetime, npy_timedelta# 
* #out = npy_long, npy_ulong, npy_long, npy_ulong, npy_long, npy_ulong, 
* npy_long, npy_ulong, npy_longlong, npy_ulonglong, 
* npy_float, npy_double, npy_longdouble, 
* npy_datetime, npy_timedelta# 
*/ 
static void 
@name@_dot(char *ip1, npy_intp is1, char *ip2, npy_intp is2, char *op, npy_intp n, 
      void *NPY_UNUSED(ignore)) 
{ 
    @out@ tmp = (@out@)0; 
    npy_intp i; 

    for (i = 0; i < n; i++, ip1 += is1, ip2 += is2) { 
     tmp += (@out@)(*((@type@ *)ip1)) * 
       (@out@)(*((@type@ *)ip2)); 
    } 
    *((@type@ *)op) = (@type@) tmp; 
} 
/**end repeat**/ 

यह वैक्टर पर एक आयामी डॉट उत्पाद, अर्थात गणना करने के लिए प्रकट होता है। गीथब ब्राउज़िंग के कुछ ही मिनटों में मैं matrices के स्रोत को खोजने में असमर्थ था, लेकिन यह संभव है कि यह परिणाम मैट्रिक्स में प्रत्येक तत्व के लिए FLOAT_dot पर एक कॉल का उपयोग करता है। इसका मतलब है कि इस फ़ंक्शन में लूप आपके आंतरिक-अधिकांश लूप से मेल खाता है।

उनके बीच एक अंतर यह है कि "घुमावदार" - इनपुट में लगातार तत्वों के बीच का अंतर - फ़ंक्शन को कॉल करने से पहले एक बार स्पष्ट रूप से गणना की जाती है। आपके मामले में कोई रास्ता नहीं है, और प्रत्येक इनपुट की ऑफ़सेट हर बार गणना की जाती है, उदा। a[i * n + k]। मैं उम्मीद करता था कि एक अच्छा कंपाइलर उस नम्पी स्ट्रैड के समान कुछ अनुकूलित करने की उम्मीद करता, लेकिन शायद यह साबित नहीं कर सकता कि चरण स्थिर है (या इसे अनुकूलित नहीं किया जा रहा है)।

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

नम्पी में विभिन्न बुनियादी कार्यान्वयन से "डॉट" सहित कुछ संचालन के कार्यान्वयन को चुनने के लिए कोड भी शामिल है। उदाहरण के लिए यह BLAS लाइब्रेरी का उपयोग कर सकता है। ऊपर चर्चा से ऐसा लगता है जैसे सीबीएलएएस का उपयोग किया जाता है। इसका अनुवाद फोरट्रान से सी में किया गया था। मुझे लगता है कि आपके परीक्षण में प्रयुक्त कार्यान्वयन यहां मिलेगा: http://www.netlib.org/clapack/cblas/sdot.c।

ध्यान दें कि यह प्रोग्राम किसी मशीन द्वारा पढ़ने के लिए मशीन द्वारा लिखा गया था। लेकिन आप नीचे देख सकते हैं कि यह एक समय में 5 तत्वों पर कार्रवाई करने के लिए एक unrolled पाश उपयोग कर रहा है:

for (i = mp1; i <= *n; i += 5) { 
stemp = stemp + SX(i) * SY(i) + SX(i + 1) * SY(i + 1) + SX(i + 2) * 
    SY(i + 2) + SX(i + 3) * SY(i + 3) + SX(i + 4) * SY(i + 4); 
} 

यह unrolling कारक कई रूपरेखा के बाद उठाया गया है की संभावना है। लेकिन इसका एक सैद्धांतिक लाभ यह है कि प्रत्येक शाखा बिंदु के बीच अधिक अंकगणितीय परिचालन किए जाते हैं, और संकलक और सीपीयू के पास अधिक से अधिक निर्देश पाइपलाइनिंग प्राप्त करने के लिए उन्हें बेहतर तरीके से शेड्यूल करने के तरीके के बारे में अधिक विकल्प होता है।

Answer 2

जो लोग न्यूमपी लिखते हैं वे स्पष्ट रूप से जानते हैं कि वे क्या कर रहे हैं।

मैट्रिक्स गुणा को अनुकूलित करने के कई तरीके हैं। उदाहरण के लिए, मैट्रिक्स को पार करने का ऑर्डर मेमोरी एक्सेस पैटर्न को प्रभावित करता है, जो प्रदर्शन को प्रभावित करता है।
एसएसई का अच्छा उपयोग अनुकूलित करने का एक और तरीका है, जो संभवतः NumPy नियोजित करता है।
ऐसे कई तरीके हो सकते हैं, जिनमें न्यूम्पी के डेवलपर्स जानते हैं और मैं नहीं करता हूं।

बीटीडब्ल्यू, क्या आपने अपने सी कोड को optiomization के साथ संकलित किया?

आप सी के लिए निम्नलिखित अनुकूलन आज़मा सकते हैं। यह समानांतर में काम करता है, और मुझे लगता है कि न्यूमपी एक ही पंक्ति के साथ कुछ करता है।
नोट: केवल आकार के लिए भी काम करता है। अतिरिक्त काम के साथ, आप इस सीमा को हटा सकते हैं और प्रदर्शन में सुधार कर सकते हैं। , संकलक बता सकता है कि मैट्रिक्स ही स्मृति का हिस्सा नहीं है गुणा किया जा रहा -

for (i = 0; i < n; i++) { 
     for (j = 0; j < n; j+=2) { 
      int sub1 = 0, sub2 = 0; 
      for (k = 0; k < n; k++) { 
       sub1 = sub1 + a[i * n + k] * b[k * n + j]; 
       sub1 = sub1 + a[i * n + k] * b[k * n + j + 1]; 
      } 
      c[i * n + j]  = sub; 
      c[i * n + j + 1] = sub; 
     } 
    } 
} 

Answer 3

सबसे आम कारण संख्यात्मक कोड में फोरट्रान की गति लाभ के लिए दिया, afaik, उस भाषा को आसान aliasing पता लगाने के लिए बनाता है जो कैशिंग को बेहतर बनाने में मदद कर सकता है (यह सुनिश्चित करने की आवश्यकता नहीं है कि परिणाम तुरंत "साझा" मेमोरी में लिखे जाएंगे)। यही कारण है कि सी 99 ने restrict पेश किया।

हालांकि, इस मामले में, मुझे आश्चर्य है कि अगर numpy कोड कुछ special instructions का उपयोग करने के लिए प्रबंधन कर रहा है तो सी कोड नहीं है (क्योंकि अंतर विशेष रूप से बड़ा लगता है)।

Answer 4

न्यूम्पी भी अत्यधिक अनुकूलित कोड है। Beautiful Code पुस्तक में इसके कुछ हिस्सों के बारे में एक निबंध है।

सीटीपी को सी से पायथन तक गतिशील अनुवाद के माध्यम से जाना है और पीछे कुछ ओवरहेड जोड़ना है। नम्पी में अधिकांश मैट्रिक्स ऑपरेशंस पूरी तरह से आंतरिक होते हैं।

Answer 5

एक निश्चित कार्यक्षमता को लागू करने के लिए उपयोग की जाने वाली भाषा स्वयं प्रदर्शन का एक खराब उपाय है। अक्सर, एक अधिक उपयुक्त एल्गोरिदम का उपयोग निर्णायक कारक है।

अपने मामले में, आप स्कूल में पढ़ाए गए मैट्रिक्स गुणा के लिए बेवकूफ दृष्टिकोण का उपयोग कर रहे हैं, जो ओ (एन^3) में है। हालांकि, आप कुछ प्रकार के मैट्रिक्स के लिए बहुत बेहतर कर सकते हैं, उदा। वर्ग matrices, अतिरिक्त matrices और इतने पर।

फास्ट मैट्रिक्स गुणा पर एक अच्छा प्रारंभिक बिंदु के लिए Coppersmith–Winograd algorithm (ओ (एन^2.3737) में वर्ग मैट्रिक्स गुणा) पर एक नज़र डालें। अनुभाग "संदर्भ" भी देखें, जो कुछ पॉइंटर्स को तेज़ तरीकों से सूचीबद्ध करता है।

आश्चर्यजनक निष्पादन लाभ का एक और अधिक मिट्टी की उदाहरण के लिए, एक तेजी से strlen() लिखने और glibc कार्यान्वयन के लिए यह तुलना करने के लिए प्रयास करें। यदि आप इसे हरा नहीं पाते हैं, तो glibc के strlen() स्रोत पढ़ें, इसकी काफी अच्छी टिप्पणियां हैं।

Answer 6

न्यूमपी मैट्रिक्स गुणा के लिए अत्यधिक अनुकूलित, ध्यान से ट्यून किए गए बीएलएएस विधि का उपयोग करता है (यह भी देखें: ATLAS)। इस मामले में विशिष्ट कार्य जीईएमएम (जेनेरिक मैट्रिक्स गुणा के लिए) है। आप dgemm.f (यह नेटलिब में है) की खोज करके मूल को देख सकते हैं।

अनुकूलन, वैसे, संकलक अनुकूलन से परे चला जाता है। ऊपर, फिलिप ने कॉपरस्मिथ – विनोग्रड का उल्लेख किया। अगर मुझे सही याद है, तो यह एल्गोरिदम है जिसका उपयोग एटीएलएएस में मैट्रिक्स गुणा के अधिकांश मामलों के लिए किया जाता है (हालांकि एक टिप्पणीकर्ता नोट करता है कि यह स्ट्रैसेन एल्गोरिदम हो सकता है)।

दूसरे शब्दों में, आपके matmult एल्गोरिदम छोटे कार्यान्वयन है। एक ही काम करने के तेज तरीके हैं।