मैंने length फ़ंक्शन के छह संस्करण लिखे हैं। कुछ प्रदर्शन अंतर समझ में आते हैं, लेकिन उनमें से कुछ मेरे द्वारा पढ़े गए लेखों से सहमत नहीं हैं (उदाहरण के लिए यह वाला और यह वाला)।

-- len1 and lenFold1 should have equivalent performance, right?

len1 :: [a] -> Integer
len1 [] = 0
len1 (x:xs) = len1 xs + 1

lenFold1 :: [a] -> Integer
lenFold1 = foldr (\_ a -> a + 1) 0


-- len2 and lenFold2 should have equivalent performance, right?

len2 :: [a] -> Integer
len2 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (1 + acc)

lenFold2 :: [a] -> Integer
lenFold2 = foldl (\a _ -> a + 1) 0


-- len3 and lenFold3 should have equivalent performance, right?
-- And len3 should outperform len1 and len2, right?

len3 :: [a] -> Integer
len3 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs $! (1 + acc)

lenFold3 :: [a] -> Integer
lenFold3 = foldl' (\a _ -> a + 1) 0

मेरी मशीन पर वास्तविक प्रदर्शन हैरान करने वाला है।

*Main Lib> :set +m +s
*Main Lib> xs = [1..10000000]
(0.01 secs, 351,256 bytes)
*Main Lib> len1 xs
10000000
(5.47 secs, 2,345,244,016 bytes)
*Main Lib> lenFold1 xs
10000000
(2.74 secs, 1,696,750,840 bytes)
*Main Lib> len2 xs
10000000
(6.02 secs, 2,980,997,432 bytes)
*Main Lib> lenFold2 xs
10000000
(3.97 secs, 1,776,750,816 bytes)
*Main Lib> len3 xs
10000000
(5.24 secs, 3,520,354,616 bytes)
*Main Lib> lenFold3 xs
10000000
(1.24 secs, 1,040,354,528 bytes)
*Main Lib> length xs
10000000
(0.21 secs, 720,354,480 bytes)

मेरे सवाल:

  1. प्रत्येक फ़ंक्शन का fold संस्करण स्पष्ट रिकर्सन का उपयोग करके लगातार संस्करण से बेहतर प्रदर्शन क्यों करता है?
  2. इस लेख की चेतावनियों के बावजूद इनमें से कोई भी कार्यान्वयन कभी भी मेरी मशीन पर स्टैक ओवरफ़्लो तक नहीं पहुंचता है। क्यों नहीं?
  3. len3, len1 या len2 से बेहतर प्रदर्शन क्यों नहीं करता?
  4. प्रस्तावना का length इनमें से किसी भी कार्यान्वयन से इतना बेहतर प्रदर्शन क्यों करता है?

संपादित करें:

कार्ल के सुझाव के लिए धन्यवाद, मेरे पहले और दूसरे प्रश्नों को इस तथ्य से संबोधित किया जाता है कि जीएचसीआई डिफ़ॉल्ट रूप से कोड की व्याख्या करता है। इसे -fobject-code के साथ फिर से चलाने से स्पष्ट रिकर्सन और फोल्ड के बीच अलग-अलग प्रदर्शन होता है। नए माप:

Prelude Lib Main> xs = [1..10000000]
(0.00 secs, 354,136 bytes)
Prelude Lib Main> len1 xs
10000000
(1.62 secs, 1,612,661,544 bytes)
Prelude Lib Main> lenFold1 xs
10000000
(1.62 secs, 1,692,661,552 bytes)
Prelude Lib Main> len2 xs
10000000
(2.46 secs, 1,855,662,888 bytes)
Prelude Lib Main> lenFold2 xs
10000000
(2.53 secs, 1,772,661,528 bytes)
Prelude Lib Main> len3 xs
10000000
(0.48 secs, 1,680,361,272 bytes)
Prelude Lib Main> lenFold3 xs
10000000
(0.31 secs, 1,040,361,240 bytes)
Prelude Lib Main> length xs
10000000
(0.18 secs, 720,361,272 bytes)

इसके बारे में मेरे पास अभी भी कुछ प्रश्न हैं।

  1. lenFold3, len3 से बेहतर प्रदर्शन क्यों करता है? मैंने इसे कुछ बार चलाया
  2. length अभी भी इन सभी कार्यान्वयनों से कैसे बेहतर प्रदर्शन करता है?
3
dan p 11 सितंबर 2020, 22:13

1 उत्तर

सबसे बढ़िया उत्तर

मुझे नहीं लगता कि आप जीएचसीआई से प्रदर्शन का ठीक से परीक्षण कर सकते हैं, इससे कोई फर्क नहीं पड़ता कि आप किस झंडे का उपयोग करने का प्रयास करते हैं।

सामान्य तौर पर, हास्केल कोड का प्रदर्शन परीक्षण करने का सबसे अच्छा तरीका मानदंड बेंचमार्किंग लाइब्रेरी का उपयोग करना और ghc -O2 के साथ संकलन करना है। मानदंड बेंचमार्क में कनवर्ट किया गया, आपका प्रोग्राम इस तरह दिखता है:

import Criterion.Main
import GHC.List
import Prelude hiding (foldr, foldl, foldl', length)

len1 :: [a] -> Integer
len1 [] = 0
len1 (x:xs) = len1 xs + 1

lenFold1 :: [a] -> Integer
lenFold1 = foldr (\_ a -> a + 1) 0

len2 :: [a] -> Integer
len2 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (1 + acc)

lenFold2 :: [a] -> Integer
lenFold2 = foldl (\a _ -> a + 1) 0

len3 :: [a] -> Integer
len3 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs $! (1 + acc)

lenFold3 :: [a] -> Integer
lenFold3 = foldl' (\a _ -> a + 1) 0

testLength :: ([Int] -> Integer) -> Integer
testLength f = f [1..10000000]

main = defaultMain
  [ bench "lenFold1" $ whnf testLength lenFold1
  , bench "len1" $ whnf testLength len1
  , bench "len2" $ whnf testLength len2
  , bench "lenFold2" $ whnf testLength lenFold2
  , bench "len3" $ whnf testLength len3
  , bench "lenFold3" $ whnf testLength lenFold3
  , bench "length" $ whnf testLength (fromIntegral . length)
  ]

और मेरी मशीन पर संक्षिप्त परिणाम हैं:

len1                 190.9 ms   (136.8 ms .. 238.6 ms)
lenFold1             207.8 ms   (151.6 ms .. 248.6 ms)
len2                 69.96 ms   (69.09 ms .. 71.63 ms)
lenFold2             1.191 s    (917.1 ms .. 1.454 s)
len3                 69.26 ms   (69.20 ms .. 69.35 ms)
lenFold3             87.14 ms   (86.95 ms .. 87.35 ms)
length               26.78 ms   (26.50 ms .. 27.08 ms)

ध्यान दें कि ये परिणाम जीएचसीआई से इन परीक्षणों को चलाने में आपके द्वारा देखे गए प्रदर्शन से काफी अलग हैं, दोनों पूर्ण और सापेक्ष शब्दों में, और -fobject-code के साथ या बिना। क्यों? मुझे पता नहीं।

वैसे भी, इस उचित बेंचमार्क के आधार पर, len1 और lenFold1 का प्रदर्शन लगभग समान है। वास्तव में, lenFold1 के लिए उत्पन्न कोर है:

lenFold1 = len1

इसलिए वे समान कार्य हैं। मेरे बेंचमार्क में स्पष्ट अंतर वास्तविक है, हालांकि, और यह कुछ कैश/संरेखण समस्या का परिणाम प्रतीत होता है। यदि मैं len1 और lenFold1 को main में पुन: क्रमित करता हूं, तो प्रदर्शन अंतर इधर-उधर हो जाता है (ताकि len1 "धीमा" हो)।

len2 और len3 का प्रदर्शन भी समान है क्योंकि वे एक जैसे कार्य हैं। (वास्तव में, len3 के लिए उत्पन्न कोड len3 = len2 है।) GHC का सख्ती विश्लेषक यह निर्धारित करता है कि अभिव्यक्ति 1 + acc को स्पष्ट $! ऑपरेटर के बिना भी कड़ाई से मूल्यांकन किया जा सकता है।

lenFold3 थोड़ा धीमा है क्योंकि foldl' इनलाइन नहीं है, इसलिए संयोजन फ़ंक्शन को हर बार एक स्पष्ट कॉल की आवश्यकता होती है। यकीनन यह एक बग है जिसकी रिपोर्ट यहां की गई है। हम lenFold3 की परिभाषा को बदलकर foldl' को स्पष्ट रूप से तीन तर्क देकर इसके समाधान कर सकते हैं:

lenFold3 xs = foldl' (\a _ -> a + 1) 0 xs

और फिर यह उतना ही अच्छा प्रदर्शन करता है len2 और len3:

lenFold3             66.99 ms   (66.76 ms .. 67.30 ms)

lenFold2 का खराब प्रदर्शन उसी समस्या का प्रकटीकरण है। इनलाइनिंग के बिना, GHC उचित अनुकूलन नहीं कर सकता। यदि हम परिभाषा को इसमें बदलते हैं:

lenFold2 xs = foldl (\a _ -> a + 1) 0 xs

यह दूसरों की तरह ही अच्छा प्रदर्शन करता है:

lenFold2             66.64 ms   (66.58 ms .. 66.68 ms)

स्पष्ट होने के लिए, इन दो परिवर्तनों को lenFold2 और lenFold3 में करने के बाद, फ़ंक्शन len2, len3, lenFold2, और lenFold3 हैं। समान, सिवाय इसके कि lenFold2 और lenFold3 + ऑपरेटर को एक अलग क्रम में लागू करते हैं। यदि हम परिभाषाओं का उपयोग करते हैं:

lenFold2 xs = foldl (\a _ -> 1 + a) 0 xs
lenFold3 xs = foldl' (\a _ -> 1 + a) 0 xs

तब उत्पन्न कोर (जिसे आप ghc -O2 -ddump-simpl -dsuppress-all -dsuppress-uniques -fforce-recomp के साथ देख सकते हैं) वास्तव में है:

len2 = ...actual definition...
lenFold2 = len2
len3 = len2
lenFold3 = len2

तो वे सभी बिल्कुल समान हैं।

वे वास्तव में len1 (या समतुल्य lenFold1) से भिन्न हैं क्योंकि len1 स्टैक फ्रेम का एक बड़ा सेट बनाता है जिसे सूची के अंत तक पहुंचने पर इसे संसाधित करने की आवश्यकता होती है और " पता चलता है" कि एक खाली सूची की लंबाई शून्य है। स्टैक ओवरफ़्लो नहीं होने का कारण यह है कि हास्केल स्टैक ओवरफ़्लो के बारे में बहुत से ब्लॉग पोस्ट या तो अप्रचलित हैं या जीएचसीआई परीक्षणों पर आधारित हैं। आधुनिक GHC संस्करणों के साथ संकलित कोड में, अधिकतम स्टैक आकार डिफ़ॉल्ट रूप से 80% भौतिक मेमोरी है, इसलिए आप वास्तव में ध्यान दिए बिना गीगाबाइट स्टैक का उपयोग कर सकते हैं। इस मामले में, +RTS -hT के साथ कुछ त्वरित प्रोफाइलिंग से पता चलता है कि स्टैक एक len1 [1..10000000] के लिए लगभग 60-70 मेगाबाइट तक बढ़ता है, कुछ भी ओवरफ्लो करने के लिए पर्याप्त नहीं है। इसके विपरीत, len2 परिवार कोई सराहनीय स्टैक जमा नहीं करता है।

अंत में, कारण length उन सभी को उड़ा देता है कि यह Integer के बजाय Int का उपयोग करके लंबाई की गणना करता है। अगर मैं टाइप सिग्नेचर को इसमें बदलता हूं:

len1 :: [a] -> Int
len2 :: [a] -> Int

तब मुझे मिलता है:

len1                 144.7 ms   (121.8 ms .. 157.9 ms)
len2                 27.38 ms   (27.31 ms .. 27.44 ms)
length               27.50 ms   (27.45 ms .. 27.54 ms)

और len2 (और इसलिए lenFold2, len3, और lenFold3) सभी length जितने तेज़ हैं।

12
K. A. Buhr 12 सितंबर 2020, 00:39