हास्केल रिकर्सिव सूचियों को अनुकूलित करना

Question

मेरे previous से एक और हास्केल अनुकूलन प्रश्न। मैं रिकर्सिवली एक सूची उत्पन्न करने, fibs समारोह कई परिचयात्मक हास्केल आलेखों में मिल के लिए इसी तरह की जरूरत है:

generateSchedule :: [Word32] -> [Word32] 
generateSchedule blkw = take 80 ws 
    where 
    ws   = blkw ++ zipWith4 gen (drop 13 ws) (drop 8 ws) (drop 2 ws) ws 
    gen a b c d = rotate (a `xor` b `xor` c `xor` d) 1 

ऊपर समारोह सबसे अधिक समय और मेरे लिए alloc -consuming समारोह के रूप में आगे निकल गया है। प्रोफाइलर मेरा पीछा आंकड़े दिखाती है:

COST CENTRE  MODULE    %time %alloc ticks  bytes 
generateSchedule Test.Hash.SHA1  22.1 40.4 31  702556640 

मैं इस सूची की गणना करने के अनबॉक्स्ड वैक्टर लागू करने के बारे में सोचा, लेकिन यह करने के लिए के बाद से सूची पुनरावर्ती है एक तरह से समझ नहीं सकता। इसका सी में प्राकृतिक कार्यान्वयन होगा लेकिन मुझे इसे तेजी से बनाने का कोई तरीका नहीं दिख रहा है (अनलॉक करने और परिवर्तनीय घोषणाओं की 80 लाइनों को लिखने के अलावा)। कोई मदद?

अपडेट: मैंने वास्तव में यह देखने के लिए इसे तुरंत अनलॉक कर दिया है कि यह मदद करता है या नहीं। कोड here है। यह बदसूरत है, और वास्तव में यह धीमा था।

COST CENTRE  MODULE    %time %alloc ticks  bytes 
generateSchedule GG.Hash.SHA1  22.7 27.6 40  394270592 

Answer 1

import Data.Array.Base 
import Data.Array.ST 
import Data.Array.Unboxed 

generateSchedule :: [Word32] -> UArray Int Word32 
generateSchedule ws0 = runSTUArray $ do 
    arr <- unsafeNewArray_ (0,79) 
    let fromList i [] = fill i 0 
     fromList i (w:ws) = do 
      unsafeWrite arr i w 
      fromList (i+1) ws 
     fill i j 
      | i == 80 = return arr 
      | otherwise = do 
       d <- unsafeRead arr j 
       c <- unsafeRead arr (j+2) 
       b <- unsafeRead arr (j+8) 
       a <- unsafeRead arr (j+13) 
       unsafeWrite arr i (gen a b c d) 
       fill (i+1) (j+1) 
    fromList 0 ws0 

एक अनबॉक्स्ड सरणी अपनी सूची के लिए इसी का निर्माण करेगा। यह इस धारणा पर निर्भर करता है कि सूची तर्क में कम से कम 14 और अधिकतम 80 आइटम हैं, अन्यथा यह बुरी तरह गलत व्यवहार करेगा। मुझे लगता है कि यह हमेशा 16 आइटम (64 बाइट्स) होगा, इसलिए यह आपके लिए सुरक्षित होना चाहिए। (लेकिन इंटरमीडिएट सूची बनाने के बजाए बाइटस्ट्रिंग से सीधे भरना शुरू करना बेहतर है।)

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

अपने हैशिंग राउंड में, अनावश्यक सीमा-जांच से बचने के लिए unsafeAt array t के माध्यम से आवश्यक Word32 प्राप्त करें।

परिशिष्ट: यदि आप, प्रत्येक wn पर एक धमाके कर दिया, हालांकि मुझे यकीन है कि नहीं कर रहा हूँ सूची के निर्माण unrolling तेजी से हो सकता है। चूंकि आपके पास पहले से कोड है, बैंग जोड़ना और जांच करना ज्यादा काम नहीं है, है ना? मैं उत्सुक हूँ।

Answer 2

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

module Main where 
import Data.Bits 
import Data.List 
import Data.Word 
import qualified Data.Vector as LV 
import Data.Array.ST 
import Data.Array.Unboxed 
import qualified Data.Array as A 
import Data.Array.Base 
import Criterion.Main 

gen :: Word32 -> Word32 -> Word32 -> Word32 -> Word32 
gen a b c d = rotate (a `xor` b `xor` c `xor` d) 1 

gss blkw = LV.toList v 
    where v = LV.fromList $ blkw ++ rest 
      rest = map (\i -> gen (LV.unsafeIndex v (i + 13)) 
           (LV.unsafeIndex v (i + 8)) 
           (LV.unsafeIndex v (i + 2)) 
           (LV.unsafeIndex v i) 
        ) 
       [0..79 - 14] 

gss' blkw = A.elems v 
    where v = A.listArray (0,79) $ blkw ++ rest 
      rest = map (\i -> gen (unsafeAt v (i + 13)) 
           (unsafeAt v (i + 8)) 
           (unsafeAt v (i + 2)) 
           (unsafeAt v i) 
        ) 
       [0..79 - 14] 

generateSchedule :: [Word32] -> [Word32] 
generateSchedule blkw = take 80 ws 
    where 
    ws   = blkw ++ zipWith4 gen (drop 13 ws) (drop 8 ws) (drop 2 ws) ws 

gs :: [Word32] -> [Word32] 
gs ws = elems (generateSched ws) 

generateSched :: [Word32] -> UArray Int Word32 
generateSched ws0 = runSTUArray $ do 
    arr <- unsafeNewArray_ (0,79) 
    let fromList i [] = fill i 0 
     fromList i (w:ws) = do 
      unsafeWrite arr i w 
      fromList (i+1) ws 
     fill i j 
      | i == 80 = return arr 
      | otherwise = do 
       d <- unsafeRead arr j 
       c <- unsafeRead arr (j+2) 
       b <- unsafeRead arr (j+8) 
       a <- unsafeRead arr (j+13) 
       unsafeWrite arr i (gen a b c d) 
       fill (i+1) (j+1) 
    fromList 0 ws0 

args = [0..13] 

main = defaultMain [ 
     bench "list" $ whnf (sum . generateSchedule) args 
     ,bench "vector" $ whnf (sum . gss) args 
     ,bench "array" $ whnf (sum . gss') args 
     ,bench "uarray" $ whnf (sum . gs) args 
     ] 

मैं -O2 साथ कोड संकलित और -funfolding-use-threshold=256 बहुत सारे इनलाइनिंग।

कसौटी मानक दर्शाते हैं कि वेक्टर समाधान थोड़ा बेहतर है, और सरणी समाधान थोड़ा बेहतर अभी भी, लेकिन वह अनबॉक्स्ड परिवर्तनशील समाधान अभी भी भारी बहुमत से जीत:

benchmarking list 
mean: 8.021718 us, lb 7.720636 us, ub 8.605683 us, ci 0.950 
std dev: 2.083916 us, lb 1.237193 us, ub 3.309458 us, ci 0.950 

benchmarking vector 
mean: 6.829923 us, lb 6.725189 us, ub 7.226799 us, ci 0.950 
std dev: 882.3681 ns, lb 76.20755 ns, ub 2.026598 us, ci 0.950 

benchmarking array 
mean: 6.212669 us, lb 5.995038 us, ub 6.635405 us, ci 0.950 
std dev: 1.518521 us, lb 946.8826 ns, ub 2.409086 us, ci 0.950 

benchmarking uarray 
mean: 2.380519 us, lb 2.147896 us, ub 2.715305 us, ci 0.950 
std dev: 1.411092 us, lb 1.083180 us, ub 1.862854 us, ci 0.950 

मैं कुछ बुनियादी रूपरेखा भी भाग गया, और ध्यान दिया कि आलसी/बॉक्स किए गए सरणी समाधान सूची समाधान से थोड़ा बेहतर थे, लेकिन फिर से अनबॉक्स किए गए सरणी दृष्टिकोण से काफी खराब।